How to generate and use universal samplers

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

doi:10.1007/978-3-662-53890-6_24

How to generate and use universal samplers

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 Scopus citations

Abstract

A 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.

Original language	English (US)
Title of host publication	Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jung Hee Cheon, Tsuyoshi Takagi
Publisher	Springer Verlag
Pages	715-744
Number of pages	30
ISBN (Print)	9783662538890
DOIs	https://doi.org/10.1007/978-3-662-53890-6_24
State	Published - Jan 1 2016
Event	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 - Hanoi, Viet Nam Duration: Dec 4 2016 → Dec 8 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10032 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
Country	Viet Nam
City	Hanoi
Period	12/4/16 → 12/8/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-53890-6_24

Fingerprint Dive into the research topics of 'How to generate and use universal samplers'. Together they form a unique fingerprint.

Cite this

Hofheinz, D., Jager, T., Khurana, D., Sahai, A., Waters, B., & Zhandry, M. (2016). How to generate and use universal samplers. In J. H. Cheon, & T. Takagi (Eds.), Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 715-744). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10032 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53890-6_24

Hofheinz, Dennis ; Jager, Tibor ; Khurana, Dakshita ; Sahai, Amit ; Waters, Brent ; Zhandry, Mark. / How to generate and use universal samplers. Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jung Hee Cheon ; Tsuyoshi Takagi. Springer Verlag, 2016. pp. 715-744 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b1c74fd59fc546a98864d8af9f81d72b,

title = "How to generate and use universal samplers",

abstract = "A 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.",

author = "Dennis Hofheinz and Tibor Jager and Dakshita Khurana and Amit Sahai and Brent Waters and Mark Zhandry",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-662-53890-6_24",

language = "English (US)",

isbn = "9783662538890",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "715--744",

editor = "Cheon, {Jung Hee} and Tsuyoshi Takagi",

booktitle = "Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

note = "22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 ; Conference date: 04-12-2016 Through 08-12-2016",

}

Hofheinz, D, Jager, T, Khurana, D, Sahai, A, Waters, B & Zhandry, M 2016, How to generate and use universal samplers. in JH Cheon & T Takagi (eds), Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10032 LNCS, Springer Verlag, pp. 715-744, 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016, Hanoi, Viet Nam, 12/4/16. https://doi.org/10.1007/978-3-662-53890-6_24

How to generate and use universal samplers. / Hofheinz, Dennis; Jager, Tibor; Khurana, Dakshita; Sahai, Amit; Waters, Brent; Zhandry, Mark.

Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jung Hee Cheon; Tsuyoshi Takagi. Springer Verlag, 2016. p. 715-744 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10032 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - How to generate and use universal samplers

AU - Hofheinz, Dennis

AU - Jager, Tibor

AU - Khurana, Dakshita

AU - Sahai, Amit

AU - Waters, Brent

AU - Zhandry, Mark

PY - 2016/1/1

Y1 - 2016/1/1

N2 - A 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.

AB - A 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.

UR - http://www.scopus.com/inward/record.url?scp=85008151918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85008151918&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53890-6_24

DO - 10.1007/978-3-662-53890-6_24

M3 - Conference contribution

AN - SCOPUS:85008151918

SN - 9783662538890

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 715

EP - 744

BT - Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Cheon, Jung Hee

A2 - Takagi, Tsuyoshi

PB - Springer Verlag

T2 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016

Y2 - 4 December 2016 through 8 December 2016

ER -

Hofheinz D, Jager T, Khurana D, Sahai A, Waters B, Zhandry M. How to generate and use universal samplers. In Cheon JH, Takagi T, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Verlag. 2016. p. 715-744. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-53890-6_24