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:
Secure Computation Based on Leaky Correlations: High Resilience Setting Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

From Obfuscation to the Security of Fiat-Shamir for Proofs

verfasst von : Yael Tauman Kalai, Guy N. Rothblum, Ron D. Rothblum

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

The Fiat-Shamir paradigm [CRYPTO’86] is a heuristic for converting three-round identification schemes into signature schemes, and more generally, for collapsing rounds in constant-round public-coin interactive protocols. This heuristic is very popular both in theory and in practice, and its security has been the focus of extensive study.
In particular, this paradigm was shown to be secure in the Random Oracle Model. However, in the plain model, the results shown were mostly negative. In particular, the heuristic was shown to be insecure when applied to computationally sound proofs (also known as arguments). Moreover, recently it was shown that even in the restricted setting where the heuristic is applied to interactive proofs (as opposed to arguments), its soundness cannot be proven via a black-box reduction to any so-called falsifiable assumption.
In this work, we give a positive result for the security of this paradigm in the plain model. Specifically, we construct a hash function for which the Fiat Shamir paradigm is secure when applied to proofs (as opposed to arguments), assuming the existence of a sub-exponentially secure indistinguishability obfuscator, the existence of an exponentially secure input-hiding obfuscator for the class of multi-bit point functions, and the existence of a sub-exponentially secure one-way function.
More generally, we construct a hash family that is correlation intractable (under the computational assumptions above), solving an open problem originally posed by Canetti, Goldreich and Halevi (JACM, 2004), under the above assumptions.
In addition, we show that our result resolves a long-lasting open problem in about zero-knowledge proofs: It implies that there does not exist a public-coin constant-round zero-knowledge proof with negligible soundness (under the assumptions stated above).

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 Incremental Program Obfuscation
Nächstes Kapitel Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization
Fußnoten
1
We note that the work of [GK03] is a followup work to [Bar01], and builds upon its techniques.
 
2
Loosely speaking, a hash family \(\{h_s\}\) is said to have this security property if for every probabilistic polynomial time adversary \(\mathcal{A}\), that is given a random seed s and outputs an element in the domain of \(h_s\), the random variable \(h_s(\mathcal{A}(s))\) conditioned on \(\mathcal{A}(s)\) has almost full min entropy.
 
3
The formalization of a falsifiable assumption, given in [BDG+13], is similar to the formalization given in [GW11], and differs slightly from the formalization given in [Nao03].
 
4
Our assumptions (see Sect. 1.1), which deal with exponential-time (rather than polynomial-time) adversaries, are inherently not falsifiable. Note that [BDG+13] allow an unbounded challenger, but restrict to polynomial-time attackers. In the context of obfuscation, the attacker is the algorithm trying to break the security of the obfuscation. We assume hardness against super polynomial-time attackers, and thus our assumptions do not fall into the category ruled out by Bitansky et al.
 
5
This assumption has been made in many previous works on \(\mathsf{iO}\) and is referred to as sub-exponential \(\mathsf{iO}\), since the security parameter can be polynomially larger than n (which makes \(2^n\) sub-exponential in the security parameter).
 
6
While DDH (and even discrete log) can be broken in time less than \(2^n\) (even in the generic group model - e.g., by the baby-step giant-step algorithm), this does not imply a non-trivial polynomial-time attack (i.e., one with success probability greater than \(\text {poly}(n)/2^n\)).
 
7
We note that this is how Barak [Bar01] obtained his negative result. He constructed a constant-round public-coin zero-knowledge argument.
 
8
Indeed, for the class of protocols that [MV16] support, reducing to 2 rounds while preserving soundness (but not necessarily zero-knowledge) is straightforward: Since the prover’s first message is not a function of the input, the verifier can compute the prover’s first message \(\alpha \) for it, and sends \(\alpha \) (together with the coins used to generate it) to the prover.
 
9
The Fiat Shamir paradigm refers to constant round protocols. Indeed, there are interactive proofs with a super-constant number of rounds (and negligible soundness error) for which the Fiat Shamir paradigm is insecure.
 
10
More specifically, the insecurity is in the sense that there exist contrived interactive arguments such that for any hash family \(\mathcal{H}\), applying the Fiat-Shamir paradigm with the hash family \(\mathcal{H}\), results in an insecure 2-round protocol [Bar01, GK03].
 
11
We use \((s\{\alpha \},\alpha ,f_s(\alpha ))\) to denote the circuit that on input \(\alpha \) outputs the hardwired value \(f_s(\alpha )\), and on any other input \(x\ne \alpha \) computes \(f_s(x)\) using the punctured seed \(s\{\alpha \}\).
 
12
We think of n as polynomially related to the security parameter, where \(2^n\) is the domain size of \(f_s\).
 
13
The fact that subexponential OWF yield PRFs for which distinguishing the entire truth table from a random truth table the truth table of a random function has been previously noted in the literature, most notably by Razborov and Rudich [RR97] in their work on natural proofs.
 
14
We remark that the reason we bound the input length is solely because we use a simplified definition of argument system that does not have a security parameter, and we are aiming for argument systems with soundness that is negligible in the input length.
 
15
Since parallel repetition decreases the soundness error of interactive proofs at an exponential rate, we may assume without loss of generality that the soundness error is negligible in n.
 
16
For 4-message proofs, the same paradigm as in Fig. 1 is used, except that the verifier also sends its first message from the base proof-system (i.e., a random string) in the first round.
 
