It is common practice for one party in a transaction to provide another party in the transaction with an identification (ID) number of the first party, for billing purposes. Familiar examples include the provision of a credit card number to a vendor by a purchaser and the provision of a telecard number by a user to a telephone system. In a face to face transaction between a purchaser and a vendor, the purchaser typically gives the vendor a credit card on which the ID number is embossed and encoded magnetically. Fraudulent use of the ID number in such a transaction requires that the credit card be stolen. In a transaction in which a user keys the ID number into a keyboard or keypad, for example the telecard transaction noted above or a remote transaction in which the purchaser transmits the ID number to the vendor electronically, e. g. over the Internet, a higher level of security is required. Often, telecard users and credit card users are provided with secondary ID numbers, commonly called"personal identification numbers"or"PINs", which the users use to certify their identities to the systems with which they communicate.

If a user commits his or her PIN to memory, the PIN provides excellent security against theft of the credit card itself or of a document bearing the credit card number, because the thief has no way of knowing or inferring the PIN associated with the stolen credit card number. The advent of cellular telephony has made this certification method less secure. Because a cellular telephone user broadcasts

essentially omnidirectionally, a thief can acquire a user's ID number and PIN by eavesdropping on a conversation in which the user transmits the ID number and the PIN to a vendor via a cellular telephone. One-time lists of PINs have been proposed as a solution to this problem. The drawback of such one-time lists is that, unlike single PINs, these lists can not be committed easily to memory. Like a credit card, a list of PINs can be stolen.

There is thus a widely recognized need for, and it would be highly advantageous to have, a method, by which one party in a transaction can certify his or her identity to another party in the transaction, that is more secure than the methods known in the art.

SUMMARY OF THE INVENTION According to the present invention there is provided a method for a user to certify an identity thereof to a vendor, including the steps of : (a) providing the user with a list of a first plurality of codes, each of the codes having an index; (b) selecting at least one of the indices, by the vendor; and (c) for each of the at least one index, transmitting the code associated with the each index to the vendor, by the user.

According to the present invention there is provided a system for enabling one of a plurality of users to certify an identity thereof to a vendor, including: (a) a mechanism for generating, for each user, a list of a plurality of codes, each of the codes having an index, the codes of the list being unique to the each user; (b) a mechanism for providing the lists to the vendor; and (c) a mechanism for randomly selecting one of the indices.

According to the present invention there is provided a method for each of a plurality of users to certify an identity thereof to each of a plurality of vendors in transactions therebetween, including the steps of: (a) providing each user with a list of a plurality of codes, each of the codes having an index; (b) providing each vendor with a mechanism for generating the lists of the pluralities of codes; (c) for each user and each vendor, in each transaction between the each user and the each vendor: (i) selecting one of the indices, by the each vendor, and (ii) transmitting the code associated with the one index to the each vendor, by the each user.

As used herein, the term"user"refers to a party in a transaction who certifies his or her identity to a second party in the transaction. The second party is referred to herein as the"vendor". This terminology has been chosen to fit the paradigmatic transaction of the present invention: the purchase on credit of an item from a vendor by a user of a cellular telephone, in which the user transmits his or her credit card number to the vendor by keying the credit card number into the keypad of the cellular telephone. It will be appreciated that the scope of the present invention includes all equivalent transactions, and that the vendor need not be human. For example, the vendor may be a computer-controlled machine with keyboard or keypad input, such as an automatic teller machine or a public telephone system. Furthermore, the verb "transmit"is intended herein to encompass any method by which the user and the vendor exchange data, including oral communication between a human user and a human vendor, either face-to-face or across a telephone or radio link.

The essence of the present invention is the use of a randomly selected PIN or similar code. Each user is provided with a list of codes, unique to that user, with each code identified by an index. Each vendor is provided either with all the users'lists or

with a mechanism for generating the users'lists from the users'ID numbers. The vendor selects an index at random from the list corresponding to a particular user's ID number and transmits the index to the user. The user responds by transmitting to the vendor the code associated with that index. If the code received by the vendor is not the code associated with the index transmitted by the vendor, then the vendor knows that the alleged user is fraudulent and terminates the transaction. The fact that different codes are used in successive transactions makes it very difficult for an eavesdropper to break the security of the present invention. Because an eavesdropper can reconstruct the list of codes by eavesdropping on a large number of transactions by the same user, the lists are replaced periodically with new lists.

Preferably, the lists are in the form of rectangular tables, with the indices being coordinate pairs.

