Generic Delay Functions: Equivalence to Factoring in RSA Groups and an Impossibility Result in Known-Order Groups

Lior Rotem


Despite the fundamental importance of delay functions, the main known delay function which offers both sufficient structure for realizing time-lock puzzles and verifiable delay functions, as well as a realistic level of practicality is the “iterated squaring” function of Rivest, Shamir and Wagner in hidden-order groups. The challenges of basing the sequentiality of iterated squaring on well-established assumptions, or of constructing new delay functions in well-understood cyclic groups of known order, have remained open for over two decades. In this talk, I will present both upper bounds, connecting the sequentiality of iterated squaring in RSA groups to the factoring assumption, and a lower bound, ruling out the existence of generic-group delay functions in cyclic groups of known order.

This talk is based on joint works with Gil Segev and Ido Shahaf.

Time and Place

Tuesday, March 23, 12:00pm