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:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Structure vs. Hardness Through the Obfuscation Lens

verfasst von : Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low complexity classes such as \({\textsf {NP}} \cap {\textsf {coNP}}\) or statistical zero-knowledge (SZK).
Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes—they imply hard problems in \({\textsf {NP}} \cap {\textsf {coNP}}\) and \({\textsf {SZK}}\), respectively. In contrast, one-way functions do not imply such hard problems, at least not by fully black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer.
We show that the above primitives, and many others, do not imply hard problems in \({\textsf {NP}} \cap {\textsf {coNP}}\) or \({\textsf {SZK}}\) via fully black-box reductions. In fact, we first show that even the very powerful notion of Indistinguishability Obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO.

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 Lower Bounds on Obfuscation from All-or-Nothing Encryption Primitives
Nächstes Kapitel Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations
Fußnoten
1
More accurately, these primitives follow from IO and OWFs (OWFs), and accordingly our separation addresses IO and OWFs in conjunction. The concept of a black-box reduction from IO and OWF requires clarification and discussion. Here we will follow the framework of Asharov and Segev [AS15]. We elaborate below.
 
2
Roughly speaking, [BI87] rule out perfectly correct constructions, where the \({\textsf {NP}} \cap {\textsf {coNP}}\) structure is guaranteed for any implementation of the OWF oracle. In [Rud88], this is generalized also to almost perfectly correct constructions that only work for an overwhelming fraction of OWF oracles. We also rule out constructions that are perfectly correct.
 
3
We note that previous work [Ost91, OV08] does imply that constant-round statistically-hiding commitments have a black-box reduction to any hard-on-average \({\textsf {SZK}}\) problem. However, [AS15] do not rule these out (but only collision-resistant hashing). We also note that in any case, our result also rules out constructions of worst-case hard \({\textsf {SZK}}\) problems (rather than average-case hard problems).
 
4
We note that in concurrent and independent work, Rosen et al. [RSS16] show that one-way functions do not have black-box reductions to \({\textsf {PPAD}}\)-hardness, which combined with [Ost91], also yields a separation between SZK and \({\textsf {PPAD}}\).
 
5
Rudich [Rud88] also considered a slight relaxation of constructions that are correct for an overwhelming fraction of oracles rather than all.
 
6
We note that this issue does not come up for black-box constructions of \({\textsf {SZK}}\) promise problems, because the construction is allowed to yield instances that do not obey the promise; there correctness is always guaranteed, and the only question is whether the instances that do satisfy the promise are hard to decide.
 
7
E.g. the language of all valid obfuscations and indices i, such that the ith bit of the obfuscated circuit is 1.
 
8
More accurately, this is the case for Rudich’s result for \({\textsf {NP}} \cap {\textsf {coNP}}\), whereas for the other results that rule out constructions of one-way permutations, one can simulate an analog of \(\mathsf {Decide}\) that inverts the permutation.
 
9
In the body, we describe a slightly more abstract construction where inner product is replaced by an arbitrary 2-universal hash function.
 
10
Similar \({\textsf {SZK}}\)-hardness is known to imply statistically-hiding commitments against malicious receivers, but with a larger (constant) number of rounds [OV08].
 
11
Rudich [Rud88] also considered a slight relaxation of constructions that are correct for an overwhelming fraction of oracles rather than all.
 
12
Similar \({\textsf {SZK}}\)-hardness is known to imply statistically-hiding commitments against malicious receivers, but with a larger (constant) number of rounds [OV08].
 
