International Association
for Cryptologic Research

Digital signatures underpin identity, authenticity, and trust in modern systems. Advanced variants of signatures—such as proofs of possession, ring signatures, and threshold signatures—offer security, privacy, and anonymity benefits but are rarely deployed due to incompatibility with widely used legacy schemes. This talk explores how to transform these legacy signatures— concretely, RSA, ECDSA, Ed25519, and the new NIST standards Falcon and Dilithium— into advanced variants using zkSNARKs. Making our zkSNARK-based schemes practical requires closing a huge efficiency gap that stems from, roughly, the cost of proving signature verification using the zkSNARK. We will present optimized protocols for expensive parts of signature verification, such as hashing and elliptic curve scalar multiplication. Using our techniques, we can generate a 240-byte proof of possession of an RSA signature over a message the size of a typical TLS certificate—two kilobytes—in only three seconds; the proof takes only 28 milliseconds to verify.

Vector commitment (VC) schemes allow one to commit concisely to an ordered sequence of values, so that the values at desired positions can later be proved concisely. In addition, a VC can be statelessly updatable, meaning that commitments and proofs can be updated to reflect changes to individual entries, using knowledge of just those changes (and not the entire vector). VCs have found important applications in verifiable outsourced databases, cryptographic accumulators, and cryptocurrencies. However, to date there have been relatively few post-quantum constructions, i.e., ones that are plausibly secure against quantum attacks. More generally, functional commitment (FC) schemes allow one to concisely and verifiably reveal various functions of committed data, such as linear functions (i.e., inner products, including evaluations of a committed polynomial). Under falsifiable assumptions, all known functional commitments schemes have been limited to ``linearizable'' functions, and there are no known post-quantum FC schemes beyond ordinary VCs. In this work we give post-quantum constructions of vector and functional commitments based on the standard Short Integer Solution lattice problem (appropriately parameterized): \begin{itemize} \item First, we present new statelessly updatable VCs with significantly shorter proofs than (and efficiency otherwise similar to) the only prior post-quantum, statelessly updatable construction (Papamanthou \etal, EUROCRYPT 13). Our constructions use private-key setup, in which an authority generates public parameters and then goes offline. \item Second, we construct functional commitments for \emph{arbitrary (bounded) Boolean circuits} and branching programs. Under falsifiable assumptions, this is the first post-quantum FC scheme beyond ordinary VCs, and the first FC scheme of any kind that goes beyond linearizable functions. Our construction works in a new model involving an authority that generates the public parameters and remains online to provide public, reusable ``opening keys'' for desired functions of committed messages. \end{itemize}