ID tag, tag reader, ID scrambling and descrambling methods, and tag manager

0001The present invention generally relates to a system comprising an ID tag and a tag manager. The tag manager may be utilized in mobile; communication systems.

0002RFID tags are well known in this art as disclosed in, for example, Patent Documents #1, #2 and #3 below, which can be applied to mobile communication systems. An example of such an RFID system is shown in <figref idref="f0001">Fig. 1</figref>.

0003In <figref idref="f0001">Fig. 1</figref>, an authentic first tag 7 transmits its own tag ID as it is without concealing the tag ID. The first tag 7 is placed at a fixed location. The tag ID of the first tag 7 and information about the first tag 7 are correlated and held in a server 2. In this manner, the server 2 can provide a service in which the location information of the first tag 7 is provided to a mobile station 5. Other types of services reflating to the location of tags are also available.

0004In such a location notifying service, the first tag 7 is placed at A station East exit. The tag ID of the first tag 7 and the location information of the first tag 7 are correlated and held in the server 2. When a reader 6 coupled to or integrated with the mobile station 5 moves close to the first tag 7, the reader 6 receives tag ID information transmitted from the first tag 7.

0005The reader 6 outputs the received tag ID information to the mobile station 6. The mobile station 6 extracts a tag ID ("12345678" in the example shown in <figref idref="f0001">Fig. 1</figref>) from the received tag information, sends information obtained from the first tag ID 7 to the server 2 via a first base station 3 and a network together with an inquiry as to where the first tag 7 is located. As mentioned above, the server 2 holds information of "A station East exit" correlated to the tag ID of the first tag 7, and answers to the mobile station 5 "A station East exit".

0006Accordingly, the user of the mobile station 5 recognizes that he is now at the East exit of A station.

0007A counterfeit tag (a second tag 8 in <figref idref="f0001">Fig. 1</figref>) transmitting the same ID "12345678" as the first tag 7 is located at B station East exit. If the mobile station 5 moves close to the second tag 8 and receives the ID of the tag 8, the same information "A station East exit" is provided to the mobile station 5. Although the user is actually at the East exit of B station, the user receives wrong information "A station East exit". If many counterfeit tags like this are placed at many places, the location notifying service becomes unreliable.

