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:
Delegating RAM Computations with Adaptive Soundness and Privacy Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Interactive Oracle Proofs

verfasst von : Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We initiate the study of a proof system model that naturally combines interactive proofs (IPs) and probabilistically-checkable proofs (PCPs), and generalizes interactive PCPs (which consist of a PCP followed by an IP). We define an interactive oracle proof (IOP) to be an interactive proof in which the verifier is not required to read the prover’s messages in their entirety; rather, the verifier has oracle access to the prover’s messages, and may probabilistically query them. IOPs retain the expressiveness of PCPs, capturing NEXP rather than only PSPACE, and also the flexibility of IPs, allowing multiple rounds of communication with the prover. IOPs have already found several applications, including unconditional zero knowledge [BCGV16], constant-rate constant-query probabilistic checking [BCG+16], and doubly-efficient constant-round IPs for polynomial-time bounded-space computations [RRR16].
We offer two main technical contributions. First, we give a compiler that maps any public-coin IOP into a non-interactive proof in the random oracle model. We prove that the soundness of the resulting proof is tightly characterized by the soundness of the IOP against state restoration attacks, a class of rewinding attacks on the IOP verifier that is reminiscent of, but incomparable to, resetting attacks.
Second, we study the notion of state-restoration soundness of an IOP: we prove tight upper and lower bounds in terms of the IOP’s (standard) soundness and round complexity; and describe a simple adversarial strategy that is optimal, in expectation, across all state restoration attacks.
Our compiler can be viewed as a generalization of the Fiat–Shamir paradigm for public-coin IPs (CRYPTO ’86), and of the “CS proof” constructions of Micali (FOCS ’94) and Valiant (TCC ’08) for PCPs. Our analysis of the compiler gives, in particular, a unified understanding of these constructions, and also motivates the study of state restoration attacks, not only for IOPs, but also for IPs and PCPs.
When applied to known IOP constructions, our compiler implies, e.g., blackbox unconditional ZK proofs in the random oracle model with quasilinear prover and polylogarithmic verifier, improving on a result of [IMSX15].

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 Delegating RAM Computations with Adaptive Soundness and Privacy
Nächstes Kapitel Adaptive Succinct Garbled RAM or: How to Delegate Your Database
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
We do not study the question of avoiding assuming random oracles: this is not our focus. Reducing assumptions when compiling constant-round IPs is the subject of much research, obtaining arguments with non-programmable random oracles and a common random string [Lin15, CPSV16], obfuscation [KRR16, MV16], and others. Extending such ideas to IOPs is an interesting direction.
 
2
Independent of our work, [RRR16] introduce Probabilistically Checkable Interactive Proofs, which are equivalent to our IOPs.
 
3
Security in the random oracle model sometimes does not imply security when the oracle is substituted with a hash function, e.g., when applying the Fiat–Shamir paradigm to zero-knowledge proofs/arguments [HT98, DNRS03, GOSV14]. However, our transformation \(T\) only assumes that the \(\mathrm{IOP}\) is zero knowledge against the honest verifier, seemingly avoiding the above limitations.
 
4
We note that [BGGL01] prove an analogous upper bound for the incomparable notion of resettable soundness (see Remark 2). Also, [BD16] prove an analogous, weaker upper bound on the related notion of backtracking soundness (see Remark 2). Neither of the two studies lower bounds, or tightness of bounds.
 
5
Proof of knowledge \(e\) implies soundness \(s:= e\). The definition that we use is equivalent to the one in [BG93, Section 6] except that: (a) we use extractors that run in strict, rather than expected, probabilistic polynomial time; and (b) we extend the condition to hold for all https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53644-5_2/432825_1_En_2_IEq549_HTML.gif , rather than for only those in \(\mathscr {L}(\mathscr {R})\), so that proof of knowledge implies soundness.
 
6
More precisely, we apply Lemma 1 to an algorithm \(\tilde{\mathbb {P}}\) that does not itself output https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53644-5_2/432825_1_En_2_IEq987_HTML.gif but this does not affect the lemma’s validity because we can substitute into the definition of the event \(E_{1}\) the fixed instance https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53644-5_2/432825_1_En_2_IEq989_HTML.gif .
 
7
Note that \(A\)’s output may contain additional information not of the above form; if so, we simply ignore it for now.
 
