In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky,Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.
AI Summary
The paper asks whether post-quantum one-way permutations suffice for classical perfect zero-knowledge arguments for every language in NP. The obstacle is that classical security reductions for NOVY commitments use rewinding, while preventing a quantum committer from producing two openings simultaneously does not generally provide the binding properties needed for argument soundness.
It proves that NOVY commitments instantiated with any post-quantum one-way permutation are perfectly hiding and computationally open-once binding, sum-binding, and collapse-binding against quantum polynomial-time adversaries. The reduction combines a state-specific, single-reflection variant of Watrous rewinding with repeated execution and state repair. After $R$ interactive-hashing rounds, the real and ideal states have purified distance at most $9/\sqrt{2^{n-R}}$. A recording theorem allows repeated successful answers to be retained without a collapsing assumption when each challenge has polynomially many accepting answers. NOVY’s unique openings then convert open-once binding into sum-binding and collapse-binding.
The paper also establishes that parallel composition preserves collapse-binding for publicly verifiable interactive commitments. Using these properties, it proves post-quantum computational soundness of the original Blum HAMCYCLE argument with NOVY commitments, obtaining perfect zero-knowledge arguments for all NP with soundness error $14/15$. Perfect simulation uses perfect hiding and exact quantum rewinding.
The stated limitations are the assumption of one-way permutations rather than arbitrary one-way functions, and the weaker soundness bound compared with the classical $1/2$. The recording theorem requires polynomially bounded accepting-answer multiplicity; the argument does not establish unrestricted recording without collapsing.
No sign of AI-generated textAI use disclosedPossible error
generative AI has only been used to solve minor \LaTeX\ issues
Error found: The recording measurement conjugates its answer projectors in the wrong order, so it is not equivalent to the experiment it is claimed to implement.
Both success-probability lower bounds immediately following the purified-distance lemma reverse the subtraction and are false as printed.
The final soundness calculation asserts positivity of a negative expression at s = 1/15, although the preceding correct bound supports the claimed 14/15 threshold.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky,Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.
The paper asks whether post-quantum one-way permutations suffice for classical perfect zero-knowledge arguments for every language in NP. The obstacle is that classical security reductions for NOVY commitments use rewinding, while preventing a quantum committer from producing two openings simultaneously does not generally provide the binding properties needed for argument soundness.
It proves that NOVY commitments instantiated with any post-quantum one-way permutation are perfectly hiding and computationally open-once binding, sum-binding, and collapse-binding against quantum polynomial-time adversaries. The reduction combines a state-specific, single-reflection variant of Watrous rewinding with repeated execution and state repair. After R interactive-hashing rounds, the real and ideal states have purified distance at most 9/2n−R. A recording theorem allows repeated successful answers to be retained without a collapsing assumption when each challenge has polynomially many accepting answers. NOVY’s unique openings then convert open-once binding into sum-binding and collapse-binding.
The paper also establishes that parallel composition preserves collapse-binding for publicly verifiable interactive commitments. Using these properties, it proves post-quantum computational soundness of the original Blum HAMCYCLE argument with NOVY commitments, obtaining perfect zero-knowledge arguments for all NP with soundness error 14/15. Perfect simulation uses perfect hiding and exact quantum rewinding.
The stated limitations are the assumption of one-way permutations rather than arbitrary one-way functions, and the weaker soundness bound compared with the classical 1/2. The recording theorem requires polynomially bounded accepting-answer multiplicity; the argument does not establish unrestricted recording without collapsing.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ϵ-zero-knowledge. Concretely, we construct the following protocols:
- We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ϵ-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ϵ-zero-knowledge property against quantum adversaries requires novel ideas.
- We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ϵ-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions.
At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ε-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ε-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ε-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ε-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider a naive parallel version of their scheme of the multiplicity logn and obtain an O(n/logn)-round scheme. In their conference paper (at CRYPTO’92), they claimed that such a round reduction of any logarithmic factor is achievable. We work out the details of their claim. Namely, we give an explicit justification of the folklore that such a parallelization would not lose the security proof. Though the parallelization raises an analytic difficulty, we introduce a new analysis technique and then overcome the difficulty. Our technique copes with expected almost pairwise independent random variables instead of the pairwise independence, which is a key property in their analysis. While the expected almost pairwise independence plays an important role in our security proof, it also provides alternative security proof for the original scheme.
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting. We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK. As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks. Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
We improve the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider a naive parallel version of their scheme of the multiplicity logn and obtain an O(n/ logn)-round scheme. Our improvement answers a question, raised by them, whether their O(n)-round scheme is essential with respect to the round complexity. Though such a parallelization raises an analytic difficulty, we introduce a new analysis technique and then overcome the difficulty. Our technique copes with expected almost pairwise independent random variables instead of the pairwise independence, which is a key property in their analysis. While the expected almost pairwise independence plays an important role in our security proof, it also provides alternative security proof for the original scheme.
Abstract. Commitment schemes are among cryptography’s most im-portant building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes ap-plied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where com-mitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commit-ment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approxi-mation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness prop-erty of a given commitment while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construc-tion yields two more interesting features: one is the ability to “convert” a Pedersen commitment into a lattice-based one, and the other one is the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.