Cryptology ePrint Archive: Report 2016/423

Modeling Random Oracles under Unpredictable Queries

Pooya Farshim and Arno Mittelbach

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.

Category / Keywords: secret-key cryptography / Random oracle, Unpredictability, UCE, RKA security, KDM security, Zipper Hash, Indifferentiability, Multi-stage security

Original Publication (with major differences): IACR-FSE-2016

Date: received 29 Apr 2016, last revised 19 May 2016

Contact author: pooya farshim at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160519:172124 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]