Cryptology ePrint Archive: Report 2014/518

Cryptography from Compression Functions: The UCE Bridge to the ROM

Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi

Abstract: This paper suggests and explores the use of UCE security for the task of turning VIL-ROM schemes into FIL-ROM ones. The benefits we offer over indifferentiability, the current leading method for this task, are the ability to handle multi-stage games and greater efficiency. The paradigm consists of (1) Showing that a VIL UCE function can instantiate the VIL RO in the scheme, and (2) Constructing the VIL UCE function given a FIL random oracle. The main technical contributions of the paper are domain extension transforms that implement the second step. Leveraging known results for the first step we automatically obtain FIL-ROM constructions for several primitives whose security notions are underlain by multi-stage games. Our first domain extender exploits indifferentiability, showing that although the latter does not work directly for multi-stage games it can be used indirectly, through UCE, as a tool for this end. Our second domain extender targets performance. It is parallelizable and shown through implementation to provide significant performance gains over indifferentiable domain extenders.

Category / Keywords: foundations / random-oracle model, indifferentiability, multi-stage games, UCE, parallelizable hash

Original Publication (with major differences): CRYPTO 2014

Date: received 2 Jul 2014

Contact author: vth005 at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20140703:180727 (All versions of this report)

Short URL: ia.cr/2014/518

Discussion forum: Show discussion | Start new discussion