CryptoDB
Naomi Sirkin
Publications
Year
Venue
Title
2022
TCC
Parallelizable Delegation from LWE
Abstract
We present the first non-interactive delegation scheme for P with time-tight parallel prover
efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation
scheme—which we refer to as a SPARG (succinct parallelizable argument)—the prover’s parallel
running time is t + polylog(t), while using only polylog(t) processors and where t is the length
of the computation. (In other words, the proof is computed essentially in parallel with the
computation, with only some minimal additive overhead in terms of time).
Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P
assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent
delegation construction of Choudhuri, Jain, and Jin (FOCS’21) and combines it with techniques
from Ephraim et al (EuroCrypt’20).
We next demonstrate how to make our SPARG time-independent—where the prover and
verifier do not need to known the running-time t in advance; as far as we know, this yields
the first construction of a time-tight delegation scheme with time-independence based on any
hardness assumption.
We finally present applications of SPARGs to the constructions of VDFs (Boneh et al,
Crypto’18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard
function).
2021
TCC
Non-Malleable Time-Lock Puzzles and Applications
📺
Abstract
Time-lock puzzles are a mechanism for sending messages "to the future", by allowing a sender to quickly generate a puzzle with an underlying message that remains hidden until a receiver spends a moderately large amount of time solving it. We introduce and construct a variant of a time-lock puzzle which is non-malleable, which roughly guarantees that it is impossible to "maul" a puzzle into one for a related message without solving it.
Using non-malleable time-lock puzzles, we achieve the following applications:
- The first fair non-interactive multi-party protocols for coin flipping and auctions in the plain model without setup.
- Practically efficient fair multi-party protocols for coin flipping and auctions proven secure in the (auxiliary-input) random oracle model.
As a key step towards proving the security of our protocols, we introduce the notion of functional non-malleability, which protects against tampering attacks that affect a specific function of the related messages. To support an unbounded number of participants in our protocols, our time-lock puzzles satisfy functional non-malleability in the fully concurrent setting. We additionally show that standard (non-functional) non-malleability is impossible to achieve in the concurrent setting (even in the random oracle model).
Program Committees
- Crypto 2022
Coauthors
- Cody Freitag (2)
- Ilan Komargodski (1)
- Rafael Pass (2)