Towards a More Robust Foundation for Cryptography from Minimal Hardness Assumptions
Abstract
Modern Cryptography relies on the principle that cryptographic schemes are proven secure based on mathematically precise assumptions. The provable security framework, initiated by Golwasser and Micali in 1984, instatiates this principle through the following steps- (a) we formalize the cryptographic task in consideration and precisely specify a model of security; (b) we define some computational intractrability assumptions (e.g., the hardness of factoring products of large primes, or the existence of one-way functions), and (c) we prove that any attack on the security of the task must violate the computational assumptions; this is done using a so-called security reduction. This paradigm has proven extremely powerful in the last decades and is the prevailing method for analyzing the security of cryptographic protocols in a mathematically precise way. We here propose to revisit and strengthen some of the foundational aspects of this paradigm, towards getting a foundation that is based on as weak assumptions as possible. Most notably, our goal is to develop and analyze the feasibility of (a) more robust security reductions, and (b) simpler and more robust constructions based on minimal cryptography hardness assumptions. In particular, our goal is to capture security proofs that remain relevant even if there are some unexpected progress in computing techniques (e.g.,quantum computers are built to scale, or some other physical phenomena enables faster-different computing architectures). At the same time, we want to design cryptographic scheme that are proven secure under the weakest and most robust computational assumptions, ideally those where it suffices to assume the existence of any distribution on which the computational problem is hard (as opposed to considering some very specific distributions); at the same time, a major goal will be to develop new and simpler constructions for basic cryptographic primitives from the weakest possible assumptions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2025
- Source ID
- FA95502410267
Entities
People
- Rafael Pass
Organizations
- Air Force Office of Scientific Research
- Cornell University
- United States Air Force