Abstract
The framework of interactive oracle proofs (IOP) has been used with great success to construct a number of efficient transparent zk-SNARKs in recent years. However, these constructions are based on Reed-Solomon codes and can only be applied directly to statements given in the form of arithmetic circuits or R1CS over large enough fields \(\mathbb {F}\).
This motivates the question: what is the best way to apply these IOPs to statements that are naturally written as R1CS over small fields, and more concretely, the binary field \(\mathbb {F}_2\)? While one can just see the system as one over an extension field \(\mathbb {F}_{2^e}\) containing \(\mathbb {F}_2\), this seems wasteful, as it uses e bits to encode just one “information” bit. In fact, in FC21 the work BooLigero devised a way to apply the well-known Ligero while being able to encode \(\sqrt{e}\) bits into one element of \(\mathbb {F}_{2^e}\).
In this paper, we introduce a new protocol for \(\mathbb {F}_2\)-R1CS which among other things relies on a more efficient embedding which (for practical parameters) allows to encode \(\ge e/4\) bits into an element of \(\mathbb {F}_{2^e}\). Our protocol makes then black box use of lincheck and rowcheck protocols for the larger field. Using the lincheck and rowcheck introduced in Aurora and Ligero respectively we obtain \(1.31 - 1.65 \times \) smaller proofs for Aurora and \(3.71 \times \) for Ligero. We also estimate the reduction of prover time by a factor of \(24.7 \times \) for Aurora and between \(6.9 - 32.5 \times \) for Ligero without interactive repetitions.
Our methodology uses the notion of reverse multiplication friendly embeddings introduced in the area of secure multiparty computation, combined with a new IOPP to test linear statements modulo a subspace \(V \le \mathbb {F}_{2^e}\) which may be of independent interest.
Research partially supported by the Spanish Government under project SecuRing (PID2019-110873RJ-I00/MCIN/AEI/10.13039/501100011033), by Madrid regional government as part of the program S2018/TCS-4339 (BLOQUES-CM) co-funded by EIE Funds of the European Union, and by a research grant from Nomadic Labs and the Tezos Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This is necessary as, for example, \(x^2 + x + 1 = 0\) is satisfiable over \(\mathbb {F}_4\) but not over \(\mathbb {F}_2\), despite the fact that the constraint only involves constants over \(\mathbb {F}_2\). Note that interpreting field multiplication as logical AND, the above constrain is equivalent to \(x \cdot (x - 1) = 1\), i.e. both x and its negation are true.
- 2.
This not only includes coordinate-wise products of secret vectors, but also the linear operations \(A \textbf{x}\) in the R1CS system, where A is a public matrix over the larger field.
- 3.
See [BCR+19] for how to see Ligero as an IOP with these characteristics.
- 4.
We cannot however apply our techniques to IOPs with preprocessing, see comment in Sect. 1.3.
- 5.
Note that u is not necessarily equal to 1.
- 6.
- 7.
Reed-Solomon IOPs are IOPs where soundness is guaranteed only when the messages sent by the prover are oracles to codewords of a Reed-Solomon code. Reed-Solomon IOPPs (proofs of proximity) additionally provide oracle access to the witness, also a set of Reed-Solomon codewords, to the verifier.
- 8.
Observe here we do not worry about their multiplicative structures.
References
Abspoel, M., Cramer, R., Escudero, D., Damgård, I., Xing, C.: Improved single-round secure multiplication using regenerating codes. IACR Cryptol. ePrint Arch. 2021, 253 (2021)
Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 2087–2104. ACM Press (2017)
Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press (2018)
Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) ICALP 2018, vol. 107 of LIPIcs, pp. 14:1–14:17. Schloss Dagstuhl (2018)
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
Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12
Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 103–128. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_4
Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2
Bhadauria, R., et al.: Ligero++: a new optimized sublinear IOP. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, pp. 2025–2038. ACM Press (2020)
Bünz, B., Fisch, B., Szepieniec, A.: Transparent SNARKs from DARK compilers. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 677–706. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_24
Ben-Sasson, E., Goldberg, L., Kopparty, S., Saraf, S.: DEEP-FRI: sampling outside the box improves soundness. In: Vidick, T. (ed.) ITCS 2020, vol. 151, pp. 5:1–5:32. LIPIcs (2020)
Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation with constant communication overhead using multiplication embeddings. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 375–398. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_20
Cascudo, I., Cramer, R., Xing, C., Yuan, C.: Amortized complexity of information-theoretically secure MPC revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 395–426. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_14
Cascudo, I., Gundersen, J.S.: A secret-sharing based MPC protocol for boolean circuits with good amortized complexity. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 652–682. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_23
Cascudo, I., Giunta, E.: On interactive oracle proofs for boolean r1cs statements. Cryptology ePrint Archive, Report 2021/694 (2021). https://ia.cr/2021/694
Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 769–793. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_27
Delpech, C., Guilhem, S., Orsini, E., Tanguy, T.: Limbo: efficient zero-knowledge mpcith-based arguments. To appear in Proceedings of ACM CCS 2021. Available at Cryptology ePrint Archive, Report 2021/215 (2021). https://eprint.iacr.org/2021/215
Damgård, I., Larsen, K.G., Nielsen, J.B.: Communication lower bounds for statistically secure MPC, with or without preprocessing. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 61–84. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_3
zk-SNARKs argument size comparison (2021). https://github.com/emanuelegiunta/snarks_comparison
Gao, S., Mateer, T.: Additive fast fourier transforms over finite fields. IEEE Trans. Inf. Theory 56(12), 6265–6272 (2010)
Gvili, Y., Scheffler, S., Varia, M.: Booligero: improved sublinear zero knowledge proofs for boolean circuits. To appear in phProceedings of Financial Crypto 2021. Available at Cryptology ePrint Archive (2021). https://eprint.iacr.org/2021/121.pdf
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) 39th ACM STOC, pp. 21–30. ACM Press (2007)
Libiop (2020). https://github.com/scipr-lab/libiop
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_21
Micali, S.: CS proofs (extended abstracts). In: 35th FOCS, pp. 436–453. IEEE Computer Society Press (1994)
Polychroniadou, A., Song, Y.: Constant-overhead unconditionally secure multiparty computation over binary fields. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 812–841. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_28
Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, pp. 49–62. ACM Press (2016)
Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 704–737. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_25
Wee, H.: On round-efficient argument systems. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 140–152. Springer, Heidelberg (2005). https://doi.org/10.1007/11523468_12
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Financial Cryptography Association
About this paper
Cite this paper
Cascudo, I., Giunta, E. (2022). On Interactive Oracle Proofs for Boolean R1CS Statements. In: Eyal, I., Garay, J. (eds) Financial Cryptography and Data Security. FC 2022. Lecture Notes in Computer Science, vol 13411. Springer, Cham. https://doi.org/10.1007/978-3-031-18283-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-18283-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-18282-2
Online ISBN: 978-3-031-18283-9
eBook Packages: Computer ScienceComputer Science (R0)