Preferably, the tables are produced by random number generators that use seeds based on the users'ID numbers. Most preferably, the algorithm for producing the seeds is implemented in a system with a hardware-embedded prime number which is multiplied by the ID number or a number related to the ID number. The resulting product is truncated to yield the corresponding seed for random number generation.

The prime number is sufficiently long to inhibit cracking of the algorithm.

One of the significant advantages of the present invention, when compared to the prior art methods, is that under the present invention, the code that identifies a user to a vendor is produced cooperatively by both the user and the vendor. The user never has complete knowledge of the full de facto code. As a result, the present invention has the advantage over the prior art methods that the code of the present invention is effectively immune to theft.

Mosley, in U. S. Patent No. 5,251,259, teaches a similar, table-based method of selecting a PIN. The difference between the present invention and the method of Mosley is that under Mosley's method the selection of the PIN is based on a (time- dependent) rule that is shared by the user and the vendor, whereas according to the present invention, the vendor chooses the rule (index) for selecting the PIN and provides that rule to the user.

BRIEF DESCRIPTION OF THE DRAWINGS The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein: FIG. 1 is an example of a table of codes with alphanumerical indices; FIG 2 is a block diagram of a system of the present invention; FIG. 3 is a block diagram of another system of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention is of a method by which one party in a transaction can certify his or her identity to another party in a transaction. Specifically, the present invention can be used to certify the identity of the owner of a credit card number or a similar identification number.

The principles and operation of identity certification according to the present invention may be better understood with reference to the drawings and the accompanying description.

Referring now to the drawings, Figure 1 illustrates a table 10 of 100 codes 12 of the present invention. Codes 12 are arranged in a rectangular array of rows and

columns, so that each code 12 is indexed by an index that includes two coordinate values, a row coordinate value 14 between 1 and 10 and a column coordinate value 16 between A and J. The rectangular arrangement shown in the Figure is only illustrative. Any geometric pattern that can be addressed by a two-coordinate index, for example, concentric circles, may be used. Codes 12 preferably are random numbers with small (typically 2 as illustrated) numbers of digits, although codes 12 can be any suitable combination of symbols, for example, short alphanumeric strings.

Two-digit codes 12 allow table 10 to be printed on the reverse side of a credit card while remaining legible. Because the code used in any particular transaction is produced cooperatively by the user and the vendor, with the vendor selecting the index and the user responding with the associated code, the effective length of the code is longer than the number of digits in the code, and is in fact the sum of the number of digits in the code and the number of characters in the index.

The scope of the present invention extends beyond the planar geometric arrangement of codes illustrated in Figure 1. For example, using a suitable holographic display, the codes can be arranged effectively in three dimensions, with three coordinate values per index. Another important special case of a table 10 within the scope of the present invention is a table 10 with a single column, i. e., a simple list of codes 12. In that case, the index of each code 12 is a single coordinate value 14.

Each user is provided with a table 10 that is associated with that user's ID number. Preferably, there is a unique association between tables 10 and ID numbers, although it is also possible for a group of users with related ID numbers to share the same table 10. For example, if codes 12 are short random numbers, then, for each user, codes 12 are generated successively using a random number generator, starting

with a seed that is based on that user's ID number. For example, if the ID number is a 16-digit credit card number, then using the credit card number itself as the seed provides a table 10 that is unique to that user, and using the last four digits of the credit card number as the seed provides a table 10 that is common to all users whose credit card numbers share the same last four digits. The generation of random numbers from seeds is well-known in the art, and is described, for example, in William H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery, Numerical Recipes in C, Second Edition (University of Cambridge, 1992), Chapter 7.

If there is only a small numbers of users, the vendors with whom the users enter into transactions are provided with copies of the users'tables 10. If there is a large number of users, as is typical in the case of users of credit cards, this is unwieldy, so the vendors are provided with random number generators for generating the user's tables on the fly. In the latter case, the seed for random number generation preferably is not the ID number itself, but rather an integer obtained by combining the ID number with a suitable prime number. For example, a bank that issues credit cards to users provides vendors with random number generator chips that can be installed in the vendors'computers (in the case of human vendors) or in the vendors themselves (in the case of robotic vendors). Each chip has embedded in the hardware thereof a binary representation of a long prime number. Each user's seed is obtained by multiplying the user's credit card number by the hardware-embedded prime number and either truncating the product or dividing the product by a second integer and taking the remainder. Because the prime number is known only to the bank, it is virtually impossible for a human vendor to reverse-engineer the algorithm for generating table 10 as a function of credit card number. The longer the prime number,

the more secure the transactions; but excessively long prime numbers increase hardware complexity.

