A Highly Efficient RFID Distance Bounding Protocol without Real-Time PRF Evaluation

There is a common situation among current distance bounding protocols in the literature: they set the fast bit exchange phase after a slow phase in which the nonces for both the reader and a tag are exchanged. The output computed in the slow phase is acting as the responses in the subsequent fast phase. Due to the calculation constrained RFID environment of being lightweight and efficient, it is the important objective of building the protocol which can have fewer number of message flows and less number of cryptographic operations in real time performed by the tag. In this paper, we propose a new highly efficient mutually-authenticated RFID distance bounding protocol that enables pre-computation which is carried out off-line by the tag. There is no evaluation on any PRF during the real time protocol running which makes the tag significantly more efficient at a low-cost. The protocol requires only O(1) complexity for achieving tag privacy. In addition, we give a detailed security analysis to prove that our protocol is secure against all common attacks in distance bounding.