EAGER: SaTC: Post-Quantum Indifferentiability

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Current technology for securing Internet traffic relies on cryptographic protocols that are based on the presumed difficulty of two mathematical problems - the factorization problem and the discrete logarithm problem. However, the emerging technology of quantum computers - a type of computer that leverages the laws of quantum mechanics to perform certain computations faster than classical computers - can efficiently solve both of these problems and thus effectively attack the respective cryptographic protocols. Anticipating the advent of quantum computers, efforts to standardize new quantum-safe (also called "post-quantum") cryptographic protocols are in progress. It is important to note that quantum attacks not only render factoring and discrete-logarithm based cryptosystems insecure, but also compromise the security of cryptosystems employing a technique known as the "random oracle methodology." This methodology assumes that all parties have access to an ideal object known as a random oracle and the security of the cryptosystem is analyzed in the random oracle model. Classical security proofs in the random oracle model fail in the quantum setting since quantum superposition queries to the oracle allow for improved attacks. This project will develop crucial tools for the security analysis of random oracle based, post-quantum cryptosystems by means of a quantum analogue of the indifferentiability framework. A fundamental tool for analyzing the security of classical cryptosystems in the random oracle model involves proving the so-called indifferentiability of constructions. The notion of indifferentiability formalizes the properties required of a construction to securely replace an ideal object (such as a random oracle) in arbitrary cryptosystems. Although often taken for granted, indifferentiability results from the classical setting do not necessarily extend to the quantum setting. Moreover, the quantum setting presents unique obstacles to proving indifferentiability, leaving in doubt whether the entire indifferentiability technique is applicable in the quantum oracle setting. This project explores the possibility of an indifferentiability framework in the quantum oracle setting. Specifically, the project encompasses the following technical problems: (1) Determining whether or not broad impossibility results apply to the quantum indifferentiability setting; (2) Developing new techniques for proving quantum indifferentiability; (3) Defining new formal security models for the analysis of symmetric and public key cryptosystems in the quantum oracle model; (4) Analyzing the security of essential constructions with respect to quantum indifferentiability or the newly introduced formal models. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.