CWI Cryptology Group

Abstract: In this talk, I will highlight a series of works that deal with proofs of knowledge in the Quantum Random-Oracle Model. Suppose we have a (zero-knowledge) proof system, where a prover claims knowledge of a witness in some NP-relation. The proof system is then said to be a 'proof of knowledge' if there exists a 'knowledge extractor' that, given black-box (rewinding) access to a prover, can produce a witness with success probability similar to that of the aforementioned prover. If the proof system is of a particular interactive form (sigma-protocol) it can be made non-interactive using a hash function, via the Fiat-Shamir transformation. Sigma-protocols of a yet more particular form (commit-and-open) use a hash for the commitment in the first message. The goal of all of these works is to prove existence of a knowledge extractor for such proof systems in the Quantum Random-Oracle Model, where the hash is modeled as a perfectly random function, to which parties are given only (superposition) oracle access.
I will explain why we *do* have a generic reduction for the Fiat-Shamir transformation that mimics the classical case, but *not* a quantum version of the forking lemma, and why this leads to non-tightness in the knowledge extraction. The more recent works however show that this non-tightness can be avoided in the case of commit-and-open protocols.

[DFMS19] Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model, https://eprint.iacr.org/2019/190.pdf
[DFM20] The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More, https://eprint.iacr.org/2020/282.pdf
[DFMS21] Online-Extractability in the Quantum Random-Oracle Model, https://eprint.iacr.org/2021/280.pdf
[DFMS22] Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM, https://eprint.iacr.org/2022/270.pdf

Abstract: In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow-up in query complexity for each oracle individually, and causes a very mild blow-up only.
In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure.
Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in order to deal with adaptivity.

Abstract: 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 WOTRO with $n - m \in {\omega}(\lg n)$ is black-box impossible in the CRQS model, meaning that no protocol can have its security black-box reduced to a cryptographic game. We define a (inefficient) quantum adversary against any WOTRO protocol that can be efficiently simulated in polynomial time, ruling out any reduction to a secure game that only makes black-box queries to the adversary. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQ\$ 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 black-box impossibility of a quantum Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC '13) to the CRQS model. Second, we show a black-box impossibility result for a strengthened version of quantum lightning (Zhandry, Eurocrypt '19) where quantum bolts have an additional parameter that cannot be changed without generating new bolts.