More Web Proxy on the site http://driver.im/

Article

How to Generate and Use Universal Samplers

Authors:

Dennis Hofheinz,

Dakshita Khurana,

Mark ZhandryAuthors Info & Claims

Proceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 10032

Pages 715 - 744

https://doi.org/10.1007/978-3-662-53890-6_24

Published: 04 December 2016 Publication History

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.

References

[1]

Ananth, P., Boneh, D., Garg, S., Sahai, A., Zhandry, M.: Differing-inputs obfuscation and applications. IACR Cryptology ePrint Archive 2013, p. 689 2013

[2]

Ball, J., Borger, J., Greenwald, G.: Revealed: how US and UK spy agencies defeat internet privacy and security. The Guardian 2013. http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security

[3]

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the Impossibility of obfuscating programs. In: Kilian, J. ed. CRYPTO 2001. LNCS, vol. 2139, pp. 1---18. Springer, Heidelberg 2001.

Digital Library

[4]

Bellare, M., Hoang, V.T., Keelveedhi, S.: Instantiating random Oracles via UCEs. In: Canetti, R., Garay, J.A. eds. CRYPTO 2013. LNCS, vol. 8043, pp. 398---415. Springer, Heidelberg 2013.

[5]

Bellare, M., Rogaway, P.: Random Oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, 3---5 November 1993, pp. 62---73 1993

Digital Library

[6]

Bellare, M., Rogaway, P.: The exact security of digital signatures - how to sign with RSA and Rabin. In: Proceeding Advances in Cryptology - EUROCRYPT 1996, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, 12---16 May 1996, pp. 399---416 1996

Digital Library

[7]

Blocki, J., Zhou, H.: Designing proof of human-work puzzles for cryptocurrency and beyond. IACR Cryptology ePrint Archive 2016, p. 145 2016. http://eprint.iacr.org/2016/145

[8]

Boneh, D., Boyen, X.: Efficient selective identity-based encryption without random oracles. J. Cryptology 244, 659---693 2011.

Digital Library

[9]

Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. ed. CRYPTO 2001. LNCS, vol. 2139, pp. 213---229. Springer, Heidelberg 2001.

Digital Library

[10]

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. ed. EUROCRYPT 2003. LNCS, vol. 2656, pp. 416---432. Springer, Heidelberg 2003.

Digital Library

[11]

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. IACR Cryptology ePrint Archive 2013, p. 352 2013

[12]

Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. eds. CRYPTO 2014. LNCS, vol. 8616, pp. 480---499. Springer, Heidelberg 2014.

[13]

Boyle, E., Chung, K.-M., Pass, R.: On extractability obfuscation. In: Lindell, Y. ed. TCC 2014. LNCS, vol. 8349, pp. 52---73. Springer, Heidelberg 2014.

[14]

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. IACR Cryptology ePrint Archive 2013, p. 401 2013

[15]

Camenisch, J., Hohenberger, S., Pedersen, M.Ø.: Batch verification of short signatures. J. Cryptology 254, 723---747 2012

Digital Library

[16]

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 514, 557---594 2004

Digital Library

[17]

Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. J. Cryptology 203, 265---294 2007

Digital Library

[18]

Dachman-Soled, D., Katz, J., Rao, V.: Adaptively secure, universally composable, multiparty computation in constant rounds. In: Dodis, Y., Nielsen, J.B. eds. TCC 2015. LNCS, vol. 9015, pp. 586---613. Springer, Heidelberg 2015.

[19]

Garg, S., Gentry, C., Halevi, S., Raykova, M.: Two-round secure MPC from indistinguishability obfuscation. In: Lindell, Y. ed. TCC 2014. LNCS, vol. 8349, pp. 74---94. Springer, Heidelberg 2014.

[20]

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013

Digital Library

[21]

Garg, S., Pandey, O., Srinivasan, A., Zhandry, M.: Breaking the sub-exponential barrier in obfustopia. IACR Cryptology ePrint Archive 2016, p. 102 2016. http://eprint.iacr.org/2016/102

[22]

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions extended abstract. In: FOCS, pp. 464---479 1984

Digital Library

[23]

Goldwasser, S., Rothblum, G.N.: On best-possible obfuscation. In: Vadhan, S.P. ed. TCC 2007. LNCS, vol. 4392, pp. 194---213. Springer, Heidelberg 2007.

Digital Library

[24]

Hofheinz, D., Kamath, A., Koppula, V., Waters, B.: Adaptively secure constrained pseudorandom functions. IACR Cryptology ePrint Archive 2014, p. 720 2014

[25]

Hohenberger, S., Koppula, V., Waters, B.: Universal signature aggregators. In: Oswald, E., Fischlin, M. eds. EUROCRYPT 2015. LNCS, vol. 9057, pp. 3---34. Springer, Heidelberg 2015.

