**#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.