Skip to main content
Erschienen in: Journal of Cryptology 3/2019

22.03.2018

The Magic of ELFs

verfasst von: Mark Zhandry

Erschienen in: Journal of Cryptology | Ausgabe 3/2019

Einloggen

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

search-config
loading …

Abstract

We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size r. We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomially many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions—for example, polynomially many hardcore bits were only known from differing inputs obfuscation, a notion whose plausibility has been seriously challenged. We also use ELFs to build a simple hash function with output intractability, a new notion we define that may be useful for generating common reference strings. Next, we give a construction of ELFs relying on the exponential hardness of the decisional Diffie–Hellman problem, which is plausible in elliptic curve groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different—and arguably better—assumptions than prior works.

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!

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!

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!

Fußnoten
1
The construction of [22] can also be made public coin by tweaking the generation procedure. However, this necessarily loses the trapdoor, as having a trapdoor and being public coin are incompatible. To the best of our knowledge, however, we are the first to observe this public coin feature.
 
2
One drawback of our construction—which is shared with some of the prior constructions—is that we achieve a relaxed notion of correctness where for some sparse “bad” choices of the obfuscation randomness, the outputted program may compute the wrong function.
 
3
The ability to sample a random image point does not follow immediately from our basic ELF definition, though this can be done in our construction. If the ELF is regular, then this can be accomplished by sampling a random input to the ELF and then applying the ELF. More generally, if it is possible to efficiently enumerate all the image points, then randomly sampling an image point is easy. Of course, enumerating all the image points will take time at least r, which is larger than the running time of the adversary, but can still potentially be done efficiently.
 
4
We also need to abort if any of the \(m_i\) do hash to \(y_i\). It is straightforward to show that we still do not abort with probability at least \(\frac{1}{2r}\).
 
5
The case of point functions is more or less equivalent to a similar result of Wee [45].
 
6
Often, the Rényi Divergence is defined to be proportional to the logarithm of this quantity. For our purposes, this representation of the divergence will be more convenient.
 
7
Note that the typical use of pairwise independence is equivalent to our notion of pairwise independence plus uniformity. For our purposes, it will be convenient to separate out the two properties.
 
8
Peikert and Waters [38] additionally require that, in the injective mode, there is a trapdoor that allows inverting the function. We will not need any such trapdoor.
 
9
A third option is that H is a “universal” almost exponentially secure one-way functions, meaning that H is an exponentially secure one-way function if and only if such one-way functions exist. [28].
 
