Douglas Stebila

Effort-release public-key encryption from cryptographic puzzles

Construction of an effort-released KEM from public key encryption and a client puzzle.

Abstract

Timed-release cryptography addresses the problem of “sending messages into the future”: a message is encrypted so that it can only be decrypted after a certain amount of time, either (a) with the help of a trusted third party time server, or (b) after a party performs the required number of sequential operations. We generalise the latter case to what we call effort-release public key encryption (ER-PKE) where only the party holding the private key corresponding to the public key can decrypt, and only after performing a certain amount of computation which may or may not be parallelisable. Effort-release PKE generalises both the sequential-operation-based timed-release encryption of Rivest, Shamir, and Wagner, and also the encapsulated key escrow techniques of Bellare and Goldwasser.

We give a generic construction for ER-PKE based on the use of moderately hard computational problems called puzzles. Our approach extends the KEM/DEM framework for public key encryption by introducing a difficulty notion for KEMs which results in effort-release PKE. When the puzzle used in our generic construction is non-parallelisable, we recover timed-release cryptography, with the addition that only the designated receiver (in the PKE setting) can decrypt.

Keywords: puzzles, difficulty, timed-release encryption, key escrow

Reference

Jothi Rangasamy, Douglas Stebila, Colin Boyd, Juan González Nieto, Lakshmi Kuppusamy. Effort-release public-key encryption from cryptographic puzzles. In Willy Susilo, Yi Mu, Jennifer Seberry, editors, Proc. 17th Australasian Conference on Information Security and Privacy (ACISP) 2012, LNCS, vol. 7372, pp. 194-207. Springer, July 2012. © Springer.

Download

BibTeX

@inproceedings{ACISP:RSBGK12,
 	Author = {Jothi Rangasamy and Douglas Stebila and Colin Boyd and Juan {Gonz{\' a}lez Nieto} and Lakshmi Kuppusamy},
 	Booktitle = {Proc. 17th Australasian Conference on Information Security and Privacy (ACISP) 2012},
 	Doi = {10.1007/978-3-642-31448-3\_15},
 	Editor = {Willy Susilo and Yi Mu and Jennifer Seberry},
 	Month = {July},
 	Pages = {194--207},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Effort-release public-key encryption from cryptographic puzzles},
 	Volume = {7372},
 	Year = {2012}
 }

Funding

• Australia–India Strategic Research Fund (AISRF) project TA020002