2006 | OriginalPaper | Buchkapitel
Reducing Time Complexity in RFID Systems
verfasst von : Gildas Avoine, Etienne Dysli, Philippe Oechslin
Erschienen in: Selected Areas in Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.