Paper 2020/779

Non-Malleable Time-Lock Puzzles and Applications

Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass

Abstract

We introduce and construct a variant of a time-lock puzzle which is non-malleable. A non-malleable time-lock puzzle guarantees, roughly, that it is impossible to "maul" a puzzle into one for a related message without solving it. The security of this construction relies on the existence of any (plain) time-lock puzzle and it is proven secure in the auxiliary-input random oracle model. We show that our construction satisfies bounded concurrency and prove that it is impossible to obtain full concurrency. We additionally introduce a more general non-malleability notion, termed functional non-malleability, which protects against tampering attacks that affect a specific function of the related messages. We show that in many (useful) cases, our construction satisfies fully concurrent functional non-malleability. We use our (functional) non-malleable time-lock puzzles to give efficient multi-party protocols for desirable tasks such as coin flipping and auctions. Our protocols are (1) fair, meaning that no malicious party can influence the output, (2) optimistically efficient, meaning that if all parties are honest, then the protocol terminates immediately, and (3) publicly verifiable, meaning that from the transcript of the protocol anyone can quickly infer the outcome, without the need to perform a long computation phase. Our protocols support an unbounded number of participants and require no adversary-independent trusted setup. Our protocol is the first protocol that satisfies all of the above properties under any assumption. Security is proven assuming the repeated squaring assumption and in the auxiliary-input random oracle model. Along the way, we introduce a publicly verifiable notion of time-lock puzzles which is of independent interest. This notion allows the solver of the puzzle to compute the solution together with a proof which can be quickly verified by anyone.