- Rinocchio: SNARKs for Ring Arithmetic
Chaya Ganesh, Anca Nitulescu, Eduardo Soria-Vazquez
Journal of Cryptology 2023
ePrint
     
Code
     
Slides
     
Talk
Abstract.
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 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 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 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 pre-existent assumptions employed in field-restricted 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 Ring-LWE-based homomorphic encryption schemes.
In the second one, we use Rinocchio to naturally prove statements about circuits over rings that closely match real-life computer architectures
such as standard CPUs.
- Linear-map 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 state-of-the-art 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 pairing-based
“powers of tau” run by real-world systems such as ZCash or Filecoin). Our implementation demonstrates that our work
over-performs 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 position-hiding vector commitment scheme: one can prove in zero-knowledge 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 multi-membership 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 Fiat-Shamir 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 zero-knowledge SNARKs (Plonk, Sonic, and Marlin) are
updatable SRS simulation extractable NIZKs and signatures of knowledge (SoK) out-of-the-box avoiding any
compilation overhead.
Towards this we generalize results for the Fiat–Shamir (FS) transformation, which turns interactive protocols
into signature schemes, non-interactive 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 multi-round 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 (trapdoor-less zero-knowledge, rewinding-based knowledge soundness, and a unique
response property) that are sufficient for argument systems based on multi-round 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 pairing-based 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 real-world FHE parameters
and even RNS-based 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 two-party 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 Hall-Andersen, Anca Nitulescu,
Elena Pagnin, Sophia Yakoubov
PKC 2022: The Public Key Cryptography
ePrint
     
Code
     
Slides
     
Talk
- Stronger Security and Constructions for Multi-Designated 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 Public-Key Cryptography
ePrint
     
Slides
     
Talk
- Lattice-Based zk-SNARGs for Arithmetic Circuits
Anca Nitulescu
Latincrypt 2019
ePrint
     
Springer
     
Slides
- Lattice-Based zk-SNARKs 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 2016-B: Theory of Cryptography Conference
Springer
     
ePrint
     
Slides
-
Robust Password-Protected 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.
Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are non-interactive 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 zk-SNARKs. 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 zk-SNARKs from first constructions to recent efficient
schemes. For the latter, it provides a modular presentation of the frameworks for state-of-the-art SNARKs.
- SoK: Vector Commitments
Work in Progress
     
Slides