Paper 2021/694
On Interactive Oracle Proofs for Boolean R1CS Statements
Ignacio Cascudo and Emanuele Giunta
Abstract
The framework of interactive oracle proofs (IOP) has been used with great success to construct a number of efficient transparent zkSNARKs in recent years. However, these constructions are based on ReedSolomon codes and can only be applied directly to statements given in the form of arithmetic circuits or R1CS over large fields $\mathbb{F}$ since their soundness error is at least $1/\mathbb{F}$. This motivates the question of 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, the recent BooLigero has devised a way to apply the wellknown 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 $\geq 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 \leq \mathbb{F}_{2^e}$ which may be of independent interest.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 zeroknowledgeInteractive oracle proofR1CSreverse multiplication friendly embedding
 Contact author(s)

ignacio cascudo @ imdea org
emanuele giunta @ imdea org  History
 20210528: received
 Short URL
 https://ia.cr/2021/694
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/694, author = {Ignacio Cascudo and Emanuele Giunta}, title = {On Interactive Oracle Proofs for Boolean R1CS Statements}, howpublished = {Cryptology ePrint Archive, Paper 2021/694}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/694}}, url = {https://eprint.iacr.org/2021/694} }