Achieving the level of performance necessary for use in large-scale authentication systems

Tokyo, December 15, 2016 - NEC Corporation (NEC; TSE: 6701) today announced the development of a basic algorithm to drastically improve processing speed as well as a search protocol that enables tabulation in databases to be used in secure computing. This enables robust prevention of data breaches by processing encrypted data.

Secure computing is a technology for processing encrypted data without the need for decryption. Among the methods for secure computing, secure multi-party computation is known to be a highly secure method that distributes keys and other confidential information across multiple servers (secret sharing) and enables processing of encrypted data without decryption. Processing speed, however, is extremely slow, preventing its progress beyond being a mere theory and making commercialization nearly impossible.

However, NEC's newly developed basic algorithm makes secure multi-party computation possible by doubling secret shares distributed to each server, which increases the amount of computation that can be processed within the server without having to transmit data to other servers. These features reduce the data communication volume between servers, thereby significantly increasing processing speed. This enables authentication processing of encrypted IDs and passwords at a speed 14 times faster than conventional methods*. This level of performance makes the technology applicable for use in large-scale authentication systems for as many as 100,000 persons.

Along with the above algorithm, NEC has also developed a fast search protocol that enables tabulation by secure multi-party computation, and developed a groundbreaking secure computing data warehouse. This has made it possible to successfully carry out tabulation with almost the same speed as a raw database, while requiring only 6 times larger server resources.

"Going forward, NEC will combine these methods to enable the construction of data utilization platforms that realize highly secure processing of complex and large-scale data mining operations, such as the analysis of personal information collected from multiple organizations," said Akira Kon, general manager, Security Research Laboratories, NEC Corporation.

Key features of the new technologies include the following:

1] Development of a basic algorithm realizing high-speed, secure, multi-party computation

A) Dramatic improvement of computational performance by reducing data communication between servers

In secure computing, a great deal of data communication between servers has traditionally been required for performing calculations with data that is still encrypted. As such, communication between servers has resulted in processing bottlenecks.

NEC's newly developed basic algorithm resolves this issue by doubling the data distributed with redundancy, to increase the amount of computation that can be processed within the server without having to transmit data to other servers, in a 3-server configuration. These features reduce the data communication volume between servers to one-fifth, in turn reducing the volume of processing for all the servers to one-third.

B) The algorithm was applied in authentication processing to demonstrate a level of performance practical for use in large-scale authentication systems for as many as 100,000 persons.

Kerberos authentication is a network authentication method with symmetric encryption and used widely for services such as single sign-on. Normally, authentication is carried out with raw secret keys of clients in a server. Using the proposed algorithm, servers can execute authentication processes without decoding the encrypted secret keys.

Trials on the authentication system demonstrated that the new technology can carry out authentication processing 35,000 times every second?a level of performance sufficient for use in authentication servers of large companies with more than 100,000 employees.

2] Development of a fast database search protocol for tabulation using secure multi-party computation

When secure multi-party computation is applied to the tabulation process on a data warehouse, filtering at a prior stage becomes a bottleneck in general. A protocol that enables high-speed filtering of data that is still encrypted was developed by combining secure multi-party computation with a searchable encryption protocol in order to utilize secret computing in a data warehouse.

NEC developed a secure computation data warehouse prototype and conducted trials using the protocol. It successfully achieved almost the same speed as a raw database with only 6 times larger server resources. The performance can be estimated to be a hundred times better than one which could be obtained with conventional application of secure computing, and it can carry out cross tabulation of one million records within a minute.

Note:

• *Fourteen times faster than the fastest secure computing methods of other companies (2016)