Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A Highly Scalable RFID Authentication Protocol
verfasst von : Jiang Wu, Douglas R. Stinson
Erschienen in: Information Security and Privacy
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
In previous RFID protocols, a hash-chain is used to achieve good privacy. Each tag is associated with a chain of
Q
hash values. To identify one tag out of a total of
N
tags, a server searches a table of size
NQ
. A naive search takes either
Θ
(
NQ
) time or
Θ
(
NQ
) memory, and therefore it does not scale well. A time-space tradeoff technique can mitigate the scalability problem. However, with the time-memory tradeoff, either time or space is still at least
Θ
((
NQ
)
2/3
).
In this paper, we propose a novel RFID protocol to solve the scalability problem. The server “solves”, instead of “searches”, for a tag ID. The protocol is based on polynomial operations, and its security and privacy is based on the difficulty of reconstructing a polynomial with noisy data. The protocol supports very large values of the product
NQ
. In our demo implementation where
N
= 2
32
and
Q
= 13700, the server takes 0.1 seconds and 10K bytes memory to identify a tag. As a comparison, a hash-chain based protocol enhanced with a time-memory tradeoff will require about 67 seconds and a 1G bytes memory.