On Equivalences, Metrics, and Polynomial Time

Alberto Cappai 1, 2 Ugo Dal Lago 2, 1
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
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.
Type de document :
Communication dans un congrès
FCT 2015, Aug 2015, Gdansk, Poland. LNCS, 9210, pp.311-323, 2015, 〈10.1007/978-3-319-22177-9_24〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

Contributeur : Ugo Dal Lago <>
Soumis le : vendredi 20 novembre 2015 - 16:47:47
Dernière modification le : mercredi 10 octobre 2018 - 10:09:26
Document(s) archivé(s) le : vendredi 28 avril 2017 - 16:49:28


Fichiers produits par l'(les) auteur(s)




Alberto Cappai, Ugo Dal Lago. On Equivalences, Metrics, and Polynomial Time. FCT 2015, Aug 2015, Gdansk, Poland. LNCS, 9210, pp.311-323, 2015, 〈10.1007/978-3-319-22177-9_24〉. 〈hal-01231790〉



Consultations de la notice


Téléchargements de fichiers