(Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography

Abstract

In this paper, we show how a recently introduced $\lambda$-calculus for randomized computation, called $\lambda \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 $\lambda \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.

arXiv commentExtended version of a paper to appear in the proceedings of FSTTCS 2026