Scalable zero knowledge with no trusted setup. (English) Zbl 1509.94063
Boldyreva, Alexandra (ed.) et al., Advances in cryptology – CRYPTO 2019. 39th annual international cryptology conference, Santa Barbara, CA, USA, August 18–22, 2019. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 11694, 701-732 (2019).
Summary: One of the approaches to constructing zero knowledge (ZK) arguments relies on PCP techniques that date back to influential works from the early 1990’s [L. Babai et al. [“Checking computations in polylogarithmic time”, in: Proceedings of the twenty-third annual ACM symposium on theory of computing, STOC ’91, New Orleans, LA, USA, May 5–8, 1991. New York, NY: Association for Computing Machinery (ACM). 21–32 (1991; doi:10.1145/103418.103428); S. Arora et al., J. ACM 45, No. 3, 501–555 (1998; Zbl 1065.68570)]. These techniques require only minimal cryptographic assumptions, namely, the existence of a family of collision-resistant hash functions, and achieve two remarkable properties: (i) all messages generated by the verifier are public random coins, and (ii) total verification time is merely poly-logarithmic in the time needed to naïvely execute the computation being verified.
Those early constructions were never realized in code, mostly because proving time was too large. To address this, the model of interactive oracle proofs (IOPs), which generalizes the PCP model, was recently suggested. Proving time for ZK-IOPs was reduced to quasi-linear, even for problems that require nondeterministic exponential time to decide.
Despite these recent advances it was still not clear whether ZK-IOP systems can lead to concretely efficient succinct argument systems. Our main claim is that this is indeed the case. We present a new construction of an IOP of knowledge (which we call a zk-STIK) that improves, asymptotically, on the state of art: for log-space computations of length \(T\) it is the first to \(O(T\log T)\) arithmetic prover complexity and \(O(\log T)\) verifier arithmetic complexity. Prior IOPs had additional \(\mathsf{poly}\log T\) factors in both prover and verifier. Additionally, we report a C++ realization of this system (which we call libSTARK). Compared to prevailing ZK realizations, it has the fastest proving and (total) verification time for sufficiently large sequential computations.
For the entire collection see [Zbl 1428.94006].
Those early constructions were never realized in code, mostly because proving time was too large. To address this, the model of interactive oracle proofs (IOPs), which generalizes the PCP model, was recently suggested. Proving time for ZK-IOPs was reduced to quasi-linear, even for problems that require nondeterministic exponential time to decide.
Despite these recent advances it was still not clear whether ZK-IOP systems can lead to concretely efficient succinct argument systems. Our main claim is that this is indeed the case. We present a new construction of an IOP of knowledge (which we call a zk-STIK) that improves, asymptotically, on the state of art: for log-space computations of length \(T\) it is the first to \(O(T\log T)\) arithmetic prover complexity and \(O(\log T)\) verifier arithmetic complexity. Prior IOPs had additional \(\mathsf{poly}\log T\) factors in both prover and verifier. Additionally, we report a C++ realization of this system (which we call libSTARK). Compared to prevailing ZK realizations, it has the fastest proving and (total) verification time for sufficiently large sequential computations.
For the entire collection see [Zbl 1428.94006].
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1065.68570References:
| [1] | Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Proceedings of the 24th ACM Conference on Computer and Communications Security (2017) |
| [2] | Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and the hardness of approximation problems, J. ACM, 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, J. ACM, 45, 1, 70-122, 1998 · Zbl 0903.68076 · doi:10.1145/273865.273901 |
| [4] | Babai, L.; Fortnow, L., Arithmetization: a new method in structural complexity theory, Comput. Complex., 1, 1, 41-66, 1991 · Zbl 0774.68040 · doi:10.1007/BF01200057 |
| [5] | Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 21-32 (1991) |
| [6] | Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, pp. 16-25 (1990) |
| [7] | Bellare, M.; Goldreich, O.; Brickell, EF, On defining proofs of knowledge, Advances in Cryptology — CRYPTO 92, 390-420, 1993, Heidelberg: Springer, Heidelberg · Zbl 0823.94016 · doi:10.1007/3-540-48071-4_28 |
| [8] | Ben-Or, M.; Goldwasser, S., Everything provable is provable in zero-knowledge, Advances in Cryptology — CRYPTO 88, 37-56, 1990, New York: Springer, New York · Zbl 0718.68033 · doi:10.1007/0-387-34799-2_4 |
| [9] | Ben-Sasson, E., et al.: Computational integrity with a public random string from quasi-linear PCPs. In: IACR Cryptology ePrint Archive 2016, p. 646 (2016). http://eprint.iacr.org/2016/646 |
| [10] | Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: libSTARK: a library for zero knowledge (ZK) scalable transparent argument of knowledge (STARK). https://github.com/elibensasson/libSTARK |
| [11] | Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9-13 July 2018, pp. 14:1-14:17 (2018). doi:10.4230/LIPIcs.ICALP.2018.14 · Zbl 1499.68141 |
| [12] | Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046 (2018). https://eprint.iacr.org/2018/046 |
| [13] | Ben-Sasson, E., Chiesa, A., Forbes, M.A., Gabizon, A., Riabzev, M., Spooner, N.: On probabilistic checking in perfect zero knowledge. In: Electron. Colloq. Comput. Complex. (ECCC) 23, 156 (2016). http://eccc.hpi-web.de/report/2016/156 |
| [14] | Ben-Sasson, E.; Chiesa, A.; Forbes, MA; Gabizon, A.; Riabzev, M.; Spooner, N.; Kalai, Y.; Reyzin, L., Zero knowledge protocols from succinct constraint detection, Theory of Cryptography, 172-206, 2017, Cham: Springer, Cham · Zbl 1416.68020 · doi:10.1007/978-3-319-70503-3_6 |
| [15] | Ben-Sasson, E.; Chiesa, A.; Gabizon, A.; Riabzev, M.; Spooner, N., Short interactive oracle proofs with constant query complexity, via composition and sumcheck, Electron. Colloq. Comput. Complex. (ECCC), 23, 46, 2016 |
| [16] | Ben-Sasson, E.; Chiesa, A.; Gabizon, A.; Virza, M.; Kushilevitz, E.; Malkin, T., Quasi-linear size zero knowledge from linear-algebraic PCPs, Theory of Cryptography, 33-64, 2016, Heidelberg: Springer, Heidelberg · Zbl 1375.94101 · doi:10.1007/978-3-662-49099-0_2 |
| [17] | Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC 2013, pp. 585-594 (2013) · Zbl 1293.94054 |
| [18] | Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: TinyRAM architecture specification v2. 00 (2013). http://scipr-lab.org/tinyram |
| [19] | Ben-Sasson, E.; Chiesa, A.; Genkin, D.; Tromer, E.; Virza, M.; Canetti, R.; Garay, JA, SNARKs for C: verifying program executions succinctly and in zero knowledge, Advances in Cryptology - CRYPTO 2013, 90-108, 2013, Heidelberg: Springer, Heidelberg · Zbl 1317.68050 · doi:10.1007/978-3-642-40084-1_6 |
| [20] | Ben-Sasson, E., Chiesa, A., Green, M., Tromer, E., Virza, M.: Secure sampling of public parameters for succinct zero knowledge proofs. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, 17-21 May 2015, pp. 287-304 (2015). doi:10.1109/SP.2015.25 |
| [21] | Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. Cryptology ePrint Archive, Report 2018/828 (2018). https://eprint.iacr.org/2018/828. To appear in Eurocrypt 2019 |
| [22] | Ben-Sasson, E.; Chiesa, A.; Spooner, N.; Hirt, M.; Smith, A., Interactive oracle proofs, Theory of Cryptography, 31-60, 2016, Heidelberg: Springer, Heidelberg · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [23] | Ben-Sasson, E.; Chiesa, A.; Tromer, E.; Virza, M.; Garay, JA; Gennaro, R., Scalable zero knowledge via cycles of elliptic curves, Advances in Cryptology - CRYPTO 2014, 276-294, 2014, Heidelberg: Springer, Heidelberg · Zbl 1334.68077 · doi:10.1007/978-3-662-44381-1_16 |
| [24] | Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Security Symposium, Security 2014, pp. 781-796 (2014). Extended version at http://eprint.iacr.org/2013/879 |
| [25] | Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC 2005, pp. 120-134 (2005) |
| [26] | Ben-Sasson, E., Kopparty, S., Saraf, S.: Worst-case to average case reductions for the distance to a code. In: 33rd Computational Complexity Conference, CCC 2018, San Diego, CA, USA, 22-24 June 2018, pp. 24:1-24:23 (2018). doi:10.4230/LIPIcs.CCC.2018.24 · Zbl 1441.68035 |
| [27] | 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 |
| [28] | Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC 2013, pp. 111-120 (2013) · Zbl 1293.68264 |
| [29] | Bitansky, N.; Chiesa, A.; Ishai, Y.; Paneth, O.; Ostrovsky, R.; Sahai, A., Succinct non-interactive arguments via linear interactive proofs, Theory of Cryptography, 315-333, 2013, Heidelberg: Springer, Heidelberg · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [30] | Bootle, J.; Cerulli, A.; Chaidos, P.; Groth, J.; Petit, C.; Fischlin, M.; Coron, J-S, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, Advances in Cryptology - EUROCRYPT 2016, 327-357, 2016, Heidelberg: Springer, Heidelberg · Zbl 1369.94520 · doi:10.1007/978-3-662-49896-5_12 |
| [31] | Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: efficient range proofs for confidential transactions. Cryptology ePrint Archive, Report 2017/1066 (2017). https://eprint.iacr.org/2017/1066 |
| [32] | Buterin, V.: (2017). https://vitalik.ca/ |
| [33] | Chiesa, A.; Zhu, ZA, Shorter arithmetization of nondeterministic computations, Theor. Comput. Sci., 600, 107-131, 2015 · Zbl 1430.68108 · doi:10.1016/j.tcs.2015.07.030 |
| [34] | Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, ICS 2010, pp. 310-331 (2010) |
| [35] | Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science. ITCS 2012, pp. 90-112 (2012) · Zbl 1347.68157 |
| [36] | Cormode, G.; Thaler, J.; Yi, K., Verifying computations with streaming interactive proofs, Proc. VLDB Endow., 5, 1, 25-36, 2011 · doi:10.14778/2047485.2047488 |
| [37] | Danezis, G.; Fournet, C.; Groth, J.; Kohlweiss, M.; Sarkar, P.; Iwata, T., Square span programs with applications to succinct NIZK arguments, Advances in Cryptology - ASIACRYPT 2014, 532-550, 2014, Heidelberg: Springer, Heidelberg · Zbl 1306.94042 · doi:10.1007/978-3-662-45611-8_28 |
| [38] | Dinur, I., The PCP theorem by gap amplification, J. ACM, 54, 3, 12, 2007 · Zbl 1292.68074 · doi:10.1145/1236457.1236459 |
| [39] | Dwork, C.; Feige, U.; Kilian, J.; Naor, M.; Safra, M.; Brickell, EF, Low communication 2-prover zero-knowledge proofs for NP, Advances in Cryptology — CRYPTO 92, 215-227, 1993, Heidelberg: Springer, Heidelberg · Zbl 0925.68143 · doi:10.1007/3-540-48071-4_15 |
| [40] | Gennaro, R.; Gentry, C.; Parno, B.; Rabin, T., Non-interactive verifiable computing: outsourcing computation to untrusted workers, Advances in Cryptology - CRYPTO 2010, 465-482, 2010, Heidelberg: Springer, Heidelberg · Zbl 1284.68065 · doi:10.1007/978-3-642-14623-7_25 |
| [41] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645, 2013, Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [42] | Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster zero-knowledge for boolean circuits. In: 25th USENIX Security Symposium (USENIX Security 16), pp. 1069-1083. USENIX Association, Austin (2016). https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/giacomelli. ISBN 978-1-931971-32-4 |
| [43] | Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for Muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 113-122 (2008) · Zbl 1231.68135 |
| [44] | 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 |
| [45] | Groth, J.; Abe, M., Short pairing-based non-interactive zero-knowledge arguments, Advances in Cryptology - ASIACRYPT 2010, 321-340, 2010, Heidelberg: Springer, Heidelberg · Zbl 1253.94049 · doi:10.1007/978-3-642-17373-8_19 |
| [46] | Groth, J.; Lee, DH; Wang, X., Efficient zero-knowledge arguments from two-tiered homomorphic commitments, Advances in Cryptology - ASIACRYPT 2011, 431-448, 2011, Heidelberg: Springer, Heidelberg · Zbl 1227.94047 · doi:10.1007/978-3-642-25385-0_23 |
| [47] | Groth, J.; Fischlin, M.; Coron, J-S, On the size of pairing-based non-interactive arguments, Advances in Cryptology - EUROCRYPT 2016, 305-326, 2016, Heidelberg: Springer, Heidelberg · Zbl 1369.94539 · doi:10.1007/978-3-662-49896-5_11 |
| [48] | Groth, J.; Maller, M.; Katz, J.; Shacham, H., Snarky signatures: minimal signatures of knowledge from simulation-extractable SNARKs, Advances in Cryptology - CRYPTO 2017, 581-612, 2017, Cham: Springer, Cham · Zbl 1410.94077 · doi:10.1007/978-3-319-63715-0_20 |
| [49] | Groth, J.; Sahai, A.; Smart, N., Efficient non-interactive proof systems for bilinear groups, Advances in Cryptology - EUROCRYPT 2008, 415-432, 2008, Heidelberg: Springer, Heidelberg · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24 |
| [50] | Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007, pp. 278-291 (2007) |
| [51] | Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 21-30. ACM (2007) · Zbl 1232.68044 |
| [52] | 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 |
| [53] | Kalai, YT; Raz, R.; Aceto, L.; Damgård, I.; Goldberg, LA; Halldórsson, MM; Ingólfsdóttir, A.; Walukiewicz, I., Interactive PCP, Automata, Languages and Programming, 536-547, 2008, Heidelberg: Springer, Heidelberg · Zbl 1155.68504 · doi:10.1007/978-3-540-70583-3_44 |
| [54] | Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 723-732 (1992) |
| [55] | Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 496-505 (1997) · Zbl 0963.68192 |
| [56] | Lin, S-J; Al-Naffouri, TY; Han, YS; Chung, W-H, Novel polynomial basiswith fast fourier transform and its application to Reed-Solomon erasure codes, IEEE Trans. Inf. Theory, 62, 11, 6284-6299, 2016 · Zbl 1359.94718 · doi:10.1109/TIT.2016.2608892 |
| [57] | Lin, S.-J., Chung, W.-H., Han, Y.S.: Novel polynomial basis and its application to Reed-Solomon erasure codes. In: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 316-325. IEEE Computer Society, Washington, DC (2014). doi:10.1109/FOCS.2014.41. ISBN 978-1-4799-6517-5 |
| [58] | Lipmaa, H.; Cramer, R., Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments, Theory of Cryptography, 169-189, 2012, Heidelberg: Springer, Heidelberg · Zbl 1303.94090 · doi:10.1007/978-3-642-28914-9_10 |
| [59] | Lund, C.; Fortnow, L.; Karloff, HJ; Nisan, N., Algebraic methods for interactive proof systems, J. ACM, 39, 4, 859-868, 1992 · Zbl 0799.68097 · doi:10.1145/146585.146605 |
| [60] | Micali, S., Computationally sound proofs, SIAM J. Comput., 30, 4, 1253-1298, 2000 · Zbl 1009.68053 · doi:10.1137/S0097539795284959 |
| [61] | Micali, S., Computationally sound proofs, SIAM J. Comput., 30, 4, 1253-1298, 2000 · Zbl 1009.68053 · doi:10.1137/S0097539795284959 |
| [62] | Mie, T., Polylogarithmic two-round argument systems, J. Math. Cryptol., 2, 4, 343-363, 2008 · Zbl 1158.94003 · doi:10.1515/JMC.2008.016 |
| [63] | Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland 2013, pp. 238-252 (2013) |
| [64] | Peck, M., A blockchain currency that beat s bitcoin on privacy [News], IEEE Spectr., 53, 12, 11-13, 2016 · doi:10.1109/MSPEC.2016.7761864 |
| [65] | Pergament, E.: Algebraic RAM. MA thesis. Technion—Israel Institute of Technology (2017) |
| [66] | Razborov, AA, Lower bounds on the size of bounded depth circuits over a complete basis with logical addition, Math. Notes Acad. Sci. USSR, 41, 4, 333-338, 1987 · Zbl 0632.94030 |
| [67] | 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, 18-21 June 2016, pp. 49-62 (2016). doi:10.1145/2897518.2897652 · Zbl 1373.68274 |
| [68] | SCIPR Lab. libsnark: a C++ library for zkSNARK proofs. https://github.com/scipr-lab/libsnark |
| [69] | Seo, JH; Catalano, D.; Fazio, N.; Gennaro, R.; Nicolosi, A., Round-efficient sub-linear zero-knowledge arguments for linear algebra, Public Key Cryptography - PKC 2011, 387-402, 2011, Heidelberg: Springer, Heidelberg · Zbl 1291.94153 · doi:10.1007/978-3-642-19379-8_24 |
| [70] | Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, HotOS 2011, p. 29 (2011) |
| [71] | Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th EuoroSys Conference, EuroSys 2013, pp. 71-84 (2013) |
| [72] | Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: Proceedings of the 2012 Network and Distributed System Security Symposium, NDSS 2012 (2012) |
| [73] | Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A.J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of the 21st USENIX Security Symposium, Security 2012, pp. 253-268 (2012) |
| [74] | Shamir, A., IP = PSPACE, J. ACM, 39, 4, 869-877, 1992 · Zbl 0799.68096 · doi:10.1145/146585.146609 |
| [75] | Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 77-82. ACM (1987) |
| [76] | Thaler, J.; Canetti, R.; Garay, JA, Time-optimal interactive proofs for circuit evaluation, Advances in Cryptology - CRYPTO 2013, 71-89, 2013, Heidelberg: Springer, Heidelberg · Zbl 1316.94093 · doi:10.1007/978-3-642-40084-1_5 |
| [77] | Valiant, P.; Canetti, R., Incrementally verifiable computation or proofs of knowledge imply time/space efficiency, Theory of Cryptography, 1-18, 2008, Heidelberg: Springer, Heidelberg · Zbl 1162.68448 · doi:10.1007/978-3-540-78524-8_1 |
| [78] | Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland 2013, pp. 223-237 (2013) |
| [79] | Wahby, R.S., Setty, S.T.V., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, 8-11 February 2014 (2015) |
| [80] | Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. Cryptology ePrint Archive, Report 2017/1132 (2017). https://eprint.iacr.org/2017/1132 |
| [81] | Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vRAM: faster verifiable RAM with program-independent preprocessing. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 203-220 (2018). doi:10.1109/SP.2018.00013 |
| [82] | Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint Archive, Report 2017/1146 (2017). https://eprint.iacr.org/2017/1146 |
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.
