Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Nonlinear Invariant Attack Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

How to Generate and Use Universal Samplers

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

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
Nächstes Kapitel Iterated Random Oracle: A Universal Approach for Finding Loss in Security Reduction
Fußnoten
1
Several cryptographic primitives (e.g. NIZKs) are realizable using only a common random string and thus only need access to a trusted random source for setup. However, many cutting edge constructions need to use a common reference string that is setup by some private computation. For example, the NIZKs in Sahai-Waters [32] and the recent two-round MPC protocol of Garg et al. [19] uses a trusted setup phase that generates public parameters drawn from a nontrivial distribution, where the randomness underlying the specific parameter choice needs to be kept secret.
 
2
We note that random oracles are often used as a tool to help sample from various distributions. For example, we might use them to select a prime. In RSA full domain hash signatures [6], they are used to select a group element in \(\mathbb {Z}_{N}^*\). This sampling occurs as a two step process. First, the function H is used to sample a fresh string x which is completely visible to the attacker. Then there is some post processing phase such as taking \(x \pmod N\) to sample an integer mod N. In the literature this is often described as one function for the sake of brevity. However, the distinction between sampling with a universal sampler scheme and applying post processing to a random oracle output is very important.
 
3
Note that once the universal sampler parameters of a fixed polynomial size are given out, it is not possible for a standard model proof to make an unbounded number of parameters consistent with the already-fixed universal sampler parameters.
 
4
In our construction of Sect. 5 we directly use our 1-bounded scheme inside the construction. However, we believe our construction can be adapted to work for any one bounded scheme.
 
5
This is actually performed by a sequence of smaller steps in our proof. We simplify to bigger steps in this overview.
 
6
Note that if we assume \(iO\) for Turing Machines, then we do not need to restrict the size of the description of d. Candidates for \(iO\) for Turing Machines were given by [1, 13].
 
7
Note that proving security against such admissible adversaries suffices to capture the intuition behind a universal sampler and in particular suffices for all our applications. This is because honest parties will still use the correctly generated output, and we would like to guarantee that no malicious adversary will be able to distinguish the samples used by honest parties from externally generated samples.
 
8
\({\mathcal A} \) does not have direct access to \({\mathcal F} \), in fact \({\mathcal A} \) will only have access to \(\mathtt {SimRO}\) which we define later to model the output of a programmable random oracle.
 
9
Looking ahead, in our proof, \(\mathtt {SimRO}\) will use the output of queries to \(\mathcal O\) to generate a programmed output of the Random Oracle.
 
10
Recall that an admissible adversary only honestly computes samples and adds them to its tape – i.e., an admissible adversary always writes \(p_d = \mathtt {Sample}^{{\mathcal H}}(U, d)\) as the honest output of the sampler program. Thus, an honest sample violation in the ideal world indicates that the simulator did not force the correct samples d(F(d)) obtained externally from a trusted party, into the output of the sampler program.
 
11
Appropriately padded to the maximum of the size of itself and Program Selective-Single-Samples: 2 in Fig. 2.
 
12
Padded to the maximum of the size of itself and Selective-Single-Samples: 2.
 
13
Padded to the maximum of the size of itself and Selective-Single-Samples.
 
14
Padded to the maximum of the size of itself and Selective-Single-Samples.
 
15
Padded to the maximum of the size of itself and Selective-Single-Samples.
 
16
This program must be padded appropriately to maximum of the size of itself and other corresponding programs in various hybrids, as described in the next section.
 
17
Appropriately padded to the maximum of the size of itself and \(P'_{K_3, p_j^*, d_j^*}\) in future hybrids.
 
18
To the maximum of the size of itself and all corresponding programs in the other hybrids.
 
Literatur
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.
3.
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44647-8_​1 CrossRef
4.
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)
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)
7.
8.
9.
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). doi:10.​1007/​3-540-39200-9_​26 CrossRef
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). doi:10.​1007/​978-3-662-44371-2_​27 CrossRef
13.
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 25(4), 723–747 (2012)MathSciNetCrossRefMATH
16.
17.
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). doi:10.​1007/​978-3-662-46497-7_​23 CrossRef
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). doi:10.​1007/​978-3-642-54242-8_​4 CrossRef
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)
21.
22.
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: FOCS, pp. 464–479 (1984)
23.
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). doi:10.​1007/​978-3-662-46803-6_​1
26.
Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. IACR Cryptology ePrint Archive 2013, p. 379 (2013)
27.
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). doi:10.​1007/​978-3-319-23318-5_​2 CrossRef
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). doi:10.​1007/​3-540-45708-9_​8 CrossRef
30.
31.
32.
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014)
Metadaten
Titel
How to Generate and Use Universal Samplers
verfasst von
Dennis Hofheinz
Tibor Jager
Dakshita Khurana
Amit Sahai
Brent Waters
Mark Zhandry
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – ASIACRYPT 2016

Print ISBN: 978-3-662-53889-0

Electronic ISBN: 978-3-662-53890-6

Copyright-Jahr: 2016

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