Cryptology ePrint Archive: Report 2009/607
Efficient Client Puzzles based on Repeated-Squaring
Ghassan O. Karame and Srdjan Capkun
Abstract: In this paper, we propose a new, non-parallelizable verification-efficient client puzzle. Our puzzle is based on repeated-squaring and enables efficient verification of the puzzle solution that is reported by the client (prover). Client puzzles based on repeated-squaring were first proposed by Rivest et al. and constitute one of the first examples of non-parallelizable puzzles.
The main drawback of these puzzles was their high verification overhead. In this work, we show how this overhead can be significantly reduced by transferring the puzzle verification burden to the prover that executes the puzzle. Given a 1024-bit modulus, the improvement gain in the verification overhead of our puzzle when compared to the original repeated-squaring puzzle
is almost 50 times. We achieve this by embedding a secret
-- only known to the verifier -- within the Euler trapdoor function
that is used in repeated-squaring puzzles. We provide a security proof for this construction. We further show how our puzzle can be integrated in a number of protocols, including those used for efficient protection against DoS attacks and for the remote verification of the computing performance of devices. We validate the performance of our puzzle on a large number of PlanetLab nodes.
Category / Keywords: cryptographic protocols / Cryptographic Puzzles
Date: received 8 Dec 2009, withdrawn 1 Mar 2010
Contact author: karameg at inf ethz ch
Available formats: (-- withdrawn --)
Version: 20100301:225543 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]