In each transaction between a user and a vendor, the vendor randomly selects a row coordinate value 14 and a column coordinate value 16 and transmits those coordinate values to the user. The user looks up, on the user's table 10, the code 12 that is indexed by the transmitted coordinate values and transmits that code 12 to the vendor. If the code 12 received by the vendor is the same as the code 12 that is indexed by the transmitted coordinates in the vendor's table 10, then the vendor continues the transaction. If the code 12 received by the vendor is not the same as the code 12 that is indexed by the transmitted coordinate values in the vendor's table 10, then the vendor cancels the transaction. When two-digit codes 12 are used, and the user has a 1% probability of guessing the correct code, it is preferable that the vendor repeat the random selection of row coordinate value 14 and column coordinate value 16 and the transmission of those values to the user at least one more time, and most preferably three more times, to force the user to look up at least two codes 12 selected at random.

It is most preferable, in a transaction between a user and another human, that it be difficult for the second human to reconstruct the user's table. This is accomplished by having the second human's computer produce row coordinate value 14 and column coordinate value 16, for example using the same random number generator as is used to make the table. In this case, both the second human and the second human's computer together constitute the"vendor". The second human receives row coordinate value 14 and column coordinate value 16 from the computer and passes these coordinate values to the user. Upon receiving the corresponding code 12 from

the user, the second human enters that code 12 in the computer. The computer generates table 10 internally, compares the entered code to the actual code, and only informs the second human of a match or a mismatch. That the computer produces only a small number of row coordinate values 14 and column coordinate values 16 per transaction makes it difficult for the second human to reconstruct the user's table by trial and error with fictitious transactions.

For further security, the"vendor"is partitioned between the second human and the computer of a credit provider who provides the second human with only a data entry terminal linked to the credit provider's computer. In this case, it is the credit provider's computer, and not the computer of the second human, that generates row coordinate values 14 and column coordinate values 16 in response to the initiation of a transaction at the data entry terminal. The credit provider's computer keeps track of the pattern of transactions initiated by the second human for any given ID number, as a function of time. For example, the credit provider's computer may keep track of the number of transactions initiated by the second human for any given ID number, as a function of time. If this function of time departs from normal expectations in a statistically significant manner, the credit provider's computer denies further access to the second human.

A further feature of the present invention is useful in a telephone transaction between a user and a second human. An unscrupulous second human is liable to debit the user's account for more money than the user intends to spend, in order to pocket the difference. To inhibit this form of theft, the user is provided with several tables 10, each table 10 associated with a different range of values of a parameter associated with the transaction. For example, the user may be provided with four tables 10: a

first table 10 for the purchase of one item per transaction, a second table 10 for the purchase of between two and five items per transaction, a third table 10 for the purchase of between six an fifteen items per transaction, and a fourth table 10 for the purchase of more than sixteen items per transaction. The second human enters both the user's ID number and the number of items to be purchased in the computer, and the computer generates table 10 that corresponds to the entered ID number and the entered number of items. One way of generating that table 10, both for the user and at the time of the transaction, is to produce the seed for the random number generator by multiplying the ID number by both the secret prime number and the low number of items in the range (1,2,6 or 16 in the above example) and truncating the product.

The user looks up code 12 on table 10 that corresponds to the number of items that the user actually wants to purchase. If the second human has entered a number of items outside the range associated with that table 10, in order to cheat the user, then code 12 that the second human receives from the user and enters into the computer does not match code 12 that is generated by the computer, and the transaction is aborted.

Another useful transaction parameter is the dollar amount of a purchase. The second human enters the dollar amount in the computer, and the computer generates a number of indices, for the user's table, that depends on the dollar amount. For example, the computer may generate one index for purchases under $100, two indices for purchases between $100 and $1000, and three indices for purchases over $1000.

If the purchase is under $100, the second human asks the user for one code 12. If the purchase is between $100 and $1000, the second human asks the user for two codes 12. If the purchase is for an amount over $1000, the second human asks the user for three codes 12. If the user desires to spend less than $100, and the second human asks

for two codes 12, the user knows that the second human has fraudulently entered a purchase amount greater than $100. The user then aborts the transaction, for example by transmitting to the second human a spurious character string that differs from the code 12 that is indexed by the second index.

The multiple-table variant of the present invention also may be used with the dollar amount of the purchase as the transaction parameter. In that case, table 10 for the smallest dollar range is printed on the reverse side of the user's credit card, and tables 10 corresponding to higher dollar amounts are printed separately and are kept by the user in secure locations. This limits the user's potential loss in case the credit card is stolen.

