Low-complexity cryptographic techniques for use with radio frequency identification devices

1. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β i unique to a given pseudonym α i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ i unique to the given pseudonym α i transmitted by the RFID device; and

wherein at least one of the values α i , β i and γ i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.

2. The method of claim 1 wherein the transmitted pseudonyms are authenticated by the reader.

3. The method of claim 1 wherein the transmitted pseudonyms are authenticated by a verifier other than the reader.

4. The method of claim 1 wherein the RFID device is configured to authenticate itself to a verifier only after the verifier has authenticated itself to the RFID device.

5. The method of claim 1 wherein one or more of the pseudonyms each comprise an identifier of the RFID device.

6. The method of claim 1 wherein the pseudonyms are stored in the RFID device as an ordered list of pseudonyms, the method further including the steps of designating a particular one of the pseudonyms as a current pseudonym and, in response to a given reader query, transmitting the current pseudonym, wherein over a plurality of reader queries the pseudonym designated as the current pseudonym periodically cycles through the list of pseudonyms.

7. The method of claim 6 wherein after the current pseudonym is transmitted by the RFID device responsive to the given query, a different one of the plurality of stored pseudonyms is designated as the current pseudonym to be transmitted responsive to a subsequent query.

8. The method of claim 1 wherein one or more of the pseudonyms are generated on an as-needed basis within the RFID device.

9. The method of claim 1 wherein one or more of the pseudonyms are generated externally to the RFID device.

10. The method of claim 1 further including the step of limiting a rate at which the RFID device is permitted to transmit pseudonyms responsive to reader queries.

11. The method of claim 1 further including the step of periodically altering one or more of the plurality of pseudonyms.

12. The method of claim 11 wherein the altering step is implemented responsive to receipt of refresh information in the RFID device from a verifier.

13. The method of claim 12 wherein the refresh information comprises one or more refresh values transmitted from the verifier to the RFID device after mutual authentication of the RFID device and the verifier.

14. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device; and

wherein for a given value κ utilized in the RFID device, a vector Δ κ ={δ κ (1) , δ κ (2) , . . . , δ κ (m) } of one-time pads is maintained in the RFID device, wherein the one-time pad δ κ (1) is designated as a live pad and is used by the RFID device to update the value κ, where m denotes a number of authentication sessions over which one-time pads are constructed.

15. The method of claim 14 wherein the value κ is updated by computing κ←κ⊕δ K (1) .

16. The method of claim 14 wherein in conjunction with updating the value κ, the vector Δ κ is updated utilizing a vector {tilde over (Δ)} κ ={{tilde over (δ)} κ (1) , {tilde over (δ)} κ (2) , . . . , {tilde over (δ)} κ (m) } of one-time pads, the vector Δ κ being updated by discarding the previous live pad {tilde over (δ)} κ (1) , setting δ κ (i) =δ κ (i+1) for 1≦i≦n−1, setting δ κ (m) =0 l , and performing an element-wise exclusive-or of Δ κ and {tilde over (Δ)} κ by computing δ κ (i) =δ κ (i) ⊕{tilde over (δ)} κ (i) , such that the updated vector Δ κ comprises a set of m one-time pads with decreasing levels of backward secrecy.

17. The method of claim 1 wherein a verifier of the system is configured to store for a given RFID device T x a static identifier id x corresponding to at least one pseudonym of T x .

18. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier is configured to store for a given RFID device T x a static identifier id x corresponding to at least one pseudonym of T x ; and

wherein the pseudonyms for T x are obtained by encrypting id x ∥ Z x under a symmetric key K α for the verifier, where Z x , comprises a pseudonym counter.

19. The method of claim 18 wherein when the verifier receives a pseudonym from the RFID device, the verifier decrypts the pseudonym using K α to obtain the corresponding static identifier id x .

20. The method of claim 1 wherein a verifier of the system in conjunction with an authentication session with the RFID device specifies a value identifying a particular pseudonym to be transmitted by the RFID device.

