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