US20090160615A1

Movatterモバイル変換

Info

Publication number: US20090160615A1
Application number: US12/314,456
Authority: US
Inventors: William G. O'Brien; Tet Hin Yeap
Original assignee: BCE Inc
Current assignee: BCE Inc
Priority date: 2007-12-20
Filing date: 2008-12-11
Publication date: 2009-06-25
Also published as: CA2647312A1; CA2645990C; CA2647312C; CA2647318A1; US7806325B2; US10726385B2; WO2009079766A1; US20100185865A1; US8553888B2; EP2235872A4; WO2009079734A1; US20130212398A1; EP2223460A4; US20090160649A1; US8103872B2; US20090161872A1; EP2235872A1; CA2936737A1; US20100320269A1; US9971986B2

Abstract

A method which comprises generating a first signature by encoding an identifier with a first additional data set at a first time instant; responding to a first read request from a tag reader by releasing the first signature; generating a second signature by encoding the identifier with a second additional data set at a second time instant, the second additional data set being different from the first additional data set; and responding to a second read request by releasing the second signature. Also, a method which comprises obtaining a signature from a contactlessly readable tag; decrypting the signature with a key to obtain a candidate identifier and a scrambling code associated with the signature; and validating the candidate identifier based on at least one of the scrambling code and the signature.

Description

CROSS-REFERENCE TO RELATED APPLICATION

This application is a continuation, and claims the benefit under 35 USC 120, of International Application No. PCT/CA2007/002343 filed on Dec. 20, 2007 and hereby incorporated by reference herein.

FIELD OF THE INVENTION

The present invention relates generally to contact-less tags and, more specifically, to a contact-less tag having a signature as well as to applications using the properties of such a tag.

BACKGROUND

Contact-less tags, such as radio frequency identification (RFID) tags, are becoming increasingly commonplace in various commercial applications, two non-limiting examples of which include access control and inventory management.

An RFID tag affixed to an item stores a code (e.g., a bit pattern) that is output in contact-less fashion to a reader, either in response to a request from the reader or autonomously by the tag. The reader captures the bit pattern and then an action may be taken, depending on the commercial application at hand. For example, in an access control scenario, the captured bit pattern may reveal that the person presumed to be carrying the tag (by virtue of an association with the bit pattern) is—or is not—authorized to enter a building or operate a vehicle. In an inventory management scenario, the bit pattern may give an indication of items contained on a pallet, for example, which may result in certain decisions being taken regarding shipping or storage of these items.

In both cases, the ease with which an RFID tag may be read by a reader enables rapid processing but also may lead to problems. In the access control scenario, for example, an RFID tag of an individual authorized to access certain property may be interrogated and then the bit pattern cloned for use by an impostor to gain what is in fact unauthorized access to such property. Similarly, in the inventory management scenario, an acquired knowledge of the bit pattern associated with a certain item may allow a malicious party to gain intelligence about inventory locations that the item's rightful owner (which may include the manufacturer all the way down to the retail customer) may wish to keep secret.

In both of the above scenarios, it is apparent that what is relevant to a malicious party is the knowledge that a certain bit pattern output by a certain RFID tag will either give access to property or indicate the presence of a specific inventory item. Whether the bit pattern is itself an encrypted version of some original data is actually of no relevance to the malicious party. Thus, schemes based on straightforward encryption of the bit pattern do not mitigate the problems mentioned above.

Against this background, there is clearly a need in the industry for a contact-less tag having improved properties.

SUMMARY OF THE INVENTION

A first broad aspect of the present invention seeks to provide a method, which comprises generating a first signature by encoding an identifier with a first additional data set at a first time instant; responding to a first read request from a tag reader by releasing the first signature; generating a second signature by encoding the identifier with a second additional data set at a second time instant, the second additional data set being different from the first additional data set; and responding to a second read request by releasing the second signature.

A second broad aspect of the present invention seeks to provide an apparatus, which comprises means for generating a first signature by encoding an identifier with an additional data set at a first time instant; means for responding to a first read request from a tag reader by releasing the first signature; means for generating a second signature by encoding the identifier with a second additional data set at a second time instant, the second additional data set being different from the first additional data set; and means for responding to a second read request from a tag reader by releasing the second signature.

A third broad aspect of the present invention seeks to provide a computer-readable medium, which comprises computer-readable program code which, when interpreted by a computing apparatus, causes the computing apparatus to execute a method. The computer-readable program code comprises first computer-readable program code for causing the computing apparatus to generate a first signature by encoding an identifier with an additional data set at a first time instant; second computer-readable program code for causing the computing apparatus to respond to a first read request from a tag reader by releasing the first signature; third computer-readable program code for causing the computing apparatus to generate a second signature by encoding the identifier with a second additional data set at a second time instant, the second additional data set being different from the first additional data set; and fourth computer-readable program code for causing the computing apparatus to respond to a second read request from a tag reader by releasing the second signature.

A fourth broad aspect of the present invention seeks to provide a device for use in contact-less communication with a reader, which comprises a memory configured to store a first signature generated by encoding an identifier with a first additional data set at a first time instant; and a controller configured to generate a new signature by encoding the identifier with a second additional data set at a second time instant, the second additional data set being different from the first additional data set. The controller is further configured to cause the new signature to be stored in the memory after the second time instant.

