nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Perfect Structure on the Edge of Chaos

Trapdoor Permutations from Indistinguishability Obfuscation

verfasst von : Nir Bitansky, Omer Paneth, Daniel Wichs

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring.

Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class \(\text{ SZK } \) — indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might.

As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation.

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 Multilinear Maps from Obfuscation

Nächstes Kapitel Cryptographic Assumptions: A Position Paper

Nur mit Berechtigung zugänglich

See Appendix A for more details on the construction of non-interactive commitments.

Formally, [KLW14] rely on injective \(\text{ PRG } \)s, but these can be replaced with injective one-way functions using an observation of [BCP14], as explained in Sect. 4.2.

[AB15]

Applebaum, B., Brakerski, Z.: Obfuscating circuits via composite-order graded encoding. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 528–556. Springer, Heidelberg (2015) CrossRef

[AC08]

Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25–28, 2008, Philadelphia, PA, USA, pp. 793–802 (2008)

[AJ15]

Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: Crypto (2015)

[BCC+14]

Bitansky, N., Canetti, R., Cohn, H., Goldwasser, S., Kalai, Y.T., Paneth, O., Rosen, A.: The impossibility of obfuscation with auxiliary input or a universal simulator. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 71–89. Springer, Heidelberg (2014) CrossRef

[BCP14]

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) CrossRef

[BFKL93]

Blum, A., Furst, M.L., Kearns, M., Lipton, R.J.: Cryptographic primitives bon hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1993)

[BGI+01]

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001) CrossRef

[BGI14]

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014) CrossRef

[BGK+13]

Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Cryptology ePrint Archive, Report 2013/631 (2013). http://eprint.iacr.org/

[Blu81]

Blum, M.: Coin flipping by telephone. In: Proceedings of the 18th Annual International Cryptology Conference, pp. 11–15 (1981)

[BP14]

Bitansky, N., Paneth, O.: Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Cryptology ePrint Archive, Report 2014/295 (2014). http://eprint.iacr.org/

[BPR15]

Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a nash equilibrium. In: FOCS (2015)

[BR14]

Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 1–25. Springer, Heidelberg (2014) CrossRef

[BV15]

Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: FOCS (2015)

[BW13]

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013) CrossRef

[CLT13]

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013) CrossRef

[CLT15]

Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Crypto (2015)

[CLTV14]

Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: Cryptology ePrint Archive, Report 2014/882 (2014). http://eprint.iacr.org/

[DPW14]

Dodis, Y., Pietrzak, K., Wichs, D.: Key derivation without entropy waste. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 93–110. Springer, Heidelberg (2014) CrossRef

[Gen14]

Craig Gentry. Computing on the edge of chaos: Structure and randomness in encrypted computation. Electronic Colloquium on Computational Complexity (ECCC), 21:106, 2014

[GGH13a]

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013) CrossRef

[GGH+13b]

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October, 2013, Berkeley, CA, USA, pp. 40–49 (2013)

[GGM86]

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)MathSciNetCrossRefMATH

[GK88]

Goldreich, O., Kushilevitz, E.: A perfect zero-knowledge proof for a problem equivalent to discrete logarithm. In: Proceedings of Advances in Cryptology - CRYPTO 1988, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21–27, 1988, pp. 57–70 (1988)

[GLSW14]

Gentry, C., Lewko, A.B., Sahai, A., Waters, B.: Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In: IACR Cryptology ePrint Archive 2014, p. 309 (2014)

[Gol11]

Goldreich, O.: Candidate one-way functions based on expander graphs. In: Goldreich, O., et al. (eds.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 76–87. Springer, Heidelberg (2011)

[GR13]

Goldreich, O., Rothblum, R.D.: Enhancements of trapdoor permutations. J. Cryptol. 26(3), 484–512 (2013)MathSciNetCrossRefMATH

[HILL99]

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRefMATH

[JP00]

Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Crypt. 20(3), 269–280 (2000)MathSciNetCrossRefMATH

[KLW14]

Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: Cryptology ePrint Archive, Report 2014/925 (2014). http://eprint.iacr.org/

[KMN+14]

Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: IACR Cryptology ePrint Archive 2014, p. 347 (2014)

[KPTZ13]

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM Conference on Computer and Communications Security, pp. 669–684 (2013)

[Nao91]

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991)MathSciNetCrossRefMATH

[NR02]

Naor, M., Reingold, O.: Constructing pseudo-random permutations with a prescribed structure. J. Cryptol. 15(2), 97–102 (2002)MathSciNetCrossRefMATH

[PW08]

Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17–20, 2008, pp. 187–196 (2008)

[Rab79]

Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. Technical report LCR/TR-212, MIT Laboratory of Computer Science (1979)

[RSA83]

Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems (reprint). Commun. ACM 26(1), 96–99 (1983)CrossRefMATH

[Sho97]

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH

[SW14]

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, May 31 – June 03, 2014, New York, NY, USA, pp. 475–484 (2014)

[Yao82]

Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, 3–5 November 1982, Chicago, Illinois, USA, pp. 80–91 (1982)

[Zim15]

Zimmerman, J.: How to obfuscate programs directly. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 439–467. Springer, Heidelberg (2015)

Titel: Perfect Structure on the Edge of Chaos
verfasst von: Nir Bitansky
Omer Paneth
Daniel Wichs
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-49095-2

Electronic ISBN: 978-3-662-49096-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49096-9_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"