(Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography

Ugo Dal Lago, Giulia Giusti

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 poly…