21. The method of claim 1 wherein the RFID device determines which of the plurality of pseudonyms to transmit responsive to a given reader query based at least in part on timing information.

22. The method of claim 1 wherein the RFID device incorporates a pseudorandom number generator, where ƒ κ x (i) represents an output of the pseudorandom number generator for index i, where κ x is a seed associated with the RFID device.

23. The method of claim 22 wherein the RFID device generates the plurality of pseudonyms as pseudonyms α 1 =ƒ(1), α 2 =ƒ(2), . . . , α k =ƒ(k).

24. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the RFID device incorporates a pseudorandom number generator, where ƒ κ x (i) represents an output of the pseudorandom number generator for index i, where κ x is a seed associated with the RFID device;

wherein the RFID device and the verifier attempt to maintain a common counter d x unique to the RFID device, and share the seed K x ; and

wherein for a given counter value d, the RFID device computes a given one of the pseudonyms as a function of both a base value b and the given counter value d, and the verifier provides a subseciuent instruction to the RFID device to increment the base value b.

25. The method of claim 24 wherein in order to determine which RFID device is associated with a given incoming value α, the verifier performs a lookup in a list {ƒ κ x (d x )} of current α values for a plurality of RFID devices.

26. The method of claim 24 wherein for the given counter value d, the RFID device computes the given pseudonym as α d =ƒ(bk+d), where ε denotes a number of pseudonyms associated with the RFID device.

27. An apparatus for use in an RFID system, the apparatus comprising:

an RFID device having a plurality of pseudonyms associated therewith and being operative to communicate with one or more readers of the system;

the RFID device being further operative to transmit different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β i unique to a given pseudonym α i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ i unique to the given pseudonym α i transmitted by the RFID device; and

wherein at least one of the values α i , β i and γ i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.

28. An RFID system comprising:

a plurality of RFID devices; and

a plurality of readers which communicate with at least a subset of the RFID devices;

wherein a plurality of pseudonyms are associated with a given one of the RFID devices, the given RFID device being configurable to transmit different ones of the pseudonyms in response to different reader queries of the given RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the given RFID device by releasing to the given RFID device an authentication value β i unique to a given pseudonym α i transmitted by the given RFID device;

wherein the given RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ i unique to the given pseudonym α i transmitted by the given RFID device; and

wherein at least one of the values α i , β i and γ i is selected from a corresponding set of such values that is stored in the given RFID device and updated using one- time pads transmitted by the verifier to the given RFID device over multiple authentication sessions carried out between the verifier and the given RFID device.

29. An apparatus for use in an RFID system, the apparatus comprising:

a reader which communicates with one or more RFID devices;

wherein a plurality of pseudonyms are associated with a given one of the RFID devices, the given RFID device transmitting different ones of the pseudonyms in response to different reader queries of the given RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the given RFID device by releasing to the given RFID device an authentication value β i unique to a given pseudonym α i transmitted by the given RFID device;

wherein the given RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ i unique to the given pseudonym α i transmitted by the given RFID device; and

wherein at least one of the values α i , β i and γ i is selected from a corresponding set of such values that is stored in the given RFID device and updated using one-time pads transmitted by the verifier to the given RFID device over multiple authentication sessions carried out between the verifier and the given RFID device.

30. A method for use in a system comprising at least one device and at least one reader which communicates with the device, the method comprising the steps of:

associating a plurality of pseudonyms with the device; and

transmitting from the device different ones of the pseudonyms in response to different reader queries of the device;

wherein the pseudonyms are determined utilizing an updateable set of one or more one-time pads maintained in the device;

wherein the device comprises an RFID device;

wherein a verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β i unique to a given pseudonym α i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ i unique to the given pseudonym α i transmitted by the RFID device; and

wherein at least one of the values α i , β i and γ i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.

31. The method of claim 1 wherein one or more of the pseudonyms each comprise a portion of an identifier of the RFID device.