Denial of Service (DoS) vulnerabilities are one of the major concerns in today's internet. Client-puzzles offer a good mechanism to defend servers against DoS attacks. In this paper, we introduce the notion of hidden puzzle difficulty, where the attacker cannot determine the difficulty of the puzzle without expending a minimal amount of computational resource. We propose three concrete puzzles that satisfy this requirement. Using game theory, we show that a defense mechanism is more effective when it uses a hidden difficulty puzzle. Based on the concept of Nash equilibrium, we develop suitable defense mechanisms that are better than the existing ones. © Springer-Verlag Berlin Heidelberg 2010.