[26]

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. IACR Cryptology ePrint Archive 2013, p. 379 2013

[27]

Larson, J., Perlroth, N., Shane, S.: Revealed: The NSA's secret campaign to crack, undermine internet security. Pro-Publica 2013. http://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption

[28]

Liang, B., Li, H., Chang, J.: The generic transformation from standard signatures to identity-based aggregate signatures. In: Lopez, J., Mitchell, C.J. eds. ISC 2015. LNCS, vol. 9290, pp. 21---41. Springer, Heidelberg 2015.

Digital Library

[29]

Nielsen, J.B.: Separating Random Oracle Proofs from Complexity Theoretic Proofs: the non-committing encryption case. In: Yung, M. ed. CRYPTO 2002. LNCS, vol. 2442, pp. 111---126. Springer, Heidelberg 2002.

Digital Library

[30]

Perlroth, N., Larson, J., Shane, S.: N.S.A. able to foil basic safeguards of privacy on web. Internation New York Times 2013. http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html

[31]

Rao, V.: Adaptive multiparty non-interactive key exchange without setup in the standard model. Cryptology ePrint Archive, Report 2014/910 2014. http://eprint.iacr.org/

[32]

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475---484 2014

Digital Library

Cited By

Lou PManohar NSahai A(2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_6
Abram DBeimel AIshai YKushilevitz ENarayanan V(2023)Cryptography from Planted Graphs: Security with Logarithmic-Size MessagesTheory of Cryptography10.1007/978-3-031-48615-9_11(286-315)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48615-9_11
Koppula VWaters BZhandry M(2022)Adaptive Multiparty NIKETheory of Cryptography10.1007/978-3-031-22365-5_9(244-273)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_9
Show More Cited By

How to Generate and Use Universal Samplers

Recommendations

Universal designated verifier signcryption
NSS'12: Proceedings of the 6th international conference on Network and System Security

Universal Designated Verifier Signature (UDVS) was introduced by Steinfeld et al. in Asiacrypt'03. UDVS allows a signature holder, who has a signature of a signer, to convince a designated verifier that he is in possession of a signer's signature, while ...
Secure universal designated verifier signature without random oracles

In Asiacrypt 2003, the concept of universal designated verifier signature (UDVS) was introduced by Steinfeld, Bull, Wang and Pieprzyk. In the new paradigm, any signature holder (not necessarily the signer) can designate the publicly verifiable signature ...
Secure universal designated verifier identity-based signcryption

In 2003, Steinfeld et al. introduced the notion of universal designated verifier signature UDVS, which allows a signature holder, who receives a signature from the signer, to convince a designated verifier whether he is possession of a signer's ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 10032

December 2016

1027 pages

ISBN:9783662538890

Editors:
Jung Hee Cheon
Seoul National University, Seoul, Korea Republic of
,
Tsuyoshi Takagi
Kyushu University, Fukuoka, Japan

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 December 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lou PManohar NSahai A(2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_6
Abram DBeimel AIshai YKushilevitz ENarayanan V(2023)Cryptography from Planted Graphs: Security with Logarithmic-Size MessagesTheory of Cryptography10.1007/978-3-031-48615-9_11(286-315)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48615-9_11
Koppula VWaters BZhandry M(2022)Adaptive Multiparty NIKETheory of Cryptography10.1007/978-3-031-22365-5_9(244-273)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_9
Lu GWaters B(2022)How to Sample a Discrete Gaussian (and more) from a Random OracleTheory of Cryptography10.1007/978-3-031-22365-5_23(653-682)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_23
Abram DScholl PYakoubov S(2022)Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One RoundAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-06944-4_27(790-820)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06944-4_27
Jain ALin HSahai AKhuller SVassilevska Williams V(2021)Indistinguishability obfuscation from well-founded assumptionsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451093(60-73)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451093
Duan LLi YLiao L(2021)Flexible Group Non-interactive Key Exchange in the Standard ModelInnovative Security Solutions for Information Technology and Communications10.1007/978-3-031-17510-7_15(210-227)Online publication date: 25-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-031-17510-7_15
Gay RJain ALin HSahai A(2021)Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and SimplificationAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77883-5_4(97-126)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77883-5_4
Ali ICaprolu MPietro R(2020)Foundations, Properties, and Security Applications of PuzzlesACM Computing Surveys10.1145/339637453:4(1-38)Online publication date: 20-Aug-2020
https://dl.acm.org/doi/10.1145/3396374
Agrikola TCouteau GIshai YJarecki SSahai A(2020)On Pseudorandom EncodingsTheory of Cryptography10.1007/978-3-030-64381-2_23(639-669)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64381-2_23
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten