jpeg07
commented
3 years ago Emailed
Closed ninitrava closed 3 years ago
jpeg07
commented
3 years ago Emailed
jpeg07
commented
3 years ago Talk given, March 11, 2021
https://www.youtube.com/watch?v=j2czM2mvFi0&list=PLhuBigpl7lqu6xWpiXtbEzJQtlMH1tqoG&index=1
Research seminars are high level talks given by both PL and non-PL employees on topics relevant to the future of computing and internet technology.
The series launched in September 2019. Talks can be found here. If you have a suggestion on someone you would like to hear speak, please share below. If you would like to be notified of research talks in the future, please email research@protocol.ai.
Speaker name
Institution
Suggested topic
Relevant paper (if any)
Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the computation is done on encoded values where the encoding is exponentiation in a bilinear group, and therefore, the choice of the prime field is limited by the existence of groups of matching order for which secure bilinear maps exist.
In this work we construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements satisfying the property that their pairwise differences are invertible. Along the way, we introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring.
We also study and generalize pre-existent (knowledge-type) assumptions employed in field-restricted SNARKs to the ring context.
We propose two applications for our SNARKs. In the first one, we instantiate our construction for the Galois Rings that allows us to naturally prove statements about circuits over integers modulo 2^k, which closely matches real-life computer architectures such as standard CPUs. Our second application is verifiable computation over encrypted data, specifically on top of Ring-LWE-based homomorphic encryption schemes. Compared with the recent work by Fiore, Nitulescu and Pointcheval (PKC '20) we can efficiently support a broader class of polynomial rings, in particular those where the integer coefficients are not modulo a prime. This enables proving computations over homomorphic encryption schemes employing plaintext packing and modulus switching.
Relevant groups at PL