Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM

• URL: http://arxiv.org/abs/2202.13730v1
• Date: Mon, 28 Feb 2022 12:51:51 GMT
• Title: Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM
• Authors: Jelle Don and Serge Fehr and Christian Majenz and Christian Schaffner
• Abstract summary: Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes. We prove tight online extractability in the quantum random oracle model (QROM) Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic.
• Score: 10.5811404306981
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction. In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkle-tree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic. Our analysis makes use of a recent framework by Chung et al. [arXiv:2010.11658] for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.

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)
• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Existential Unforgeability in Quantum Authentication From Quantum Physical Unclonable Functions Based on Random von Neumann Measurement [45.386403865847235]
  Physical Unclonable Functions (PUFs) leverage inherent, non-clonable physical randomness to generate unique input-output pairs. Quantum PUFs (QPUFs) extend this concept by using quantum states as input-output pairs. We show that no random unitary QPUF can achieve existential unforgeability against Quantum Polynomial Time adversaries. We introduce a second model where the QPUF functions as a nonunitary quantum channel, which also guarantees existential unforgeability.
  arXiv  Detail & Related papers  (2024-04-17T12:16:41Z)
• Secret extraction attacks against obfuscated IQP circuits [0.92463347238923]
  In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of IQP circuits. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test. Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol.
  arXiv  Detail & Related papers  (2023-12-15T19:08:35Z)
• IQP Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security [1.7586417032126085]
  We introduce a family of IQP sampling protocols called the emphstabilizer scheme, which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP circuit correlation functions. To assess classical security, we explore a class of attacks based on secret extraction, including the Kahanamoku-Meyer's attack as a special case.
  arXiv  Detail & Related papers  (2023-08-14T14:03:33Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• 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)
• Device-Independent-Quantum-Randomness-Enhanced Zero-Knowledge Proof [25.758352536166502]
  Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement. As an efficient variant of ZKP, non-interactive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir is essential to a wide spectrum of applications.
  arXiv  Detail & Related papers  (2021-11-12T13:36:43Z)
• Efficient Quantum Digital Signatures without Symmetrization Step [7.848038078036641]
  Quantum digital signatures (QDS) exploit quantum laws to guarantee non-repudiation, unforgeability and transferability of messages. Current QDS protocols face two major restrictions, including the requirement of the symmetrization step. We present an efficient QDS protocol to overcome these issues by utilizing the classical post-processing operation called post-matching method.
  arXiv  Detail & Related papers  (2021-04-08T01:54:50Z)
• Quantum Sampling for Optimistic Finite Key Rates in High Dimensional Quantum Cryptography [1.5469452301122175]
  We revisit so-called sampling-based entropic uncertainty relations, deriving newer, more powerful, relations and applying them to source-independent quantum random number generators and high-dimensional quantum key distribution protocols. These sampling-based approaches to entropic uncertainty, and their application to quantum cryptography, hold great potential for deriving proofs of security for quantum cryptographic systems.
  arXiv  Detail & Related papers  (2020-12-08T01:32:59Z)

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.