17
In the original protocol \(\varPi \), it may be the case that different messages \(\alpha \) sent by the prover can lead the verifier to accept with different probabilities. E.g., some specific \(\alpha \)’s may lead the verifier to accept with probability \(\mu \) and others with probability 0. This presents a technical difficulty later in the proof and so we construct the relaxed verifier \(V'\) so that every string \(\alpha \) leads it to accept with roughly the same probability (up to a small multiplicative constant) without increasing the soundness error by too much.
 
18
It may at first seem odd that we only use the soundness of the underlying proof-system with respect to a cheating prover that just sends a random message \(\alpha ^*\). Recall however that here we consider the relaxed verifier who, by design, has a (roughly) similar acceptance probability given any string \(\alpha \).
 
Literatur
[AABN02]
Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From identification to signatures via the fiat-shamir transform: minimizing assumptions for security and forward-security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 418–433. Springer, Heidelberg (2002). doi:10.​1007/​3-540-46035-7_​28 CrossRef
[Bar01]
Barak, B.: How to go beyond the black-box simulation barrier. In: FOCS, pp. 106–115 (2001)
[BBC+14]
Barak, B., Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O., Sahai, A.: Obfuscation for evasive functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 26–51. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​2 CrossRef
[BC14]
[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. LNCS, vol. 8617, pp. 71–89. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44381-1_​5 CrossRef
[BDG+13]
Bitansky, N., Dachman-Soled, D., Garg, S., Jain, A., Kalai, Y.T., López-Alt, A., Wichs, D.: Why “Fiat-Shamir for Proofs” lacks a proof. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 182–201. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-36594-2_​11 CrossRef
[BDNP08]
Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: ACM Conference on Computer and Communications Security, pp. 257–266 (2008)
[BGGL01]
Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zero-knowledge and its applications. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 116–125 (2001)
[BGI+12]
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNetCrossRefMATH
[BGI14]
[BGL+15]
Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14–17, 2015, pp. 439–448 (2015)
[BIN97]
Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19–22, 1997, pp. 374–383 (1997)
[BL04]
[Blu87]
Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, pp. 1444–1451 (1987)
[BLV06]
Barak, B., Lindell, Y., Vadhan, S.P.: Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72(2), 321–391 (2006)MathSciNetCrossRefMATH
[BM14]
Brzuska, C., Mittelbach, A.: Indistinguishability obfuscation versus multi-bit point obfuscation with auxiliary input. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 142–161. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​8
[BR93]
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
[BS16]
Bellare, M., Stepanovs, I.: Point-function obfuscation: a framework and generic constructions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 565–594. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​21 CrossRef
[BW13]
[Can97]
Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997). doi:10.​1007/​BFb0052255 CrossRef
[CCR15]
Canetti, R., Chen, Y., Reyzin, L.: On the correlation intractability of obfuscated pseudorandom functions. IACR Cryptology ePrint Archive, 2015:334 (2015)
[CD08]
[CGH04]
[CKPR02]
Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds. SIAM J. Comput. 32(1), 1–47 (2002)MathSciNetCrossRefMATH
[DNRS99]
Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. In: FOCS, pp. 523–534 (1999)
[DRV12]
Dodis, Y., Ristenpart, T., Vadhan, S.: Randomness condensers for efficiently samplable, seed-dependent sources. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 618–635. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-28914-9_​35 CrossRef
[FS86]
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). doi:10.​1007/​3-540-47721-7_​12 CrossRef
[GGH+13]
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]
[GK96]
[GK03]
Goldwasser, S., Kalai, Y.T.: On the (in)security of the fiat-shamir paradigm. In: FOCS, pp. 102–113 (2003)
[GK05]
Goldwasser, S., Kalai, Y.T.: On the impossibility of obfuscation with auxiliary input. In: FOCS, pp. 553–562 (2005)
[GK16]
[GLSW14]
Gentry, C., Lewko, A.B., Sahai, A., Waters, B.: Indistinguishability obfuscation from the multilinear subgroup elimination assumption. IACR Cryptology ePrint Archive 2014:309 (2014)
[GMR89]
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH
[GO94]
[GW11]
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC, pp. 99–108 (2011)
[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
[HT98]
Hada, S., Tanaka, T.: On the existence of 3-round zero-knowledge protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 408–423. Springer, Heidelberg (1998). doi:10.​1007/​BFb0055744 CrossRef
[KPR98]
Kilian, J., Petrank, E., Rackoff, C.: Lower bounds for zero knowledge on the internet. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, November 8–11, 1998, Palo Alto, California, USA, pp. 484–492 (1998)
[KPTZ13]
Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM CCS, pp. 669–684 (2013)
[Mic94]
Micali, S.: CS proofs. In: FOCS, pp. 436–453 (1994)
[MNPS04]
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: USENIX Security Symposium, pp. 287–302 (2004)
[MV16]
Mittelbach, A., Venturi, D.: Fiat–shamir for highly sound protocols is instantiable. In: Zikas, V., Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 198–215. Springer, Cham (2016). doi:10.​1007/​978-3-319-44618-9_​11
[Nao03]
[OO98]
Ohta, K., Okamoto, T.: On concrete security treatment of signatures derived from identification. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 354–369. Springer, Heidelberg (1998). doi:10.​1007/​BFb0055741 CrossRef
[PS96]
[Rey01]
Reyzin, L.: Zero-Knowledge with Public Keys. Ph.D. thesis, MIT (2001)
[Ros00]
[RR97]
[RRR16]
Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–21, 2016, pp. 49–62 (2016)
[SW14]
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014)
Metadaten
Titel
From Obfuscation to the Security of Fiat-Shamir for Proofs
verfasst von
Yael Tauman Kalai
Guy N. Rothblum
Ron D. Rothblum
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63714-3

Electronic ISBN: 978-3-319-63715-0

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63715-0_8