METHODS AND APPARATUS FOR ENHANCING PRIVACY OF OBJECTS ASSOCIATED WITH RADIO-FREQUENCY IDENTIFICATION TAGS
Encoding radio-frequency identification (RFID) tags, each of the RFID tags having an tag identifier, t, and associated with a corresponding item, in a manner that preserves privacy of information associated with the item includes the steps of: generating a key, k; encrypting each of a plurality of tag identifiers, t, using the key, k to produce a plurality of encrypted tag identifiers; selecting a threshold value, T; dividing the key, k, into a plurality of key shares, n, such that retrieval of T or more key shares allows the key, k, to be reconstituted; and encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier and one of the key shares, and any other data useful to reconstitute the key k.
1 . A method for encoding a plurality of radio-frequency identification (RFID) tags, each of the RFID tags having a tag identifier, t, the method comprising:
(a) generating a key, k;
(b) encrypting each of a plurality of tag identifiers, t, using the key, k, to produce a plurality of encrypted tag identifiers;
(c) selecting a threshold value, T less than the number of tag identifiers comprising the plurality of tag identifiers;
(d) dividing the key, k, into a plurality of key shares, n, such that retrieval of T or more key shares allows the key, k, to be reconstituted; and
(e) encoding each of the plurality of RFID tags with a concatenation of the encrypted tag identifier and one of the key shares.
2 . The method of claim 1 wherein step (a) comprises generating a key, k, having a data length in bits equal to a data length in bits of each of the tag identifiers, t.
3 . The method of claim 1 wherein step (a) comprises generating a key, k, having a bit length equal to 128 bits.
4 . The method of claim 1 wherein step (a) comprises generating a string of random bits.
5 . The method of claim 1 wherein step (a) comprises generating a key, k, by determining the y-intercept of a polynomial function having degree T−1 over a Galois Field of prime order, p, where p>k.
6 . The method of claim 5 wherein step (d) comprises dividing the key, k, into a plurality of key shares, each of the key shares produced by evaluating the polynomial function at a random point.
7 . The method of claim 5 wherein step (e) comprises encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and an x-coordinate associated with the random point at which the polynomial was evaluated to produce the key share.
8 . The method of claim 1 wherein step (b) comprises encrypting each of a plurality of tag identifiers, t, with a symmetric encryption algorithm using the key, k, to produce a plurality of encrypted tag identifiers.
9 . The method of claim 1 wherein step (c) comprises selecting a threshold value, T, to be less than or equal to the greatest integer less than the number of tags likely to be readable from a given plurality of tags.
10 . The method of claim 1 wherein step (e) comprises encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and other data useful for reconstituting the key, k.
11 . The method of claim 1 further comprising the step of associating the generated key, k, with an identifier of a pallet, p, on which the items are loaded.
12 . The method of claim 8 further comprising storing the association between the pallet identifier, p, and the key, k.
13 . An apparatus for encoding a plurality of radio-frequency identification (RFID) tags, each of the RFID tags having a tag identifier, t, and associated with a corresponding item, the apparatus comprising:
a key source generating a key, k;
an encryption engine in communication with the key source, the encryption engine producing a plurality of encrypted tag identifiers using the key, k, generated by the key source;
a processor identifying a threshold value, T, wherein T is less than the number of tag identifiers;
a key engine dividing the key, k, into a plurality of key shares, n, such that retrieval of T or more key shares allows the key, k, to be reconstituted; and
a tag reader encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier and one of the key shares.
14 . The apparatus of claim 13 wherein the key source generates a key, k, having a bit length equal to a bit length of each of the tag identifiers, t.
15 . The apparatus of claim 13 wherein the key source generates a key, k, having a bit length equal to 128 bits.
16 . The apparatus of claim 13 wherein the key source comprises a random number generator.
17 . The apparatus of claim 13 wherein the key source generates a key, k, by determining the y-intercept of a polynomial function having degree T−1 over a Galois Field of prime order, p, where p>k.
18 . The apparatus of claim 17 wherein the tag reader encodes each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and an x-coordinate associated with determined y-intercept of the polynomial function.
19 . The apparatus of claim 17 wherein the key engine divides the key, k, into a plurality of key shares, each of the key shares produced by evaluating the polynomial function at a random point.
20 . The apparatus of claim 13 further comprising a memory element storing an association between an identifier of a pallet, p, on which the items are loaded and the key, k.
21 . The apparatus of claim 13 wherein the processor identifies a threshold value, T, wherein T is less than or equal to the number of tags likely to be readable from a given plurality of tags.
22 . The apparatus of claim 13 wherein the tag reader encodes each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and other data useful to reconstitute the key, k.
23 . An apparatus for encoding a plurality of radio-frequency identification (RFID) tags, each of the RFID tags having a tag identifier, t, the apparatus comprising:
(a) means for generating a key, k;
(b) means for encrypting each of a plurality of tag identifiers, t, using the key, k, to produce a plurality of encrypted tag identifiers;
(c) means for selecting a threshold value, T less than the number of tag identifiers comprising the plurality of tag identifiers;
(d) means for dividing the key, k, into a plurality of key shares, n, such that retrieval of T or more key shares allows the key, k, to be reconstituted; and
(e) means for encoding each of the plurality of RFID tags with a concatenation of the encrypted tag identifier and one of the key shares.
24 . The apparatus of claim 23 wherein the generating means comprises means for generating a key, k, having a data length in bits equal to a data length in bits of each of the tag identifiers, t.
25 . The method of claim 23 wherein the generating means comprises means for generating a key, k, having a bit length equal to 128 bits.
26 . The method of claim 23 wherein the generating means comprises means for generating a string of random bits.
27 . The method of claim 23 wherein the generating means comprises means for generating a key, k, by determining the y-intercept of a polynomial function having degree T−1 over a Galois Field of prime order, p, where p>k.
28 . The method of claim 27 wherein the dividing means comprises means for dividing the key, k, into a plurality of key shares, each of the key shares produced by evaluating the polynomial function at a random point.
29 . The method of claim 27 wherein the encoding means comprises the means for encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and an x-coordinate associated with the random point at which the polynomial was evaluated to produce the key share.
30 . The method of claim 23 wherein the encrypting means comprises means for encrypting each of a plurality of tag identifiers, t, with a symmetric encryption algorithm using the key, k, to produce a plurality of encrypted tag identifiers.
31 . The method of claim 23 wherein the selecting means comprises means for selecting a threshold value, T, to be less than or equal to the greatest integer less than the number of tags likely to be readable from a given plurality of tags.
32 . The method of claim 23 wherein the encoding means comprises means for encoding each of a plurality of RFID tags with a concatenation of the encrypted tag identifier, one of the key shares, and other data useful for reconstituting the key, k.
33 . The method of claim 23 further comprising means for associating the generated key, k, with an identifier of a pallet, p, on which the items are loaded.
34 . The method of claim 33 further comprising means for storing the association between the pallet identifier, p, and the key, k.