Method of authenticating an object or entity using a random binary ID code subject to bit drift

• US 6,802,447 B2
• Filed: 08/26/2002
• Issued: 10/12/2004
• Est. Priority Date: 08/26/2002
• Status: Expired due to Fees

• Current Assignee: ICID, LLC
• Original Assignee: ICID, LLC
• Inventors: Horng, Chi-Song
• Primary Examiner(s): Lee, Diane I.
• Application Number:
  US10/228,678
• Publication Number:
  US 20040035919A1
• Time in Patent Office: 778 Days
• Field of Search: 235/375, 235/385, 235/487, 716/4, 716/8, 702/73, 364/468.22, 364/468.23, 700/115, 700/116, 700/117, 713/168, 713/185, 717/106
• US Class Current: 235/375
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10019 resolving collision on the communication channels between simultaneously or concurrently interrogated record carriers. collision between the communication channels used by wireless communication devices, where the solution is not particularly adapted for RFIDs or the like, H04W74/08

Abstract

Each object (such as for example an integrated circuit) of a population of similar objects is configured to generate instances of a dynamic binary identification code (ID) that differ from instances of IDs generated by all other member objects of the population. While bits residing in most of the bit positions of the ID generated by each member object of the population do not vary in state from instance-to-instance of that ID, bits residing in one or more of the bit positions of the ID may vary (drift) in state from instance-to-instance of that ID. A set of instances of the ID generated by each member object of the population are analyzed to construct a separate “drift profile” for each member object'"'"'s ID indicating for each bit position a probability that the bit position will contain a bit of a particular state. Thereafter, to verify that a particular object is a specific member object of the population, a set of instances of the ID generated by that particular object is analyzed to construct a drift profile for that particular object'"'"'s ID. That drift profile is then compared to the drift profiles of the IDs generated by the member objects of the population to determine whether the particular object is a certain specific member object of the population.

Claims

1. A method for verifying an identity of a particular object to determine whether the particular object is a specific member of a population of similar objects, the method comprising the steps of:

a. configuring each member object to generate instances of a dynamic binary identification code (ID), wherein the ID generated by each member object differs from IDs generated by all other member objects of the population, wherein the ID generated by each member object includes a plurality of bit positions, wherein bits residing in most of the bit positions of the ID generated by each member object do not vary in state from instance-to-instance of that ID, and wherein bits residing in at least one other of the bit positions or the ID may vary in state from instance-to-instance of that ID;

b. analyzing a set of instances of the ID generated by each member object of the population to produce a separate drift profile for each member object'"'"'s ID indicating for each bit position of the ID a probability that the bit position will contain a bit of a particular state;

c. analyzing a set of instances of the ID generated by a particular object to produce a particular drift profile for that object'"'"'s ID; and

d. comparing the particular drift profile to drift profiles of the IDs of member objects of the population to verify that the particular object is a specific member object of the population.

2. The method in accordance with claim 1 wherein each member object of the population is an integrated circuit.

3. A method for determining whether an object is a member of a population, the method comprising the steps of:

a. configuring each member of the population to generate instances of a binary identification code (ID) having N bit positions, where N>

2,

wherein bits residing in some of the bit positions of each member'"'"'s ID do not vary in state from instance-to-instance of that member'"'"'s ID, and

wherein a bit residing in at least one bit position of some members'"'"' IDs varies in state from instance-to-instance of those members'"'"' IDs;

b. for each member of the population, analyzing a plurality of instances of an ID generated by that member of the population to produce a drift profile for that member'"'"'s ID indicating whether, for each bit position of that member'"'"'s ID, a bit residing at that bit position varied in state among the analyzed plurality of instances of that member'"'"'s ID.

4. The method in accordance with claim 3 further comprising the step of:

c. analyzing a plurality of instances of an ID having N bit positions generated by the object to produce a drift profile for that object'"'"'s ID indicating whether, for each bit position of the object'"'"'s ID, a bit residing at that bit position varied in state among the analyzed plurality of instances of the object'"'"'s ID.

5. The method in accordance with claim 4 further comprising the step of:

d. comparing the drift profile of the object'"'"'s ID to a drift profile of the ID of a particular member of the population to determine whether the particular object is that particular member of the population.

6. The method in accordance with claim 3 further comprising the step of:

c. for each member of the population, analyzing at least one instance of the ID generated by that member of the population to determine a representative ID for that member of the population.

7. The method in accordance with claim 6 further comprising the steps of:

d. analyzing at least one instance of an ID having N bit positions generated by the object to determine a representative ID for that object; and