A fifth broad aspect of the present invention seeks to provide a device for use in contact-less communication with a reader, which comprises a memory configured to store a signature that encodes a pre-determined identifier; a transceiver configured to contactlessly receive read requests from the reader and to contactlessly transmit responses thereto; a controller configured to respond to read requests received via the transceiver by releasing via the transceiver a current version of the signature stored in the memory, wherein the version of the signature stored in the memory varies over at least two time instants while continuing to encode the pre-determined identifier; and a power source for powering at least the controller.

These and other aspects and features of the present invention will now become apparent to those of ordinary skill in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

In the accompanying drawings:

FIG. 1 is a block diagram of a system comprising a reader and a tag, in accordance with a non-limiting embodiment of the present invention.

FIG. 2 is a block diagram showing details of the tag, in accordance with a non-limiting embodiment of the present invention.

FIG. 3 illustrates a decoding function implemented by a controller in the tag, for generation of a signature at two points in time.

FIGS. 4A and 4B depict two possible functional architectures for generation of a signature.

FIG. 5 illustrates application of an embodiment of the present invention in an inventory management context.

FIG. 6A shows application of a non-limiting embodiment of the present invention in a validation context.

FIG. 6B is a block diagram of a multi-reader architecture, in accordance with a non-limiting embodiment of the present invention.

FIG. 7A is a flowchart showing operation of a processing entity ofFIG. 6 when considering tags whose signatures encode a variable scrambling code and that are encrypted using a common key that is known to the reader or can be determined from an index supplied with the signature.

FIG. 7B is a flowchart similar to that ofFIG. 7A, but where the common key is unknown to the reader.

FIG. 8 shows application of a non-limiting embodiment of the present invention in an identification context when considering tags whose signatures are encrypted using a variable key.

FIG. 9 is a flowchart showing operation of a processing entity ofFIG. 8 when considering tags whose signatures are encrypted using a variable key.

It is to be expressly understood that the description and drawings are only for the purpose of illustration of certain embodiments of the invention and are an aid for understanding. They are not intended to be a definition of the limits of the invention.

DETAILED DESCRIPTION

With reference toFIG. 1, there is shown a system comprising areader12 and atag14. Communication between thereader12 and thetag14 occurs over acontact-less medium16. In a specific non-limiting embodiment, thecontact-less medium16 is a wireless medium that may include a spectrum of radio frequencies. Depending on the application at hand, thetag14 could be affixed to: an item for sale, goods during transportation, a person's clothing, an animal, a piece of equipment (including communications equipment such as wireless communications equipment) and so on. For its part, thereader12 can be fixed or mobile. In the fixed scenario, thereader12 could be located at any desired position within a building, vehicle, warehouse, campus, etc. In the mobile scenario, thereader12 could be implemented in a handheld or portable unit, for example.

FIG. 2 shows details of thetag14, in accordance with a specific non-limiting embodiment of the present invention. Thetag14 comprises amemory202, a transceiver204 (including an antenna), acontroller206 and apower source208.

Thememory202 stores acurrent signature212. In addition, thememory202 may store a program for execution by thecontroller206, including computer-readable program code for causing thecontroller206 to execute various steps and achieve wide-ranging functionality. In a non-limiting embodiment, thecurrent signature212 can take the form of a bit pattern having a certain number of bits. In accordance with an embodiment of the present invention, the bit pattern exhibited by thecurrent signature212 is dynamic, that is to say thecurrent signature212 changes over time.

Thecontroller206 executes various functions that allow communication to take place via thetransceiver204 between thetag14 and an external reader such as thereader12. In what follows, communications will hereinafter be referred to as occurring with thereader12 although it will be appreciated that thetag14 may communicate similarly with other external readers that it encounters.

As part of its functionality, thecontroller206 is operative to retrieve thecurrent signature212 from thememory202 and to release thecurrent signature212 via thetransceiver204. Alternatively, depending on the computational capabilities of thecontroller206, thecontroller206 can be operative to compute thecurrent signature212 on demand and to release via thetransceiver204 thecurrent signature212 so computed.

It is recalled that in this embodiment, thecurrent signature212 is dynamic. Accordingly, thecontroller206 is operative to communicate with thememory202 in order to change the bit pattern of thecurrent signature212 stored in thememory202. This can be achieved by executing diverse functionality that will be described in greater detail later on, and which may include implementing functional elements such as anencryption engine222, acounter230, apseudo-random number generator240, a geo-location module250 and aclock module260, among others.

The configuration of thepower source208 and its inter-relationship with thecontroller206 depend on whether thetag14 is categorized as “passive”, “active” or somewhere in between. Specifically, thetag14 may be designed as “passive”, whereby transmissions of thecurrent signature212 via thetransceiver204 are effected in response to detection of a burst of energy via thetransceiver204, such burst of energy typically coming from thereader12 issuing a “read request”. In this case, thecontroller206 only needs to be powered during the short time period following the detection of the burst. In fact, the burst itself can charge thepower source208 for a brief period, enough to allow thecontroller206 to cause transmission of thecurrent signature212 via thetransceiver204 in response to the read request. Thecurrent signature212 may be extracted from thememory202 or it may be generated on demand, upon receipt of the read request.

