Recently Chen and Movassagh proposed the quantum Merkle tree, which is a quantum analogue of the well-known classical Merkle tree. It gives a succinct verification protocol for quantum state commitment. Although they only proved security against semi-honest provers, they conjectured its general security. Using the proposed quantum Merkle tree, they gave a quantum analogue of Kilian's succinct argument for NP, which is based on probabilistically checkable proofs (PCPs). A nice feature of Kilian's argument is that it can be extended to a zero-knowledge succinct argument for NP, if the underlying PCP is zero-knowledge. Hence, a natural question is whether one can also make the quantum succinct argument by Chen and Movassagh zero-knowledge as well. This work makes progress on this problem. We generalize the recent result of Broadbent and Grilo to show that any local quantum verifier can be made simulable with a minor reduction in completeness and soundness. Roughly speaking, a local quantum verifier is simulable if in the yes case, the local views of the verifier can be computed without knowing the actual quantum proof; it can be seen as the quantum analogue of the classical zero-knowledge PCPs. Hence we conjecture that applying the proposed succinct quantum argument of Chen and Movassagh to a simulable local verifier is indeed zero-knowledge.Recently Chen and Movassagh proposed the quantum Merkle tree, which is a quantum analogue of the well-known classical Merkle tree. It gives a succinct verification protocol for quantum state commitment. Although they only proved security against semi-honest provers, they conjectured its general security. Using the proposed quantum Merkle tree, they gave a quantum analogue of Kilian's succinct argument for NP, which is based on probabilistically checkable proofs (PCPs). A nice feature of Kilian's argument is that it can be extended to a zero-knowledge succinct argument for NP, if the underlying PCP is zero-knowledge. Hence, a natural question is whether one can also make the quantum succinct argument by Chen and Movassagh zero-knowledge as well. This work makes progress on this problem. We generalize the recent result of Broadbent and Grilo to show that any local quantum verifier can be made simulable with a minor reduction in completeness and soundness. Roughly speaking, a local quantum verifier is simulable if in the yes case, the local views of the verifier can be computed without knowing the actual quantum proof; it can be seen as the quantum analogue of the classical zero-knowledge PCPs. Hence we conjecture that applying the proposed succinct quantum argument of Chen and Movassagh to a simulable local verifier is indeed zero-knowledge.

arXiv:2209.10798Sep 22, 20220 citations

Compressed Zero-Knowledge Proofs for Lattice-Based Accumulator

Shumin Si, Xiuhan Lin, Puwen Wei

Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$ , where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$ . In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$, where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.

The Computer JournalMar 10, 20233 citations

The Round Complexity of Quantum Zero-Knowledge

Orestis Chardouvelis, Giulio Malavolta

Lecture notes in computer scienceJan 1, 20212 citations

2^{32}

members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in

l\cdot n_{s}

, where

l

and

n_{s}

denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when

l=32

. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.