e. comparing the representative ID for that object to the representative ID of a particular member of the population to determine whether it is possible that the object is that particular member of the population.

8. The method in accordance with claim 7 wherein step e comprises determining that is possible that the object is that particular member of the population by determining whether the representative ID of the object and the representative ID of that particular member have at least a minimum number of matching bits, wherein the minimum number is less than N.

9. The method in accordance with claim 7 further comprising the steps of:

f. analyzing a plurality of instances of the ID generated by the object to produce a drift profile for that object'"'"'s ID indicating whether, for each bit position of the object'"'"'s ID, a bit residing at that bit position varied in state among the analyzed plurality of instances of the object'"'"'s ID; and

g. comparing the drift profile for the object'"'"'s ID to the drift profile of the ID of the particular member of the population to verify that the object is the particular member of the population.

10. The method in accordance with claim 9

wherein the drift profile for each member of the population includes, for each Jth bit position of the member'"'"'s ID, a drift ratio R1_J indicating a probability that the bit residing at the Jth bit is likely to be of a particular state, and

wherein the drift profile for the object includes, for each Jth bit position of the object'"'"'s ID, a drift ratio R2_J indicating a probability that the bit residing at the Jth bit is likely to be of a particular state.

11. The method in accordance with claim 10 wherein the object is verified at step g to be the particular member of the population when, for the drift profile of the object'"'"'s ID and the drift profile of the particular member'"'"'s ID, $\sum _{}^{}$

J=1N



R1J-R2J

<

T

where T is a threshold number.

12. The method in accordance with claim 11 where T>

0.

13. The method in accordance with claim 9 wherein the object and each member of the population is an integrated circuit.

14. The method in accordance with claim 3 wherein the drift profile for each member'"'"'s ID indicates, for each bit position of that member'"'"'s ID, a probability that the bit position will contain a bit of a particular state.

15. A method for determining whether an object is a member of a population,

wherein each member of the population generates instances of a binary identification code (ID) having N bit positions,

wherein the ID generated by each member of the population differs from IDs generated by other members of the population,

wherein bits residing in some of the bit positions of each members'"'"' ID do not vary in state from instance-to-instance of that ID,

wherein a bit residing in at least one bit position of some members'"'"' IDs varies in state from instance-to-instance of those members'"'"' IDs, and

wherein the object generates instances of a binary identification code having N bit positions, the method comprising the steps of:

a. for each member of the population, analyzing a plurality of instances of the ID generated by that member of the population to produce a drift profile for that member'"'"'s ID indicating whether, for each bit position of that member'"'"'s ID, a bit residing at that bit position varied in state among the analyzed plurality of instances of that member'"'"'s ID, and

b. analyzing a plurality of instances of the ID generated by the object to produce a drift profile for the object'"'"'s ID indicating whether, for each bit position of the object'"'"'s ID, a bit residing at that bit position varied in state among the analyzed plurality of instances of the object'"'"'s ID, and

c. comparing the drift profile for the object'"'"'s ID to a drift profile for the ID of a particular member of the population to determine whether the object is that particular member of the population.

16. The method in accordance with claim 15 further comprising the steps of:

d. for each member of the population, analyzing at least one instance of the ID generated by that member of the population to determine a representative ID for that member of the population;

e. analyzing at least one instance of the ID generated by the object to determine a representative ID for that object; and

f. determining whether it is possible that the object is a particular member of the population by determining whether the representative ID of the object and a representative ID of a member of the population have at least a minimum number of matching bits, wherein the minimum number is less than N.

17. The method in accordance with claim 15

wherein the drift profile for each member of the population includes, for each Jth bit position of the member'"'"'s ID, a drift ratio R1_J indicating a probability that the bit residing at the Jth bit is likely to be of a particular state, and

wherein the drift profile for the object includes, for each Jth bit position of the object'"'"'s ID, a drift ratio R2_J indicating a probability that the bit residing at the Jth bit is likely to be of a particular state.

18. The method in accordance with claim 17 wherein the object is determined at step c to be said member of the population when, for the object drift profile and the particular member'"'"'s drift profile, $\sum _{}^{}$

J=1N



R1J-R2J

<

T

where T>

0.

19. The method in accordance with claim 15 wherein the object and each member of the population is an integrated circuit.

20. The method in accordance with claim 15

wherein the drift profile for the ID of each member of the population indicates, for each bit position of that member'"'"'s ID, a probability that the bit position will contain a bit of a particular state, and

wherein the drift profile for the object'"'"'s ID indicates, for each bit position of the object'"'"'s ID, a probability that the bit position will contain a bit of a particular state.