Interactive behaviors are ubiquitous in modern cryptography, but are also present in λ-calculi, in the form of higher-order constructions. Traditionally, however, typed λ-calculi simply do not fit well into cryptography, being both deterministic and too powerful as for the complexity of functions they can express. We study interaction in a λ-calculus for probabilistic polynomial time computable functions. In particular, we show how notions of context equivalence and context metric can both be characterized by way of traces when defined on linear contexts. We then give evidence on how this can be turned into a proof methodology for computational indistinguishability, a key notion in modern cryptography. We also hint at what happens if a more general notion of a context is used.
On equivalences, metrics, and polynomial time / Cappai, Alberto; Dal Lago, Ugo. - ELETTRONICO. - 9210:(2015), pp. 311-323. (Intervento presentato al convegno 20th International Symposium on Fundamentals of Computation Theory, FCT 2015 tenutosi a Polonia nel 2015) [10.1007/978-3-319-22177-9_24].
On equivalences, metrics, and polynomial time
CAPPAI, ALBERTO;DAL LAGO, UGO
2015
Abstract
Interactive behaviors are ubiquitous in modern cryptography, but are also present in λ-calculi, in the form of higher-order constructions. Traditionally, however, typed λ-calculi simply do not fit well into cryptography, being both deterministic and too powerful as for the complexity of functions they can express. We study interaction in a λ-calculus for probabilistic polynomial time computable functions. In particular, we show how notions of context equivalence and context metric can both be characterized by way of traces when defined on linear contexts. We then give evidence on how this can be turned into a proof methodology for computational indistinguishability, a key notion in modern cryptography. We also hint at what happens if a more general notion of a context is used.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.