Formal Indistinguishability Extended to the Random Oracle Model

Cristian Ene 1 Yassine Lakhnech 1 Van Chan Ngo 2
2 ESPRESSO - Synchronous programming for the trusted component-based engineering of embedded systems and mission-critical systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Several generic constructions for transforming one-way func-tions to asymmetric encryption schemes have been proposed. One-way functions only guarantee the weak secrecy of their arguments. That is, given the image by a one-way function of a random value, an adversary has only negligible probability to compute this random value. Encryp-tion schemes must guarantee a stronger secrecy notion. They must be at least resistant against indistinguishability-attacks under chosen plaintext text (IND-CPA). Most practical constructions have been proved in the random oracle model (ROM for short). Such computational proofs turn out to be complex and error prone. Bana et al. have introduced Formal Indistinguishability Relations (FIR), as an abstraction of computational indistinguishability. In this paper, we extend the notion of FIR to cope with the ROM on one hand and adaptive adversaries on the other hand. Indeed, when dealing with hash functions in the ROM and one-way func-tions, it is important to correctly abstract the notion of weak secrecy. Moreover, one needs to extend frames to include adversaries in order to capture security notions as IND-CPA. To fix these problems, we consider pairs of formal indistinguishability relations and formal non-derivability relations. We provide a general framework along with general theorems, that ensure soundness of our approach and then we use our new frame-work to verify several examples of encryption schemes among which the construction of Bellare Rogaway and Hashed ElGamal.
Type de document :
Communication dans un congrès
ESORICS 2009, Sep 2009, St Malo, France. pp.555 - 570, 2009, 〈10.1007/978-3-642-04444-1_34〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger
Contributeur : Van Chan Ngo <>
Soumis le : mardi 25 novembre 2014 - 10:40:03
Dernière modification le : vendredi 6 juillet 2018 - 10:08:02
Document(s) archivé(s) le : jeudi 26 février 2015 - 11:00:37


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



Cristian Ene, Yassine Lakhnech, Van Chan Ngo. Formal Indistinguishability Extended to the Random Oracle Model. ESORICS 2009, Sep 2009, St Malo, France. pp.555 - 570, 2009, 〈10.1007/978-3-642-04444-1_34〉. 〈hal-01086874〉



Consultations de la notice


Téléchargements de fichiers