×

Interactive oracle proofs. (English) Zbl 1397.94048

Hirt, Martin (ed.) et al., Theory of cryptography. 14th international conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016, Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53643-8/pbk; 978-3-662-53644-5/ebook). Lecture Notes in Computer Science 9986, 31-60 (2016).
Summary: 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 [E. Ben-Sasson et al., TCC 2016-A (2016), Lect. Notes Comput. Sci. 9563, 33–64 (2016; Zbl 1375.94101)], constant-rate constant-query probabilistic checking [the author et al., Short interactive oracle proofs with constant query complexity, via composition and sumcheck (2016). Crypto ePrint 2016/324], and doubly-efficient constant-round IPs for polynomial-time bounded-space computations [O. Reingold et al., in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016. New York, NY: ACM, 49–62 (2016; Zbl 1373.68274)].{ } 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 [A. Fiat and A. Shamir, Crypto 1986, Lect. Notes Comput. Sci. 263, 186–194 (1987; Zbl 0636.94012)], and of the “CS proof” constructions of [S. Micali, FOCS 1994, see SIAM J. Comput. 30, No. 4, 1253–1298 (2000; Zbl 1009.68053)] and P. Valiant [TCC 2008, Lect. Notes Comput. Sci. 4948, 1–18 (2008; Zbl 1162.68448)] 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 [Y. Ishai et al., On zero-knowledge PCPs: limitations, simplifications, and applications (2015), http://www.cs.virginia.edu/mohammad/files/papers/ZKPCPs-Full.pdf].
For the entire collection see [Zbl 1349.94008].

MSC:

94A60 Cryptography

Software:

Pinocchio
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems (1992) · Zbl 0977.68539
[2] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. JACM 45(3), 501–555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306
[3] Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. JACM 45(1), 70–122 (1998) · Zbl 0903.68076 · doi:10.1145/273865.273901
[4] Babai, L.: Trading group theory for randomness. In: STOC 1985 (1985) · doi:10.1145/22145.22192
[5] Babai, L.: E-mail and the unexpected power of interaction. Technical report, University of Chicago, Chicago, IL, USA (1990) · Zbl 0906.68072
[6] 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 · Zbl 1122.94350 · doi:10.1007/978-3-540-24676-3_11
[7] Brassard, G., Crépeau, C.: Non-transitive transfer of confidence: a perfect zero-knowledge interactive protocol for SAT and beyond. In: FOCS 1986 (1986)
[8] Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988) · Zbl 0656.68109 · doi:10.1016/0022-0000(88)90005-0
[9] 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
[10] Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasilinear-size zero knowledge from linear-algebraic PCPs. In: TCC 2016-A (2016) · Zbl 1375.94101
[11] Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: TCC 2013 (2013) · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18
[12] Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs, 2016. Crypto ePrint 2016/116 · Zbl 1397.94048
[13] Bishop, A., Dodis, Y.: Interactive coding for interactive proofs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 352–366. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49099-0_13 · Zbl 1382.94068 · doi:10.1007/978-3-662-49099-0_13
[14] 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) · Zbl 1315.94060 · doi:10.1007/978-3-642-36594-2_11
[15] Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. In: SFCS 1990 (1990) · Zbl 0774.68041 · doi:10.1109/FSCS.1990.89520
[16] Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991 (1991) · doi:10.1145/103418.103428
[17] Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993). doi: 10.1007/3-540-48071-4_28 · Zbl 0823.94016 · doi:10.1007/3-540-48071-4_28
[18] Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661–1694 (2008) · Zbl 1180.94047 · doi:10.1137/070709244
[19] Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zero-knowledge and its applications. In: FOCS 2001 (2001) · doi:10.1109/SFCS.2001.959886
[20] 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) · Zbl 1192.68286 · doi:10.1145/1007352.1007361
[21] Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC 1988 (1988)
[22] Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987) · Zbl 0653.68037 · doi:10.1016/0020-0190(87)90232-8
[23] 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) · Zbl 1410.68140 · doi:10.1109/FOCS.2013.42
[24] Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993 (1993) · doi:10.1145/168588.168596
[25] Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38(2), 551–607 (2008) · Zbl 1172.68025 · doi:10.1137/050646445
[26] Bernhard, D., Warinschi, B.: On limitations of the Fiat-Shamir transformation. ePrint 2015/712 (2015)
[27] Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. JACM 51(4), 557–594 (2004) · Zbl 1204.94063 · doi:10.1145/1008731.1008734
[28] Chung, K.-M., Ostrovsky, R., Pass, R., Visconti, I.: Simultaneous resettability from one-way functions. In: FOCS 2013 (2013) · doi:10.1109/FOCS.2013.15
[29] 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) · Zbl 1377.94045 · doi:10.1007/978-3-662-49099-0_4
[30] Damgård, I.B.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990). doi: 10.1007/0-387-34805-0_39 · Zbl 0724.68029 · doi:10.1007/0-387-34805-0_39
[31] Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. JACM 50(6), 852–921 (2003) · Zbl 1325.68034 · doi:10.1145/950620.950623
[32] 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 · Zbl 1145.94467 · doi:10.1007/11535218_10
[33] Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols (1988) · Zbl 0938.68824
[34] 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 · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12
[35] 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 · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37
[36] Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205–214 (1998) · Zbl 1338.68104 · doi:10.1016/S0020-0190(98)00116-1
[37] 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 · Zbl 1280.94063 · doi:10.1007/978-3-642-14623-7_10
[38] Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS 2003 (2003)
[39] Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for Muggles. In: STOC 2008 (2008) · Zbl 1231.68135 · doi:10.1145/1374376.1374396
[40] Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012
[41] Goyal, V., Ostrovsky, R., Scafuro, A., Visconti, I.: Black-box non-black-box zero knowledge. In: STOC 2014 (2014) · Zbl 1315.94077 · doi:10.1145/2591796.2591879
[42] Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-17373-8_19 · Zbl 1253.94049 · doi:10.1007/978-3-642-17373-8_19
[43] Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: STOC 1986 (1986) · doi:10.1145/12130.12137
[44] Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1–2), 1–53 (2002) · Zbl 1053.68045 · doi:10.1007/s00037-002-0169-0
[45] Harsha, P., Sudan, M.: Small PCPs with low query complexity. Comput. Complex. 9(3–4), 157–201 (2000) · Zbl 0986.68134 · doi:10.1007/PL00001606
[46] 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 · Zbl 0931.94009 · doi:10.1007/BFb0055744
[47] Ito, T., Kobayashi, H., Matsumoto, K.: Oracularization and two-prover one-round interactive proofs against nonlocal strategies. In: CCC 2009 (2009) · doi:10.1109/CCC.2009.22
[48] Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: CCC 2007 (2007) · doi:10.1109/CCC.2007.10
[49] Ishai, Y., Mahmoody, M., Sahai, A.: On efficient zero-knowledge PCPs. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 151–168. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-28914-9_9 · Zbl 1304.68056 · doi:10.1007/978-3-642-28914-9_9
[50] Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: limitations, simplifications, and applications (2015). http://www.cs.virginia.edu/mohammad/files/papers/ZKPCPs-Full.pdf
[51] Ito, T.: Polynomial-space approximation of no-signaling provers. In: ICALP 2010 (2010) · Zbl 1287.68051 · doi:10.1007/978-3-642-14165-2_13
[52] Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992 (1992)
[53] Kalai, Y., Raz, R.: Interactive PCP. In: ICALP 2008 (2008) · Zbl 1155.68504 · doi:10.1007/978-3-540-70583-3_44
[54] Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 143–159. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-03356-8_9 · Zbl 1252.94079 · doi:10.1007/978-3-642-03356-8_9
[55] Kalai, Y., Raz, R., Rothblum, R.: Delegation for bounded space. In: STOC 2013 (2013) · Zbl 1293.68176
[56] Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: STOC 2014 (2014) · Zbl 1315.68135 · doi:10.1145/2591796.2591809
[57] Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of Fiat-Shamir for proofs. ePrint 2016/303 (2016) · Zbl 1409.94881
[58] Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. JACM 39(4), 859–868 (1992) · Zbl 0799.68097 · doi:10.1145/146585.146605
[59] 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 · Zbl 1354.94038 · doi:10.1007/978-3-662-46494-6_5
[60] 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 · Zbl 1303.94090 · doi:10.1007/978-3-642-28914-9_10
[61] Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990). doi: 10.1007/0-387-34805-0_21 · doi:10.1007/0-387-34805-0_21
[62] Merkle, R.C.: One way hash functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990). doi: 10.1007/0-387-34805-0_40 · doi:10.1007/0-387-34805-0_40
[63] Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000) · Zbl 1009.68053 · doi:10.1137/S0097539795284959
[64] Mittelbach, A., Venturi, D.: Fiat-shamir for highly sound protocols is instantiable. ePrint 2016/313 (2016) · Zbl 1416.94055
[65] Pass, R.: On deniability in the common reference string and random oracle model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 316–337. Springer, Heidelberg (2003). doi: 10.1007/978-3-540-45146-4_19 · Zbl 1122.94394 · doi:10.1007/978-3-540-45146-4_19
[66] Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Oakland 2013 (2013) · doi:10.1109/SP.2013.47
[67] Pointcheval, D., Stern, J.: Security proofs for signature schemes. In EUROCRYPT ’96, 1996 · Zbl 1304.94106 · doi:10.1007/3-540-68339-9_33
[68] 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) · Zbl 1124.68039 · doi:10.1016/j.tcs.2007.06.013
[69] 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 · Zbl 1252.94092 · doi:10.1007/978-3-642-03356-8_10
[70] Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: STOC 2016 (2016) · Zbl 1373.68274 · doi:10.1145/2897518.2897652
[71] 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) · doi:10.1145/2465351.2465359
[72] Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: HotOS 2011 (2011)
[73] Shamir, A.: IP = PSPACE. JACM 39(4), 869–877 (1992) · Zbl 0799.68096 · doi:10.1145/146585.146609
[74] Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: NDSS 2012 (2012)
[75] 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)
[76] 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 · Zbl 1162.68448 · doi:10.1007/978-3-540-78524-8_1
[77] Wee, H.: Zero knowledge in the random oracle model, revisited. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 417–434. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-10366-7_25 · Zbl 1267.94102 · doi:10.1007/978-3-642-10366-7_25
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.