Low-cost client puzzles based on modular exponentiation

Ghassan O. Karame, Srdjan Čapkun

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    Client puzzles have been proposed as a useful mechanism for mitigating Denial of Service attacks on network protocols. While several puzzles have been proposed in recent years, most existing non-parallelizable puzzles are based on modular exponentiations. The main drawback of these puzzles is in the high cost that they incur on the puzzle generator (the verifier). In this paper, we propose cryptographic puzzles based on modular exponentiation that reduce this overhead. Our constructions are based on a reasonable intractability assumption in RSA: essentially the difficulty of computing a small private exponent when the public key is larger by several orders of magnitude than the semi-prime modulus. We also discuss puzzle constructions based on CRT-RSA [11]. Given a semi-prime modulus N, the costs incurred on the verifier in our puzzle are decreased by a factor of when compared to existing modular exponentiation puzzles, where k is a security parameter. We further show how our puzzle can be integrated in a number of protocols, including those used for the remote verification of computing performance of devices and for the protection against Denial of Service attacks. We validate the performance of our puzzle on PlanetLab nodes.

    Original languageEnglish
    Title of host publicationComputer Security, ESORICS 2010 - 15th European Symposium on Research in Computer Security, Proceedings
    Pages679-697
    Number of pages19
    Volume6345 LNCS
    DOIs
    Publication statusPublished - 2010
    Event15th European Symposium on Research in Computer Security, ESORICS 2010 - Athens, Greece
    Duration: 20 Sept 201022 Sept 2010

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6345 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other15th European Symposium on Research in Computer Security, ESORICS 2010
    Country/TerritoryGreece
    CityAthens
    Period20/09/1022/09/10

    Keywords

    • Client Puzzles
    • DoS Attacks
    • Outsourcing of Modular Exponentiation
    • Secure Verification of Computing Performance

    Fingerprint

    Dive into the research topics of 'Low-cost client puzzles based on modular exponentiation'. Together they form a unique fingerprint.

    Cite this