Calculus captures cryptographic polynomial time computations precisely
(Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography
Programming LanguagesCryptography and Security
Summary
Cryptography relies on computations that run in polynomial time to keep data secure. The authors show that a special kind of math system called a lambda calculus can perfectly describe these computations. This means cryptographic experiments and attacks can be represented without losing track of how complex they are. Even with minimal building blocks, this system can express all necessary polynomial-time computations used in cryptography.
What this means in practice
- •For cryptography engineers: Formulate cryptographic experiments and adversaries within a guaranteed polynomial-time computational framework to ensure security reductions remain valid.
- •For programming language designers: Design complexity-aware programming languages that enforce polynomial-time computation for randomized algorithms used in security contexts.
A theory result. No direct application yet.
Authors
Ugo Dal Lago, Giulia Giusti
Abstract
In this paper, we show how a recently introduced $λ$-calculus for randomized computation, called $λ\mathbf{BLL}$, can accurately capture the notions of first- and second-order polytime computations used in cryptographic definitions and proofs. These results, spelled out in the style of so-called \emph{implicit computational complexity}, imply that $λ\mathbf{BLL}$ is sufficiently powerful to express experiments and adversaries as used in cryptography, and that reductions, when formulated within the calculus, are guaranteed to be complexity-preserving. Remarkably, while polynomial-time soundness holds for the full calculus, polynomial-time completeness already follows in presence of a minimal finite set of basic functions.