Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared
Entanglement
- URL: http://arxiv.org/abs/2204.02265v4
- Date: Wed, 21 Feb 2024 15:57:06 GMT
- Title: Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared
Entanglement
- Authors: Fr\'ed\'eric Dupuis, Philippe Lamontagne, Louis Salvail
- Abstract summary: We call this the Common Reference Quantum State (CRQS) model, in analogy to the well-known Common Reference String (CRS)
We formalize this notion as a Weak One-Time Random Oracle (WOTRO)
We show that any protocol for WOTRO in the CRQS model can be attacked by an (inefficient) adversary.
Our adversary is efficiently simulatable, which rules out the possibility of proving the computational security of a scheme by a fully black-box reduction to a cryptographic game assumption.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explore the cryptographic power of arbitrary shared physical resources.
The most general such resource is access to a fresh entangled quantum state at
the outset of each protocol execution. We call this the Common Reference
Quantum State (CRQS) model, in analogy to the well-known Common Reference
String (CRS). The CRQS model is a natural generalization of the CRS model but
appears to be more powerful: in the two-party setting, a CRQS can sometimes
exhibit properties associated with a Random Oracle queried once by measuring a
maximally entangled state in one of many mutually unbiased bases. We formalize
this notion as a Weak One-Time Random Oracle (WOTRO), where we only ask of the
$m$-bit output to have some randomness when conditioned on the $n$-bit input.
We show that when $n-m\in\omega(\lg n)$, any protocol for WOTRO in the CRQS
model can be attacked by an (inefficient) adversary. Moreover, our adversary is
efficiently simulatable, which rules out the possibility of proving the
computational security of a scheme by a fully black-box reduction to a
cryptographic game assumption. On the other hand, we introduce a non-game
quantum assumption for hash functions that implies WOTRO in the CRQS model
(where the CRQS consists only of EPR pairs). We first build a statistically
secure WOTRO protocol where $m=n$, then hash the output.
The impossibility of WOTRO has the following consequences. First, we show the
fully-black-box impossibility of a quantum Fiat-Shamir transform, extending the
impossibility result of Bitansky et al. (TCC 2013) to the CRQS model. Second,
we show a fully-black-box impossibility result for a strenghtened version of
quantum lightning (Zhandry, Eurocrypt 2019) where quantum bolts have an
additional parameter that cannot be changed without generating new bolts. Our
results also apply to $2$-message protocols in the plain model.
Related papers
- Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - Certified Randomness from Quantum Supremacy [5.313318620422295]
We propose an application for near-term quantum devices, namely, generating cryptographically certified random bits.
Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling.
We show that our protocol's output is unpredictable even to a computationally unbounded adversary.
arXiv Detail & Related papers (2023-03-02T23:28:31Z) - Obfuscation of Pseudo-Deterministic Quantum Circuits [14.026980555435841]
We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model.
Our obfuscator outputs a quantum state $ketwidetildeQ$ repeatedly on arbitrary inputs.
arXiv Detail & Related papers (2023-02-22T01:14:20Z) - 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) - 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) - 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) - 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) - 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) - 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) - Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
A client remotely prepares a quantum state using a classical channel.
Privacy loss incurred by employing $RSP_CC$ as a sub-module is unclear.
We show that a specific $RSP_CC$ protocol can replace the quantum channel at least in some contexts.
arXiv Detail & Related papers (2020-07-03T13:15:13Z)
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.