World's first commitment scheme [1] to achieve both strong post-quantum security and communication efficiency, consisting of only one-way functions [2]
Introduction of a new security proof method in cryptographic protocols against quantum computers

Tokyo - November 6, 2023 - NTT Corporation (NTT) is the first company in the world to construct a commitment scheme that achieves both strong security (non-malleability) ^[3] against quantum computers and communication efficiency (constant-round), using only one-way functions, which are the most fundamental building blocks in cryptography. As a future application of this result, it is expected to be applied to secure computation, which is both highly secure against quantum computers and efficient. The results will be presented at the IEEE Symposium on Foundations of Computer Science (FOCS) 2023 ^[4], the premier international conference on theoretical computer science.

1. Background

Quantum computers are computers that apply the principles of quantum mechanics and are currently in competition for development worldwide. Shor's factorization algorithm, developed in 1994, shows that the RSA cipher, which is widely used today, can be broken by quantum computers. For this reason, research has been actively conducted in recent years on post-quantum cryptography that cannot be broken even by quantum computers. Public-key cryptography and digital signatures have been standardized by the National Institute of Standards and Technology (NIST), among other post-quantum cryptography, and practical research has progressed. However, there are many theoretical uncertainties regarding the post-quantum security of other cryptographic protocols. In particular, in order to construct a commitment scheme that satisfies strong security called non-malleability against quantum computers, the only known solutions were to either increase the number of interaction according to the security level we want to achieve or make strong assumptions as the basis of security.

2. Research Results

In a paper ^[5] co-authored with Dr. Xiao Liang of the NTT Research Cryptography & Information Security Lab, Omkant Pandey, Associate Professor of Stony Brook University, and Takashi Yamakawa, a Distinguished Researcher at NTT, has constructed the world's first commitment scheme that simultaneously achieves non-malleability against quantum computers and communication efficiency (constant round), in which the number of interaction is independent of the desired security level, using only one-way functions, which is regarded as the minimum.

Figure 1 An example of a commitment scheme. The value initially determined by the sender is shared with the receiver through communication and computation with the receiver.

Figure 2 Examples of vulnerability of commitment schemes that do not satisfy post-quantum non-malleability. Even if you commit to "Data _A," an attacker using a quantum computer tampers with the value "Data _A '" associated with "Data _A."

When only considering security against classical computers, commitment schemes of similar nature have been known since 2011, but achieving security against quantum computers has been unsolved for more than 10 years since then. This is because quantum computers operate on very different principles from classical computers, and traditional security proofs for attackers using classical computers cannot be applied to attackers using quantum computers. For this reason, conventional methods could be vulnerable to attackers using quantum computers. On the other hand, Yamakawa and his colleagues proved their non-malleability against quantum computers by redesigning the commitment scheme with a completely different idea. As an application of the commitment with non-malleability, for example, there is a secure computation protocol in which multiple users perform computations cooperatively while keeping their own data secret. This result is expected to lead to the development of a more secure and efficient secure computation protocol for quantum computers in the future. The results were adopted by the IEEE Symposium on Foundations of Computer Science (FOCS) 2023, the premier international conference in theoretical computer science, and will be presented at Session 4A on Nov. 6. This is the third year in a row that a paper by Researcher Yamakawa has been selected for FOCS ^[6].

3. Outlook

The new security proof technique introduced here is expected to have broader applications beyond commitment schemes. In the future, we will apply this method to other cryptographic protocols such as secure computation protocols and aim to prove post-quantum security.

^[1]Commitment scheme: A cryptographic protocol that electronically encloses a message in an envelope. That is, a protocol that simultaneously realizes the property that a "committed" message is hidden until it is released later (hiding) and that a message cannot be changed after it is "committed" (binding). It has broad applications as a component of more sophisticated cryptographic protocols such as zero-knowledge proofs and secure computations.

^[2] One-way function: A function that is easy to compute but difficult to invert. It is considered to be a minimal component in cryptography.

^[3]Non-malleability: When one user commits to a message, another user cannot commit to the related message by tampering with it.

^[4]FOCS 2023: https://focs.computer.org/2023/

^[5]A New Approach to Post-Quantum Non-Malleability. Xiao Liang (NTT Research), Omkant Pandey (Stony Brook University), Takashi Yamakawa (NTT Social Informatics Laboratories)

^[6]https://group.ntt/jp/topics/2022/02/08/accepted_paper_focs2021.html
https://group.ntt/jp/newsrelease/2022/10/31/221031b.html

About NTT

NTT contributes to a sustainable society through the power of innovation. We are a leading global technology company providing services to consumers and business as a mobile operator, infrastructure, networks, applications, and consulting provider. Our offerings include digital business consulting, managed application services, workplace and cloud solutions, data center and edge computing, all supported by our deep global industry expertise. We are over $95B in revenue and 330,000 employees, with $3.6B in annual R&D investments. Our operations span across 80+ countries and regions, allowing us to serve clients in over 190 of them. We serve over 75% of Fortune Global 100 companies, thousands of other enterprise and government clients and millions of consumers.