Solving An Open Problem in Zero-Knowledge Proofs
Established an approach for zero-knowledge arguments that do not leak secret information even if randomness is reused during proof generation

News Highlights:

TOKYO - September 19, 2024 - NTT Corporation (Headquarters: Chiyoda Ward, Tokyo; Representative Member of the Board and President: Akira Shimada; hereinafter "NTT") has proved for the first time in the world that the use of witness encryption is essentially indispensable for the construction of the resettable statistical zero-knowledge argument, which is a zero-knowledge proof with high security. Zero-knowledge proof is a cryptographic protocol that proves the validity of a statement without revealing additional information to the other party. As an example, this revolutionary technology can prove the knowledge of the correct password without disclosing the password. This achievement established a construction approach for the resettable statistical zero-knowledge argument, thereby greatly contributing to the practical application of zero-knowledge proofs, which are expected to be used in various fields such as finance, medical care, and healthcare in the future. This achievement was presented at the 44th Annual International Cryptology Conference (Crypto 2024), the premier international conference on cryptology.

1. Background

Zero-knowledge proof is a cryptographic protocol that proves the validity of a statement without disclosing any additional information. For example, it can be used as an authentication technology to prove the knowledge of the correct password without disclosing the password. It is also a revolutionary technology from the viewpoint of privacy protection because it enables age verification without presenting personal information to the other party (Figure 1). In recent years, it has attracted attention because it has also been used in cryptocurrencies to prove that transactions were executed correctly while keeping the contents of transactions secret.
　Resettable statistical zero-knowledge arguments are highly secure zero-knowledge proofs and known to be constructed using a cryptographic primitive called witness encryption. However, it has been an open question whether resettable statistical zero-knowledge arguments can be constructed without witness encryption.

Figure 1 Example of Age Verification with Zero-Knowledge Proof

2. Results and technical points of this research

This time, we solved the open problem by proving that it is impossible to construct a resettable statistical zero-knowledge argument without using witness encryption. Specifically, we have shown that witness encryption can be constructed by using a resettable statistical zero-knowledge argument, thereby showing that constructing a resettable statistical zero-knowledge argument is equivalent to constructing witness encryption (Figure 2).
　As a technical point, in this research, instead of directly using the security of the resettable statistical zero-knowledge argument to construct witness encryption, we used it indirectly and constructed witness encryption from the resettable statistical zero-knowledge argument by the following two steps.

Specifically, we first focus on the fact that the high security of the resettable statistical zero-knowledge argument places significant constraints on the messages sent by the prover, and show that in certain cases the messages sent by the prover must be determined only by the randomness used by the prover, independent of the secret information held by the prover. Next, we focus on the fact that this property can be used to realize witness encryption relatively easily, thereby constructing witness encryption from a resettable statistical zero-knowledge argument (Figure 3).

Figure 2 Results of this Research

Figure 3 Technical Points of this Study

3．Outlook

We will continue to promote the R&D of zero-knowledge proofs as a technology of IOWN PETs, with the aim of achieving the goal of the "world without plaintext," where safe data distribution is enabled by the technical guarantee that data will be used only within the scope of the data owner's policy during the entire period from creation to destruction. In the future, we aim to utilize this technology for our LLM tsuzumi's secure learning and to put it into practical use for IOWN PETs.

[Glossary]

^1.Witness encryption
Witness encryption is an encryption scheme proposed as a generalization of public-key encryption. In normal public-key encryption, encryption is performed with a public key and decryption is performed with the corresponding private key, but in witness encryption, encryption is performed with an arbitrary NP instance (e.g., mathematical theorems) and decryption is performed with the corresponding witness (e.g., proof of a theorem).

^2.Zero-knowledge proof
Zero-knowledge proof is a cryptographic protocol between two parties called a prover and a verifier. Broadly speaking, in a zero-knowledge proof, the prover tries to convince the verifier of the correctness of a statement in the following way: At the start of a proof, both the prover and the verifier have the statement to be proved as public information, and the prover has the evidence that the statement holds as secret information. (The evidence is called "witness.") Then, the prover proves that the statement is true by conducting a question-and-answer type interaction in which the prover answers the question by the verifier, and the verifier verifies the proof by checking the content of the response by the prover. Zero-knowledge proofs provide three security guarantees: completeness (a prover with appropriate evidence can prove a true statement), soundness (a malicious prover cannot prove a false statement), and zero-knowledge (a malicious verifier cannot learn information on the evidence beyond the validity of the statement).

^3.Statistical zero-knowledge argument
Zero-knowledge proofs are classified into computational and statistical depending on what kind of computing power an adversary has in the definition of zero-knowledge, and also into proof and argument depending on what kind of computing power an adversary has in the definition of soundness. In the case of statistical zero-knowledge arguments, zero-knowledge is guaranteed against an adversary with unbounded computing power while soundness is guaranteed only against an adversary with realistically bounded computing power (specifically, what is called a polynomial-time adversary).

^4.Resettable statistical zero-knowledge argument
The resettable statistical zero-knowledge argument is a statistical zero-knowledge argument that guarantees zero-knowledge even when multiple proofs are generated using the same randomness. Using randomness is essential for many cryptographic primitives, including zero-knowledge proofs. However, the generation of randomness (especially that having sufficiently high quality required for cryptographic primitives) requires high-cost operations such as the use of physical phenomena. An advantage of the resettable statistical zero-knowledge argument is that randomness generation is no longer necessary during proof generation. In particular, it guarantees zero-knowledge even if randomness is generated in advance and subsequently reused in every proof generation. Because of this advantage, the resettable statistical zero-knowledge argument can be used even in environments where it is difficult to generate randomness because of cost restrictions.

^5.IOWN PETs: https://www.rd.ntt/e/sil/project/iown-pets/iown-pets.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 businesses 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 $97B 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.