Bonjour à tous,

Vous êtes cordialement invité.e.s à la soutenance de thèse de Mohammed Barhoush le vendredi 11 septembre à 10h30 EST (mode hybride).

Title : Dodging Impossibilities in Quantum Cryptography: On the Feasibility of One-Time Programs, Signing Quantum States and Cryptography without One-Way Functions.

Date: Vendredi 11 septembre à 10h30 

Salle: Pavillon André-Aisenstadt, 2920 Ch. de la Tour, au AA-6214

Jury

Abstract:

This thesis by articles investigates the frontiers of quantum cryptographic feasibility, demonstrating how the unique properties of quantum information can be leveraged to circumvent fundamental impossibility results. We explore three distinct regimes where traditional “No-Go” theorems are overcome: the attain- ability of one-time programs via memory bounds, the signing of quantum messages via temporal constraints, and the realization of cryptography without one-way functions.

The first part of this work utilizes the Bounded Quantum Storage Model, where adversaries are limited with respect to their quantum memory. We demonstrate that this physical limitation enables the construction of one-time programs—a powerful form of program obfuscation proven impossible in the plain model. Crucially, because security is derived from memory constraints rather than computational hardness, our constructions achieve information-theoretic security. We utilize one-time programs to develop for the first time fundamental cryptographic applications, including asymmetric key encryption and digital signatures with information-theoretic guarantees.

The second contribution challenges the long-standing paradigm that signing quantum messages is inherently impossible. We introduce time-dependent signatures, where security is maintained through the temporal synchronization of signing and verification processes. We show that this framework allows for the signing of quantum states using any one-way function and time-lock puzzle. Furthermore, we demonstrate that by utilizing dynamic verification keys that evolve over time, the requirement for time-lock puzzles can be eliminated. We apply the signature scheme to construct time-dependent authenticated quantum public-key encryption and public-key quantum money.

The final part of the thesis contributes to the growing body of research re-evaluating the foundational necessity of one-way functions (OWF) as the “minimal” requirement for non-trivial cryptography. Specifically, we provide a black-box separation demonstrating that a pseudorandom generator (PRG) augmented with a quantum input sampling procedure represents a potentially weaker assumption than a traditional PRG with uniform sampling, which is equivalent to OWF. Using this insight, we show that essential applications, such as message authentication and commitments under classical communication, are also black-box separated from traditional PRGs. This provides evidence for a new, potentially weaker foundation for these cryptographic applications.

Together, these contributions provide a multifaceted perspective on the evolving landscape of quantum cryptography. By shifting foundational assumptions—from computational hardness to memory bounds, from time-independence to time-dependence, and from uniform sampling to quantum sampling—this thesis establishes that a broader range of secure primitives is attainable than previously suggested by standard theory.

Venez nombreux!