Alternatively, in some embodiments of an “active” tag, transmissions of thecurrent signature212 via thetransceiver204 are similarly effected in response to detection of a read request via thetransceiver204. In this case, the availability of thepower source208 allows thecontroller206 to transmit thecurrent signature212 at a longer range than for passive devices. Certain active tags also have the capability to switch into a passive mode of operation upon depletion of thepower source208. In other embodiments of an active tag, transmissions of thecurrent signature212 are effected via thetransceiver204 at instances or intervals that are controlled by thecontroller206. This can be referred to as autonomous (or unsolicited) issuance of thecurrent signature212. To this end, thecontroller206 needs to be continuously powered from thepower source208.

Active and passive tags may have other features that will be known to those of skill in the art.

In still other cases, the power source208 (either continually storing a charge or accumulating a sensed charge) can be connected to thecontroller206 via aswitch210, which is optional. Theswitch210 can be toggled between a first state during which an electrical connection is established between thepower source208 and thecontroller206, and a second state during which this electrical connection is broken. Theswitch210 is biased in the second state, and can be placed into the first state. Toggling into the first state can be achieved by a burst of energy that is sensed at a sensor (not shown) or by use of an activation element. In various non-limiting embodiments, the activation element may be a touch-sensitive pad on a surface of thetag14, or a mechanical component (e.g., a button). Placing theswitch210 into the first state may also trigger thecontroller260 to change thecurrent signature212 in thememory202.

With reference now toFIG. 3, there is shown conceptually how thecurrent signature212 stored in thememory202 may change over time. Specifically, different versions of the current signature212 (denoted S_Aand S_B) are generated by anencoding function302 implemented by thecontroller206. For notational convenience, thecurrent signature212 is used to denote which of the two signatures S_A, S_Bis currently stored in thememory202. Theencoding function302 generates the signatures S_Aand S_Bby encoding a common “identifier” (denoted I_D) with a respective “additional data set” (denoted D_Aand D_B) at respective time instants (denoted T_Aand T_B). Thus, at T_A, the signature S_Ais generated by encoding the identifier I_Dwith the additional data set D_A, whereas at T_B, the signature S_Bis generated by encoding the identifier I_Dwith the additional data set D_B. While in this example, two time instants are shown and described, this is solely for simplicity, and it should be understood that in actuality, thecurrent signature212 may change many times.

The identifier I_Dis constant, and in one embodiment conveys information about the item, animal, vehicle, piece of equipment, etc., to which thetag14 is affixed. Examples of such information include, without limitation: a serial number, a universal product code (UPC), a vehicle registration number (VIN) and a customized identifier. In another embodiment, the identifier I_Dconveys information about an expected user of the vehicle, clothing or mobile communication device, computer, restricted access area, network, etc., to which thetag14 is affixed. Examples of such information include, without limitation: a name, an ID number, a driver's license number, an account number and login credentials.

In accordance with a non-limiting embodiment of the present invention, the additional data sets D_Aand D_Bare different, which makes both signatures S_A, S_Bdifferent. In fact, the two signatures S_A, S_Bwill appear scrambled relative to one another due to use of theencryption engine222 within theencoding function302. More specifically, the signatures S_Aand S_Bcan be generated from the additional data sets D_Aand D_Bin a variety of ways, two of which will be described herein below.

First Approach

In a first approach, described with reference toFIG. 4A, the identifier I_Dis encrypted by theencryption engine222 with a dynamic key—represented by the additional data sets D_A, D_Bthemselves, resulting in the two signatures S_A, S_B. The two signatures S_A, S_Bwill be different because the additional data sets D_A, D_Bare different. In fact, they will appear scrambled relative to one another when observed by someone who has not applied a decryption process using a counterpart to the keys used by theencryption engine222.

It will be noted that in order to make the first approach practical, thereader12 needs to have knowledge of which key (i.e., which of the additional data sets D_A, D_B) was used for encryption of a received one of the signatures S_A, S_B, in order to effect proper decryption and recover the identifier I_D. For this purpose, in order to assist thereader12 in identifying the correct key to be used for decryption, and with reference again toFIG. 2, thecurrent signature212 may be accompanied by anindex214 also stored in thememory202. Theindex214 may point thereader12 to the correct key to be used. Thereader12 may have access to a key database (not shown) for this purpose.

For example, consider the case where the keys (in this case, the additional data sets D_A, D_B) correspond to outputs of thepseudo-random number generator240 having a seed known a priori to thetag14 and to thereader12. Here, at T_A, theindex214 may indicate the sequential position in the output of thepseudo-random number generator240 that corresponds to the additional data set D_A, while at T_B, theindex214 may indicate the sequential position in the output of thepseudo-random number generator240 that corresponds to the additional data set D_B. Thereader12 can then easily find the value occupying the correct sequential position in the output of an identical local pseudo-random number generator and effect successful decryption of the received signature (S_Aor S_B).

