Unclonable Non-Interactive Zero-Knowledge

• URL: http://arxiv.org/abs/2310.07118v3
• Date: Tue, 24 Sep 2024 17:16:31 GMT
• Title: Unclonable Non-Interactive Zero-Knowledge
• Authors: Ruta Jawale, Dakshita Khurana,
• Abstract summary: A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them. In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone.
• Score: 11.013799869152132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them. However, an adversary that obtains a NIZK proof may be able to clone this proof and distribute arbitrarily many copies of it to various entities: this is inevitable for any proof that takes the form of a classical string. In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone. We define and construct unclonable non-interactive zero-knowledge arguments (of knowledge) for NP, addressing a question first posed by Aaronson (CCC 2009). Besides satisfying the zero-knowledge and argument of knowledge properties, these proofs additionally satisfy unclonability. Very roughly, this ensures that no adversary can split an honestly generated proof of membership of an instance $x$ in an NP language $\mathcal{L}$ and distribute copies to multiple entities that all obtain accepting proofs of membership of $x$ in $\mathcal{L}$. Our result has applications to unclonable signatures of knowledge, which we define and construct in this work; these non-interactively prevent replay attacks.

Related papers

• Collaborative CP-NIZKs: Modular, Composable Proofs for Distributed Secrets [3.3373764108905455]
  Composability allows users to combine different specialized NIZKs. We present the first, general definition for collaborative commit-and-prove NIZK.
  arXiv  Detail & Related papers  (2024-07-27T08:45:34Z)
• The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
  We study the study of round compression of protocols in the bounded quantum storage model (BQSM) In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol. We show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques.
  arXiv  Detail & Related papers  (2024-05-28T15:24:48Z)
• Generating Natural Language Proofs with Verifier-Guided Search [74.9614610172561]
  We present a novel stepwise method NLProofS (Natural Language Proof Search) NLProofS learns to generate relevant steps conditioning on the hypothesis. It achieves state-of-the-art performance on EntailmentBank and RuleTaker.
  arXiv  Detail & Related papers  (2022-05-25T02:22:30Z)
• Verifiable Quantum Advantage without Structure [18.816869896281666]
  We replace a random oracle with a concrete cryptographic hash function such as SHA2. We obtain plausible Minicrypt instantiations of the above results.
  arXiv  Detail & Related papers  (2022-04-05T08:58:24Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning [73.09791959325204]
  We focus on a type of linguistic formal reasoning where the goal is to reason over explicit knowledge in the form of natural language facts and rules. A recent work, named PRover, performs such reasoning by answering a question and also generating a proof graph that explains the answer. In our work, we address a new and challenging problem of generating multiple proof graphs for reasoning over natural language rule-bases.
  arXiv  Detail & Related papers  (2021-06-02T17:58:35Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  We present a simple proof for the benefit of depth in multi-layer feedforward network with rectified activation ("depth separation") We present a concrete neural network with linear depth (in $m$) and small constant width ($leq 4$) that classifies the problem with zero error.
  arXiv  Detail & Related papers  (2021-01-18T15:40:27Z)
• Experimental relativistic zero-knowledge proofs [4.334542470441071]
  We develop a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity. This demonstrates the practical potential of multi-prover zero-knowledge protocols.
  arXiv  Detail & Related papers  (2020-12-18T19:00:01Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  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.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

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.