Paper 2011/665

Efficient Modular Exponentiation-based Puzzles for Denial-of-Service Protection

Jothi Rangasamy, Douglas Stebila, Lakshmi Kuppusamy, Colin Boyd, and Juan Gonzalez Nieto

Abstract

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 \etal{} (Asiacrypt 2009). We present experimental results which show that, for $1024$-bit moduli, our proposed puzzle can be up to $30 \times$ faster to verify than the Karame-Čapkun puzzle and $ 99 \times$ faster than the Rivest \etal's time-lock puzzle.

Note: to appear in ICISC 2011 proceedings

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
client puzzlestime-lock puzzlesdenial of service resistanceRSApuzzle difficulty
Contact author(s)
j rangasamy @ qut edu au
History
2011-12-09: received
Short URL
https://ia.cr/2011/665
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/665,
      author = {Jothi Rangasamy and Douglas Stebila and Lakshmi Kuppusamy and Colin Boyd and Juan Gonzalez Nieto},
      title = {Efficient Modular Exponentiation-based Puzzles for Denial-of-Service Protection},
      howpublished = {Cryptology ePrint Archive, Paper 2011/665},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/665}},
      url = {https://eprint.iacr.org/2011/665}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.