Method for generating unpredictable authentication identification symbols

• US 6,212,638 B1
• Filed: 12/02/1997
• Issued: 04/03/2001
• Est. Priority Date: 12/02/1997
• Status: Expired due to Fees

• Current Assignee: Lee, George C., Zhong Liang
• Original Assignee: Lee, George C., Zhong Liang
• Inventors: Lee, George C., Liang, Zhong
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Tucker, Christopher M.
• Application Number:
  US08/982,406
• Time in Patent Office: 1,218 Days
• Field of Search: 380/1, 380/51, 235/375, 235/385, 708/250, 708/255, 382/103, 382/100, 705/22, 713/179
• US Class Current: 713/179
• CPC Class Codes: G06F 21/46 by designing passwords or checking the strength of passwords
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083

Abstract

A method for generating authentication identification symbols, such as numbers, letters, etc., generates sequences of unpredictable symbols which are employed by vendors of various types of goods to authenticate the goods. Using special mathematical functions, an agent generates a first unpredictable subset of symbols to be supplied to a vendor for marking the vendor'"'"'s goods. The subset is unpredictable in that knowledge of one or more symbols in the subset cannot be employed to predict other symbols in the subset. Preferably, the vendor then selects another subset of symbols from the first subset, and the symbols in this sub-subset are employed for marking the vendor'"'"'s goods. The unpredictability of the symbol sequences prevents a counterfeiter from being able to predict other symbols in the sequence. In addition, the vendor'"'"'s use of a sub-subset of symbols prevents the agent from knowing which of the original subset of symbols the vendor is employing to mark the goods. Checking procedures are also employed to permit authentication of the identification symbols by a customer, for example.

Claims

1. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first and second subsets of symbols from said first sequence, said first and second subsets of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subsets cannot be employed to predict other symbols in said subset;

c) providing said first and second subsets of symbols to an individual for use as authentication symbols on a plurality of objects;

d) marking each of said objects with an identification symbol pair comprising a first symbol from said first subset, and a second symbol from said second subset;

e) entering a symbol pair into a checking means to check whether it is valid, said checking means carrying out the steps of;

f) checking the first symbol in said pair to determine whether it is valid, and if not, generating an indication that the symbol pair is invalid;

g) if said first symbol in said pair is valid, checking said second symbol in said pair to determine whether it is valid, and if so, generating an indication that said symbol pair is valid, and if not, generating an indication that said symbol pair is invalid.

2. The method of claim 1, wherein said steps of checking further comprise entering said first and second symbols in said symbol pair into first and second functions, respectively, and determining that said symbols are valid only if a predetermined value is generated by each of said functions.

3. The method of claim 1, wherein said first symbol of said pair is selected to be shorter in length than said second symbol of said pair.

4. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable by using mathematical functions based on the Nyquist sampling theorem so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects; and

d) marking each of said objects with a corresponding one of said symbols in said subset.

5. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols by;

1) generating a nonlinear function in a multiple coordinate system having a plurality of axes, said function being represented try a first curve in said multiple coordinate system, and including a plurality of frequency components, the highest of which has a period of length T;

2) selecting a first plurality of points along said first curve, with the minimum spacing interval between any two of said points being greater than T/2, each of said points being denoted by a coordinate value for each of said axes; and

3) defining a group of said coordinate values for one of said axes to be said sequence of identification symbols;

b) selecting a first subset of symbols from said first sequence, said sub set of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbol on a plurality of objects; and

d) marking each of said objects wit a corresponding one of said symbols in said subset.

6. The method of claim 5, further comprising the steps of:

e) generating a second nonlinear function represented by a second curve in said multiple coordinate system, said function including a plurality of frequency components, the highest of which has a period of length T2;

f) selecting a second plurality of points along said second curve, with the minimum spacing interval between any two of said points being greater than T2/2, each of said points being denoted by a coordinate value for each of said axes;

g) defining a group of said coordinate values for one of said axes to be a second sequence of identification symbols; and

h) selecting a second subset of symbols from said second sequence; and

i) providing said second subset of symbols to said individual for use as authentication identification symbols.

7. The method of claim 6, wherein said steps of selecting said first and second pluralities of points further comprise applying a selection function to said first and second nonlinear functions, respectively.

8. The method of claim 5, wherein said step of selecting said plurality of points along said first curve further comprises applying a first selection function to said first nonlinear function.

9. The method of claim 8, wherein at least a first key is applied to said first selection function.

10. The method of claim 5, wherein a first key is employed to generate said nonlinear function, a second key is employed to select said first plurality of points, and a third key is employed to select said subset.

11. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects;

d) said individual selecting a sub-subset of symbols from said first subset, said sub-subset of symbols also being selected to be unpredictable;

e) marking each of said objects with a corresponding one of said symbols in said sub-subset;

