Modeling Random Oracles Under Unpredictable Queries

Abstract : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Pooya Farshim <>
Soumis le : vendredi 17 février 2017 - 20:12:48
Dernière modification le : mardi 24 avril 2018 - 17:20:13
Document(s) archivé(s) le : jeudi 18 mai 2017 - 15:25:28


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




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⟩



Consultations de la notice


Téléchargements de fichiers