A new paper on arXiv shows that a recently introduced lambda calculus for randomized computation, called λBLL, can accurately capture the notions of first- and second-order probabilistic polynomial time. These complexity classes are central to cryptography, where security proofs typically rely on the assumption that certain randomized problems cannot be solved efficiently.
The authors demonstrate that λBLL provides a precise formal setting for expressing such polytime computations. This matters because cryptographic reasoning often requires a rigorous, syntax-level account of what it means for an algorithm to run in probabilistic polynomial time, rather than relying on informal or ad hoc characterizations.
The abstract does not go into technical detail about the proof strategy, but the result positions λBLL as a potentially useful bridge between programming language theory and cryptographic complexity. As the paper notes, the framework captures both first- and second-order polytime computations, suggesting broad applicability across different layers of cryptographic construction and analysis.