Skip to Main content Skip to Navigation
Conference papers

Formal Indistinguishability Extended to the Random Oracle Model

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : van Chan Ngo <>
Submitted on : Tuesday, November 25, 2014 - 10:40:03 AM
Last modification on : Thursday, November 19, 2020 - 3:58:03 PM
Long-term archiving on: : Thursday, February 26, 2015 - 11:00:37 AM


Files produced by the author(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, ⟨10.1007/978-3-642-04444-1_34⟩. ⟨hal-01086874⟩



Record views


Files downloads