Alternatively, the keys (in this case, the additional data sets D_A, D_B) are provided by thereader12. This can be done where the reader12 (or an entity associated therewith) decides that a change in thecurrent signature212 is required. As a variant, thereader12 may issue a trigger which, when received by thecontroller206, causes thecontroller206 to effect a change in thecurrent signature212. In such cases, changes to the key (and thus to the current signature212) are effected by thecontroller206 in response to triggers received from thereader12.

Second Approach

For other applications, the approach ofFIG. 4B may be useful. Here, the identifier I_Dis augmented with differing scrambling codes (denoted C_Aand C_B), and then encrypted by theencryption engine222 with a common key (denoted K), thus producing the two signatures S_A, S_B. The “additional data set” D_Aused for encryption at T_Ais therefore composed of the key K and the scrambling code C_A, while the “additional data set” D_Bused for encryption at T_Bis composed of the same key K and the scrambling code C_B. The encryption process can be designed so that small differences (in terms of the number of bits where there is a difference) between the scrambling codes C_Aand C_Bwill cause large differences (in terms of the number of bits where there is a difference) in the resultant signatures S_Aand S_B. Thus, the scrambling codes C_A, C_Bhave the effect of scrambling (i.e., randomizing) the resultant signatures S_A, S_B.

Thecontroller206 is responsible for determining which scrambling code is to be used to generate a particular signature at a particular time instant. The current version of the scrambling code can be stored in thememory202 and is denoted220 for convenience. It will be appreciated based on the above description that the scrambling code C_Acorresponds to thecurrent scrambling code220 at T_Aand that the scrambling code C_Bcorresponds to thecurrent scrambling code220 at T_B.

Continuing with the second approach, several classes of embodiments are contemplated for changing thecurrent scrambling code220. In a first class of embodiments relevant to the approach ofFIG. 4B, thecurrent scrambling code220 is changed in a way that can be predicted by thereader12, that is to say, where the reader12 (or an entity associated therewith) has knowledge of how each successive scrambling code is generated.

For example, thecurrent scrambling code220 can be changed each time (or, generally, each N^thtime where N≧1) that thecontroller206 receives a read request or releases thecurrent signature212 in response to a read request. This can ensure that thecurrent signature212 is different each N^thtime that thecontroller206 receives a read request. Alternatively, thecurrent scrambling code220 is changed every thecurrent scrambling code220 can be changed every set period of time (ex. every N seconds, minutes, hours, days, etc.). The variations in thecurrent scrambling code220 may governed in a variety of ways that are predictable to thereader12. For example, thecontroller206 may implement acounter230, whose output is incremented (by a step size that can equal unity or can be negative, for example) after each N^thtime that thecontroller206 responds to a read request received from a nearby reader (or each N seconds, etc.). If thecurrent scrambling code220 is set to correspond to the current output of thecounter230, then the scrambling codes C_A, C_Bused to generate the two signatures S_A, S_Bwill differ by the step size.

Alternatively, thecontroller206 may implement the aforesaidpseudo-random number generator240, which produces an output that depends on one or more previous values of the output and on a seed. If thecurrent scrambling code220 is set to correspond to the current output of thepseudo-random number generator240, then the scrambling codes C_A, C_Bused to generate the two signatures S_A, S_Bwill differ in accordance with the characteristics of thepseudo-random number generator240.

Other variants will become apparent to those of skill in the art without departing from the scope of the present invention.

In a second class of embodiments relevant to the approach ofFIG. 4B, the additional data sets D_A, D_Bare not only predicted by thereader12 but are actually controlled by thereader12. This can be useful where the reader12 (or an entity associated therewith) decides that a change in thecurrent signature212 is required. Alternatively, and recognizing that the key K is common to both of the additional data sets D_A, D_B, thereader12 could supply the unique portions of the additional data sets D_A, D_B, namely the scrambling codes C_A, C_B.

As a variant, thereader12 may simply issue a trigger which, when received by thecontroller206, causes thecontroller206 to effect a change in thecurrent signature212. In such cases, changes to thecurrent signature212 are effected by thecontroller206 in response to triggers received from thereader12.

In a third class of embodiments relevant to the approach ofFIG. 4B, it may be desired to change the signatures S_A, S_Bin a stochastic way, that is to say, without the need to follow an underlying pattern that could be predicted by thereader12.

For example, thecontroller206 may implement the aforementioned geo-location module250, which is configured to output a current spatial position of thetag14 or of an item or person to which it is affixed. If thecurrent scrambling code220 is set to correspond to the current output of the geo-location module250, then the scrambling codes C_A, C_Bused to generate the two signatures S_A, S_Bwill differ in a stochastic fashion.

Alternatively, thecontroller206 may implement aclock module260, which is configured to determine a current time. If thecurrent scrambling code220 is set to correspond to a value measured by the clock module260 (e.g., number of milliseconds elapsed since midnight of the day before), then the scrambling codes C_A, C_Bused to generate the two signatures S_A, S_Bwill differ in a stochastic fashion.

