#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
• Miro whiteboard frame
• Additional related 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.