Literatur
[ALM+92]
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems (1992)
[ALM+98]
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. JACM 45(3), 501–555 (1998)MathSciNetCrossRefMATH
[AS98]
[Bab85]
Babai, L.: Trading group theory for randomness. In: STOC 1985 (1985)
[Bab90]
Babai, L.: E-mail and the unexpected power of interaction. Technical report, University of Chicago, Chicago, IL, USA (1990)
[BBP04]
Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24676-3_​11 CrossRef
[BC86]
Brassard, G., Crépeau, C.: Non-transitive transfer of confidence: a perfect zero-knowledge interactive protocol for SAT and beyond. In: FOCS 1986 (1986)
[BCC88]
[BCG+16]
Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Short interactive oracle proofs with constant query complexity, via composition and sumcheck (2016). Crypto ePrint 2016/324
[BCGV16]
Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasilinear-size zero knowledge from linear-algebraic PCPs. In: TCC 2016-A (2016)
[BCI+13]
Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: TCC 2013 (2013)
[BCS16]
Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs, 2016. Crypto ePrint 2016/116
[BD16]
[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: TCC 2013 (2013)
[BFL90]
Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. In: SFCS 1990 (1990)
[BFLS91]
Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991 (1991)
[BG93]
[BG08]
[BGGL01]
Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zero-knowledge and its applications. In: FOCS 2001 (2001)
[BGH+04]
Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs and applications to coding. In: STOC 2004 (2004)
[BGKW88]
Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC 1988 (1988)
[BHZ87]
Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987)MathSciNetCrossRefMATH
[BKK+13]
Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O., Stichtenoth, H.: Constant rate PCPs for circuit-SAT with sublinear query complexity. In: FOCS 2013 (2013)
[BR93]
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993 (1993)
[BS08]
[BW15]
Bernhard, D., Warinschi, B.: On limitations of the Fiat-Shamir transformation. ePrint 2015/712 (2015)
[CGH04]
[COPV13]
Chung, K.-M., Ostrovsky, R., Pass, R., Visconti, I.: Simultaneous resettability from one-way functions. In: FOCS 2013 (2013)
[CPSV16]
Ciampi, M., Persiano, G., Siniscalchi, L., Visconti, I.: A transform for NIZK almost as efficient and general as the Fiat-Shamir transform without programmable random oracles. In: TCC 2016-A (2016)
[Dam89]
[DNRS03]
[Fis05]
Fischlin, M.: Communication-efficient non-interactive proofs of knowledge with online extractors. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 152–168. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​10 CrossRef
[FRS88]
Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols (1988)
[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
[GGPR13]
Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38348-9_​37 CrossRef
[GH98]
Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205–214 (1998)MathSciNetCrossRefMATH
[GIMS10]
Goyal, V., Ishai, Y., Mahmoody, M., Sahai, A.: Interactive locking, zero-knowledge PCPs, and unconditional cryptography. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 173–190. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​10 CrossRef
[GK03]
Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS 2003 (2003)
[GKR08]
Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for Muggles. In: STOC 2008 (2008)
[GMR89]
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH
[GOSV14]
Goyal, V., Ostrovsky, R., Scafuro, A., Visconti, I.: Black-box non-black-box zero knowledge. In: STOC 2014 (2014)
[Gro10]
[GS86]
Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: STOC 1986 (1986)
[GVW02]
Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1–2), 1–53 (2002)MathSciNetCrossRefMATH
[HS00]
[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
[IKM09]
Ito, T., Kobayashi, H., Matsumoto, K.: Oracularization and two-prover one-round interactive proofs against nonlocal strategies. In: CCC 2009 (2009)
[IKO07]
Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: CCC 2007 (2007)
[IMS12]
[IMSX15]
[Ito10]
Ito, T.: Polynomial-space approximation of no-signaling provers. In: ICALP 2010 (2010)
[Kil92]
Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992 (1992)
[KR08]
Kalai, Y., Raz, R.: Interactive PCP. In: ICALP 2008 (2008)
[KR09]
[KRR13]
Kalai, Y., Raz, R., Rothblum, R.: Delegation for bounded space. In: STOC 2013 (2013)
[KRR14]
Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: STOC 2014 (2014)
[KRR16]
Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of Fiat-Shamir for proofs. ePrint 2016/303 (2016)
[LFKN92]
Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. JACM 39(4), 859–868 (1992)MathSciNetCrossRefMATH
[Lin15]
Lindell, Y.: An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 93–109. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46494-6_​5
[Lip12]
Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169–189. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-28914-9_​10 CrossRef
[Mer89a]
[Mer89b]
[Mic00]
[MV16]
Mittelbach, A., Venturi, D.: Fiat-shamir for highly sound protocols is instantiable. ePrint 2016/313 (2016)
[Pas03]
[PGHR13]
Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Oakland 2013 (2013)
[PS96]
Pointcheval, D., Stern, J.: Security proofs for signature schemes. In EUROCRYPT ’96, 1996
[PSSV07]
Pavan, A., Selman, A.L., Sengupta, S., Vinodchandranm, N.V.: Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. Theoret. Comput. Sci. 385(1), 167–178 (2007)MathSciNetCrossRefMATH
[PTW09]
Pass, R., Tseng, W.-L.D., Wikström, D.: On the composition of public-coin zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 160–176. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-03356-8_​10 CrossRef
[RRR16]
Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: STOC 2016 (2016)
[SBV+13]
Setty, S., Braun, B., Victor, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: EuroSys 2013 (2013)
[SBW11]
Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: HotOS 2011 (2011)
[Sha92]
[SMBW12]
Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: NDSS 2012 (2012)
[SVP+12]
Setty, S., Victor, V., Panpalia, N., Braun, B., Blumberg, A.J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Security 2012 (2012)
[Val08]
Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78524-8_​1 CrossRef
[Wee09]
Metadaten
Titel
Interactive Oracle Proofs
verfasst von
Eli Ben-Sasson
Alessandro Chiesa
Nicholas Spooner
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-53643-8

Electronic ISBN: 978-3-662-53644-5

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53644-5_2