While the above embodiments have focused on temporal variations in thecurrent signature212 stored in thememory202 of thetag14, it is also within the scope of the present invention for thecurrent signature212 stored in thememory202 of two different tags to be different at a common time instant (e.g., at a time when the tags are being read in bulk). This can be referred to as spatial scrambling. More particularly, with reference toFIG. 5, a plurality oftags514 are affixed to a number ofunits506 of a particular article. Theunits506 may be arranged on apallet508, on a shelf or in a container, for example. To take a simple non-limiting example, the article in question can be a pair of denim jeans of a certain brand, size, style and color. Of course, the article could be any other item of which multiple units are available, such as a consumer product, food product, vehicle, etc. Other possibilities that may appear to one of skill in the art are within the scope of the present invention.

Thetags514 storerespective signatures510 that are each derived by encrypting an identifier550 (common to the tags514) and a respective one of a plurality of current scrambling codes520 (different for the various tags514) with a common key. Thecommon identifier550 can be used to identify the article in question (in this case, a pair of jeans of a particular brand, size, style, color, etc.). To ensure that thesignatures510 appear scrambled while nevertheless encrypting thecommon identifier550, approaches such as the following may be taken.

In one non-limiting approach, a centralized entity generates uniquecurrent scrambling codes520 andunique signatures510 for each of thetags514. Thetags514 are pre-loaded with their respectiveunique signatures510 before being affixed to theunits506. In this approach, theunique signatures510 are fixed, as a result of which thetags514 can be greatly simplified since they do not need to perform any processing functions. Practically speaking, this allows a distributor to purchase a plurality oftags514 that have been pre-loaded withunique signatures510 in order to securely identify theunits506 of a particular article.

In another non-limiting approach, thetags514 may each operate a respective clock module which, though structurally identical, may output different results, due to differences in oscillation characteristics (e.g., the oscillation crystals used, etc.) This will result in differences between the current scrambling code produced based on an output of the clock module of one of thetags514 and the current scrambling code produced based on an output of the clock module of another one of thetags514, albeit at the same time instant.

In yet another non-limiting approach, differentcurrent scrambling codes520 can be produced as a result of thetags514 each operating a respective pseudo-random number generator using a different seed, which could be pre-loaded by the above mentioned centralized entity.

Still other ways of making thecurrent scrambling codes520 different among thevarious tags514 are within the scope of the present invention.

It is noted that thesignatures510 will tend to be widely varying even if the differences in thecurrent scrambling codes520 used to generate them are small, this effect being due to application of an encryption process, even when a common key is used. In fact, to an observer not equipped with the complementary key for decryption (which may be the same as the common key in a symmetric encryption scenario), thesignatures510 corresponding to thevarious units506 on thepallet508 will appear scrambled. This provides protection against external observers (e.g., thieves, corporate intelligence investigators) who may have gathered knowledge of signatures output by one or more units of the article in the past (e.g., from a previous purchase—or knowledge of a previous shipment—of the same brand, size, style and color of jeans) and are now on the lookout for the presence of units of the same article on thepallet508. On the other hand, by using the appropriate key in order to decrypt any of thesignatures510, then no matter how diverse one such signature is from another, thecommon identifier550 will be revealed alongside a stochastically derived scrambling code.

In order to allow thereader12 to identify the appropriate key for decryption, each of thesignatures510 may be accompanied by theaforesaid index214 stored in thememory202. Theindex214 may point thereader12 to the correct key for decryption. For example, theindex214 could be a piece of public information such as a manufacturer identification code or a product category, such information being common to theunits506 but sufficiently generic to be of little value to an outside observer. This will allow the reader12 (or an entity associated therewith) to select the correct key for decryption by accessing a table of keys (not shown) on the basis of the index. Such an approach can be useful to accelerate the decryption process and reduce the incidence of false positives (successful but inadvertent decryption of the wrong identifier) when multiple keys are potentially available to thereader12.

It should also be appreciated that thesignatures510 on thevarious tags514 can, in addition, be designed to change in a dynamic fashion (as described earlier), thus providing, in addition to spatial scrambling of thesignatures510, temporal scrambling of thesignatures510 that leads to even greater security vis-à-vis external observation.

In view of the foregoing, it should thus be appreciated that a common identifier, which is encoded within a plurality of signatures that vary over space (for multiple tags) and/or time (for the same tag), can be extracted by the reader12 (or an entity associated therewith) by utilizing the appropriate key for decryption. This allows the reader12 (or an entity associated therewith) to perform

- (I) validation of the identifier based on the signature and/or the scrambling code; and/or
- (II) an action related to identification, based on the identifier.

Both of these scenarios, which are not mutually exclusive, are now described in some detail.

In scenario (I), a dynamic scrambling code is used in the generation of a signature that continually encodes the same identifier, and it is of interest to recover the current scrambling code to detect a potential instance of tag cloning. Accordingly, with reference toFIG. 6A, there is shown a system that is similar to the system ofFIG. 1. In addition, the system ofFIG. 6A comprises aprocessing entity610 that implements a validation operation, as will be described herein below. In various embodiments, theprocessing entity610 referred to above may be connected to thereader12, or it may be a remote entity. Such a remote entity may be reachable over a network, or it may be integrated with thereader12. The system ofFIG. 6A also includes a storage entity, such as adatabase602, that is accessible to theprocessing entity610 and stores a plurality ofrecords604, each associated with a respective identifier. For the purposes of the present example, one can consider that each identifier for which there exists a record in thedatabase602 is indicative of a privilege to access certain property or make certain transactions, although other scenarios are possible without departing from the scope of the present invention.

