We put forth the notion of efficient dual receiver cryptosystems and implement it based on bilinear pairings over certain elliptic curve groups. The cryptosystem is simple and efficient yet powerful, as it helps to solve two problems of practical importance whose solutions had proven to be elusive until now: (1) A provably secure “combined” public-key cryptosystem (with a single secret key per user) where the key is used for both decryption and signing and where encryption can be escrowed and recovered, while the signature capability never leaves its owner. This is an open problem proposed by the work of Haber and Pinkas. (2) A puzzle is a method for ratelimiting remote users by forcing them to solve a computational task (the puzzle). Puzzles have been based on cryptographic challenges in the past, but the successful design of embedding a useful cryptographic task inside a puzzle, originally posed by Dwork and Naor, has remained problematic. We model and present “useful security puzzles” applicable as an online transaction server (such as a Web server).
['Ted Diament', 'Homin K. Lee', 'Angelos D. Keromytis', 'Moti Yung']
The Efficient Dual Receiver Cryptosystem and Its Applications