Modeling Random Oracles Under Unpredictable Queries - ENS - École normale supérieure Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Modeling Random Oracles Under Unpredictable Queries


In recent work, Bellare, Hoang, and Keelveedhi (CRYPTO 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed how they can replace random oracles (ROs) across a wide range of cryptosystems. We formulate a new framework, called Interactive Computational Extractors (ICEs), that extends UCEs by viewing them as models of ROs under unpredictable (aka. high-entropy) queries. We overcome a number of limitations of UCEs in the new framework, and in particular prove the adaptive RKA and semi-adaptive KDM securities of a highly efficient symmetric encryption scheme using ICEs under key offsets. We show both negative and positive feasibility results for ICEs. On the negative side, we demonstrate ICE attacks on the HMAC and NMAC constructions. On the positive side we show that: 1) ROs are indeed ICE secure, thereby confirming the structural soundness of our definition and enabling a finer layered approach to protocol design in the RO model; and 2) a modified version of Liskov's Zipper Hash is ICE secure with respect to an underlying fixed-input-length RO, for appropriately restricted classes of adversaries. This brings the first result closer to practice by moving away from variable-input-length ROs. Our security proofs employ techniques from indifferentiability in multi-stage settings.
Fichier principal
Vignette du fichier
main.pdf (655.83 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01470886 , version 1 (17-02-2017)



Pooya Farshim, Arno Mittelbach. Modeling Random Oracles Under Unpredictable Queries. 23rd International Conference on Fast Software Encryption (FSE 2016), Mar 2016, Bochum, Germany. pp.453-473, ⟨10.1007/978-3-662-52993-5_23⟩. ⟨hal-01470886⟩


94 Consultations
327 Téléchargements



Gmail Facebook Twitter LinkedIn More