In accordance with one embodiment of the present invention, each of therecords604 also comprises afield606 indicative of zero or more scramblingcodes608 that were encoded in signatures which were previously received and which encoded the respective identifier for that record. Thus, receipt of a particular signature that encodes the identifier in a given one of therecords604 as well as one of the scrambling code(s)608 stored in thecorresponding field606 will indicate that the particular signature has been previously received and therefore its instant receipt may be indicative that a cloning attempt has been made.

More specifically, with reference to the flowchart inFIG. 7A, consider what happens followingstep710 when a signature S_Xis received at a particular time instant by thereader12. At the time of receipt, whether the signature S_Xencodes any particular identifier or scrambling code is unknown to thereader12. Atstep730, an attempt to decrypt the signature S_Xis made by theprocessing entity610 using a decryption key K_X. The decryption key K_Xmay be known in advance to theprocessing entity610. Alternatively, as shown instep720, the signature S_Xmay be accompanied by an index that allows theprocessing entity610 to determine the appropriate decryption key K_X. The result of the decryption attempt atstep730 is a candidate identifier I_Xand a candidate scrambling code, denoted C_X.

Atstep740, theprocessing entity610 consults thedatabase602 based on the candidate identifier I_Xin an attempt to identify a corresponding record and extract therefrom a list of scrambling code(s) that have been received in the past in association with the candidate identifier I_X. For the purposes of the present example, it is useful to assume that such a record exists (i.e., the “YES” branch is taken out of step740), but if there is no such record, this may indicate that there is a high-level failure requiring further action. Atstep750, theprocessing entity610 compares the candidate scrambling code C_Xto the scrambling code(s)608 in thefield606 of the record identified atstep740 and corresponding to identifier I_X.

If there is a match, this indicates that the scrambling code C_Xhas been used in the past in association with the identifier I_X. Under certain conditions, this may lead theprocessing entity610 to conclude that the validation operation was unsuccessful.

For example, if the signature S_Xwas expected to change at least as often as every time that the tag on which it is stored was read, then the fact that the scrambling code C_Xmatches one of the scrambling code(s)608 stored in thefield606 of the record corresponding to identifier I_Xmay lead theprocessing entity610 to conclude that the validation operation was unsuccessful. Alternatively, if the signature S_Xwas expected to change every N^thtime that the tag on which it is stored was read, then theprocessing entity610 may look at how many of the scrambling code(s)608 stored in thefield606 of the record corresponding to identifier I_Xcorrespond to the scrambling code C_X, and if this number is greater than or equal to N, this may lead theprocessing entity610 to conclude that the validation operation was unsuccessful. Alternatively still, if the signature S_Xwas expected to change at least as often as every N seconds etc., then theprocessing entity610 may look at how long ago it has been since a matching one of the scrambling code(s)608 was first stored in thefield606 of the record corresponding to identifier I_X, and if this time interval is greater than or equal to a pre-determined number of seconds, minutes, hours, days, etc., this may lead theprocessing entity610 to conclude that the validation operation was unsuccessful. Where a conclusion is reached that the validation operation was unsuccessful, the privilege to access the property or make transactions may be revoked or at least questioned on the basis of suspected tag cloning.

On the other hand, if there is no match between the scrambling code C_Xand any of the scrambling code(s)608 stored in thefield606 of the record corresponding to identifier I_X, this may lead theprocessing entity610 to conclude that the validation operation was potentially successful. In such a case, the default privilege to access the property or make transactions may be granted (or at least not revoked on the basis of suspected tag cloning).

In accordance with an alternative embodiment of the present invention, thefield606 in the record associated with each particular identifier may be indicative of an “expected” scrambling code, i.e., the scrambling code that should (under valid circumstances) be encoded in a signature received from a tag that encodes the particular identifier. Alternatively, thefield606 in the record associated with each particular identifier may be indicative of an “expected” signature, i.e., the signature that should (under valid circumstances) be received from a tag that encodes the particular identifier. Thus, upon receipt of the signature S_X, if it is found to correspond to the expected signature (or if the scrambling code C_Xis found to correspond to the expected scrambling code), this may lead theprocessing entity610 to conclude that the validation operation was potentially successful. On the other hand, if there is no match between the signature S_Xand the expected signature stored in the database602 (or between the scrambling code C_Xand the expected scrambling code), this may lead theprocessing entity610 to conclude that the validation operation was unsuccessful.

It should be appreciated that in the above alternative embodiments, theprocessing entity610 may obtain knowledge of the expected scrambling code or the expected signature by implementing plural pseudo-random number generators for each of the identifiers, analogous to thepseudo-random number generator240 implemented by thecontroller206 in a giventag14, which produces an output that depends on one or more previous values of the output and on a seed. Thus, the next output of the pseudo-random number generator implemented by theprocessing entity610 for a given identifier allows theprocessing entity610 to predict the scrambling code (or the signature) that should be received from a tag legitimately encoding the given identifier. In another embodiment, theprocessing entity610 may know what is the expected scrambling code/signature because it has instructed thereader12 to cause this expected scrambling code/signature to be stored in the memory of the tag.

