×
Xie, Tiacheng; Zhang, Jiaheng; Zhang, Yupeng; Papamanthou, Charalampos; Song, Dawn

Libra: succinct zero-knowledge proofs with optimal prover computation. (English) Zbl 1509.94140

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, 733-764 (2019).
Summary: We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if \(C\) is the size of the circuit being proved (i) the prover time is \(O(C)\) irrespective of the circuit type; (ii) the proof size and verification time are both \(O(d\log C)\) for \(d\)-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by S. Goldwasser et al. [J. ACM 62, No. 4, Article No. 27, 64 p. (2015; Zbl 1393.68071)] (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.
For the entire collection see [Zbl 1428.94006].

Cited in 39 Documents

MSC:

94A60 Cryptography

Keywords:

zero-knowledge proof system; linear-time algorithm

Citations:

Zbl 1393.68071

Software:

SNARKs for C; Libra; jsnark; ZKBoo; vSQL; Ligero; libsnark; libiop; Geppetto; Pinocchio; gmp
Cite Review PDF
Full Text: DOI

References:

[1] Ate-pairing. https://github.com/herumi/ate-pairing
[2] The GNU multiple precision arithmetic library. https://gmplib.org/
[3] Hyrax reference implementation. https://github.com/hyraxZK/hyraxZK
[4] jsnark. https://github.com/akosba/jsnark
[5] libsnark. https://github.com/scipr-lab/libsnark
[6] Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (2017)
[7] Bayer, S.; Groth, J.; Pointcheval, D.; Johansson, T., Efficient zero-knowledge argument for correctness of a shuffle, Advances in Cryptology - EUROCRYPT 2012, 263-280, 2012, Heidelberg: Springer, Heidelberg · Zbl 1297.94045 · doi:10.1007/978-3-642-29011-4_17
[8] Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint (2018)
[9] Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: Proceedings of the Symposium on Security and Privacy SP (2014)
[10] 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
[11] Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. Cryptology ePrint (2018)
[12] 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
[13] Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the USENIX Security Symposium (2014)
[14] 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
[15] Blum, M.; Evans, W.; Gemmell, P.; Kannan, S.; Naor, M., Checking the correctness of memories, Algorithmica, 12, 2-3, 225-244, 1994 · Zbl 1323.68200 · doi:10.1007/BF01185212
[16] Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: Proceedings of the Symposium on Security and Privacy (SP), pp. 319-338 (2018)
[17] 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
[18] Bootle, J.; Cerulli, A.; Ghadafi, E.; Groth, J.; Hajiabadi, M.; Jakobsen, SK; Takagi, T.; Peyrin, T., Linear-time zero-knowledge proofs for arithmetic circuit satisfiability, Advances in Cryptology - ASIACRYPT 2017, 336-365, 2017, Cham: Springer, Cham · Zbl 1417.94046 · doi:10.1007/978-3-319-70700-6_12
[19] Braun, B., Feldman, A.J., Ren, Z., Setty, S.T.V., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP (2013)
[20] Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. IACR Cryptology ePrint Archive 2018:1004 (2018)
[21] Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1825-1842. ACM (2017)
[22] Chiesa, A., Forbes, M.A., Spooner, N.: A zero knowledge sumcheck and its applications. CoRR abs/1704.02086 (2017). http://arxiv.org/abs/1704.02086
[23] Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012 (2012) · Zbl 1347.68157
[24] Costello, C., et al.: Geppetto: Versatile verifiable computation. In: S&P (2015)
[25] Cramer, R.; Damgård, I.; Krawczyk, H., Zero-knowledge proofs for finite field arithmetic, or: can zero-knowledge be for free?, Advances in Cryptology — CRYPTO ’98, 424-441, 1998, Heidelberg: Springer, Heidelberg · Zbl 0964.94019 · doi:10.1007/BFb0055745
[26] Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology — CRYPTO’ 86, 186-194, 1987, Heidelberg: Springer, Heidelberg · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12
[27] Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., Parno, B.: Hash first, argue later: adaptive verifiable computations on outsourced data. In: ACM SIGSAC Conference on Computer and Communications Security (2016)
[28] 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
[29] Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster zero-knowledge for boolean circuits. In: USENIX Security Symposium, pp. 1069-1083 (2016)
[30] Goldwasser, S.; Kalai, YT; Rothblum, GN, Delegating computation: interactive proofs for Muggles, J. ACM, 62, 4, 27:1-27:64, 2015 · Zbl 1393.68071 · doi:10.1145/2699436
[31] 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
[32] Groth, J.; Halevi, S., Linear algebra with sub-linear zero-knowledge arguments, Advances in Cryptology - CRYPTO 2009, 192-208, 2009, Heidelberg: Springer, Heidelberg · Zbl 1252.94068 · doi:10.1007/978-3-642-03356-8_12
[33] 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
[34] Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: 22nd Annual IEEE Conference on Computational Complexity (CCC 2007) (2007)
[35] Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 21-30. ACM (2007) · Zbl 1232.68044
[36] Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the ACM Symposium on Theory of Computing (1992)
[37] Kosba, A., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: the blockchain model of cryptography and privacy-preserving smart contracts. In: Proceedings of Symposium on Security and Privacy (SP) (2016)
[38] 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
[39] Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N., Algebraic methods for interactive proof systems, J. ACM, 39, 4, 859-868, 1992 · Zbl 0799.68097 · doi:10.1145/146585.146605
[40] Merkle, RC; Pomerance, C., A digital signature based on a conventional encryption function, Advances in Cryptology — CRYPTO ’87, 369-378, 1988, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-48184-2_32
[41] Micali, S.: Computationally sound proofs. SIAM J. Comput. (2000) · Zbl 1009.68053
[42] Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: S&P 2013, pp. 238-252 (2013)
[43] 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
[44] Turkowski, K.: Filters for common resampling tasks. In: Graphics Gems, pp. 147-165. Academic Press Professional, Inc. (1990)
[45] Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation. In: Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP 2013 (2013)
[46] Wahby, R.S., et al.: Full accounting for verifiable outsourcing. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM (2017)
[47] Wahby, R.S., Setty, S.T., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: NDSS (2015)
[48] Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 926-943. IEEE (2018)
[49] Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint (2017)
[50] Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vSQL: verifying arbitrary SQL queries over dynamic outsourced databases. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 863-880. IEEE (2017)
[51] Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vRAM: faster verifiable RAM with program-independent preprocessing. In: Proceeding of IEEE Symposium on Security and Privacy (S&P) (2018)
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.