english only
School of Computer and Communication Sciences
LASEC - Security and Cryptography Laboratory
EPFL > IC > LASEC > publications
Banner IC
INDEX
Home
People
Research
Teaching
Publications
Softwares & Events
Intranet
How to reach us

CONTACT

EPFL - I&C - ISC - LASEC
Station 14 - Building INF
CH-1015 Lausanne
Switzerland

Tel. +41 21 693 7603
Fax. +41 21 693 7689

Ref: ADO05


Reducing Time Complexity in RFID Systems
Gildas Avoine, Etienne Dysli, and Philippe Oechslin

Published:
The 12th Annual Workshop on Selected Areas in Cryptography (SAC'05), Kingston, Canada, August 11 & 12, 2005, LNCS, Springer-Verlag, 2005

Abstract:
Radio frequency identification systems based on low-cost computing devices is the new plaything that every company would like to adopt. Its goal can be either to improve the productivity or to strengthen the security. Specific identification protocols based on symmetric challenge-response have been developed in order to assure the privacy of the device bearers. Although these protocols fit the devices' constraints, they always suffer from a large time complexity. Existing protocols require O(n) cryptographic operations to identify one device among n. Molnar and Wagner suggested a method to reduce this complexity to O(log n). We show that their technique could degrade the privacy if the attacker has the possibility to tamper with at least one device. Because low-cost devices are not tamper-resistant, such an attack could be feasible. We give a detailed analysis of their protocol and evaluate the threat. Next, we extend an approach based on time-memory trade-offs whose goal is to improve Ohkubo, Suzuki, and Kinoshita's protocol. We show that in practice this approach reaches the same performances as Molnar and Wagner's method, without degrading privacy.


Download   [HTTP]

© 2011, EPFL