In accordance with an alternative embodiment of the present invention, thedatabase602 simply comprises a running list of all signatures that have been received in the past. Thus, upon receipt of the signature S_X, if it is found to correspond to one of the signatures on the list, this may lead theprocessing entity610 to conclude that the validation operation was unsuccessful. On the other hand, if there is no match between the signature S_Xand any of the signatures stored in thedatabase602, this may lead theprocessing entity610 to conclude that the validation operation was potentially successful (or at least not unsuccessful).

It should also be appreciated that having obtained the identifier I_X, theprocessing entity610 may also perform an action related to identification of an item associated with the particular tag that encoded the identifier I_X.

In a first example of an action related to identification, theprocessing entity610 may simply note the fact that the item (bearing the identifier I_X) was encountered in a vicinity of thereader12. This information may be stored in a database (not shown) or sent as a message, for example. In an inventory management scenario, theprocessing entity610 may consult an inventory list and “check off” the item as having been located, or may signal that the presence of a spurious item (that is not on the inventory list) has been detected.

In another example of an action related to identification, theprocessing entity610 may consult another database (not shown) in order to ascertain whether the identifier is on a list of identifiers associated with individuals/objects permitted to access, or prohibited from accessing, certain property. Examples of property include, without limitation: computing equipment, a computer network, a building, a portion of a building, an entrance, an exit and a vehicle.

In another example of an action related to identification, theprocessing entity610 may consult another database (not shown) in order to ascertain whether the identifier is on a list of identifiers associated with individuals permitted to effect, or prohibited from effecting, a transaction, which could be a financial transaction or a login to controlled online content, for example.

FIG. 7B shows a variant where multiple keys are possible but no index (or one that does not permit identification of the appropriate decryption key) is provided along with the signature S_X. Specifically, taking the “NO” branch afterstep750 does not conclude the validation operation. Rather, the validation operation goes throughstep770 where a next key is selected and then the validation operation returns to step730, wherebysteps730 through770 are re-executed until the earlier occurrence of (i) taking the “YES” branch atstep750 and (ii) exhaustion of all keys, which can result in the equivalent of taking the “NO” branch out of740 (i.e., this may indicate that there is a high-level failure requiring further action).

It should be appreciated that in the above embodiments, encryption and decryption can be effected using various techniques known in the art, including encryption using a symmetric key, an asymmetric key pair, a public/private key pair, etc., as well as in accordance with a variety of algorithms and protocols For example, RSA and ECC are suitable examples of asymmetric encryption algorithms, while AES, DES, and Blowfish are suitable examples of symmetric algorithms. Still other possibilities exist and are within the scope of the present invention.

In the above example with reference toFIGS. 6A,7A and7B, although a single reader was described and illustrated, it should be appreciated that it is within the scope of the present invention to provide a multi-reader architecture, as shown inFIG. 6B. A plurality ofreaders1012 are connected to each other and to acentralized control entity1010 by anetwork1030, which can be a public packet-switched network, a VLAN, a set of point-to-point links, etc. In such a case, the centralized control entity1010 (e.g., a network controller) can implement the functionality of theprocessing entities610, including encryption and validation. To this end, thecentralized control entity1010 maintains amaster database1020, which includes the equivalent of a consolidated version of various instances of thedatabase602 previously described as being associated with thereader12 in the single-reader scenario.

Thus, decryption and validation can be performed entirely in thecentralized control entity1010. Alternatively, certain functionality (such as decryption) can be performed by thereaders1012 while other functionality (such as validation) can be performed by thecentralized control entity1010. Still alternatively, theprocessing entities610 can inter-operate amongst themselves in the absence of thecentralized entity1010, thereby to implement decryption on a local basis, and the validation operation in a joint fashion. In such a distributed scenario, themaster database1020 can still be used, or theprocessing entities610 can communicate with one another to share information in theirrespective databases602.

In scenario (II), a dynamic key is used in the generation of a signature that encodes a constant identifier, and it is of interest to recover the underlying identifier despite the time-varying key. Accordingly, with reference now toFIG. 8, there is shown a system that is similar to the system ofFIG. 1. In addition, the system ofFIG. 8 comprises aprocessing entity810 that implements an identification operation, as will be described herein below. Theprocessing entity810 may be connected to thereader12, or it may be a remote entity. Such a remote entity may be reachable over a network, or it may be integrated with thereader12. It should be understood that the system inFIG. 8 is being shown separately from the system inFIG. 6; however, it is within the scope of the present invention to combine the functionality of both systems.

With reference to the flowchart inFIG. 9, consider what happens followingstep910 when a signature S_Yis received from a particular tag at a particular time instant by thereader12. The signature S_Yis assumed to have been generated by encrypting an identifier I_Yusing an encryption key that varies in a dynamic fashion. To this end, the particular tag may have generated the dynamic encryption key based on, for example:

