### Non-Malleable Time-Lock Puzzles and Applications

Cody Freitag, Ilan Komargodski, Rafael Pass, and Naomi Sirkin

##### 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: (1) The first fair non-interactive multi-party protocols for coin flipping and auctions in the plain model without setup. (2) 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).

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2021
Keywords
Time-lock puzzlesNon-malleableCoin-flipping
Contact author(s)
nephraim @ cs cornell edu
cfreitag @ cs cornell edu
History
2021-10-25: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/779

CC BY

BibTeX

@misc{cryptoeprint:2020/779,
author = {Cody Freitag and Ilan Komargodski and Rafael Pass and Naomi Sirkin},
title = {Non-Malleable Time-Lock Puzzles and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2020/779},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/779}},
url = {https://eprint.iacr.org/2020/779}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.