 Rinocchio: SNARKs for Ring Arithmetic
Chaya Ganesh, Anca Nitulescu, Eduardo SoriaVazquez
Journal of Cryptology 2023
ePrint
Code
Slides
Talk
Abstract.
Succinct noninteractive arguments of knowledge (SNARKs) enable noninteractive 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 choice of the prime order field
is limited by the existence of groups of matching order for which secure bilinear maps exist.
In this work we overcome such restrictions and enable verifying computations over rings.
We construct the first designatedverifier 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 such that their pairwise differences are invertible.
Our contribution is threefold:
We fist introduce Quadratic Ring Programs (QRPs) as a characterization
of NP where the arithmetic is over a ring.
Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT 2013), we design SNARKs over rings in a modular way.
We generalize preexistent assumptions employed in fieldrestricted SNARKs to encoding schemes over rings.
As our encoding notion is generic in the choice of the ring, it amenable to different settings.
Finally, we propose two applications for our SNARKs.
Our first application is verifiable computation over encrypted data, specifically for evaluations of RingLWEbased homomorphic encryption schemes.
In the second one, we use Rinocchio to naturally prove statements about circuits over rings that closely match reallife computer architectures
such as standard CPUs.
 Linearmap Vector Commitments and their Practical Applications
Matteo Campanelli, Anca Nitulescu, Carla Ràfols, Alexandros Zacharakis, Arantxa Zapico
Asiacrypt 2022
ePrint
Code
Slides
Talk
Abstract.
Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then “open” some of
its positions efficiently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized
networks of large size and whose content is dynamic. In this work, we examine the demands on the properties that an ideal
vector commitment should satisfy in the light of the emerging plethora of practical applications and propose new constructions
that improve the stateoftheart in several dimensions and offer new tradeoffs. We also propose a unifying framework that
captures several constructions and show how to generically achieve some properties from more basic ones.
On the practical side,
we focus on building efficient schemes that do not require new trusted setup (we can reuse existing ceremonies for pairingbased
“powers of tau” run by realworld systems such as ZCash or Filecoin). Our implementation demonstrates that our work
overperforms in efficiency prior schemes with same properties.
 Caulk: Lookup Arguments in Sublinear Time
Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, Mark Simkin
ACM CCS 2022
ePrint
Code
Slides
Talk
Abstract.
We present a new positionhiding vector commitment scheme: one can prove in zeroknowledge that one or m values
that comprise commitment cm all belong to the vector of size N committed to in C. It can be used for membership proofs and lookup arguments and
outperforms all existing alternatives in prover time by orders of magnitude.
For both single and multimembership proofs our construction Caulk beats SNARKed Merkle proofs by the factor of 100 even if the latter instantiated with Poseidon hash.
Asymptotically our prover needs O(m^{^2} + m log N) time to prove a batch of openings,
whereas proof size is O(1) and verifier time is O(log log N).
As a lookup argument, Caulk is the first scheme with prover time sublinear in the table size,
assuming O(N log N) preprocessing time and O(N) storage. It can be used as a subprimitive in
verifiable computation schemes in order to drastically decrease the lookup overhead.
Our scheme comes with a reference implementation and benchmarks.
 What Makes FiatShamir zkSNARKs
(Updatable SRS) Simulation Extractable?
Chaya Ganesh, Hamidreza Khoshakhlagh, Markulf Kohlweiss, Anca Nitulescu, Michał Zając
SCN 2022: Security and Cryptography for Networks
ePrint
Slides
Talk
Abstract.
We show that three popular universal zeroknowledge SNARKs (Plonk, Sonic, and Marlin) are
updatable SRS simulation extractable NIZKs and signatures of knowledge (SoK) outofthebox avoiding any
compilation overhead.
Towards this we generalize results for the Fiat–Shamir (FS) transformation, which turns interactive protocols
into signature schemes, noninteractive proof systems, or SoK in the random oracle model (ROM). The security
of the transformation relies on rewinding to extract the secret key or the witness, even in the presence of signing
queries for signatures and simulation queries for proof systems and SoK, respectively. We build on this line
of work and analyze multiround FS for arguments with a structured reference string (SRS). The combination
of ROM and SRS, while redundant in theory, is the model of choice for the most efficient practical systems to
date.
We also consider the case where the SRS is updatable and define a strong simulation extractability notion
that allows for simulated proofs with respect to an SRS to which the adversary can contribute updates.
We define three properties (trapdoorless zeroknowledge, rewindingbased knowledge soundness, and a unique
response property) that are sufficient for argument systems based on multiround FS to be also simulation
extractable in this strong sense. We show that Plonk, Sonic, and Marlin satisfy these properties, and conjecture
that many other argument systems such as Lunar, Basilisk, and transparent variants of Plonk fall within the
reach of our main theorem.
 MyOPE: Malicious securitY for Oblivious Polynomial
