Efficient modular exponentiation-based puzzles for denial-of-service protection

A new client puzzle based on modular exponentiation.


Client puzzles are moderately-hard cryptographic problems—neither easy nor impossible to solve—that can be used as a countermeasure against denial of service attacks on network protocols. Puzzles based on modular exponentiation are attractive as they provide important properties such as non-parallelisability, deterministic solving time, and linear granularity. We propose an efficient client puzzle based on modular exponentiation. Our puzzle requires only a few modular multiplications for puzzle generation and verification. For a server under denial of service attack, this is a significant improvement as the best known non-parallelisable puzzle proposed by Karame and Čapkun (ESORICS 2010) requires at least 2k-bit modular exponentiation, where k is a security parameter. We show that our puzzle satisfies the unforgeability and difficulty properties defined by Chen et al. (Asiacrypt 2009). We present experimental results which show that, for 1024-bit moduli, our proposed puzzle can be up to 30x faster to verify than the Karame-Čapkun puzzle and 99x faster than the Rivest et al.'s time-lock puzzle.

Keywords: client puzzles, time-lock puzzles, denial of service resistance, RSA, puzzle difficulty


Jothi Rangasamy, Douglas Stebila, Colin Boyd, Juan González Nieto, Lakshmi Kuppusamy. Efficient modular exponentiation-based puzzles for denial-of-service protection. In Howon Kim, editor, Proc. 14th International Conference on Information Security and Cryptology (ICISC) 2011, LNCS, vol. 7259, pp. 319-331. Springer, November 2011. © Springer.





This research was supported by:
  • Australia–India Strategic Research Fund (AISRF) project TA020002