Alex Bredariol Grilo

Abstract The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications: 1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

Abstract We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of CLDM in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of QMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a ``sigma'' protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition.

Abstract A non-interactive zero-knowledge (NIZK) proof system for a language L in NP allows a prover (who is provided with an instance x and a witness w) to compute a classical certificate for the claim that x is in L, with the following properties: 1) the protocol can be verified efficiently, and 2) the protocol does not reveal any information about w, besides the fact that it exists (i.e., that x is in L). While NIZKs are known to be impossible in the plain model (i.e., with no additional trusted resource), they are well studied in alternative models and have seen widespread application in classical cryptography. Given the importance of NIZKs, and more generally zero-knowledge protocols, in classical cryptography, there has been a recent effort to achieve such protocols for QMA, a natural quantum analog of NP. However, all previous results only achieved interactive protocols, limiting their cryptographic use. Moreover, they all rely on quantum communication between the prover and the verifier, which may be difficult to achieve. In this submission, we present two NIZK protocols for QMA in the Common Reference String (CRS) model, with additional offline setup. Both protocols are achieved through the homomorphic computation of classical NIZKs for NP, and rely on the hardness of the Learning With Errors problem. However, each of them then combines this core idea with different (seemingly incomparable) techniques: 1) our first protocol makes use of quantum teleportation and quantum communication in an offline setup phase, with a classical online phase; our second protocol leverages techniques for classical verification of quantum computations, and is the only known NIZK for QMA to be completely classical, as well as reusable, meaning that a single setup allows to prove many theorems. Security of the latter is in the Quantum Random Oracle model.

Abstract MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT.

In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero- knowledge proof systems, PoKs are an important part of secure protocols such as digital signature schemes and authentication schemes as they en- able a prover to demonstrate posession of a certain piece of information (such as a private key or a credential), without revealing it. Formally, A PoK is defined via the existence of an extractor, which is capable of recon- structing the key information that makes a verifier accept, given oracle access to the prover. We extend the concept of a PoK in the setting of a single classical verifier and two quantum provers, and exhibit the PoK property for the Hamil- tonian game, a non-local game between a single classical verifier and two quantum provers for the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers’ strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self- testing, where, in addition to certifying a pre-shared entangled state and the prover’s strategy, the verifier also certifies a local quantum state. This technique thus provides a method to ascertain that a prover has access to a quantum system, in particular, a ground state, Thus indicating a new level of verification for a proof of quantumness.

Secret sharing is a fundamental primitive in cryptography, and it can be achieved even with perfect security. However, the distribution of shares requires computational assumptions, which can compromise the overall security of the protocol. While traditional Quantum Key Distribution (QKD) can maintain security, its widespread deployment in general networks would incur prohibitive costs. In this work, we present a quantum protocol for distributing additive secret sharing of 0, which we prove to be composably secure within the Abstract Cryptography framework. Moreover, our protocol targets the Qline, a recently proposed quantum network architecture designed to simplify and reduce the cost of quantum communication. Once the shares are distributed, they can be used to securely perform a wide range of cryptographic tasks, including standard additive secret sharing, anonymous veto, and symmetric key establishment.

While one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it. In this work, we study the cryptographic usefulness of quantum pseudoresources —a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting. Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource.

Oblivious transfer (OT) is a fundamental primitive in cryptography, allowing the construction of general multi-party computation. Recent results have proved the possibility of quantum protocols from one-way functions, which is expected to be weaker than the assumptions needed in OT in the classical setting. In particular, a recent result by Diamanti et al. provided a quantum protocol for OT considering practical aspects of the protocol, while maintaining its composable security. In this work, we provide the first experimental implementation of a composable oblivious transfer protocol from OWF. The setup implements a weak-coherent pulses BB84 state source in polarization encoding, whose experimental parameters are employed to optimize the theoretical security bounds. The obtained security parameters are then used to perform a secure execution of the protocol, whose performances are profiled and compared with the literature benchmark.

We present a new simulation-secure quantum oblivious transfer (QOT) protocol based on one-way functions in the plain model. With a focus on practical implementation, our protocol surpasses prior works in efficiency, promising feasible experimental realization. We address potential experimental errors and their correction, offering analytical expressions to facilitate the analysis of the required quantum resources. Technically, we achieve our results by achieving simulation security for QOT through an equivocal and relaxed-extractable quantum bit commitment.

We present the implementation of a new simulation-secure quantum oblivious transfer protocol based on one-way functions. The protocol allows an efficient and noise-tolerant experimental realization, surpassing prior works' performances in terms of required quantum and classical resources. We provide the complete integration of a software and an experimental source, achieving a black-box implementation of the quantum oblivious transfer primitive, to be leveraged in the future for secure multiparty computation.