Cryptology ePrint Archive: Report 2014/507

How to Generate and use Universal Samplers

Dennis Hofheinz and Tibor Jager and Dakshita Khurana and Amit Sahai and Brent Waters and Mark Zhandry

Abstract: The random oracle is an idealization that allows us to model a hash function as an oracle that will output a uniformly random string given any input. We introduce the notion of a universal sampler scheme that extends the notion of a random oracle, to a method of sampling securely from arbitrary distributions.

We describe several applications that provide a natural motivation for this notion; these include generating the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal samplers by showing how they give rise to simple constructions of identity-based encryption and multiparty key exchange. In particular, we construct adaptively secure non-interactive multiparty key exchange in the random oracle model based on indistinguishability obfuscation; obtaining the first known construction of adaptively secure NIKE without complexity leveraging.

We give a solution that shows how to transform any random oracle into a universal sampler scheme, based on indistinguishability obfuscation. At the heart of our construction and proof is a new technique we call “delayed backdoor programming” that we believe will have other applications.

Category / Keywords: cryptographic protocols / obfuscation

Date: received 27 Jun 2014, last revised 10 Oct 2015

Contact author: dakshita at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20151010:094806 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]