How to Generate and use Universal Samplers

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

Paper 2014/507

How to Generate and use Universal Samplers

Dennis Hofheinz, Tibor Jager, Dakshita Khurana, Amit Sahai, 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.

Note: -

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: obfuscation
Contact author(s): dakshita @ cs ucla edu
History: 2015-10-10: last of 8 revisions; 2014-06-28: received; See all versions
Short URL: https://ia.cr/2014/507
License: CC BY

BibTeX

@misc{cryptoeprint:2014/507,
      author = {Dennis Hofheinz and Tibor Jager and Dakshita Khurana and Amit Sahai and Brent Waters and Mark Zhandry},
      title = {How to Generate and use Universal Samplers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/507},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/507}},
      url = {https://eprint.iacr.org/2014/507}
}