A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

• URL: http://arxiv.org/abs/2011.02670v4
• Date: Mon, 30 Oct 2023 05:42:21 GMT
• Title: A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
• Authors: Nai-Hui Chia and Kai-Min Chung and Takashi Yamakawa
• Abstract summary: We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. 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.
• Score: 12.525959293825318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\epsilon$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-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 $\epsilon$-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 $\epsilon$-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.

Related papers

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Post-Quantum Zero-Knowledge with Space-Bounded Simulation [8.69082943773532]
  We introduce a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. For verifiers with logarithmic quantum space $s$ and classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be achieved. For verifiers with superlogarithmic quantum space $s$, assuming existence of post-quantum one-way, we show that $(s,f)$-space-bounded QZK protocols, with fully black
  arXiv  Detail & Related papers  (2022-10-12T11:13:56Z)
• Commitments to Quantum States [11.217084610985674]
  A commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. Commitments to quantum states open the door to many new cryptographic possibilities.
  arXiv  Detail & Related papers  (2022-10-11T04:34:36Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
  We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model. This yields the first post-quantum succinct argument system from any falsifiable assumption.
  arXiv  Detail & Related papers  (2021-03-15T05:09:17Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• On the Concurrent Composition of Quantum Zero-Knowledge [11.09538194395154]
  We study the notion of zero-knowledge secure against quantum-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting. Our result yields a proof of quantum knowledge system for QMA with better parameters than prior works.
  arXiv  Detail & Related papers  (2020-12-05T23:09:29Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.