0008In another available service, a user having a mobile station with tag reader function can monitor an ID transmitted from a tag attached to his wallet to always know where the wallet is, and he can notice that he forgot or dropped the wallet. Such a tag transmits a constant ID. Therefore, someone can detect the constant ID and know where the tag holding person is, which may invade individual privacy. [Patent Document #1] <patcit id="pcit0001" dnum="JP2003524242A"><text>Japanese Laid-open, No. 2003-524242</text></patcit> [Patent Document #2] <patcit id="pcit0002" dnum="JP2002533846A"><text>Japanese Laid-Open No. 2002-533846</text></patcit> [Patent Document #3] <patcit id="pcit0003" dnum="JP2000224219A"><text>Japanese Laid-Open No. 2000-224219</text></patcit>

0009<patcit id="pcit0004" dnum="EP1469408A"><text>EP-A-1469408</text></patcit>, relevant only under EPC Art 54(3), discloses a pharmaceutical tracking system having a server and which authenticates tags attached to packaging of pharmaceutical products.

0010The invention providers a system as defined in Claim 1.

0011The present invention can recognize counterfeit tags and avoid service degradation and privacy invasion.

BRIEF DESCRIPTION OF THE DRAWINGS

0012<ul id="ul0001" list-style="none"><li><figref idref="f0001">Fig. 1</figref> schematically shows a conventional RFID system employing RAPID tags;</li><li><figref idref="f0002">Fig. 2</figref> is a block diagram showing an ID tag and a tag reader;</li><li><figref idref="f0003">Fig. 3</figref> shows a data string;</li><li><figref idref="f0004">Fig. 4</figref> is a block diagram showing an ID tag;</li><li><figref idref="f0005">Fig. 5</figref> is a block diagram showing a tag reader;</li><li><figref idref="f0006">Fig. 6</figref> shows division methods;</li><li><figref idref="f0007">Fig. 7</figref> is a block diagram showing an alternative ID tag;</li><li><figref idref="f0008">Fig. 8</figref> schematically shows an RFID system according to an embodiment of the present invention;</li><li><figref idref="f0009">Fig. 9</figref> is a block diagram showing an ID tag and a tag reader, in which changes of the tag ID are recognized;</li><li><figref idref="f0010">Fig. 10</figref> is a flowchart showing a procedure of correcting a timer in the tag reader;</li><li><figref idref="f0011">Fig. 11</figref> is a block diagram showing an ID tag and a tag reader using CRC; and</li><li><figref idref="f0012">Fig. 12</figref> is a flowchart showing operations of the ID tag and the tag reader.</li></ul>

DESCRIPTION OF THE PREFERRED EMBODIMENTS

0013The following is a description of ID tags, tag reader, tag ID transmission methods, ID tag recovering methods, and tag managers.

0014Throughout all the figures, members and parts having the same or similar functions are assigned the same or similar reference numerals or symbols, and redundant explanations are omitted.

0015Apparatus outside the scope of the invention will first be described, to assist in understanding the invention, with reference to <figref idref="f0002 f0003 f0004 f0005 f0006 f0007">Figures 2 to 7</figref> and <figref idref="f0009 f0010 f0011 f0012">9-12</figref>.

0016A first system is explained below with reference to <figref idref="f0002">Fig. 2</figref> and <figref idref="f0012">Fig. 12</figref>.

0017<figref idref="f0002">Fig. 2</figref> is a block diagram generally showing an ID tag and a tag reader.

0018<figref idref="f0012">Fig. 12</figref> is a flow chart generally showing operations in the ID tag and the tag reader.

0019The ID tag 101 comprises an ID storage 102, an ID scrambler 103, a random value generator 104, a first tag unique value 105, a timer 106, a data constructor 107, a time information scrambler 108, a second tag unique value 109 and an output terminal 110.

0020In each tag 101, a predetermined unique tag ID is stored in the ID storage 102. Each tag can be identified by using this ID. An RF ID tag is typical for an RF transmission tag, but the present invention can be applied to the ID tag systems utilizing visible light and infrared-rays.

0021Two unique values of the first tag unique value 105 and the second tag unique value 109 are previously given to each tag 101. These tag unique values are not related to a tag ID mentioned below, and can be determined at random. The tag unique values do not have to be different from each other, but should be kept secret from persons other than readers and servers having authenticating functions. As for tags held by a mobile user, the "other person" means any person other than the mobile user. As for tags located at a predetermined location for providing location related services, the "other person" means any entity other than the provider of the services. In a tag, the first tag unique value and the second tag unique value may be the same, but when these values are different from each other, their security becomes higher because the decryption has to be done twice.

0022The first tag unique value 105 given to the tag 101 is input from the ID storage 102 to the random value generator 104. In the random value generator 104, using variables dependent on the first tag unique value 105, time information output from the timer 106 is converted to a random value dependent on time. As such randomizing operation processes, complex operational processes such as remainder calculation by generating a polynomial or bit permutation based on a matrix can be performed. More specifically, the random value generator 104 generates a matrix or vector uniquely corresponding to the first tag unique value 105, and can bit-permute the time information output from the timer 106 utilizing the matrix or can calculate remainders of division by the vector. The randomization is an example of concealing. In the present Specification and Claims, the "time" means not only an absolute time but also a counter for counting up by a time duration (such as one minute, one hour, one day, etc.) and the like, and the "time information" means an amount of the absolute time and a value in the counter and the like.

0023The generated random value dependent on time is input to the ID scrambler 103. In the ID scrambler 103, the ID of the tag 101 output from the ID storage 102 is scrambled with the random value. The scrambling process may include bit-to-bit exclusive OR operations between two input values. Scrambling is one example of concealing. Since the time information is employed, the resultant values are not constant even without any complex calculation, and have regularity, because of which the transmitted time information can be easily recovered in a receiver.

0024The scrambled tag ID is output to the data constructor 107 and subjected to additional processing mentioned below in the data constructor 107.

0025On the other hand, the second tag unique value 109 given to the tag 101 is input to the time information scrambler 108. In the time information scrambler 108, the time information output from the timer 106 is scrambled with the second tag unique value 109. Scrambling is one example of concealing. As an example of scrambling processing, a bit string uniquely corresponding to the second tag unique value 109 can be generated, and bit-to-bit exclusive OR operations are done between the bit string and the time information output from the timer 106.

0026The scrambled time information is input to the data constructor 107. In the data constructor 107, the scrambled time information is added to the scrambled tag ID to construct one data string as shown in <figref idref="f0003">Fig. 3</figref>. The constructed data string is output via the output terminal 110 to the outside of the tag 101.

0027The operating process in the tag 101 is explained using alpha expressions.

0028In the random value generator 104, the first unique value "i" is randomized with the time information c output from the timer 106, to obtain B (i) c^t. In the ID scrambler 103, the tag ID "a" is scrambled with the random value B(i)c^t, to obtain the scrambled tag ID a^t(+)B(i)c^t. On the other hand, in the time information scrambler 108, the time information "c" is scrambled with a scrambling vector d(j) dependent on the second tag unique value "j", to obtain the scrambled time information c^t(+)d(j)^t. The data string (c^t(+)d(j)^t , a^t(+)B(i)c^t ) mixing those two data items is output from the data constructor 107. B(i) means conversion matrix in the random value generator 104, (+) means exclusive OR and "t" means translocation.

0029Next, a tag reader 111 receiving the tag ID from the tag 101 is explained.

0030The tag reader 111 comprises an input terminal 120, a data separator 112, a time information descrambler 113, a second tag unique value 114, an ID recoverer 115, a random value generator 116, a first tag unique value 117, an authenticator 118 and an output terminal 119.

0031The tag reader 111 is also previously given the first tag unique value 117 and the second tag unique value 114, which are the same as the first tag unique value 105 and the second tag unique value 109 given to the tag 101, respectively.

0032One method of registering the tag unique values in the tag reader 111 held by an individual is that the individual previously registers the tag unique values of the tag 101 into the tag reader 111. As for a tag placed at a specific location, a tag unique value can be downloaded or provided via a mobile station from a tag manager such as a server and registered into the tag reader.

0033Data from the tag 101 received through the input terminal 120 is input to the data separator 112. The data separator 112 performs an operation inverse to that of the data constructor 107 of the tag 101, to separate or divide the received data into the scrambled time information and the scrambled tag ID. The scrambled time information is input to the time information descrambler 113, and the scrambled tag ID is input to the ID recoverer 115. The time information descrambler 113 performs an operation (descrambling) inverse to that of the time information scrambler 108 of the tag 101, using the second tag unique value 114 to extract the time information.

0034The extracted time information is input to the random value generator 116. Similar to the random value generator 104, the random value generator 116 converts the input time information to a value dependent on time, using the first tag unique value 117.

0035The random value obtained in the random value generator 116 is input to the ID recoverer 115. The ID recoverer 115 performs an operation inverse to that of the ID scrambler 103 of the tag 101, to convert the scrambled tag ID to the original tag ID.

0036The recovered tag ID is input to the authenticator 118. The authenticator 118 compares the previously stored tag ID and the recovered tag ID to determine authentication. If the tag ID transmitted by the tag 101 is incorrect, authentication is denied. Further, if the unique values used in the tag 101 transmitting the tag ID are incorrect, the recovered tag ID becomes incorrect, and then authentication is also denied. Accordingly, only when both the tag ID and the unique values are correct, authentication is affirmed. In this manner, authentication is performed by confirming whether the combination of the tag ID and the unique values are correct.

0037A tag ID determined to be authentic is output through the output terminal 119. A tag ID determined to be not authentic is discarded.

0038The operations process in the tag reader 111 is explained using alpha expressions.

0039The data separator 112 receives the data string (c^t(+)d(j)^t,a^t(+)B(i)c^t), and separates the data. The separated scrambled time information c^t(+)d(j)^t is input to the time information descrambler 113 and the separated scrambled tag ID a^t(+)B(i)c^t is input to the ID recoverer 115. The time information descrambler 113 uses the second tag unique value "j" and descrambles the scrambled time information c^t(+)d(j)^t to (c^t(+)d(j)^t)(+)d(j)^t = c^t, to extract the time information c^t, which is input to the random value generator 116. The random value generator 116 uses the input time information c^t and randomizes the first tag unique value "i" to obtain B(i)c^t.

0040The scrambled tag ID (a^t(+)B(i)c^t) is input from the data separator 112 to the ID recoverer 115. In the ID recoverer 115, the scrambled tag ID (a^t(+)B(i)c^t) is descrambled with B(i)c^t, to extract the recovered tag ID a^t, which is output to the authenticator 118.

0041In the above explained method, the tag ID and the time informations are both transmitted each time as shown in <figref idref="f0003">Fig. 3</figref>. However, by recognizing changes of the randomized tag ID, it is possible to eliminate the transmission of the time information. When registering tag unique values into the tag reader, the tag reader can be synchronized with the tag by resetting counters in the tag and tag reader. After: synchronization, the tag reader can recognize the counter value of the tag. Both counters are becoming offset as time goes by. However, since this offset does not appear so suddenly or drastically, the tag reader can recognize the changes of the scrambled ID sent from the tag. Therefore, the tag reader can compensate for the offset between the two counters. In such an alternative, tag reader can correctly recover the ID randomized with the time information even without transmitting the time information each time, as explained below.

0042Witch reference to <figref idref="f0009">Fig. 9</figref>, a method of recognizing the change of the tag ID randomized with the time informations is explained.

0043In this alternative, a tag reader 911 monitors a tag ID transmitted from a tag 901. The tag 901 randomizes the tag ID with time information from a timer 906; in a similar manner. The timer 906 in the tag 901 and a timer 913 in the tag reader 911 are reset simultaneously.

0044The timer 913 of the tag reader 911 can be synchronized with the timer 906 of the tag 901 initially, and the tag reader can determine authenticity of tag IDs by utilizing the synchronized timer 913. However, both the timers 906 and 913 operate separately and become different from each other more and more with passing time.

0045When an authenticator 918 of the tag reader 911 determines that a tag ID is incorrect, the tag reader 911 performs a correction process on the timer 913. The correction process can be done by a method as shown in <figref idref="f0010">Fig. 10</figref>.

0046Since the tag reader 911 knows the randomized tang 10 value after resetting, the tag reader can recognize the timer value in the tag 901 by recognizing the received randomized tag ID value. It is also possible to correct the timer 913 to the time when the tag ID has been received.

0047In the alternative, CRC (Cycle Redundancy Code) generated by the tag ID can be also used.

0048As shown in <figref idref="f0011">Fig. 11</figref>, based on a tag ID output from an ID storage 1102, a CRC calculator 1108 of a tag 1101 generates a CRC, and mixes the generated CRC and the tag ID and outputs them to an ID scrambler 1103. Other processes are the same as in the above alternative.

0049An authenticator 1118 of a tag reader 1111 calculates the CRC using a recovered tag ID, and compares the calculated CRC and a received CRC calculated by the tag 1101. If they are the same, the authenticator 1118 determines that the tag ID is authentic, and if they are different, the authenticator 1118 determines that.the tag ID is counterfeit.

0050<figref idref="f0004">Fig. 4</figref> is a block diagram generally showing an ID tag

0051A tag 201 comprises an ID storage 202, an ID divider 203, two padders 204, a timer 205, two ID fragment scramblers 206, two random value generators 207, a third tag unique value 208, a fourth tag unique value 209, an output switch 210, and an output terminal 211.

0052In the 201, a tag ID output from the ID storage 202 is input to the ID divider 203, where the tag is divided into a plurality of tag ID fragments. In this second embodiment, the number of fragments is two, but is not limited to two. The divided tag ID fragments may have the same length or may have different lengths. There may be a variety of dividing methods. As shown in <figref idref="f0006">Fig. 6A</figref>, the tag ID can be divided into the MSB side and the LSB side. As shown in <figref idref="f0006">Fig. 6B</figref>, the tag ID can be divided so as to extract specific bits according to a predetermined rule.

0053The divided tag ID fragments are subject to a padding process (filling with bits process) in the padder 204. For example, a 64-bit tag ID is divided into a 20-bit fragment and a 44-bit fragment, and the 20-bit fragment is padded with 44 bits to lengthen the fragment to the original size and the 44-bit fragment is padded with 24 bits to lengthen it to the original size. Each padder 204 can further scramble the tag ID fragment depending on the tag ID fragment ordering. The first tag ID fragment can be scrambled with a value dependent on the third tag unique value and the second tag ID fragment can be scrambled with a value dependent on the fourth tag unique value. This additional randomization makes it more difficult to counterfeit tag IDs.

0054After padding, the padded ID fragments are input to the ID scrambler 206.

0055On the other hand, time information output from the timer 205 is input to the random value generator 207, the same as the first example. The random value generators 207 Perform conversion depending on the third tag unique value 208 and the fourth tag unique value 209, respectively, to convert the time information, to random values dependent on time and outputs them to the corresponding ID scramblers 206.

0056Each of the ID fragment scramblers 206 uses a random value dependent on the receiving time, scramblers the padded tag ID fragment and outputs it to the output switch 210.

0057The output switch 210 switches the data received from the ID fragments scramblers 206, and alternately outputs them to the output terminal 211.

0058The time information is randomized with each tag ID unique value and each of the tag ID fragments is scrambled with the randomized time information.

0059However, as shown in <figref idref="f0007">Fig. 7</figref>, each of the tag ID fragments can be randomized or scrambled with a corresponding tag ID unique value (a fifth tag unique value, a sixty tag unique value) in a tag ID fragment randomizer, before being input to an ID fragment scrambler. Then each of the randomized tag ID fragments can be scramble with time information randomized with one tag unique value (a seventh unique values) that is independent from the orders of the ID fragments. <figref idref="f0007">Fig. 7</figref> illustrates an alternative corresponding to a portion enclosed with a dotted line in <figref idref="f0004">Fig. 4</figref>.

0060In a further alternative, the tag ID fragments scrambled with time independent information or time dependent information can be accompanied by scrambles time information as shown in <figref idref="f0002">Fig. 2</figref> and <figref idref="f0003">Fig. 3</figref>.

0061It is necessary to recover the time information of the tag in a tag reader, and therefore the scrambled time information is desirably transmitted together with the data similar to the <figref idref="f0002">Fig. 2</figref>. example.

0062With reference to <figref idref="f0005">Fig. 5</figref>, a tag reader 221 receiving the tag ID from the tag 201 is explained.

0063The tag reader 221 has a third tag unique value 226 and a fourth tag unique value 227 the same as the third tag unique value 208 and the fourth tag unique value 209 given to the tag 201, respectively. A method of registering the tag unique values into the tag reader 221 is the same as in the first embodiment.

0064Plural data items sent from the tag 201 are needed in order to recover the tag ID. The tag 201 data received via an input terminal 220 are first stored in a buffer 222. A fragmentation determiner 242 provided in the buffer 222 determines whether the received tag ID has been fragmented, divides it if fragmented, and outputs the divided fragments into corresponding ID fragment descramblers 224.

0065When registering the tag ID into the tag reader 221, the timer 205 in the tag 201 and the timer 223 in the tag reader 221 can be reset. The timer 223 can output synchronized time information to each random value generator 225. Each random value generator 225 performs conversion dependent on the third or fourth tag unique value, respectively, converts the time information to a random value dependent on time, and outputs it to the corresponding ID fragment descrambler 224.

0066Each ID fragment descrambler 224 performs an operation inverse to that of the ID fragments scrambler 206 of the tag 201, to extract a descrambled ID fragment and outputs it to a corresponding de-padder 228.

0067the de-padder 228 performs an operations inverse to that of the padder 204 in the tag 201, to de-pad (remove) the padded (filling) bits. In a case where scrambling or randomizing dependent on the order of the tag ID fragments has been performed on the tag 201 as shown in <figref idref="f0007">Fig. 7</figref>, the de-padder 228 can Optionally perform descrambling or de-randomizing to extract the divided tag ID fragments.

0068The extracted tag ID fragments are input to an ID combiner 229. The ID combiner 229 performs an operation inverse to that of the ID divider 203 of the tag 201 to recover the tag ID.

0069The recovered tag ID is input to an authenticator 231, which determines whether the combination of recovered tag ID and its unique values:is correct. If it is determined that the combination is incorrect, the division ratio in the buffer 222 is reversed and the same operations are performed again. If it is determined that the combination is still incorrect in the second trial, the resultant tag ID is discarded.

0070With reference to <figref idref="f0008">Fig. 8</figref>, a first embodiment of the present invention is explained. Instead of a tag reader, a server has an authenticator.

0071A server 2 shown in <figref idref="f0008">Fig. 8</figref> has a tag manager 802. The tag manager 802 comprises a storage 804. The storage 804 correlates each tag ID, information indicated by the tag ID, and location information of a base station closest to the tag, and is storing the information together as a group. The tag manager 802 receives data including tag ID informations and other information sent from the tag via a mobile station and a base station. If the received data include an extracted tag ID, it is not necessary to have an extractor. If not, an extractor 806 of the tag manager 802 extracts tag ID information, tag location information, and other information. The above mentioned technique can be utilized for extraction. An authenticator 808 compares the received tag ID information and location information with the stored information, and determines whether the received tag ID is authentic.

0072When a tag reader 6 moves close to a first tag 7 and receives information transmitted by the first tag 7, a mobile station 5 having the tag reader 6 is located in an area belonging to a first base station 3. The mobile station 5 sends an inquiry to the server 2 via the first base station 3 as to whether the first tag 7 is authentic.

0073The server 2 understands that the inquiry has been transmitted via the first base station 3, and therefore replies to the mobile station 5 that the first tag is authentic.

0074On the other hand, the tag reader 6 moves close to a second tag reader 8 and receives information transmitted by the second tag 8, the mobile station having the tag reader 6 being located in an area belonging to a second base station 4. The mobile station 5 sends an inquiry to the server 2 via the second base station 4 as to whether the second tag 8 is authentic.

0075The server 2 understands that the inquiry about the second tag 8 has been transmitted via the second bases station 4, and therefore replies to the mobile station 5 that the second tag 8 is counterfeit.

0076In this manner, the server holds information of the base stations close to tags, and therefore can determine whether tags are authentic or counterfeit. When the mobile station sends such an inquiry, it can also send information on the location of the mobile station at the time of receiving the information from the tag, and therefore the authenticity of the tag can be determined even when the mobile station sends the inquiry later instead of sending it immediately after receiving the tag information.

0077The tag manager 802 can be provided not only in the server but also in a base station, a mobile station, or a tag reader. In a case where the tag manager is provided in a mobile station, the information stored in the server can be downloaded to the tag manager in the mobile station and the mobile station can determine the authenticity. Instead of a server, a base station can have a storage for correlating and storing information about each tag, its tag ID, its information, and its location information. A tag reader can determine the authenticity, as in the first and second examples. Each base station can previously send to a server, information of tag IDs of tags located close to the base station.

[Industrial Applicability]

0078ID tags, tag readers, ID tag security systems, and ID tag transmission and recovering methods can be utilized for improving the tag services in mobile communication systems.