- the output of the aforementioned clock module260 (e.g., in terms of seconds, minutes or hours of elapsed time since an event known also to the processing entity810);
- the output of the aforementioned geo-location module250;
- an index;
- a seed for use by a pseudo-random number generator.

Still other possibilities are within the scope of the present invention. The decryption key can then be determined based on the above quantity. For example, the decryption key could be the above-mentioned output of the clock module or the geo-location module. Alternatively, the encryption key could be the output of a table or a pseudo-random number generator (both known to the processing entity810) based on the above-mentioned seed, or at a position that corresponds to the above-mentioned index. In the latter case, the index or seed can be supplied along with the signature S_Y.

In accordance with the present embodiment, once the signature S_Yis read by thereader12, theprocessing entity810 is expected to determine the appropriate decryption key, denoted K_Y. Accordingly, atstep930, theprocessing entity810 first determines a dynamic parameter that will allow the decryption key K_Yto be determined. Examples of the dynamic parameter include:

- the output of a clock module (which attempts to emulate the aforementioned clock module260) at the time of receipt of the signature S_Y(e.g., in terms of seconds, minutes or hours of elapsed time since a known event);
- the output of a geo-location module (which can be similar to the aforementioned geo-location module250);
- the index or seed provided along with the signature S_Y.

Next, atstep940, theprocessing entity810 obtains the decryption key K_Ybased on the dynamic parameter determined atstep930. For example, where the dynamic parameter corresponds to the output of a clock module or a geo-location module, the decryption key K_Ycould be the dynamic parameter itself. Alternatively, where the dynamic parameter is an index or a seed, the decryption key K_Ycould be the output of the aforementioned table or pseudo-random number generator known to theprocessing entity810, at a position that corresponds to the received index, or using the received seed.

Once the decryption key has been obtained, the signature S_Yis decrypted atstep950 using the decryption key. This leads to extraction of the identifier I_Y. It is noted that a scrambling code was not required in this embodiment, although its use is not disallowed. Having obtained the identifier I_Y, theprocessing entity810 proceeds to step960, where it performs an action related to identification of an item associated with the particular tag that encoded the identifier I_Y.

In a first example of an action related to identification, theprocessing entity810 may simply note the fact that the item (bearing the identifier I_y) was encountered in a vicinity of thereader12. This information may be stored in a database (not shown) or sent as a message, for example. In an inventory management scenario, theprocessing entity810 may consult an inventory list and “check off” the item as having been located, or may signal that the presence of a spurious item (that is not on the inventory list) has been detected.

In another example of an action related to identification, theprocessing entity810 may consult another database (not shown) in order to ascertain whether the identifier is on a list of identifiers associated with individuals/objects permitted to access, or prohibited from accessing, certain property. Examples of property include, without limitation: computing equipment, a computer network, a building, a building, a portion of a building, an entrance, an exit and a vehicle.

In yet another example of an action related to identification, theprocessing entity810 may consult another database (not shown) in order to ascertain whether the identifier is on a list of identifiers associated with individuals permitted to effect, or prohibited from effecting, a transaction, which could be a financial transaction or a login to controlled online content, for example.

It should be appreciated that theprocessing entity810 may also perform an action related to validation of the identifier I_Yin conjunction with the above action related to identification. Specifically, in accordance with one embodiment of the present invention, the processing entity may consult a variant of theaforementioned database602, where each of therecords604 now includes a field indicative of zero or more signatures which were previously received and which encoded the respective identifier for that record. Thus, receipt of a particular signature that encodes the identifier in a given one of therecords604 as well as one of the signature(s) stored in the corresponding field will indicate that the particular signature has been previously received and therefore its instant receipt may be indicative that a cloning attempt has been made.

In the above example with reference toFIGS. 8 and 9, although a single reader was described and illustrated, it should be appreciated that it is within the scope of the present invention to provide a multi-reader architecture, as inFIG. 6B.

Also, those skilled in the art will appreciate that in some embodiments, the functionality of any or all of theprocessing entity610, theprocessing entity810, thereader12 and thereaders1012 may be implemented using pre-programmed hardware or firmware elements (e.g., application specific integrated circuits (ASICs), electrically erasable programmable read-only memories (EEPROMs), etc.), or other related components. In other embodiments, the functionality of the entity in question may be achieved using a computing apparatus that has access to a code memory (not shown) which stores computer-readable program code for operation of the computing apparatus, in which case the computer-readable program code could be stored on a medium which is fixed, tangible and readable directly by the entity in question (e.g., removable diskette, CD-ROM, ROM, fixed disk, USB drive), or the computer-readable program code could be stored remotely but transmittable to the entity in question via a modem or other interface device (e.g., a communications adapter) connected to a network (including, without limitation, the Internet) over a transmission medium, which may be either a non-wireless medium (e.g., optical or analog communications lines) or a wireless medium (e.g., microwave, infrared or other transmission schemes) or a combination thereof.

While specific embodiments of the present invention have been described and illustrated, it will be apparent to those skilled in the art that numerous modifications and variations can be made without departing from the scope of the invention as defined in the appended claims.