Evaluation
Malika Izabachène, Anca Nitulescu, Paola de Perthuis, David Pointcheval
SCN 2022: Security and Cryptography for Networks
ePrint
Slides
Talk
Abstract.
Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a
sender with a private polynomial and a receiver with a private evaluation point where the receiver
learns the evaluation of the polynomial in their point and no additional information. They are used
in Private Set Intersection (PSI) protocols.
We introduce a scheme for OPE in the presence of malicious senders, enforcing honest sender
behavior and consistency by adding verifiability to the calculations. The main tools used are FHE for
input privacy and arguments of knowledge for the verifiability property. MyOPE deploys sublinear
communication costs in the sender’s polynomial degree and one to five rounds of interaction.
In other words, it can be used as a verifiable computation scheme for polynomial evaluation over
FHE ciphertexts. While classical techniques in pairingbased settings allow generic succinct proofs
for such evaluations, they require large prime order subgroups which highly impact the communication complexity, and prevent the use of FHE with practical parameters. MyOPE builds on generic
secure encodings techniques that allow composite integers and enable realworld FHE parameters
and even RNSbased optimizations. It is best adapted for the unbalanced setting where the degree
of the polynomial and the computing power of the sender are large.
MyOPE can be used as a building block in specialized twoparty protocols such as PSI (this usecase is hereafter described), oblivious keyword search, set membership and more using the OPE
instantiation.
As another contribution, our techniques are generalized to applications other than OPE, such as
Symmetric Private Information Retrieval (SPIR), to make them secure against a malicious sender.
 SnarkPack: Practical SNARK Aggregation
Nicolas Gailly, Mary Maller, Anca Nitulescu
FC 2022: Financial Cryptography and Data Security
ePrint
Code
Slides
Talk
 Count Me In! Extendability for Threshold Ring Signatures
Diego Aranha, Mathias HallAndersen, Anca Nitulescu,
Elena Pagnin, Sophia Yakoubov
PKC 2022: The Public Key Cryptography
ePrint
Code
Slides
Talk
 Stronger Security and Constructions for MultiDesignated Verifiers Signatures
Ivan Damgård, Helene Haagh,
Rebekah Mercer,
Anca Nitulescu,
Claudio Orlandi,
Sophia Yakoubov
TCC 2020: Theory of Cryptography Conference
ePrint
Slides
Talk
 Boosting Verifiable Computation on Encrypted Data
Dario Fiore, Anca Nitulescu,
David Pointcheval
PKC 2020: Conference on Practice and Theory of PublicKey Cryptography
ePrint
Slides
Talk
 LatticeBased zkSNARGs for Arithmetic Circuits
Anca Nitulescu
Latincrypt 2019
ePrint
Springer
Slides
 LatticeBased zkSNARKs from Square Span Programs
Rosario Gennaro, Michele Minelli, Anca Nitulescu, Michele Orrù
CCS 2018: Conference on Computer and Communications Security
ePrint
Code
Slides
 On the (In)security of SNARKs in the Presence of Oracles
Dario Fiore, Anca Nitulescu
TCC 2016B: Theory of Cryptography Conference
Springer
ePrint
Slides

Robust PasswordProtected Secret Sharing
Michel Abdalla, Mario Cornejo, Anca Nitulescu, David Pointcheval
ESORICS 2016: European Symposium on Research in Computer Security
Springer
ePrint
Slides
 A Gentle Introduction to SNARKs
Survey
Slides
Talk
Abstract.
ZeroKnowledge Succinct Noninteractive Arguments of Knowledge (zkSNARKs) are noninteractive systems with short proofs
(i.e., independent of the size of the witness) that enable verifying NP computations with substantially lower complexity than that
required for classical NP verification. This is a short, gentle introduction to zkSNARKs. It recalls some important advancements in the
history of proof systems in cryptography following the evolution of the soundness notion, from first interactive proof systems to arguments of knowledge.
The main focus of this introduction is on zkSNARKs from first constructions to recent efficient
schemes. For the latter, it provides a modular presentation of the frameworks for stateoftheart SNARKs.
 SoK: Vector Commitments
Work in Progress
Slides