- ProtogaLattice: Constant-Round Lattice-based Folding for
General Polynomial Relations
David Balbás, Anca Nitulescu, Maxime Plançon
To appear - talk in ZKProof 8, May 2026
Abstract.
Folding schemes are gaining traction recently as they unlock practical instantiations of
incrementally verifiable computation (IVC) and proof-carrying data (PCD). In particular, there has
been a growing interest in folding schemes for high-degree relations, as these can efficiently arithmetize
complex computations. While the landscape of folding schemes is vast, all existing constructions based
on lattices, such as Latticefold+ [Boneh & Chen, CRYPTO’ 25] and Neo [Nguyen & Setty, ’25], heavily
rely on the sumcheck protocol. Sumcheck leads to very efficient proving times, but also presents draw-
backs: the folded relations must be expressed by products of multilinear polynomials, and the verifier
circuits become very large, partially because of the many random oracle calls required. The latter in-
curs a significant overhead when building IVC and PCD, as the prover must prove the execution of the
verifier circuit at every iteration.
We present ProtogaLattice, a new lattice-based folding scheme for general high-degree polynomial
relations that drastically reduces the size of the verifier’s circuits. We deviate from the sumcheck
approach and instead take inspiration from Protostar [Bünz & Chen, Asiacrypt ’24] and Protogalaxy
[Eagen & Gabizon ’23], which fold witnesses using algebraic techniques in a constant number of rounds.
Our contribution is threefold: (1) a novel technique to achieve PCD through Protogalaxy, which we find
of interest also in the classical (i.e. pairing-based) setting, (2) a folding scheme that combines multiple
instances of polynomial relations into accumulators, and (3) a bootstrapping protocol to reduce the
norm of the witnesses underlying these accumulators. A full iteration of ProtogaLattice requires only
four random oracle calls (not counting the overhead induced by the extra range proof used as a black-
box). Our techniques open new directions towards building lattice-based proofs that support more
expressive relations and that present smaller recursion overheads.
- Crossing with Confidence: Formal Analysis and
Model Checking of Blockchain Bridges
Pyrros Chaidos, Pooya Farshim, Denis Firsov, D. Jetchev, Aggelos Kiayias, Markulf Kohlweiss, Anca Nitulescu
ePrint
Abstract.
We develop formal code-based security definitions for
blockchain bridges and apply them to several bridge architectures
deployed in practice. We derive both traditional pen-and-paper
proofs and on the other, automated guarantees against bounded
counterexamples. The latter is achieved via bounded model
checking of our formally specified properties, implemented in
Quint, a specification language and model checker closely related
to TLA+.
Our definitions are expressed in a precise, code-based variant
of the Universal Composition (UC) framework. This enables the
modular use of hybrid functionalities—even for property-based
definitions—and is essential for bounded model checking, where
underlying primitives must be idealized.
Accordingly, we idealize and model-check all building blocks
used in our protocols. Notably, we formulate a novel UC ideal
functionality for Advanced Threshold Signatures (ATS) and modelcheck it for attacks to ensure its robustness.
Index Terms—Formal Security, Universal Composition, Model Checking, Blockchain Bridges, Advanced Threshold Signatures.
- FLIP-and-prove R1CS
Anca Nitulescu, Nikitas Paslis, Carla RÃ fols
IACR Communications in Cryptology 2025 Volume 2 Issue 4
ePrint
Slides
Talk
Abstract.
In this work, we consider the setting where one or more users with low computational resources would lie to outsource
the task of proof generation for SNARKs to one external entity, named Prover.
We study the scenario in which Provers have access to all statements and witnesses to be proven beforehand. We take a different approach to proof
aggregation and design a new protocol that reduces simultaneously proving
time and communication complexity, without going through recursive proof composition.
Our two main contributions: We first design FLIP, a communication efficient folding scheme
where we apply the Inner Pairing Product Argument to fold R1CS instances of the same language into
a single relaxed R1CS instance. Then, any proof system for relaxed R1CS language can be
applied to prove the final instance. As a second contribution,
we build a novel variation of Groth16 with the same communication complexity for
relaxed R1CS and two extra pairings for verification, with an adapted trusted setup.
Compared to SnarkPack - a prior solution addressing scaling for multiple Groth16 proofs - our scheme improves
in prover complexity by orders of magnitude, if we consider the total cost to generated the SNARK proofs
one by one and the aggregation effort.
An immediate application of our solution is Filecoin, a decentralized storage network based on incentives that
generates more than 6 million SNARKs for large circuits of 100 million constraints per day.
- Anonymous, Timed and Revocable Proxy Signatures
Ghada Almashaqbeh, Anca Nitulescu
ISC 2024 Best Paper Award
ePrint
Abstract.
A proxy signature enables a party to delegate her signing power to another. This is useful in practice to achieve goals related to
robustness, crowd-sourcing, and workload sharing. Such applications, especially in the blockchain model, usually require delegation to satisfy
several properties, including time bounds, anonymity, revocability, and policy enforcement. Despite the large amount of work on proxy signatures
in the literature, none of the existing schemes satisfy all these properties;
even there is no unified formal notion that captures them.
In this work, we close this gap and propose RelaySchnorr, an anonymous,
timed, and revocable proxy signature scheme. We achieve this in two steps:
First, we introduce a tokenizable digital signature based on Schnorr
signature allowing for secure distribution of signing tokens. Second, we
utilize a public bulletin board, instantiated as a blockchain, and timelock encryption to support:
(1) one-time usage of the signing tokens by tracking
tokens used so far based on unique values associated to them,
(2) timed delegation so that a proxy signer cannot sign outside a given period, and
(3) delegation revocation allowing the original signer to end a delegation earlier than provisioned. All of these are done in a decentralized and
anonymous way so that no one can tell that someone else signed on behalf
of the original signer or even that a delegation took place.
We define a formal notion for proxy signatures capturing all these properties, and
prove that our construction realizes this notion. We also discuss several
design considerations addressing issues related to deployment in practice.
- Rinocchio: SNARKs for Ring Arithmetic
Chaya Ganesh, Anca Nitulescu, Eduardo Soria-Vazquez
Journal of Cryptology 2023
ePrint
Code
Slides
Talk
- 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
- 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
- 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
- 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
- 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.
- Book Chapter: SNARKs
to appear
Full Book