Literatur
[ABW10]
Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Proceedings of 42nd ACM Symposium on Theory of Computing, STOC 2010, USA, 5–8 June 2010, Cambridge, Massachusetts, pp. 171–180 (2010)
[AGGM06]
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Kleinberg [Kle06], pp. 701–710 (2006)
[AH91]
Aiello, W., Hastad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42(3), 327–345 (1991)MathSciNetCrossRefMATH
[Ale03]
Alekhnovich, M., More on average case vs approximation complexity. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11–14 October 2003, Cambridge, MA, USA, Proceedings [DBL03], pp. 298–307 (2003)
[AR04]
Aharonov, D., Regev, O.: Lattice problems in NP cap coNP. In: 45th Symposium on Foundations of Computer Science (FOCS 2004), 17–19 October 2004, Rome, Italy, Proceedings, pp. 362–371. IEEE Computer Society (2004)
[AR16]
Applebaum, B., Raykov, P.: From private simultaneous messages to zero-information arthur-merlin protocols and back. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 65–82. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​3 CrossRef
[AS15]
Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. In: Symposium on the Foundations of Computer Science (2015)
[AS16]
Asharov, G., Segev, G.: On constructing one-way permutations from indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 512–541. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​19 CrossRef
[Bar13]
[BB15]
Bogdanov, A., Brzuska, C.: On basing size-verifiable one-way functions on NP-hardness. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 1–6. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46494-6_​1
[BBF13]
[BGI+01]
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
[BGL+15]
Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: Symposium on Theory of Computing, STOC 2015 (2015)
[BHZ87]
[BI87]
Blum, M., Impagliazzo, R.: Generic oracles and oracle classes. In: Proceedings of 28th Annual Symposium on Foundations of Computer Science, SFCS 1987, pp. 118–126. IEEE Computer Society, Washington (1987)
[BKSY11]
Brakerski, Z., Katz, J., Segev, G., Yerukhimovich, A.: Limits on the power of zero-knowledge proofs in cryptographic constructions. In: Ishai [Ish11], pp. 559–578 (2011)
[BL13]
Bogdanov, A., Lee, C.H.: Limits of provable security for homomorphic encryption. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 111–128. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40041-4_​7 CrossRef
[BM09]
Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal—an O(n 2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374–390. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-03356-8_​22 CrossRef
[BP15]
Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 401–427. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​16 CrossRef
[BPR15]
NBitansky, ., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a nash equilibrium. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, 17–20 October 2015, Berkeley, CA, USA, pp. 1480–1498. IEEE Computer Society (2015)
[BPW16]
[Bra79]
Brassard, G.: Relativized cryptography. In: 20th Annual Symposium on Foundations of Computer Science, 29–31 October 1979, San Juan, Puerto Rico, pp. 383–391. IEEE Computer Society (1979)
[BT03]
Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11–14 October 2003, Cambridge, MA, USA, Proceedings [DBL03], pp. 308–317 (2003)
[BV11]
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) FOCS, pp. 97–106. IEEE (2011). (Invited to SIAM Journal on Computing)
[CDT09]
[CHJV15]
Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: Proceedings of 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, 14–17 June 2015, Portland, OR, USA, pp. 429–437 (2015)
[CLTV15]
Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 468–497. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​19 CrossRef
[Cra12]
Cramer, R. (ed.): Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, 19–21 March 2012, Taormina, Sicily, Italy, Proceedings. LNCS vol. 7194. Springer, Heidelberg (2012)
[DBL00]
Prceedings of 41st Annual Symposium on Foundations of Computer Science, FOCS 2000: 12–14 November 2000. IEEE Computer Society, Redondo Beach (2000)
[DBL03]
Prceedings of 44th Symposium on Foundations of Computer Science (FOCS 2003: 11–14 October 2003. IEEE Computer Society, Cambridge (2003)
[DGP06]
Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. In: Kleinberg [Kle06], pp. 71–78 (2006)
[DH76]
[DHT12]
Dodis, Y., Haitner, I., Tentes, A.: On the instantiability of hash-and-sign RSA signatures. In: Cramer [Cra12], pp. 112–132 (2012)
[DLMM11]
Dachman-Soled, D., Lindell, Y., Mahmoody, M., Malkin, T.: On the black-box complexity of optimally-fair coin tossing. In: Ishai [Ish11], pp. 450–467 (2011)
[ESY84]
Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Inf. Control 61(2), 159–173 (1984)MathSciNetCrossRefMATH
[Fis12]
[For89]
Fortnow, L.J.: Complexity-theoretic aspects of interactive proof systems. Ph.D. thesis, Massachusetts Institute of Technology (1989)
[Gen09]
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178 (2009)
[GG98]
Goldreich, O., Goldwasser, S.: On the possibility of basing cryptography on the assumption that \(p \ne NP\). IACR Cryptology ePrint Archive, 1998:5 (1998)
[GGH+13a]
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. IEEE Computer Society (2013)
[GGH+13b]
Garg, S., Gentry, C., Halevi, S., Sahai, A., Raikova, M., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS (2013)
[GGKT05]
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)MathSciNetCrossRefMATH
[GK93]
Goldreich, O., Kushilevitz, E.: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. J. Cryptol. 6(2), 97–116 (1993)MathSciNetCrossRefMATH
[GKLM12]
Goyal, V., Kumar, V., Lokam, S.V., Mahmoody, M.: On black-box reductions between predicate encryption schemes. In: Cramer [Cra12], pp. 440–457 (2012)
[GKM+00]
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12–14 November 2000, Redondo Beach, California, USA [DBL00], pp. 325–335 (2000)
[GM82]
Goldwasser, S., Micali, S.: Probabilistic encryption and how to play mental poker keeping secret all partial information. In: Lewis, H.R., Simons, B.B., Burkhard, W.A., Landweber, L.H. (eds.) Proceedings of 14th Annual ACM Symposium on Theory of Computing, 5–7 May 1982, San Francisco, California, USA, pp. 365–377. ACM (1982)
[GMM07]
Gertner, Y., Malkin, T., Myers, S.: Towards a separation of semantic and CCA security for public key encryption. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 434–455. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-70936-7_​24 CrossRef
[GMR85]
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: Sedgewick, R. (ed.) Proceedings of 17th Annual ACM Symposium on Theory of Computing, 6–8 May 1985, Providence, Rhode Island, USA, pp. 291–304. ACM (1985)
[GMR01]
Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 126–135. IEEE Computer Society (2001)
[GMW91]
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)MathSciNetCrossRefMATH
[Gol06]
Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006). doi:10.​1007/​11685654_​12 CrossRef
[GT00]
Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12–14 November 2000, Redondo Beach, California, USA [DBL00], pp. 305–313 (2000)
[GV99]
Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In: Proceedings of 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, 4–6 May 1999, p. 54 (1999)
[Has88]
Hastad, J.: Dual vectors and lower bounds for the nearest lattice point problem. Combinatorica 8(1), 75–81 (1988)MathSciNetCrossRef
[HH09]
[HHRS15]
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols—tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193–242 (2015)MathSciNetCrossRefMATH
[HMX10]
Haitner, I., Mahmoody, M., Xiao, D.: A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP. In: 2010 IEEE 25th Annual Conference on Computational Complexity (CCC), pp. 76–87. IEEE (2010)
[HR04]
Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 92–105. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-28628-8_​6 CrossRef
[IKO05]
[IR89]
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of 21st Annual ACM Symposium on Theory of Computing, pp. 44–61. ACM (1989)
[Ish11]
Ishai, Y. (ed.): Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA. LNCS, 28–30 March 2011. Proceedings, vol. 6597. Springer, Heidelberg (2011)
[Kle06]
Kleinberg, J.M. (ed.): Proceedings of 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 21–23 May 2006. ACM (2006)
[KLW15]
Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: Proceedings of 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, 14–17 June 2015, Portland, OR, USA, pp. 419–428 (2015)
[KMN+14]
Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, 18–21 October 2014, Philadelphia, PA, USA, pp. 374–383. IEEE Computer Society (2014)
[KSS11]
Kahn, J., Saks, M.E., Smyth, C.D.: The dual BKR inequality and rudich’s conjecture. Comb. Probab. Comput. 20(2), 257–266 (2011)MathSciNetCrossRefMATH
[KST99]
Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17–18 October 1999, New York, NY, USA, pp. 535–542. IEEE Computer Society (1999)
[LLJS90]
Lagarias, J.C., Lenstra Jr., H.W., Schnorr, C.-P.: Korkin-zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10(4), 333–348 (1990)MathSciNetCrossRefMATH
[LV16]
Liu, T., Vaikuntanathan, V.: On basing private information retrieval on NP-hardness. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 372–386. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49096-9_​16 CrossRef
[MM11]
[MP91]
Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81(2), 317–324 (1991)MathSciNetCrossRefMATH
[MV03]
Micciancio, D., Vadhan, S.P.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282–298. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-45146-4_​17 CrossRef
[MX10]
Mahmoody, M., Xiao, D.: On the power of randomized reductions and the checkability of sat. In: 2010 IEEE 25th Annual Conference on Computational Complexity (CCC), pp. 64–75. IEEE (2010)
[Ost91]
Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of 6th Annual Structure in Complexity Theory Conference, pp. 133–138. IEEE (1991)
[OV08]
[Pap94]
Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498–532 (1994)MathSciNetCrossRefMATH
[Pas06]
Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness. In: 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16–20 July 2006, Prague, Czech Republic, pp. 96–110. IEEE Computer Society (2006)
[Pas13]
[RAD78]
Rivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–177. Academic Press (1978)
[RSA78]
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
[RSS16]
Rosen, A., Segev, G., Shahaf, I.: Can PPAD hardness be based on standard cryptographic assumptions? In: Electronic Colloquium on Computational Complexity (ECCC), vol. 23, p. 59 (2016)
[RTV04]
[Rud88]
Rudich, S.: Limits on the provable consequences of one-way functions. Ph.D. thesis, University of California, Berkeley (1988)
[Rud91]
Rudich, S.: The use of interaction in public cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 242–251. Springer, Heidelberg (1992). doi:10.​1007/​3-540-46766-1_​19
[Sim98]
Simon, D.R.: Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998). doi:10.​1007/​BFb0054137
[SV03]
[SW14]
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May–03 June 2014, pp. 475–484. ACM (2014)
[Vad99]
Vadhan, S.P.: A study of statistical zero-knowledge proofs. Ph.D. thesis, Massachusetts Institute of Technology (1999)
[Wat15]
Waters, B.: A punctured programming approach to adaptively secure functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 678–697. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48000-7_​33 CrossRef
Metadaten
Titel
Structure vs. Hardness Through the Obfuscation Lens
verfasst von
Nir Bitansky
Akshay Degwekar
Vinod Vaikuntanathan
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_23