whereby, an individual having knowledge of said first sequence cannot predict the identity of symbols in said subset and sub-subset, an individual having knowledge of said subset cannot predict the identity of symbols in said first sequence and said sub-subset, an individual having knowledge of said sub-subset cannot predict the identity of symbols in said first sequence and said subset; and

, an individual having knowledge of some, but not all, symbols in said sub-subset, cannot predict the identity of other symbols in said sub-subset.

12. The method of claim 11, wherein said step of providing a first sequence further comprises:

1) generating a nonlinear function in a multiple coordinate system having a plurality of axes, said function being represented by a first curve in said multiple coordinate system, and including a plurality of frequency components, the highest of which has a period of length T;

2) selecting a first plurality of points along said first curve, with the minimum spacing interval between any two of said points being greater than T/2, each of said points being denoted by a coordinate value for each of said axes; and

3) defining a group of said coordinate values for one of said axes to be said sequence of identification symbols.

13. The method of claim 12, further comprising the steps of:

f) generating a second nonlinear function represented by a second curve in said multiple coordinate system, said function including a plurality of frequency components, the highest of which has a period of length T2;

g) selecting a second plurality of points along said second curve, with the minimum spacing interval between any two of said points being greater than T2/2, each of said points being denoted by a coordinate value for each of said axes;

h) defining a group of said coordinate values for one of said axes to be a second sequence of identification symbols; and

i) selecting a second subset of symbols from said second sequence; and

j) providing said second subset of symbols to said individual for use as authentication identification symbols.

14. The method of claim 13, wherein said individual further carries out the steps of:

k) selecting a second sub-subset of symbols from said second subset; and

l) employing said first and second sub-subsets of symbols as authentication identification symbols by marking each of a plurality of objects distributed by said individual with a pair of said symbols, one from said first sub-subset, and a second from said second sub-subset.

15. The method of claim 12, wherein a first key is employed to generate said nonlinear function, a second key is employed to select said first plurality of points, a third key is employed to select said subset, and a fourth key is employed to select said sub-subset.

16. The method of claim 11, further comprising the steps of:

f) selecting a second sub-subset of symbols;

g) providing said second sub-subset of symbols to a second individual;

h) selecting a subset of said sub-subset of symbols; and

i) marking objects held by said second individual with symbols from said subset of said sub-subset.

17. The method of claim 11, wherein the step of selecting a sub-subset of symbols further comprises applying a selection function with a secret key to said subset of symbols, said secret key being encoded using irrational numbers.

18. The method of claim 11, wherein the step of selecting a sub-subset of symbols further comprises selecting a first sub-subset of symbols using a first selection function, and a second sub-subset of symbols using a second selection function.

19. The method of claim 11, wherein the step of selecting a sub-subset of symbols further comprises selecting a first sub-subset of symbols by applying a selection function with a first secret key to said subset of symbols, and selecting a second sub-subset of symbols by applying said selection function with a second secret key to said subset of symbols.

20. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects;

d) marking each of said objects with a corresponding one of said symbols in said subset.

e) entering an identification symbol in a checking means to check whether it is valid;

f) preventing further data entry once an authentication identification symbol to be validated has been entered;

g) determining whether said identification symbol is valid; and

h) generating an output indicating whether said identification symbol is valid.

21. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects;

d) marking each of said objects with a corresponding one of said symbols in said subset. e) entering an identification symbol in a checking means to check whether it is valid;

f) determining whether said identification symbol is valid by applying said identification symbol to a check function, and determining that said symbol is valid only if a predetermined value is generated by said check function; and

g) generating an output indicating whether said identification symbol is valid.

22. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects;

d) marking each of said objects with a corresponding one of said symbols in said subset.

e) entering an identification symbol in a checking means to check whether it is valid;

f) determining whether said identification symbol is valid by comparing said identification symbol to a plurality of valid identification symbols in a database; and

g) generating an output indicating whether said identification symbol is valid.

23. The method of claim 22, further comprising the steps of entering additional identification information, and generating an indication that said symbol is invalid if said additional identification information is determined to be invalid.

24. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects;

d) marking each of said objects with a corresponding one of said symbols in said subset;

e) entering an identification symbol in a checking means to check whether it is valid;

f) determining whether said identification symbol is valid;

g) if said identification symbol is determined to be valid, marking said symbol as invalid for any future inquiries; and

h) generating an output indicating whether said identification symbol is valid.

25. A method for providing authentication identification symbols on a plurality of objects comprising the steps of:

a) providing a first sequence of symbols;

b) selecting a first subset of symbols from said first sequence, said subset of symbols being selected to be unpredictable so that knowledge of one or more of said symbols in said subset cannot be employed to predict other symbols in said subset, each of said symbols comprising a character and an associated angular position for said character;

c) providing said subset of symbols to an individual for use as authentication symbols on a plurality of objects; and

d) marking each of said objects with a corresponding one of said symbols in said subset.