Figure 2 is a block diagram of a system for implementing the present invention. The system of Figure 2 includes two kinds of units, a central unit 20 and a peripheral unit 40. Typically, one central unit 20 is used by a credit provider, such as a credit card company or a bank, for producing copies of table 10 that are distributed to the users, and each vendor includes a peripheral unit 40. In the above example in which the second human and the second human's computer together constitute the "vendor", peripheral unit 40 is an integral part of the second human's computer.

Central unit 20 includes a processor 24, an input device 22 that preferably includes a keyboard and a disk reader, and an output device 26 such as a printer for producing tables 10. Processor 24 includes, either in the form of suitable software or as dedicated hardware, a random number generator (RNG) 32. Processor 24 is connected to a read-only memory (ROM) 28 wherein is permanently stored a prime number 30 that is used as described above to generate the seeds for RNG 32.

The credit provider produces tables 10 by entering the users'ID numbers via input device 22. For each user, processor 24 combines the user's ID number with prime number 30 to produce a seed for RNG 32, as described above, and then uses RNG 32 to generate the user's table 10. The user's copy of that table 10 is outputted by output device 26. Tables 10 thus produced are distributed to the users.

Peripheral unit 40 includes a processor 44 that is similar to processor 24, an input/output (I/O) device 42 that preferably includes a keyboard and a video display, and a ROM 46 that is similar to ROM 28. In particular, the same prime number 30 that is stored in ROM 28 also is permanently stored in ROM 46. Processor 24 also includes a RNG 48 that is substantially identical to RNG 32 of processor 24.

In a transaction with a user, a vendor equipped with peripheral unit 40 operates as described above. The user's ID number is entered into I/O device 42, along with other transaction details. Processor 44 combines the ID number with prime number 30 in exactly the same way as processor 24 previously combined the ID number with prime number 30, to produce a seed for RNG 48. Processor 44 provides this seed to RNG 48 and then uses RNG 48 to reproduce the user's table 10. Processor 44 then uses RNG 48, either with the same seed or with a different seed, to randomly select a row coordinate value 14 and a column value coordinate value 16 that are transmitted, with the help of I/O device 42, to the user. For example, in the above example in which the second human and the second human's computer together constitute the "vendor", this row coordinate value 14 and this column coordinate value 16 are displayed on the video screen of I/O device 42. The second human informs the user of row coordinate value 14 and column coordinate value 16, and transfers the character string, provided by the user in response to that information, to peripheral

unit 40, using the keyboard of I/O device 42. Processor 44 compares this character string with code 12 of the reproduced copy of the user's table 10 that is indexed by row coordinate value 14 and column coordinate value 16, and informs the second human, via the video screen of I/O unit 42, whether the character string matches code 12.

Figure 3 is a block diagram of a system for implementing the present invention under the embodiment described above wherein the human part of each"vendor" (the "second human") is provided with only a data entry terminal. The system of Figure 3 includes only one unit 60, which is identical to central unit 20, so that like reference numerals refer to like parts in Figures 2 and 3, with the addition of several data entry terminals 62 at remote vendor locations. Data entry terminals 62 are substantially identical to I/O device 42. As in the system of Figure 2, for each user, processor 24 combines the user's ID number with prime number 30 to produce a seed for RNG 32, and then uses RNG 32 to generate the user's table. In addition, in response to a user ID number entered via one of data entry terminals 62, processor 24 combines the ID number with prime number 30 to reproduce the same seed for RNG 32 and then uses RNG 32 to reproduce the user's table 10. Processor 24 then uses RNG 32, either with the same seed or with a different seed, to randomly select a row coordinate value 14 and a column coordinate value 16 that are displayed to the second human on the video screen of that data entry terminal 62. The second human informs the user of row coordinate value 14 and column coordinate value 16, and transfers the character string provided by the user, in response to that information, to processor 24, using the keyboard of data entry terminal 62. Processor 24 compares this character string with code 12 of the reproduced copy of the user's table 10 that is indexed by row

coordinate value 14 and column coordinate value 16, and informs the second human, via the video screen of data entry terminal 62, whether the character string matches code 12. Processor 24 also monitors transactions entered with respect to each user's ID number at each data entry terminal 62, and disables a data entry terminal 62 that exhibits a suspicious pattern of transactions using a particular ID number.

Alternatively, each"second human"is provided with a password for access to processor 24 via data entry terminals 62, and a password is rendered invalid by processor 24 when a suspicious pattern of transactions using that password and a particular ID number are noted.

While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made.