Time-Lock Puzzles from Randomized Encodings

Authors: Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, Brent Waters - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science 2015 cited by 108

Time-lock puzzles are a mechanism for sending messages “to the future”. A sender can quickly generate a puzzle with a solution s that remains hidden until a moderately large amount of time t has elapsed. The solution s should be hidden from any adversary that runs in time significantly less than t, including resourceful parallel adversaries with polynomially many processors. While the notion of time-lock puzzles has been around for 22 years, there has only been a single candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an “inherently sequential ” computation. We show that various flavors of randomized encodings give rise to time-lock puzzles of varying strengths, whose security can be shown assuming the existence of non-parallelizing languages, which are languages that require circuits of depth at least t to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles. We instantiate the construction with different randomized encodings from the literature,