Paper 2016/423

Modeling Random Oracles under Unpredictable Queries

Pooya Farshim and Arno Mittelbach


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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2016
Random oracleUnpredictabilityUCERKA securityKDM securityZipper HashIndifferentiabilityMulti-stage security
Contact author(s)
pooya farshim @ gmail com
2016-05-19: revised
2016-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pooya Farshim and Arno Mittelbach},
      title = {Modeling Random Oracles under Unpredictable Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2016/423},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.