Literatur
2.
Zurück zum Zitat A. Akavia, S. Goldwasser, V. Vaikuntanathan, Simultaneous hardcore bits and cryptography against memory attacks, in O. Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, March 15–17, 2009), pp. 474–495 A. Akavia, S. Goldwasser, V. Vaikuntanathan, Simultaneous hardcore bits and cryptography against memory attacks, in O. Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, March 15–17, 2009), pp. 474–495
4.
Zurück zum Zitat E. Boyle, K.-M. Chung, R. Pass. On extractability obfuscation, in Y. Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, San Diego, CA, USA, February 24–26, 2014), pp. 52–73 E. Boyle, K.-M. Chung, R. Pass. On extractability obfuscation, in Y. Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, San Diego, CA, USA, February 24–26, 2014), pp. 52–73
5.
Zurück zum Zitat N. Bitansky, R. Canetti, O. Paneth, A. Rosen, On the existence of extractable one-way functions, in D.B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing (ACM Press, New York, NY, USA, May 31–June 3, 2014), pp. 505–514 N. Bitansky, R. Canetti, O. Paneth, A. Rosen, On the existence of extractable one-way functions, in D.B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing (ACM Press, New York, NY, USA, May 31–June 3, 2014), pp. 505–514
6.
Zurück zum Zitat C. Brzuska, P. Farshim, A. Mittelbach, Indistinguishability obfuscation and UCEs: the case of computationally unpredictable sources, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2014), pp. 188–205 C. Brzuska, P. Farshim, A. Mittelbach, Indistinguishability obfuscation and UCEs: the case of computationally unpredictable sources, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2014), pp. 188–205
7.
Zurück zum Zitat I. Berman, I. Haitner, From non-adaptive to adaptive pseudorandom functions, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 357–368 I. Berman, I. Haitner, From non-adaptive to adaptive pseudorandom functions, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 357–368
8.
Zurück zum Zitat F. Böhl, D. Hofheinz, T. Jager, J. Koch, J.H. Seo, C. Striecks, Practical signatures from standard assumptions, in T. Johansson, P.Q. Nguyen, editors, Advances in Cryptology—EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Athens, Greece, May 26–30, 2013), pp. 461–485 F. Böhl, D. Hofheinz, T. Jager, J. Koch, J.H. Seo, C. Striecks, Practical signatures from standard assumptions, in T. Johansson, P.Q. Nguyen, editors, Advances in Cryptology—EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Athens, Greece, May 26–30, 2013), pp. 461–485
9.
Zurück zum Zitat M. Bellare, V.T. Hoang, S. Keelveedhi, Instantiating random oracles via UCEs, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 18–22, 2013), pp. 398–415 M. Bellare, V.T. Hoang, S. Keelveedhi, Instantiating random oracles via UCEs, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 18–22, 2013), pp. 398–415
10.
Zurück zum Zitat N. Bitansky, O. Paneth, Point obfuscation and 3-round zero-knowledge, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 190–208 N. Bitansky, O. Paneth, Point obfuscation and 3-round zero-knowledge, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 190–208
11.
Zurück zum Zitat M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in V. Ashby, editor, ACM CCS 93: 1st Conference on Computer and Communications Security (ACM Press, Fairfax, Virginia, USA, November 3–5, 1993), pp. 62–73 M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in V. Ashby, editor, ACM CCS 93: 1st Conference on Computer and Communications Security (ACM Press, Fairfax, Virginia, USA, November 3–5, 1993), pp. 62–73
12.
Zurück zum Zitat M. Bellare, I. Stepanovs, S. Tessaro, Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation, in P. Sarkar, T. Iwata, editors, Advances in Cryptology—ASIACRYPT 2014, Part II, volume 8874 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014), pp. 102–121 M. Bellare, I. Stepanovs, S. Tessaro, Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation, in P. Sarkar, T. Iwata, editors, Advances in Cryptology—ASIACRYPT 2014, Part II, volume 8874 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014), pp. 102–121
13.
Zurück zum Zitat M. Bellare, I. Stepanovs, S. Tessaro, Contention in cryptoland: obfuscation, leakage and UCE, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part II, volume 9563 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 542–564 M. Bellare, I. Stepanovs, S. Tessaro, Contention in cryptoland: obfuscation, leakage and UCE, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part II, volume 9563 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 542–564
14.
Zurück zum Zitat D. Boneh, M. Zhandry, Secure signatures and chosen ciphertext security in a quantum computing world, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 18–22, 2013), pp. 361–379 D. Boneh, M. Zhandry, Secure signatures and chosen ciphertext security in a quantum computing world, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 18–22, 2013), pp. 361–379
15.
Zurück zum Zitat R. Canetti, Towards realizing random oracles: hash functions that hide all partial information, in B.S. Kaliski Jr., editor, Advances in Cryptology—CRYPTO’97, volume 1294 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 1997), pp. 455–469 R. Canetti, Towards realizing random oracles: hash functions that hide all partial information, in B.S. Kaliski Jr., editor, Advances in Cryptology—CRYPTO’97, volume 1294 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 1997), pp. 455–469
16.
Zurück zum Zitat R. Canetti, Y. Chen, L. Reyzin, On the correlation intractability of obfuscated pseudorandom functions, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 389–415 R. Canetti, Y. Chen, L. Reyzin, On the correlation intractability of obfuscated pseudorandom functions, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 389–415
17.
Zurück zum Zitat R. Canetti, O. Goldreich, S. Halevi. The random oracle methodology, revisited (preliminary version), in 30th Annual ACM Symposium on Theory of Computing (ACM Press, Dallas, Texas, USA, May 23–26, 1998), pp. 209–218 R. Canetti, O. Goldreich, S. Halevi. The random oracle methodology, revisited (preliminary version), in 30th Annual ACM Symposium on Theory of Computing (ACM Press, Dallas, Texas, USA, May 23–26, 1998), pp. 209–218
18.
Zurück zum Zitat R. Canetti, D. Micciancio, O. Reingold, Perfectly one-way probabilistic hash functions (preliminary version), in 30th Annual ACM Symposium on Theory of Computing (ACM Press, Dallas, Texas, USA, May 23–26, 1998), pp. 131–140 R. Canetti, D. Micciancio, O. Reingold, Perfectly one-way probabilistic hash functions (preliminary version), in 30th Annual ACM Symposium on Theory of Computing (ACM Press, Dallas, Texas, USA, May 23–26, 1998), pp. 131–140
19.
Zurück zum Zitat S. Dziembowski, K. Pietrzak, Leakage-resilient cryptography, in 49th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Philadelphia, Pennsylvania, USA, October 25–28, 2008), pp. 293–302 S. Dziembowski, K. Pietrzak, Leakage-resilient cryptography, in 49th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Philadelphia, Pennsylvania, USA, October 25–28, 2008), pp. 293–302
20.
Zurück zum Zitat Y. Dodis, A. Smith, Correcting errors without leaking partial information, in H.N. Gabow, R. Fagin, editors, 37th Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 22–24, 2005), pp. 654–663 Y. Dodis, A. Smith, Correcting errors without leaking partial information, in H.N. Gabow, R. Fagin, editors, 37th Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 22–24, 2005), pp. 654–663
21.
Zurück zum Zitat N. Döttling, D. Schröder, Efficient pseudorandom functions via on-the-fly adaptation, in R. Gennaro, M.J.B. Robshaw, editors, Advances in Cryptology—CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 16–20, 2015), pp. 329–350 N. Döttling, D. Schröder, Efficient pseudorandom functions via on-the-fly adaptation, in R. Gennaro, M.J.B. Robshaw, editors, Advances in Cryptology—CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 16–20, 2015), pp. 329–350
22.
Zurück zum Zitat D.M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, G. Segev, More constructions of lossy and correlation-secure trapdoor functions, in P.Q. Nguyen, D. Pointcheval, editors, PKC 2010: 13th International Conference on Theory and Practice of Public Key Cryptography, volume 6056 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Paris, France, May 26–28, 2010), pp. 279–295 D.M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, G. Segev, More constructions of lossy and correlation-secure trapdoor functions, in P.Q. Nguyen, D. Pointcheval, editors, PKC 2010: 13th International Conference on Theory and Practice of Public Key Cryptography, volume 6056 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Paris, France, May 26–28, 2010), pp. 279–295
23.
Zurück zum Zitat S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Berkeley, CA, USA, October 26–29, 2013), pp. 40–49 S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Berkeley, CA, USA, October 26–29, 2013), pp. 40–49
24.
Zurück zum Zitat S. Garg, C. Gentry, S. Halevi, D. Wichs, On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2014), pp. 518–535 S. Garg, C. Gentry, S. Halevi, D. Wichs, On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2014), pp. 518–535
25.
Zurück zum Zitat S. Garg, C. Gentry, A. Sahai, B. Waters, Witness encryption and its applications, in D. Boneh, T. Roughgarden, J. Feigenbaum, editors, 45th Annual ACM Symposium on Theory of Computing (ACM Press, Palo Alto, CA, USA, June 1–4, 2013), pp. 467–476 S. Garg, C. Gentry, A. Sahai, B. Waters, Witness encryption and its applications, in D. Boneh, T. Roughgarden, J. Feigenbaum, editors, 45th Annual ACM Symposium on Theory of Computing (ACM Press, Palo Alto, CA, USA, June 1–4, 2013), pp. 467–476
26.
Zurück zum Zitat S. Goldwasser, Y.T. Kalai, Cryptographic assumptions: a position paper, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 505–522 S. Goldwasser, Y.T. Kalai, Cryptographic assumptions: a position paper, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 505–522
27.
Zurück zum Zitat O. Goldreich, L.A. Levin, A hard-core predicate for all one-way functions, in 21st Annual ACM Symposium on Theory of Computing (ACM Press, Seattle, Washington, USA, May 15–17, 1989), pp. 25–32 O. Goldreich, L.A. Levin, A hard-core predicate for all one-way functions, in 21st Annual ACM Symposium on Theory of Computing (ACM Press, Seattle, Washington, USA, May 15–17, 1989), pp. 25–32
28.
Zurück zum Zitat O. Goldreich, Foundations of Cryptography: Basic Tools, vol. 1 (Cambridge University Press, Cambridge, UK, 2001)CrossRefMATH O. Goldreich, Foundations of Cryptography: Basic Tools, vol. 1 (Cambridge University Press, Cambridge, UK, 2001)CrossRefMATH
29.
Zurück zum Zitat C. Gentry, D. Wichs, Separating succinct non-interactive arguments from all falsifiable assumptions, in L. Fortnow, S.P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing (ACM Press, San Jose, California, USA, June 6–8, 2011), pp. 99–108 C. Gentry, D. Wichs, Separating succinct non-interactive arguments from all falsifiable assumptions, in L. Fortnow, S.P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing (ACM Press, San Jose, California, USA, June 6–8, 2011), pp. 99–108
31.
Zurück zum Zitat S. Hohenberger, A. Sahai, B. Waters, Replacing a random oracle: Full domain hash from indistinguishability obfuscation, in P.Q. Nguyen, E. Oswald, editors, Advances in Cryptology—-EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Copenhagen, Denmark, May 11–15, 2014), pp. 201–220 S. Hohenberger, A. Sahai, B. Waters, Replacing a random oracle: Full domain hash from indistinguishability obfuscation, in P.Q. Nguyen, E. Oswald, editors, Advances in Cryptology—-EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Copenhagen, Denmark, May 11–15, 2014), pp. 201–220
32.
Zurück zum Zitat R. Impagliazzo, L.A. Levin, M. Luby, Pseudo-random generation from one-way functions (extended abstracts), in 21st Annual ACM Symposium on Theory of Computing (ACM Press, Seattle, Washington, USA, May 15–17, 1989), pp. 12–24 R. Impagliazzo, L.A. Levin, M. Luby, Pseudo-random generation from one-way functions (extended abstracts), in 21st Annual ACM Symposium on Theory of Computing (ACM Press, Seattle, Washington, USA, May 15–17, 1989), pp. 12–24
33.
Zurück zum Zitat H. Krawczyk, T. Rabin, C. signatures, in ISOC Network and Distributed System Security Symposium—NDSS 2000 (The Internet Society, San Diego, California, USA, February 2–4, 2000) H. Krawczyk, T. Rabin, C. signatures, in ISOC Network and Distributed System Security Symposium—NDSS 2000 (The Internet Society, San Diego, California, USA, February 2–4, 2000)
34.
Zurück zum Zitat M. Naor, On cryptographic assumptions and challenges (invited talk), in D. Boneh, editor, Advances in Cryptology—CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2003), pp. 96–109 M. Naor, On cryptographic assumptions and challenges (invited talk), in D. Boneh, editor, Advances in Cryptology—CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 17–21, 2003), pp. 96–109
35.
Zurück zum Zitat M. Naor, G. Segev, Public-key cryptosystems resilient to key leakage, in S. Halevi, editor, Advances in Cryptology—CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 16–20, 2009), pp. 18–35 M. Naor, G. Segev, Public-key cryptosystems resilient to key leakage, in S. Halevi, editor, Advances in Cryptology—CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 16–20, 2009), pp. 18–35
36.
Zurück zum Zitat K. Pietrzak, A. Rosen, G. Segev, Lossy functions do not amplify well, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 458–475 K. Pietrzak, A. Rosen, G. Segev, Lossy functions do not amplify well, in R. Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Taormina, Sicily, Italy, March 19–21, 2012), pp. 458–475
37.
Zurück zum Zitat S. Patel, G.S. Sundaram, An efficient discrete log pseudo random generator, in H. Krawczyk, editor, Advances in Cryptology—CRYPTO’98, volume 1462 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 23–27, 1998), pp. 304–317 S. Patel, G.S. Sundaram, An efficient discrete log pseudo random generator, in H. Krawczyk, editor, Advances in Cryptology—CRYPTO’98, volume 1462 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 23–27, 1998), pp. 304–317
38.
Zurück zum Zitat C. Peikert, B. Waters, Lossy trapdoor functions and their applications, in R.E. Ladner, C. Dwork, editors, 40th Annual ACM Symposium on Theory of Computing (ACM Press, Victoria, British Columbia, Canada, May 17–20, 2008), pp. 187–196 C. Peikert, B. Waters, Lossy trapdoor functions and their applications, in R.E. Ladner, C. Dwork, editors, 40th Annual ACM Symposium on Theory of Computing (ACM Press, Victoria, British Columbia, Canada, May 17–20, 2008), pp. 187–196
40.
Zurück zum Zitat A. Rosen, G. Segev, Chosen-ciphertext security via correlated products, in O. Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, March 15–17, 2009), pp. 419–436 A. Rosen, G. Segev, Chosen-ciphertext security via correlated products, in O. Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, March 15–17, 2009), pp. 419–436
41.
Zurück zum Zitat D.R. Simon, Finding collisions on a one-way street: can secure hash functions be based on general assumptions? in K. Nyberg, editor, Advances in Cryptology—-EUROCRYPT’98, volume 1403 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Espoo, Finland, May 31 – June 4, 1998), pp. 334–345 D.R. Simon, Finding collisions on a one-way street: can secure hash functions be based on general assumptions? in K. Nyberg, editor, Advances in Cryptology—-EUROCRYPT’98, volume 1403 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Espoo, Finland, May 31 – June 4, 1998), pp. 334–345
42.
Zurück zum Zitat A.W. Schrift, A. Shamir, The discrete log is very discreet, in 22nd Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 14–16, 1990), pp. 405–415 A.W. Schrift, A. Shamir, The discrete log is very discreet, in 22nd Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 14–16, 1990), pp. 405–415
43.
Zurück zum Zitat A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in D.B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing (ACM Press, New York, NY, USA, May 31–June 3, 2014), pp. 475–484 A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in D.B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing (ACM Press, New York, NY, USA, May 31–June 3, 2014), pp. 475–484
44.
Zurück zum Zitat J.L. Villar, Optimal reductions of some decisional problems to the rank problem, in X. Wang, K. Sako, editors, Advances in Cryptology—ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Beijing, China, December 2–6, 2012), pp. 80–97 J.L. Villar, Optimal reductions of some decisional problems to the rank problem, in X. Wang, K. Sako, editors, Advances in Cryptology—ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Beijing, China, December 2–6, 2012), pp. 80–97
45.
Zurück zum Zitat H. Wee, On obfuscating point functions, in H.N. Gabow, R. Fagin, editors, 37th Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 22–24, 2005), pp. 523–532 H. Wee, On obfuscating point functions, in H.N. Gabow, R. Fagin, editors, 37th Annual ACM Symposium on Theory of Computing (ACM Press, Baltimore, Maryland, USA, May 22–24, 2005), pp. 523–532
46.
Zurück zum Zitat A. Young, M. Yung, Kleptography: using cryptography against cryptography, in W. Fumy, editor, Advances in Cryptology—EUROCRYPT’97, volume 1233 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Konstanz, Germany, May 11–15, 1997), pp. 62–74 A. Young, M. Yung, Kleptography: using cryptography against cryptography, in W. Fumy, editor, Advances in Cryptology—EUROCRYPT’97, volume 1233 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Konstanz, Germany, May 11–15, 1997), pp. 62–74
47.
Zurück zum Zitat M. Zhandry, How to construct quantum random functions, in 53rd Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, New Brunswick, NJ, USA, October 20–23, 2012), pp. 679–687 M. Zhandry, How to construct quantum random functions, in 53rd Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, New Brunswick, NJ, USA, October 20–23, 2012), pp. 679–687
48.
Zurück zum Zitat M. Zhandry, How to avoid obfuscation using witness PRFs, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part II, volume 9563 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 421–448 M. Zhandry, How to avoid obfuscation using witness PRFs, in E. Kushilevitz, T. Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part II, volume 9563 of Lecture Notes in Computer Science (Springer, Heidelberg, Germany, Tel Aviv, Israel, January 10–13, 2016), pp. 421–448
Metadaten
Titel
The Magic of ELFs
verfasst von
Mark Zhandry
Publikationsdatum
22.03.2018
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 3/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-018-9289-9

Weitere Artikel der Ausgabe 3/2019

Journal of Cryptology 3/2019 Zur Ausgabe