Proposal: Rinocchio: SNARKs for Ring Arithmetic

![](https://i.imgur.com/WeIvTiX.png =150x) **#4 Home Edition** # Proposal: Rinocchio: SNARKs for Ring Arithmetic **Moderator:** Daniel Benarroch **Presenters:** Anca Nitulescu **Authors:** * Chaya Ganesh * Anca Nitulescu * Eduardo Soria-Vazquez To be presented on 2021-04-19. Resources: * [Latest PDF version](https://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-rinocchio.pdf) * [Miro whiteboard frame](https://miro.com/app/board/o9J_lJQRFxQ=/?moveToWidget=3074457357481295789&cot=14) * [Additional related links](https://hackmd.io/@workshop4/links) * [Related conversation]() ---- ## Real-time notes _Note Taker:_ Sean Coughlin _SNARKs Background:_ Properties: Succinct, non-interactive, knowledge soundness Public vs. Designated verifier Will discuss pre-processing non-updatable SNARKs; will allow for more complexity than Groth16 (ECRH = Extractable Crash-Resistant Hash function) Encodings must be secure under knowledge assumtions Considering arithmatical and Boolean circuit satisfiability, abstractly a circuit over a field vs a circuit over a ring Transforming a circuit over a ring to a circuit over a field: bit decomposition costs, ... C?... Pinocchio is over a field, with Rinocchio over a ring Applications: * Verifiable computation on encrypted data * Anonymous credentials using RSA signatures _Framework:_ Proving NP statements: circuit satisfiability is finding a set of polynomials that solve ... Polynomial problem: reduce statement of all polynomials into proving at a secret point using CRS, polynomial will encode proof The encoding properties are linearly homomorphic, quadratic root detection, image verifcation QAP: find solution of quadratic arithmatic problem using secret point, so can convince verifier that prover know the witnesses Schwartz-Zippel Lemma over fields Encodings over fields: DLog problem allows for field General encoding: encoding needs to be linearly homomorphic Quadratic Root detection (with pairings): public verifier can be public, while designated verifier needs a secret key Assumptions on DL encodings for fields: d-PKE vs d-PDH _Construction of SNARKs for ring arithmatic:_ Polynomial EQ with coefficients in rings: isomorphism for QRP soundness equivalent to ideals being co-prime Exceptional sets: have uniqueness but have no algebraic structure Schwartz-Zippel Lemma over fields: ... Assumptions on DL encodings for rings: d-PKE vs d-PDH Ring-augmented PDH assumptions on rings: PDH: s in field extension, PDH: s in exceptional set extension (subset of ring) Encoding instance for ring Z_{2^k}: need sample from d-1 (degree of Galois extension) Encoding instance for ring R_q = Z_q[h]... This is designated-verifier (except for special cases where we have pairings). _Conclusions:_ QAP and SNARKs over fields: many implemenations, not standardized Rinocchio: SNARKs for ring arithmatic, Open questions: ## Questions: - Quadratic Ring Programs (QRP) as an abstraction capturing circuit satisfiability/R1CS over commutative rings. QRPs recover previous abstractions such as QAPs (by instantiating the ring with a field) and QPPs (as in the Trueset paper). They furthermore allow to build SNARKs for ring arithmetic as we show in our work. - Security assumptions when generalizing over rings. Linear-only extractable vs q-PDH & q-PKE. - Generally speaking: Interfacing QRPs and SNARKs over rings with existing interfaces in the standards. - Daira: can we have pairings over rings? Anca: we can have composite ground for pairings - Mary: are there any problems in ring that are not secure in field? Anca: can have QAP solutions that are not solutions to ring - Daira: Can we have more information on the encryption? Anca & Eduardo: security depends on the size exceptional set, which is proportional to the QAP. - Carla: What about interactive settings (to remove designated verifier)? Eduardo: can use Fiat-Shamir, etc. Daniel: Use FS to go NI? Carla: Latices have issues with NI due to encoding. Eduardo & Jonathan B.: Latices, Bulletproofs can do the same with rings with suitable encoding, interactive proofs possible but more complex with rings & there may be no need for exceptional sets. - Daira: Have there been concrete comparisons? Anca: Don't have complete practical implementation. The overhead will be in the encoding scheme, parallel implementation, etc. Too early to estimate. - Daniel: How efficient can these be for ring-enherent operations? (Sieve program could be more efficient.) Daria: The costs are in the reductions, not the multiplications. In R1CS, 1 gate per bit; two times the size of modulus. In PLONK/Plookup can use lookup table to reduce multiples at once. (More efficient in rows than R1CS gates, but not equivalent.) Estimate approximately a factor of 100 times the cost. Eduardo: RSA costs... Anca: Lookup tables can be efficient. Daira: Lookup tables can improve due to parallalism, so 2^2 and 2^20 have similar costs. - Daniel: How close are the assumptions to ring RLE assumptions? Eduardo: There's different ways to instantiate the encodings, which are basically linearly homomorphic encryption schemes (take that statement with a pinch of salt). We have one encoding based on RLWE. - Daniel: How close are we to standardizing/documentating? Daira: We're not close yet. Mary: Can standardize ring arithmatic in circuit. Daniel: Document SNARKs over rings, example that compares ring SNARK vs field SNARK? Daira: Implementors need to know if standard exists or if customization needed. Eduardo: Paper shows that if we have the exceptional set then we can build the SNARK. We could prove that ... ideals will not be co-prime. - Pratyush: QAPs are restricted to setup-based SNARKs. Research has more opportunitied to move away from these. Jonathan: Polynomial QAPs defined over ... require exceptional set. - Mary & Daira: Do we need to know the order of the group, considering groups of unknown order, hidden order, composite groups? Anca & Eduardo: Paper does not cover that. Chaya: Possible that can be covered, but would likely require exceptional sets. Carla: In RSA, order is unknown but structure is known, so it's possible to have an exceptional set. Anca: If we have an exceptional set at definition then we can do this. Daira: Does exceptional set leak information about the group? Anca: Unknown, but this should be researched. Jonathan: If a non-exceptional set is provided and an exception is found then the group information can be discovered. (You can solve the hard problem.) - Daniel: Are these discussions mature enough to create working group, or instead a stand-alone section in the standard document ready to be worked on? Vote is to create working group. Anca will create Telegram group and prepare for discussion, in 1 week.