Quantum Rewinding for IOP-Based Succinct Arguments

• URL: http://arxiv.org/abs/2411.05360v1
• Date: Fri, 08 Nov 2024 06:33:08 GMT
• Title: Quantum Rewinding for IOP-Based Succinct Arguments
• Authors: Alessandro Chiesa, Marcel Dall Agnol, Zijing Di, Ziyi Guan, Nicholas Spooner,
• Abstract summary: We prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapsing. As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best complexity known.
• Score: 45.5096562396529
• License:
• Abstract: We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. We prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapsing. Our proof builds on and extends prior work on the post-quantum security of Kilians succinct interactive argument, which is instead based on probabilistically checkable proofs (PCPs). We introduce a new quantum rewinding strategy that works across any number of rounds. As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best asymptotic complexity known.

Related papers

• 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)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• 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)
• Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM [10.5811404306981]
  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.
  arXiv  Detail & Related papers  (2022-02-28T12:51:51Z)
• 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)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• 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 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)
• 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)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)

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.