Paper 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.