Mohammed Barhoush

The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message authentication codes, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, signature tokens, and program broadcast. These schemes are secure against adversaries with roughly e^{\sqrt{m}} quantum memory where m is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.

Functional encryption is a powerful cryptographic primitive that enables fine- grained access to encrypted data and underlies numerous applications. Although the ideal security notion for FE—simulation security—has been shown to be impossible in the classical setting, those impossibility results rely on inherently classical arguments. This leaves open the question of whether simulation-secure functional encryption can be achieved in the quantum regime. In this work, we rule out this possibility by showing that the classical impossibility results largely extend to the quantum world. In particular, when the adversary can issue an un- bounded number of challenge messages, we prove an unconditional impossibility, matching the classical barrier. In the case where the adversary may obtain many functional keys, clas- sical arguments only yield impossibility under the assumption of pseudorandom functions; we strengthen this by proving impossibility under the potentially weaker assumption of pseudo- random quantum states. In the same setting, we also establish an alternative impossibility based on public-key encryption. Since public-key encryption is not known to imply pseudo- random quantum states, this provides independent evidence of the barrier. As part of our proofs, we show a novel incompressibility property for pseudorandom states, which may be of independent interest.

Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic PRG: informally, for a fixed seed, the output is the same with 1 − 1/poly probability. In this work, we introduce new definitions for ⊥-PRG and ⊥-PRF. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability 1 − 1/poly) or recognizable abort, denoted ⊥. Our approach admits a natural definition of multi-time PRG security, as well as the adaptive security of a PRF. We construct a ⊥-PRG from any pseudo-deterministic PRG and, from that, a ⊥-PRF. Even though most mini-crypt primitives, such as symmetric key encryption, commitments, MAC, and length-restricted one-time digital signatures, have been shown based on various quantum pseudorandomness assumptions, digital signatures remained elusive. Our main application is a (quantum) digital signature scheme with classical public keys and signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa’s work (Crypto, 2022). Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys.

The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide everlasting and information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message-authentication, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, and signature tokens. These schemes are secure against adversaries with roughly $e^{\sqrt{m}}$ quantum memory where $m$ is the quantum memory required for the honest user. All of the constructions additionally satisfy notions of disappearing and unclonable security.