“Now you don’t see it, now you do”: time-lock puzzles and fair exchange

Thesis

Time-Release Encryption (TRE) is a cryptographic scheme designed to conceal messages for a predetermined duration. Constructing practical TRE schemes without relying on external parties typically involves Time-Lock Puzzles (TLPs) – unparallelisable computational challenges with predictable solving times. The solution to a TLP reveals the hidden message. This thesis investigates the potential of TLPs in two key areas.

First, we address a gap in the literature by constructing an efficient, practical, and quantum-secure TLP. We build upon the widely used concept of repeated squaring in RSA moduli, but modify the approach by performing these operations modulo a prime number. To further enhance security, we chain together multiple exponentiations using random permutations. The resulting TLP retains most of the efficiency of existing repeated-squaring-based puzzles while offering stronger security guarantees, particularly against attacks from quantum computers.

Second, we apply TLPs to the problem of fair exchange. This problem involves two or more parties, each holding a secret item, and explores how they can exchange these items while ensuring that no one cheats. Traditionally, exchanging secrets without a trusted neutral party is considered impossible. However, the field of partial fairness aims to design protocols that achieve some probability of fairness in all situations. By leveraging TLPs, we overcome previous limitations and significantly improve the round efficiency of fair exchange protocols. Specifically, we present 2-party and multi-party protocols that achieve optimal fairness, meaning no shorter protocol can offer a higher chance of a successful and fair exchange.

Authors: Maffei, I

• DOI: 10.5287/ora-x579qqeed
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: commutative encryption; time-lock puzzle; fair exchange; multi-party computation; partial fairness
• Subjects: Computer security