A guided tour puzzle for denial of service prevention

Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle¹, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n-piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.