Date Added: Jun 2010
RFID authentication protocols are susceptible to different types of relay attacks such as mafia and distance frauds. A countermeasure against these types of attacks are the well-known distance-bounding protocols. These protocols are usually designed to resist to only one of these frauds, though, behave poorly when both are considered. In this paper, the authors extend the analysis of mafia and distance frauds in recently released protocols. They introduce the concept of distance-bounding protocols based on graphs while previous proposals rely on linear registers or binary trees. They propose an instance of the graph-based protocol that resists to both mafia and distance frauds without sacrificing memory.