CN100568253C - Tag privacy protection method, update device, update request device, tag device - Google Patents

Abstract

A tag privacy protection method, which prevents the user's private information from being obtained based on the information output by the tag device. The hidden ID information sid _h that hides the ID information id _h of each tag is stored in the secret value memory of each tag device. The tag device is in The above-mentioned hidden ID information sid _h stored in the above-mentioned secret value memory is read out in the read/write unit, and the above-mentioned hidden ID information sid _h is output to an update device provided outside each of the above-mentioned tag devices in the first output unit, and the above-mentioned update The device accepts input of the above-mentioned hidden ID information sid _h in the first input unit, generates new hidden ID information sid h' whose correlation with the above-mentioned hidden ID information sid _h is difficult to grasp in the update unit, and generates new hidden ID information sid _h ' in the second output unit. The above-mentioned new hidden ID information sid _h ' is output to the above-mentioned tag device, and the above-mentioned tag device accepts the input of the above-mentioned new hidden ID information sid _h ' in the second input part, and the above-mentioned new hidden ID information is transferred to the above-mentioned read-write part. sid _h ' is stored in the above-mentioned secret value memory.

Description

Tag privacy protection method, update device, update request device, tag device

This application is a divisional application of the following patent application: the application date is September 27, 2004, the application number is 200480001507.3, and the title of the invention is "label privacy protection method, label device, back-end device, update device, update entrusting device, and other Programs and recording media and editing systems storing their programs.

technical field

The present invention relates to tagging technology to which information security technology is applied, and in particular to a tagging privacy protection method, a tagging device, a backend device, an update device, an update entrusting device, a program, and a record for preventing the user's private information from being obtained from information output by a tag device. media.

Background technique

In recent years, the introduction of automatic tag identification systems such as RFID (Radio Frequency Identification: radio frequency identification) has been promoted. This system includes a small information recording medium called a "tag device", a reader called a "reader device", and a database server called a "back-end device". , for logistics management, etc. Hereinafter, this technique will be briefly described.

[Handling of Label Devices]

In a basic automatic tag identification system, the tag ID information unique to each tag device is stored in the tag device (for example, the ID determined by MIT's Auto-ID Center includes: manufacturer code, product code indicating the type of product, product individual number of individual numbers). Furthermore, the tag device is attached to the article, and the tag ID information unique to each tag device is transmitted to a reading device installed in a store or the like by wireless communication.

[Handling of reading device]

The reading device reads the tag ID information from the tag device through wireless communication, transmits the tag ID information to the back-end device, and requests acquisition of distribution information and the like.

[Handling of back-end devices]

The back-end device manages a database of IDs and distribution information of each tag device. Then, the back-end device uses the tag ID information sent from the reading device as a key to search the distribution information and the like in the database, and sends the search result to the reading device.

[Problems of basic automatic tag recognition system]

However, in the basic automatic tag identification system, since anyone who has a reading device can read the tag ID information, there is a danger that the information of the item in possession will leak from the tapped tag ID information. .

In contrast, Non-Patent Document 2 describes a method in which a tag device outputs a hash value to a reading device.

In the case of this method, first, the tag device transmits a hash value H(id|r) obtained by combining bits of ID information id and a random number r, and the random number r to the reading device. The reading device sends them to the backend device. The back-end device combines the received random number r with each id' bit stored in the database to obtain its hash value H(id'|r). Then, the back-end device checks whether the calculated hash value H(id'|r) is consistent with the received H(id|r), and sends the logistics information corresponding to the consistent id' to the reading device. Thereby, leakage of tag ID information to a third party can be prevented. In addition, H(*) represents the process of using the hash function H for *.

Furthermore, in the methods shown in Unpublished Patent Application Nos. 2003-111342 and 2003-113798, a secret ID in which tag information is encrypted is used to prevent tag ID information from being leaked to a third party. That is, in these methods, the privileged ID is stored in advance in the tag device, and the client device that reads the privileged ID requests decoding of the privileged ID to the security server device on the network. The security server device that received the request, after confirming that the source of the request is an official client device, responds with plain text tag ID information of the decoding result of the privileged ID. Thereby, leakage of tag ID information to a third party can be prevented.

Non-Patent Document 1: EPC global, Inc., "EPCglobal", [online], [retrieved on September 9, 2004], Internet <http://www.epcglobalinc.org/>

Non-Patent Document 2: Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels, Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems, First International Conference on Security in Pervasive Computing.

However, in the conventional method, the distribution process of the labeling device may be traced based on the information output from the labeling device.

In other words, for example, in the case of the method described in Non-Patent Document 2, the hash value H(id|r) sent from the tag device to the reader is a simple random number for a third party who does not know the id . Furthermore, since the random number r is generated every time the tag device communicates with the reader, the hash value H(id|r) is different for every communication. Therefore, in general, an attacker cannot know the correlation between the hash value H(id|r) intercepted from the tag device and the hash value H(id'| _ri ) of the past communication history. However, in the case that the attacker obtains the ID information id through the intervention of the tag device, the attacker can calculate the hash value H(id'| _ri ) according to the random number r _i of the communication history (if the hash function is known h). Then, by checking whether the calculated value is consistent with the hash value (corresponding to the random number r _i ) of the communication history, the attacker can know whether the communication history corresponds to the obtained ID, by collecting the communication history corresponding to the ID The circulation process of labeling devices can be tracked.

Moreover, for example, in the method shown in Patent Application No. 2003-111342, etc., since the same hidden ID is usually returned from the wireless tag device, even if the attacker cannot decipher the ID in plain text, by tracking the hidden ID, it is possible to track the hidden ID. Circulation process of labeling devices.

Contents of the invention

The present invention has been made in view of the above-mentioned problems, and an object of the present invention is to provide a technology capable of preventing a third party from tracking the distribution process of label devices.

In order to solve the above-mentioned problems, encrypted information of ID information is previously stored in a tag device, and it is updated at a predetermined timing. Therefore, it is difficult for an attacker to obtain the correlation between the information output by the tag device in the past and the updated encrypted information, and it is difficult to trace the distribution process of the tag device.

For example, in the first present invention, the secret value memory corresponding to each tag ID information is stored in advance in the secret value memory of each tag device. Then, the tag device outputs tag output information corresponding to the secret value of the secret value storage in the output unit in response to the call from the reading device. Then, in the first calculation unit, at least a part of the elements of the secret value are read from the secret value memory, and the first function F1, which is difficult to obtain an inverse image, is used thereon, and the secret value in the secret value memory is overwritten with the result of the calculation. renew. Here, since the secret value in the secret value storage is overwritten and updated, even if an attacker obtains the secret value stored in the secret value storage through intervention, the updated secret value does not correspond to the information sent from the tag device before the update. Furthermore, since this update is performed using the first function F1 whose inverse image is difficult to obtain, it is difficult to obtain the secret value before updating from the secret value at a certain time. Therefore, an attacker cannot know the correspondence between the tag device and the communication history.

Furthermore, for example, in the second invention, the update device installed outside the tag device updates the privileged ID information stored in the tag device at a predetermined timing to a new secret ID information whose correlation is difficult to grasp. ID information. In this way, since the privileged ID information is updated, an attacker cannot know the correspondence between the privileged ID information output from the tag device to the back-end device before the update and the new privileged ID information after the update. Therefore, an attacker cannot know the correspondence between the tag device and the communication history.

The present invention also provides a label privacy protection method, which prevents the user's private information from being obtained according to the information output by the label device. The secret value memory of each label device stores hidden ID information sid _h that hides the ID information id _h of each label. The above-mentioned Each tag device reads the privileged ID information sid _h stored in the secret value memory in the read/write unit, and outputs the privileged ID information sid h in the first output unit to an updating device provided outside each tag device. _h , the updating device accepts the input of the hidden ID information sid _h in the first input unit, and generates new hidden ID information sid _h ' whose correlation with the hidden ID information sid _h is difficult to grasp in the updating unit, and in the In the second output unit, the above-mentioned new concealed ID information sid _h ' is output to each of the above-mentioned tag devices, and each of the above-mentioned tag devices accepts the input of the above-mentioned new concealed ID information sid _h ' in the second input part, and the above-mentioned read-write part will The above-mentioned new covert ID information sid _h ' is stored in the above-mentioned secret value memory.

The present invention also provides a label privacy protection method to prevent the user's private information from being obtained according to the information output by the label device. The hidden ID information sid _h corresponding to each label ID information id _h is stored in the secret value memory of each label device h, wherein , h∈{1,...,m}, m is the total number of tag devices, the hidden ID information sid _h is a random value r _h , which is set in the hidden ID memory of the external update device of each tag device h to correspond to storing the above-mentioned tag ID information id _h , and the concealed ID information sid _h corresponding to the tag ID information id _h , the concealed ID information sid _h is a random value r _h , and the above-mentioned tag devices h are read in the first read-write unit The above-mentioned privileged ID information sid _h stored in the above-mentioned secret value memory is output, and the above-mentioned privileged ID information sid _h is output to the above-mentioned updating device through the first output unit. The above-mentioned updating device receives the above-mentioned privileged ID information sid _h through the first input unit. input, in the random value generation unit, generate a new random value r _h ', in the second reading and writing unit, select the tag ID information id corresponding to the input hidden ID information sid _h from the hidden ID memory _h , store the above-mentioned new random value r _h ' as new concealed ID information sid _h ' in the concealed ID memory correspondingly, and output the above-mentioned new concealed ID information to each tag device h in the second output unit sid _h ', the above-mentioned each tag device h accepts the input of the above-mentioned new concealed ID information sid _h ' in the second input part, and stores the above-mentioned new concealed ID information sid _h ' in the above-mentioned secret in the above-mentioned first read-write part in value memory.

The present invention also provides a tag privacy protection method, which prevents the user's private information from being obtained according to the information output by the tag device. The hidden ID information sid h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device _h . The hidden ID information sid _h has the first encrypted text of the common key encryption method and the key ID information kid _j of the common key k _j used for the encryption, where h∈{1,...,m}, m is the total number of tag devices, j∈{1,...,n}, n is the total number of keys, and each key ID information kid is correspondingly stored in the key memory of the updating device installed outside each tag device h _j and each common key k _j , each tag device h reads out the hidden ID information sid h stored in the secret value memory in the first read-write unit, and outputs the above-mentioned ID information sid _h to the update device in the first output unit For the concealed ID information sid _h , the updating device accepts the input of the concealed ID information sid _h in the first input unit, and in the second read/write unit, extracts the secret key included in the concealed ID information sid _h from the key memory. The above-mentioned common key k _j corresponding to the key ID information kid _j , in the ID extracting part, use the above-mentioned common key k _j extracted by the above-mentioned second reading and writing part to decode the above-mentioned first encrypted text, and extract the tag ID information id _h , in the encryption unit, using the tag ID information id _h extracted by the ID extraction unit and the common key k _j used for the extraction, the second encrypted text whose relationship with the first encrypted text is difficult to grasp is generated , in the second output part, output the new concealed ID information sid h _' with the above-mentioned second encrypted text and the above-mentioned key ID information kid _j of the common key k _j to each of the above-mentioned tag devices h, and each of the above-mentioned tag devices h The second input unit accepts input of the new privileged ID information sid _h ', and the first read/write unit stores the new privileged ID information sid _h ' in the secret value memory.

The present invention also provides a tag privacy protection method, which prevents the user's private information from being obtained according to the information output by the tag device. The hidden ID information sid h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device _h . The hidden ID information sid _h has the first encrypted text of the public key encryption method and the key ID information kid _j of the key pair (sk _j , pk _j ), where h∈{1,...,m}, m is the total number of tag devices, sk _j is the key, pk _j is the public key, j∈{1,...,n}, n is the total number of keys, and the updates set outside each of the above tag devices h Each key ID information kid _j and each key pair (sk _j , pk _j ) are correspondingly stored in the key memory of the device, and each tag device h reads out the key stored in the secret value memory in the first read-write part The above-mentioned privileged ID information sid _h outputs the above-mentioned privileged ID information sid _h to the above-mentioned updating device in the first output unit, and the above-mentioned updating device receives the input of the above-mentioned privileged ID information sid _h in the first input unit, , the key pair (sk _j , pk _j ) corresponding to the key ID information kid _j included in the hidden ID information sid _h input to the first input unit is extracted from the key memory, and the ID extraction In the part, the above-mentioned first encrypted text is decoded using the above-mentioned key sk _j extracted by the above-mentioned second reading and writing part, and the above-mentioned tag ID information id _h is extracted, and in the encryption part, the above-mentioned tag ID information extracted by the above-mentioned ID extracting part is used id _h and the above-mentioned public key pk _j extracted by the above-mentioned second reading and writing unit generate a second encrypted text whose correlation with the above-mentioned first encrypted text is difficult to grasp, and output the second encrypted text to each of the above-mentioned tag devices h in the second output unit. The above-mentioned second encrypted text and the new hidden ID information sid _h ' of the above-mentioned key ID information kid _j of the above-mentioned key pair (sk _j , pk _j ), each of the above-mentioned tag devices h accepts the above-mentioned new When the privileged ID information sid _h ' is input, the new privileged ID information sid _h ' is stored in the secret value memory in the first read/write unit.

The present invention also provides a tag privacy protection method, which prevents the user's private information from being obtained according to the information output by the tag device. The hidden ID information sid h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device _h . The hidden ID information sid _h has the first encrypted text of the re-encryptable public key encryption method and the key ID information kid _j of the public key pk _j , where h∈{1,...,m}, m is the total number of tag devices, j∈{1,...,n}, n is the total number of keys, and each key ID information kid is correspondingly stored in the key memory of the updating device installed outside each tag device h _j and each public key pk _j , each tag device h reads the hidden ID information sid h stored in the secret value memory in the first read/write unit, and outputs the above-mentioned ID information sid _h to the update device in the first output unit. Concealed ID information sid _h , wherein the updating means accepts input of the privileged ID information sid _h in the first input unit, and in the second read/write unit, extracts the key memory inputted to the first input unit. The above-mentioned public key pk _j corresponding to the above-mentioned key ID information _{kid j} included in the hidden ID information sid _h is converted to The above-mentioned first encrypted text possessed by sid _h is re-encrypted to generate a second encrypted text whose correlation with the above-mentioned first encrypted text is difficult to grasp, and the second output part outputs the above-mentioned second encrypted text and The new concealed ID information sid _h ' of the above-mentioned key ID information kid _j of the above-mentioned public key pk _j , the above-mentioned each tag device h accepts the input of the above-mentioned new concealed ID information sid _h ' in the second input part, and in the above-mentioned The first read-write unit stores the above-mentioned new concealed ID information sid _h ' in the above-mentioned secret value memory.

The present invention also provides a tag privacy protection method, which prevents the user's private information from being obtained according to the information output by the tag device. The secret value memory of each tag device h stores hidden ID information sid _h that hides the ID information id _h of each tag, Wherein, h∈{1,...,m}, m is the total number of tag devices, and each tag device h reads out the above-mentioned concealed ID information sid _h stored in the above-mentioned secret value memory in the first read-write part, In the first output part, the above-mentioned privileged ID information sid _h is output to a first update device provided outside the above-mentioned tag devices h, and the above-mentioned first update device receives an input of the above-mentioned privileged ID information sid _h in the first input part, In the ID extraction part, the tag ID information id _h is obtained based on the hidden ID information sid _h , and in the second output part, the tag ID information id h is output to the second update device installed outside the tag devices _h , The above-mentioned second updating device accepts the input of the above-mentioned tag ID information id _h in the third input part, and in the encryption part, generates new concealed ID information sid _h ' with the above-mentioned tag ID information id _h concealed, and in the third In the output unit, the above-mentioned new hidden ID information sid _h ' is output to each of the above-mentioned tag devices h, and each of the above-mentioned tag devices h receives the input of the above-mentioned new hidden ID information sid _h ' in the second input part, In the writing unit, the above-mentioned new hidden ID information sid _h ' is stored in the above-mentioned secret value memory.

The present invention also provides an updating device, which updates the hidden ID information of the tag device, which is arranged outside the above-mentioned tag device, and has: a hidden ID memory, correspondingly storing each tag ID information id _h and the hidden ID information corresponding to the tag ID information id _h ID information sid _h , the hidden ID information sid _h is a random value r _h ; the first input unit accepts the input of the hidden ID information sid _h output from the tag device; the random value generation unit generates a new random value r _h '; The second read-write unit is connected to the above-mentioned hidden ID memory, selects the tag ID information _id h corresponding to the above-mentioned hidden ID information sid _h input to the above-mentioned first input unit from the hidden ID memory, and uses the above-mentioned new random The value r _h ' is correspondingly stored in the hidden ID memory as new hidden ID information sid _h '; and the second output unit outputs the new hidden ID information sid _h ' to the tag device. The present invention also provides an update device for updating the concealed ID information of the tag device, which is arranged outside the above-mentioned tag device, and has: a key memory, correspondingly storing each key ID information kid _j (j∈{1,..., n}, n is the total number of tag devices) and each common key k _j of the common key encryption method; the first input unit accepts the first encrypted text with the common key encryption method corresponding to the tag ID information id _h , and the input of hidden ID information sid _h of key ID information kid _j of common key k _j used for this encryption; the second reading and writing unit is connected to the above-mentioned key memory, and extracts the above-mentioned hidden ID from the key memory the above-mentioned common key k _j corresponding to the above-mentioned key ID information kid _j possessed by the information sid _h ; the ID extracting unit uses the above-mentioned common key k _j extracted by the above-mentioned second reading and writing unit to decode the above-mentioned first encrypted text, and extracting tag ID information id _h ; the encryption unit uses the tag ID information id _h extracted by the ID extracting unit and the common key k _j used for the extraction to generate a code that is difficult to grasp the relevance to the first encrypted text a second encrypted text; and a second output unit that outputs new privileged ID information sid _h ' having the second encrypted text and the key ID information kid _j of the common key k _j to the tag device h.

The present invention also provides an update device for updating the concealed ID information of the tag device h, which is characterized in that it is arranged outside the tag device h, and has: a key memory, correspondingly storing each key ID information kid _j and a common key Each common key k _j of the encryption method, wherein, j∈{1,...,n}, n is the total number of keys; the first input part accepts the input of hidden ID information sid _h , and the hidden ID information sid _h has the first encrypted text and the key ID information kid _j of the common key k _j used for this encryption, and the first encrypted text corresponds to the common key encryption method of the tag ID information id _h ; the second read-write part , connected to the above-mentioned key memory, extract the above-mentioned common key k _j corresponding to the above-mentioned key ID information kid _j possessed by the above-mentioned concealed ID information sid _h from the key memory; the ID extracting part uses the above-mentioned second read-write The above-mentioned common key k _j extracted by the above-mentioned part decodes the above-mentioned first encrypted text, and extracts the tag ID information id _h ; the encryption part uses the above-mentioned tag ID information id _h extracted by the above-mentioned ID extraction part, and the above-mentioned common The key k _j generates a second encrypted text whose correlation with the first encrypted text is difficult to grasp; and a second output unit outputs the above-mentioned encrypted text having the second encrypted text and the common key k _j to the label device h. New concealed ID information sid _h ' of the key ID information kid _j .

The present invention also provides an update device for updating the concealed ID information of the tag device h, which is characterized in that it is arranged outside the tag device h, and has: a key memory, correspondingly storing each key ID information kid _j and a key pair (sk _j , pk _j ), wherein, j∈{1,...,n}, n is the total number of keys, sk _j is the key, and pk _j is the public key; the first input part accepts the hidden ID input of information sid _h , the hidden ID information sid _h has the first encrypted text corresponding to the key ID information kid _j of the public key pk _j used for the encryption, the first encrypted text corresponds to the tag ID information id _h public key encryption method; the second read/write unit is connected to the key memory, and extracts the key ID information kid _j included in the hidden ID information sid _h input to the first input unit from the key memory The corresponding above-mentioned key pair (sk _j , pk _j ); the ID extraction part uses the above-mentioned key sk _j extracted by the above-mentioned second reading and writing part to decode the above-mentioned first encrypted text, and extract the above-mentioned tag ID information id _h ; The encryption unit uses the tag ID information id _h extracted by the ID extraction unit and the public key pk _j extracted by the second reading/writing unit to generate a second encrypted text whose relationship with the first encrypted text is difficult to grasp. and a second output unit that outputs new hidden ID information sid h ' with the second encrypted text and the key ID information kid _j corresponding to the key pair (sk _j , pk _j ) to the tag device _h .

The present invention also provides an update device for updating the concealed ID information of the tag device h, which is characterized in that it is arranged outside the tag device h, and has: a key memory, correspondingly storing each key ID information kid _j and each public key key pk _j , wherein, j∈{1,...,n}, n is the total number of keys; the first input part accepts the input of concealed ID information sid _h , and the concealed ID information sid _h has the first encrypted text and the key ID information kid _j of the public key pk _j , the first encrypted text corresponds to the re-encryptable public key encryption method of the tag ID information id _h ; the second read-write part is connected to the above-mentioned key memory for extracting the public key pk _j corresponding to the key ID information kid _j included in the hidden ID information sid _h input to the first input unit from the key memory; the encryption unit uses the second The above-mentioned public key pk _j extracted by the reading and writing unit re-encrypts the above-mentioned first encrypted text included in the above-mentioned hidden ID information sid _h to generate a second encrypted text whose relationship with the first encrypted text is difficult to grasp; and the second The output unit outputs new privileged ID information sid h _' having the second encrypted text and the key ID information kid _j of the public key pk _j to the tag device h.

The present invention also provides an update entrusting device, which entrusts the updating device with updating of the hidden ID information of the tag device, which is provided outside the tag device, and has: a hidden ID input unit for inputting a plurality of types corresponding to the same tag ID information id _h A secret ID of encrypted text that can be re-encrypted; a secret ID memory that stores a plurality of input types of the above-mentioned secret ID; a secret ID extracting unit that is connected to the above-mentioned secret ID memory, and extracts a secret ID from the secret ID memory at a predetermined timing. ID; and a privileged ID output unit that outputs the extracted privileged ID to the tag device.

The present invention also provides a tag device, which is used in an automatic tag identification system, comprising: a hidden ID input unit for inputting a plurality of hidden IDs corresponding to re-encryptable encrypted text of the same tag ID information id _h ; a hidden ID memory, A plurality of types of the above-mentioned privileged IDs input are stored; a privileged ID extracting unit is connected to the above-mentioned privileged ID memory, and extracts one privileged ID from the privileged ID memory at a predetermined timing; and a privileged ID output portion outputs the extracted privileged ID. .

The present invention also provides a label privacy protection method, which prevents the user's private information from being obtained based on the information output from the label device, and stores the key ID and the key in the key storage; the above-mentioned label device has a hidden ID storage, and the hidden ID The ID memory has a read-only area for storing the key ID and a rewritable area for storing the first concealed ID, and the above-mentioned tag device extracts the above-mentioned key ID and the above-mentioned first concealed ID from the above-mentioned concealed ID memory in the read-write part, and The first output unit outputs the extracted key ID and the first secret ID to the update device, and the update device accepts the key ID and the first secret ID at the first input unit, In the extraction unit, a key corresponding to the key ID input to the first input unit is extracted from the key memory, and in the concealed ID update unit, the key extracted by the first key extraction unit is used, and the first hidden ID input to the first input unit to generate a second hidden ID whose relationship with the first hidden ID is difficult to grasp, and the second output unit outputs the second hidden ID, and the label The device accepts input of the second privileged ID in the second input unit, and stores the second privileged ID in the rewritable area of the privileged ID memory in the read/write portion.

The present invention also provides a label device, which is used in an automatic label identification system, which has: a hidden ID memory, a read-only area for storing the key ID and a rewritable area for storing the first hidden ID; The key ID and the first secret ID are extracted from a memory; the first output unit outputs the extracted key ID and the first secret ID; and the second input unit accepts that it is difficult to grasp the relationship with the first secret ID. input of a second confidential ID, and the read/write unit stores the input second confidential ID in the rewritable area of the confidential ID memory.

As described above, in the present invention, since the third party cannot know the correspondence between the tag device and the communication history, it is possible to prevent the third party from tracking the distribution process of the tag device.

Description of drawings

1A is a block diagram illustrating an overall automatic label recognition system according to the first embodiment, FIG. 1B is a block diagram illustrating a schematic configuration of a label device, and FIG. 1C is a block diagram illustrating a schematic configuration of a backend device.

FIG. 2 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 1. FIG.

FIG. 3 is a flowchart for explaining the processing of the first embodiment.

FIG. 4 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 2. FIG.

FIG. 5 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 3. FIG.

FIG. 6 is a flowchart for explaining the processing of the backend device according to the third embodiment.

FIG. 7 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 4. FIG.

FIG. 8 is a flowchart for explaining the processing of the backend device according to the fourth embodiment.

FIG. 9 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 5. FIG.

FIG. 10A is a flowchart for explaining the processing of the label device of the fifth embodiment, and FIG. 10B is a flowchart for explaining the processing of the back-end device of the present embodiment.

FIG. 11 is a diagram illustrating an overall configuration of an automatic mark recognition system according to Embodiment 6. FIG.

FIG. 12 is a flowchart for explaining the processing of the sixth embodiment.

FIG. 13 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 7. FIG.

FIG. 14 is a flowchart for explaining the processing of the seventh embodiment.

FIG. 15 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 8. FIG.

FIG. 16A is an illustration of data stored in a secret value memory of a tag device, and FIG. 16B is an illustration of data stored in a database memory of a backend device.

FIG. 17 is a flowchart for explaining the processing of the eighth embodiment.

FIG. 18 is a flowchart for explaining the processing of the eighth embodiment.

FIG. 19 is a diagram illustrating an overall configuration of an automatic tag identification system according to Embodiment 9. FIG.

FIG. 20A is an illustration of data stored in a secret value memory of a tag device, and FIG. 20B is an illustration of data stored in a database memory of a backend device.

FIG. 21 is a diagram illustrating an overall configuration of an automatic tag identification system of Embodiment 10. FIG.

Fig. 22 is a flowchart for explaining the processing of the label device of the tenth embodiment.

FIG. 23 is a flowchart for explaining the processing of the backend device in the tenth embodiment.

FIG. 24 is a diagram illustrating the overall structure of the automatic label identification system of Embodiment 11

Fig. 25 is a flowchart for explaining the processing of the labeling device according to the eleventh embodiment.

FIG. 26 is a flowchart for explaining part of the processing of the backend device in the eleventh embodiment.

Fig. 27 is a flowchart for explaining the processing of the label device according to the twelfth embodiment.

FIG. 28 is a block diagram illustrating a schematic configuration of the second embodiment.

FIG. 29 is a conceptual diagram illustrating an overall configuration of an update system of Embodiment 14. FIG.

FIG. 30 is a block diagram illustrating a functional configuration of an update system of Embodiment 14. FIG.

Fig. 31 is a flowchart for explaining the processing procedure of the fourteenth embodiment.

FIG. 32 is a block diagram illustrating the functional configuration of the updating system of the fifteenth embodiment.

Fig. 33 is a flowchart for explaining the processing procedure of the fifteenth embodiment.

FIG. 34 is a block diagram illustrating a functional structure of an update system of Embodiment 16. FIG.

Fig. 35 is a flowchart for explaining the processing procedure of the sixteenth embodiment.

FIG. 36 is a block diagram illustrating a functional configuration of an update system of Embodiment 17. FIG.

Fig. 37 is a flowchart for explaining the processing procedure of the seventeenth embodiment.

FIG. 38 is a conceptual diagram illustrating an overall configuration of an update system of Embodiment 18. FIG.

FIG. 39 is a block diagram illustrating a functional structure of an update system of Embodiment 18. FIG.

Fig. 40 is a flowchart for explaining the processing procedure of the eighteenth embodiment.

FIG. 41 is a block diagram illustrating a functional configuration of an update system of Embodiment 19.

Fig. 42 is a flowchart for explaining the processing procedure of the nineteenth embodiment.

FIG. 43 is a block diagram illustrating a functional configuration of an update system of Embodiment 20. FIG.

FIG. 44 is a flowchart for explaining the processing procedure of the twentieth embodiment.

FIG. 45 is a block diagram illustrating a functional configuration of an update system of Embodiment 21.

FIG. 46 is a block diagram illustrating a functional configuration of an update system of Embodiment 22. FIG.

FIG. 47 is a conceptual diagram illustrating an overall configuration of an update system of Embodiment 23.

FIG. 48 is a block diagram illustrating a functional configuration of an update system of Embodiment 23.

Fig. 49 is a flowchart for explaining the processing procedure of the twenty-third embodiment.

FIG. 50 is a flowchart for explaining the processing procedure of the twenty-third embodiment.

FIG. 51 is a diagram illustrating a functional configuration of a security server device according to the twenty-fourth embodiment.

Fig. 52 is a diagram illustrating the format of Embodiment 24.

Fig. 53 is a flowchart for explaining the processing procedure of the security server device in the twenty-fourth embodiment.

FIG. 54 is a block diagram illustrating a functional configuration of an update system of Embodiment 25. FIG.

FIG. 55 is a block diagram illustrating a functional structure of an update system of Embodiment 25. FIG.

Fig. 56 is a flowchart for explaining the processing procedure of the twenty-fifth embodiment.

Fig. 57 is a flowchart for explaining the processing procedure of the twenty-fifth embodiment.

FIG. 58 is a diagram illustrating a functional configuration of a tag device in Embodiment 26. FIG.

Symbol Description

1 Label automatic identification system

10 label device

11 Secret value memory

12 First Computing Department

13 Second Computing Department

14 output section

20 reading device

30 backend device

31 Database storage

32 input part

33 Computing Department

34 Comparative Department

35 Reading Department

40 network

1500 Update system

1510 Label device

1511 secret value memory

1512 Literacy Department

1513 output unit

1514 input unit

1560 Security Server Device

1561 input unit

1562 Update Department

1563

Detailed ways

Hereinafter, embodiments of the present invention will be described with reference to the drawings.

[first embodiment]

<structure>

FIG. 1A is a block diagram illustrating the whole of an automatic label identification system 1 in the first embodiment. 1B is a block diagram illustrating a schematic configuration of the tag device 10 , and FIG. 1C is a block diagram illustrating a schematic configuration of the backend device 30 .

As shown in FIG. 1A , the automatic label identification system 1 of this mode includes: a label device 10 , a reading device 20 , and a back-end device 30 connected to the reading device 20 through a network 40 .

Moreover, as shown in FIG. 1B , the tag device 10 of this mode includes: a secret value memory 11, which stores secret values corresponding to each tag ID information; a first computing unit 12, which uses a first function F1 which is difficult to obtain an inverse image; The second calculation unit 13 uses the second function F2 that disturbs the relationship between the elements of the domain and its mapping; and the output unit 14 outputs the label output information corresponding to the secret value of the secret value memory 11 to the back-end device 30 .

And, as shown in Figure 1C, the back-end device 30 of this mode includes: a database memory 31, which establishes a correspondence between each tag ID information and its corresponding secret value; an input unit 32, which accepts the input of tag output information; a computing unit 33 , use the above-mentioned first function F1 and second function; the comparison unit 34 compares the calculation result of the calculation unit 33 with the label output information; and the reading unit 35 extracts information from the database memory 31 .

<Processing of Label Device 10>

When the tag device 10 receives a reading request from the reading device 20, first, the second calculation unit 13 of the tag device 10 reads the secret value from the secret value memory 11, and generates tag output information using the second function F2 thereon. This tag output information is sent to the output unit 14, and is output (wirelessly or wired) to the back-end device 30 in the output unit 14. After that, in the first computing unit 12, at least some elements of the secret value are read from the secret value memory 11, and the first function F1 is applied thereto, and the secret value in the secret value memory 11 is overwritten and updated as a result of the computation. Here, the secret value in the secret value memory 11 is overwritten and updated after the tag output information is generated, but the tag output information may be generated after the secret value in the secret value memory 11 is overwritten.

<Processing by Reader 20>

The reading device 20 receives input of tag output information output from the tag device 10 to the back-end device 30 , and transmits it to the back-end device 30 through the network 40 .

<Processing by Backend Device 30 >

The input unit 32 of the backend device 30 receives input of the tag output information transmitted from the reading device 20 . Using this as a trigger, the computing unit 33 further uses the second function used by the tag device 10 after using the first function F1 used by the tag device 10 a predetermined number of times for at least some elements of the secret value in the database memory 31 . Then, in the comparison unit 34, the calculation result in the calculation unit 33 is sequentially compared with the label output information, and if they match, the reading unit 35 extracts from the database memory 31 the result corresponding to the matching calculation result and the label output information. The secret value establishes the corresponding tag ID information.

[Example 1]

FIG. 2 is a diagram illustrating the overall configuration of the automatic label recognition system 100 of the first embodiment, and FIG. 3 is a flowchart for explaining the processing of the first embodiment.

Hereinafter, the functional configuration and processing method of Embodiment 1 will be described using these figures.

<structure>

As shown in FIG. 2 , the automatic label identification system 100 of Embodiment 1 has: a label device 110 , a reading device 120 , and a backend device 130 that can be connected to the reading device 120 through a network 140 . In addition, in FIG. 2 , only one label device 110 is illustrated for the sake of simplification of description, but actually there are more than this number of label devices 110 . In addition, in FIG. 2 , one reader 120 and one back-end device 130 are shown, but this system may be constituted by more than this number of readers 120 and back-end device 130 .

<label device>

The tag device 110 of this example has: a secret value storage 111, a hash calculation unit 112 (corresponding to a “second calculation unit”), a hash calculation unit 113 (corresponding to a “first calculation unit”), an interface 114 (corresponding to a “first calculation unit”), and an interface 114 (corresponding to a “first calculation unit”). "output section"), and the control section 115 including the memory 115a.

Here, the secret value memory 111 and the memory 115a are, for example, readable and writable memories such as EEPROM (Electronically Erasable and Programmable Read Only Memory), FeRAM (Ferroelectric Random Access Memory), flash memory, and NV (Nonvolatile) RAM.

The hash calculation unit 112 and the hash calculation unit 113 are, for example, hash functions G, H: {0, 1} ^* →{0, 1} ^L that use a unidirectional function for input values, respectively, and output the The resulting integrated circuit is constructed. In addition, {0, 1} ^* represents the set of all binary sequences, and {0, 1} ^L represents the set of L-bit long binary sequences. Furthermore, as such hash functions G, H, SHA-1, MD5, etc. can be illustrated. In addition, this hash function H corresponds to "the first function F1 which is difficult to find an inverse image", and the hash function G corresponds to "the second function F2 which disturbs the relationship between the elements of the domain and their mapping". Furthermore, the control unit 115 is, for example, an integrated circuit configured to control the overall processing of the tag device 110 .

The interface 114 is, for example, hardware that outputs data to the reading device 120 via wireless or wired. Specifically, the interface 114 includes, for example: an encoding/decoding circuit for encoding/decoding by NRZ code, Manchester encoding, Miller code, or unipolar RZ encoding, etc.; a modulation/demodulation circuit for performing encoding/decoding by ASK (Amplitude Shift Keying) or PSK (Phase Shift Keying) or FSK (Frequency Shift Keying) for modulation and demodulation; and antennas such as dipole antennas, microstrip antennas, loop antennas, or cored coils, using frequencies in the long wave band or ISM band (Industry Science Medical band) Send and receive signals. In addition, the communication method utilizes, for example, an electromagnetic induction method or a radio wave method.

Furthermore, the hash calculation unit 112 and the hash calculation unit 113 are electrically connected to the confidential value memory 111, and the hash calculation unit 112 is electrically connected to the interface 114 (corresponding to an "output unit"). Moreover, although omitted in this figure, the control unit 115 is electrically connected to each unit of the label device 110 .

<reading device>

The reader 120 of this example has a physical distribution information memory 121 , an interface 122 , a communication unit 123 , a memory 124 a , and a control unit 124 .

The logistics information memory 121 is, for example, a magnetic recording device such as a hard disk device and a floppy disk, an optical disk device such as DVD-RAM (Random Access Memory), CD-R (Recordable)/RW (ReWritable), or an opto-magnetic recording device such as MO (Magneto-Optical disc). Devices, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), semiconductor memory such as flash memory, etc. The interface 122 is, for example, the same hardware as the interface 114 . The communication unit 123 is, for example, a LAN card, a modem, a terminal adapter, etc., and the control unit 124 is, for example, a CPU (Central Processing Unit) of a CISC (Complex Instruction Set Computer) system or a RISC (Reduced Instruction Set Computer) system having a memory 124a.

Furthermore, the interface 122 and the physical distribution information memory 121 are electrically connected to the communication unit 123 , and although omitted in the figure, the control unit 124 is electrically connected to each unit of the reading device 120 .

<backend device>

The backend device 130 of this example has: a database memory 131, a communication unit 132 (equivalent to an “input unit”), a hash calculation unit 133 (corresponding to a “third calculation unit”), a comparison unit 134, and a read/write unit 135 ( Corresponds to "reading unit"), memory 136 a, and control unit 136 . Specifically, the backend device 130 is configured by causing a well-known Neumann computer to execute a predetermined program, and the computer is connected to, for example, a CPU, a RAM, a ROM (Read Only Memory), a magnetic recording device, an optical disk device, etc. through a bus. External storage device, LAN card or modem or terminal adapter, etc. Also, the CPU reads a program stored in the RAM, and executes processing according to the program, thereby realizing each processing function shown below.

<preprocessing>

First, a predetermined program is installed in the backend device 130 so that the hash calculation unit 133 of the backend device 130 can use the same hash functions G, H as those of the tag device 110 .

Each tag ID information id _k (k ∈ {1, ..., m}, k corresponds to each tag device, m is the total number of tag devices) corresponding to the secret value sk _{, 1} (equivalent to "the first secret value") is stored one in each secret value memory 111 of each tag device 110. In addition, this secret value _sk,1 is generated, for example, by a random number generator (not shown) outside the tag device 110 using a pseudorandom number generation algorithm based on a calculation amount theory using a unidirectional hash function such as SHA-1. Pseudorandom number s _k,1 ∈{0,1} ^L . In addition, the random numbers _sk,1 stored in different tag devices are inconsistent with each other. Moreover, in the database memory 131 of the back-end device 130, the secret value s _n,1 corresponding to each tag device n (equivalent to the "second secret value", n∈{1,...,m},n corresponds to k) is correspondingly stored with data _n such as tag ID information id _n and logistics information.

<Handling of Label Device>

Hereinafter, the processing when the reading device 120 is made to read the tag device 110 for the ith time (i is a natural number) will be described. In addition, the processing of the tag apparatus 110 is performed under the control of the control part 115, and the data necessary for this control is read and written to the memory 115a one by one.

First, in the hash calculation unit 112, the secret value _sk,i (corresponding to the "first secret value") is read from the secret value memory 111 (step S1), and the label output information as its hash value is generated. G(s _{k, i} ) (step S2). The tag output information G( _{sk, i} ) is sent to the interface 114, and then sent from the interface 114 to the reading device 120 by wire or wirelessly (step S3).

Next, in the hash calculation unit 113, the hash value sk, _i+1 =H(s _k,i ) of the secret value sk, _i read from the secret value memory 111 is calculated (step S4), and the Hash value _{sk, i+1} is covered and saved on secret value memory 111 as new secret value _{sk, i+1} (equivalent to "new first secret value") (deletes the secret value s of secret value memory 111 _k,i , instead the secret value _sk,i+1 is stored: step S5). In addition, H(*) represents the process of using the hash function H for *.

<Handling of reading device>

The processing of the reading device 120 is performed under the control of the control unit 124, and data required for this control is read and written to the memory 124a one by one.

First, the reading device 120 receives the tag output information G(s _{k, i} ) transmitted from the tag device 110 through the interface 122 (step S6 ), and sends it to the communication unit 123 . The communication unit 123 extracts the logistics information pd (for example, the store code of the reading device 120, etc.) from the logistics information memory 121 (step S7), and passes the logistics information pd and the label output information G( _{sk, i} ) through The network 140 sends to the backend device 130 (step S8).

<Handling of back-end devices>

The processing of the back-end device 130 is performed under the control of the control unit 136, and data necessary for this control is read and written to the memory 136a one by one.

First, the back-end device 130 receives the physical distribution information pd and the label output information G(s _k,i ) transmitted from the reading device 120 in the communication unit 132 (accept input: step S9). In addition, the received distribution information pd and label output information G(s _k,i ) are stored in the memory 136a. Next, the control unit 136 substitutes 1 for n and stores it in the memory 136a (step S10). Then, the control unit 136 refers to the value of n in the memory 136a, and causes the hash calculation unit 133 to extract the secret value _sk,i from the database memory 131 (step S11). Next, the control unit 136 substitutes 0 for j and stores it in the memory 136a (step S12). Then, the control unit 136 refers to the value of j in the memory 136a, and causes the hash calculation unit 133 to calculate a hash value G(H ^j (s _{n, 1} )) (corresponding to "the calculation result in the third calculation unit") (step S13 ). Also, H ^j (s _n,1 ) indicates that the hash function H is used j times for the secret value s _n,1. Also, H ⁰ (s _n,1 ) represents sn _,1 .

Next, in the comparison unit 134, G(H ^j (s _{n, 1} )) is acquired from the hash calculation unit 133, and label output information G(s _{k, i} ) is acquired from the memory 136a, and compared (step S14).

Here, when these values do not match (step S15), the control unit 136 substitutes j+1 into j in the memory 136a (step S16), and determines whether j exceeds a predetermined maximum value j _max (step S17). Here, when j is less than or equal to the maximum value j _max , the control unit 136 executes the processing after step S13, and if j exceeds the maximum value j _max , it determines whether n in the memory 136a is m (step S18). Here, if not n=m, the control unit 136 stores n+1 in n of the memory 136a (step S19), executes the processing after step S11 again, and ends the processing if n=m. In addition, in this process, under the control of the control unit 136, if the tag output information G( _{sk, i} )- and the hash value G(H ^j (s _{n, 1} )) do not match, at least one of n and j The change in the value corresponds to performing the processing in the hash operation unit 133 and the comparison unit 134 again.

On the other hand, when the tag output information G( _{sk, i} ) matches the hash value G(H ^j (s _{n, 1} )) (step S15), the control unit 136 assigns the matched hash value G( The secret value _{sn, 1} corresponding to H ^j (s _{n, 1} )) is sent to the read-write unit 135, and the read-write unit 135 extracts the corresponding hash value G from the database memory 131 (H ^j (s _{n, 1} )) data _n such as tag ID information id _n corresponding to the secret value s _{n, 1} and logistics information, and send it to the communication unit 132 (step S20). Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, associates the physical distribution information pd with the secret value _sn,1 , and writes it into the database memory 131 (step S20).

The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S21), and are received and output by the communication unit 123 of the reader 120 (step S22).

<Features of Embodiment 1>

[Untraceability]

In Example 1 of this mode, the hash value G( _{sk, i} ) is used as tag output information in communication. Due to the unrecognizability of the hash value, the hash value G(s _{k, i} ) is regarded as a purely random number for an attacker who does not know the secret value. Therefore, the attacker cannot know whether G(s _{k, i} ) and G(s _{k, i+1} ) are output values from the same tag device 110 , and cannot trace the distribution process of the tag device 110 .

[Forward Safe]

In Embodiment 1 of this form, the secret value in the secret value memory 111 used for communication is updated by the hash function H. Moreover, due to the unidirectionality of the hash function, even if the secret value _sk,i is leaked by the tag device 110 such as being interfered with, the attacker cannot obtain the past secret value _{sk, i-Δi based on the secret value sk,i} . Therefore, even if the secret value _sk,i is leaked, the attacker cannot obtain the correspondence between the obtained secret value _sk,i and the communication history, and cannot trace the tag device 110 .

[Tracking Possibility]

On the other hand, according to the hash function G, the collision difficulty of H (the hash value of different values is difficult to take the same value), the back-end device 130 that knows the secret value _{sn, 1} can track the circulation process of the tag device 110 .

[efficiency]

Since the communication data is constituted only by the operation of the hash function, the scale of the circuit in the tag device 110 is reduced compared with the conventional method of generating random numbers, and is suitable for applications requiring low cost.

In addition, the hash value H ^j (s _{n, 1} ) calculated in the process of step S13 in the backend device 130 may be stored in the memory 136a and used in step S13 of the next cycle. That is, using the recorded H ^j (s _{n, 1} ) to calculate the hash value H ^j+1 (s _{n, 1} ) through H(H ^j (s _{n, 1} )), and then storing the value in the memory 136a Can. In this case, the number of hash calculations performed by the hash calculation unit 133 can be reduced, and the calculation efficiency of the backend device 130 can be improved.

[Example 2]

Embodiment 2 is a modified example of Embodiment 1. The tag device further maintains tag ID information id _k (equivalent to "the first intrinsic value W _k "), by s _k,i+1 =H(s _k,i |id _k ) to update the secret value s _k,i , which is different from Embodiment 1 only in this point. Hereinafter, only the points of difference from Embodiment 1 will be described.

FIG. 4 is a diagram illustrating an overall configuration of an automatic tag identification system 200 in Embodiment 2. As shown in FIG. In addition, in this figure, the part common to Example 1 is given the code|symbol common to Example 1. Hereinafter, in this figure, the functional configuration and processing method of the second embodiment will be described.

<preprocessing>

The only difference from the first embodiment is that the tag ID information id _k and the corresponding secret value _sk,i are stored in the secret value memory 211 of the tag device 210 . Moreover, in the database memory 131 of the back-end device 130, the secret value s _{n, 1} corresponding to each tag device n is correspondingly stored with data _n such as tag ID information id _n and logistics information, but the tag ID information id _n This corresponds to the "second eigenvalue W _n ".

<Handling of Label Device>

Only the processing of step S4 is different from that of the first embodiment. That is, instead of the processing of step S4 in the first embodiment, in the hash calculation unit 213 (corresponding to the “first calculation unit”), the secret value sk _,i and the tag ID information id _k are extracted from the secret value memory 211, Operation s _k,i+1 =H(s _k,i |id _k ). α|β indicates the bit combination of α and β. Then, this calculation result is overwritten in the secret value memory 211 as a new secret value _sk,i+1 .

<Handling of reading device>

Same as Example 1.

<Handling of back-end devices>

Only the processing of steps S11, S13, and S14 is different from that of the first embodiment. That is, in Embodiment 2, instead of step S11, in the hash calculation unit 233 (equivalent to the “third calculation unit”) of the backend device 230, the secret value _sn,1 is extracted from the database memory 131 and the corresponding The tag ID information id _n .

Next, similarly to the first embodiment, the control unit 136 substitutes 0 for j and stores it in the memory 136a (step S12). Thereafter, instead of step S13, the hash calculation unit 233 calculates a hash value G(I ^j (n)). Wherein, it is defined as I ^j (n)=s _n,1 (j=0), I ^j (n)=H(I ^j-1 (n)|id _n )(j≥1). That is, the hash operation unit 233 recursively obtains I ^j (n) from the secret value s _n,1 and the corresponding label, and calculates the hash value G(I ^j (n)). In addition, this recursive operation temporarily stores each I ^j '(n) (j'∈{1,...,j-1}) in the memory 136a during the operation, and uses it for the next I ^{j '+1} (n) calculation to achieve. Furthermore, I ^j (n) obtained when the hash value G(I ^j (n)) is calculated is stored in the memory 136a at least until the next hash value G(I ^j+1 (n)) is calculated. Thus, I ^j (n) obtained temporarily can be used for I ^{j+1 (} n)=H(I ^j (n)| id _n ), and can realize the efficiency of operation.

Thereafter, instead of step S14, the comparison unit 134 acquires the hash value G(I ^j (n)) from the hash calculation unit 233 and the tag output information G(s _k,i ) from the memory 136a, and compares them. Thereafter, the processing from step S15 onward is executed in the same manner as in the first embodiment.

As described above, in the second embodiment, the secret value sk, _i of the secret value memory 211 of the tag device 210 is updated by the calculation of s _k,i+1 =H(sk _,i |id _k ). Thereby, it is possible to prevent the semi-permanent coincidence of the update contents of secret values corresponding to different tag ID information id _k . That is, when the same hash function is used for different secret values and the like, there may be a case (collision) in which these calculation results coincide at a certain point of time. However, even in this case, since the tag ID information id _k corresponding to each secret value sk _,i is different, the next secret calculated by s _k,i+1 =H(s _k,i |id _k ) The values are not the same. This is an effect that cannot be obtained when the secret value is updated by s _k,i+1 =H(s _k,i ).

In addition, in Embodiment 2, the tag ID information id _k and id _n are respectively set as the first intrinsic value w _k and the second intrinsic value w _n , but other information corresponding to each tag ID information may also be Used as a fixed value.

[Example 3]

This method is a modified example of Embodiment 1. In the back-end device, the calculation value G(H ^j (s _{n, 1} )) (j=0, ..., j _max ) calculated in advance is recorded. Different from Example 1. Hereinafter, only the points of difference from Embodiment 1 will be described.

FIG. 5 is a diagram illustrating an overall configuration of an automatic tag identification system 300 in Embodiment 3. As shown in FIG. In addition, in this figure, the part common to Example 1 is given the code|symbol common to Example 1. FIG. 6 is a flowchart for explaining the processing of the backend device 330 of the third embodiment. Hereinafter, in this figure, the functional configuration and processing method of the third embodiment will be described.

<preprocessing>

In the database memory 331 of the backend device 330, the calculation result G(H ^j ₍ s _{n, 1} )) (j=0, . s _n,1 corresponds to storage, which is different from the first embodiment only in this point.

<Handling of Tag Devices and Handling of Reader Devices>

Same as Example 1.

<Handling of back-end devices>

First, the back-end device 330 receives the distribution information pd and the label output information G(s _k,i ) transmitted from the reading device 120 in the communication unit 132 (step S31 ). In addition, the received distribution information pd and label output information G(s _k,i ) are stored in the memory 136a. Next, the control unit 136 substitutes 1 for n, and stores it in the memory 136a (step S32). Next, the control unit 136 substitutes 0 for j, and stores it in the memory 136a (step S33). Then, the control unit 136 refers to the value of n,j in the memory 136a, and extracts the calculation result G(H ^j (s _n,1 )) stored in the database memory 331 (step S34).

Next, in the comparing unit 134, the calculation result G(H ^j (s _{n, 1} )) is compared with the label output information G( _{sk, i} ) extracted from the memory 136a (step S35).

Here, when these values do not match (step S36), the control unit 136 substitutes j+1 into j in the memory 136a (step S37), and determines whether j exceeds a predetermined maximum value j _max (step S38). Here, when j is less than or equal to the maximum value j _max , the control unit 136 executes the processing after step S13, and if j exceeds the maximum value j _max , it determines whether n in the memory 136a is m (step S39). Here, if not n=m, the control unit 136 stores n←n+1 (n+1 is set as a new n) (step S40), and executes the processing after step S33, and ends the processing if n=m. In addition, in this process, under the control of the control unit 136, if the tag output information G( _{sk, i} )- and the hash value G(H ^j (s _{n, 1} )) do not match, at least one of n and j The change in the value corresponds to performing the processing in the hash operation unit 133 and the comparison unit 134 again.

On the other hand, when the tag output information G( _{sk, i} ) matches the hash value G(H ^j (s _{n, 1} )) (step S36), the control unit 136 assigns the matched hash value G( The secret value _{sn, 1} corresponding to H ^j (s _{n, 1} )) is sent to the read-write unit 135, and the read-write unit 135 extracts the corresponding hash value G from the database memory 131 (H ^j (s _{n, 1} )) data _n such as ID information id _n corresponding to the secret value s _{n, 1} and physical distribution information, etc., and send it to the communication unit 132 (step S40). Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, associates the physical distribution information pd with the secret value _sn,1 , and writes it into the database memory 131 (step S40). The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S41).

As described above, in the third embodiment, the calculation result G(H ^j (s _{n, 1} )) calculated in advance is stored in the database memory 331 . Therefore, compared with the case of calculating G(H ^j (s _{n, 1} )) for each comparison process, the processing amount of the back-end device 330 can be reduced.

[Example 4]

Embodiment 4 is a modified example of Embodiment 1. The tag device sends information specifying the number of updates of the secret value, and the back-end device uses the number of updates of the secret value for processing. The only difference from Embodiment 1 is this. Hereinafter, only the points of difference from Embodiment 1 will be described.

FIG. 7 is a diagram illustrating an overall configuration of an automatic tag identification system 400 in Embodiment 4. As shown in FIG. In addition, in this figure, the part common to Example 1 is given the code|symbol common to Example 1. FIG. 8 is a flowchart for explaining the processing of the backend device 430 according to the fourth embodiment. Hereinafter, in this figure, the functional configuration and processing method of the fourth embodiment will be described.

<Structure of label device>

The tag device 410 is different from the first embodiment only in that it has a counter 416 that counts the number of updates m of secret values.

<Handling of Label Device>

In addition to the secret value _sk,i , the secret value memory 411 of the tag device 410 stores the number of updates _{rn of the secret value sk,i} counted by the counter 416, and the information specifying the number of updates rn is hashed. The difference from the first embodiment is that the unit 112 and the interface 114 (corresponding to the “output unit”) transmit to the reading device 120 .

<Handling of reading device>

The interface 122 also receives information specifying the update count rn, and the communication unit 123 also transmits the information specifying the update count rn to the backend device 430 via the network 140, which is different from the first embodiment.

<Handling of back-end devices>

First, the back-end device 430 receives information specifying rn transmitted from the reading device 120, distribution information pd, and tag output information G(s _k,i ) in the communication unit 132 (step S50). In addition, information specifying received rn, distribution information pd, and label output information G( _sk,i ) are stored in the memory 136a. Next, the control unit 136 substitutes 1 for n and stores it in the memory 136a (step S51). Then, the control unit refers to the value of n,j in the memory 136a, causes the hash operation unit 433 to extract the secret value _sn,1 from the database memory 131 (step S52), and uses the hash function H rn times for it, and further The hash function G is used, and a hash value G(H ^j (s _{n, 1} ))(j=rn) is calculated (step S53).

Next, in the comparison unit 134, the hash value G(H ^j (s _{n, 1} )) is obtained from the hash operation unit 433, and the label output information G(s _{k, i} ) is obtained from the memory 136a, and they are compared. (step S54).

Here, when these values do not match (step S55), the control part 136 judges whether n of the memory 136a is m (step S56). Here, if not n=m, then the control unit 136 stores n←n+1 (n+1 is a new n) in the memory 136a (step S57), and then executes the processing after step S52, if n= m ends the processing. In addition, this processing is equivalent to changing the value of n when the hash value G(H ^j (s _{n, 1} )) and the label output information G(s _{k, i} ) do not match, and then performing the hash calculation unit 433 And the processing in the comparison unit 134 .

On the other hand, when the tag output information G( _{sk, i} ) matches the hash value G(H ^j (s _{n, 1} )) (step S36), the control unit 136 assigns the matched hash value G( The secret value _{sn, 1} corresponding to H ^j (s _{n, 1} )) is sent to the read-write unit 135, and the read-write unit 135 extracts the corresponding hash value G from the database memory 131 (H ^j (s _{n, 1} )) data _n such as ID information id _n corresponding to the secret value s _{n, 1} and physical distribution information, etc., and send it to the communication unit 132 (step S58). Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, associates the physical distribution information pd with the secret value _sn,1 , and writes it into the database memory 131 (step S59). The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S59).

As described above, in the fourth embodiment, the tag device 410 transmits rn, and the backend device 430 uses the rn to calculate the hash value G(H ^j (s _{n, 1} )) and perform comparison processing. As a result, the comparison processing by the backend device 430 is performed only once for each sn _,1 , and the amount of processing required for this processing can be reduced.

[Example 5]

Embodiment 5 is a modification of Embodiment 1, and differs from Embodiment 1 only in that a secret value is updated and compared using a key encryption function instead of a hash function. Hereinafter, only the points of difference from Embodiment 1 will be described.

FIG. 9 is a diagram illustrating an overall configuration of an automatic tag identification system 500 in Embodiment 5. As shown in FIG. In addition, in this figure, the part common to Example 1 is given the code|symbol common to Example 1. FIG. 10A is a flowchart for explaining the processing of the tag device 510 of the fifth embodiment, and FIG. 10B is a flowchart for explaining the processing of the backend device 530 of the fifth embodiment. Hereinafter, in this figure, the functional configuration and processing method of this embodiment will be described.

<preprocessing>

In Embodiment 5, a key storage 515 is provided on the tag device 510, and a key storage 536 is provided on the backend device 530, and the common keys KG and KH are respectively stored. Furthermore, the tag device 510 is provided with encryption function calculation units 512 and 513 instead of the hash calculation units 112 and 113 of the first embodiment, and the backend device 530 is provided with an encryption function calculation unit 533 instead of the hash calculation unit 133 . Then, the encryption function calculation units 512, 513, and 533 may perform calculations using common key encryption functions such as AES and Camellia instead of the hash function. In addition, in Embodiment 5, the common key encryption function E using the common key KG corresponds to "the first function F1 which is difficult to find an inverse image", and the common key encryption function E using the common key KG corresponds to "scrambling A second function F2' that defines the relationship between the elements of the domain and their mappings. That is, the first function F1 and the second function F2 of this example are the same common key encryption function to which different common keys are applied.

The above point is different from Example 1.

<Handling of Label Device>

First, in the encryption function calculation unit 512 (corresponding to the “second calculation unit”), the secret value _sk,i is extracted from the secret value memory 111 (step S61), the common key KG is extracted from the key memory 515, and The common key encryption function _{E is used with the common key KG for the secret value sk,} i (E _KG (s _k,i ): step S62). The calculated encrypted text E _KG (sk _{, i} ) is sent as tag output information E _KG ( _{sk, i} ) from the interface 114 to the reading device 120 via wireless or wired (step S63 ).

Next, in the encryption function calculation unit 513 (corresponding to the “first calculation unit”), the common key KH is extracted from the key storage 515, the secret value _sk,i is extracted from the secret value storage 111, and the secret value s _{k, i} use the common key encryption function E (step S64) with the common key, and the operation result is stored on the secret value storage 111 as a new secret value s _i+1 =E _KH (s _{k, i} ) (step S65).

<Handling of reading device>

Same as Example 1.

<Handling of back-end devices>

First, the back-end device 530 receives the distribution information pd and the label output information E _KG ( _{sk, i} ) transmitted from the reading device 120 in the communication unit 132 (step S70). In addition, the received distribution information pd and label output information E _KG ( _{sk, i} ) are stored in the memory 136a. Next, the control unit 136 substitutes 1 for n and stores it in the memory 136a (step S71). Then, the control unit 136 refers to the value of n in the memory 136a, and causes the hash calculation unit 533 (corresponding to the "third calculation unit") to extract the secret value _sn,1 from the database memory 131 (step S72). Next, the control unit 136 substitutes 0 for j and stores it in the storage unit 136a (step S73). Then, the control unit 136 refers to the value of j in the memory 136a, and causes the hash calculation unit 533 to calculate the encrypted text E ^j _KG (E _KH (s _{n, 1} )) (equivalent to “the calculation result in the third calculation unit”) (step S74). Also, E ^j _KH (s _n,1 ) indicates that the common key function E is used j times with the common key for the secret value s _n,1. Next, in the comparison unit 134, the encrypted text E ^j _KG (E _KH (s _{n, 1} )) is obtained from the hash operation unit 133, and the storage 136a obtains the label output information E _KG (s _{k, i} ), and compares them ( Step S75).

Here, when these values do not match (step S76), the control unit 136 substitutes j+1 into the memory 136a (step S77), and determines whether j exceeds a predetermined maximum value j _max (step S78). Here, when j is less than or equal to the maximum value j _max , the control unit 136 executes the processing after step S74, and if j exceeds the maximum value j _max , it determines whether n in the memory 136a is m (step S18). Here, if not n=m, then control unit 136 stores n←n+1 (making n+1 new n) (step S80) in memory 136a, and then executes the processing after step S72, if n= m ends the processing. In addition, under the control of the control unit 136, if the label output information E _KG (s _{k, i} ) is inconsistent with the encrypted text E ^j _KG (E _KH (s _{n, 1} )), at least one of n and j The change in the value of is equivalent to performing the processing in the encryption function calculation unit 533 and the comparison unit 134 again.

On the other hand, when the tag output information E _KG (s _{k, i} ) matches the encrypted text E ^j _KG (E _KH (s _{n, 1} )) (step S76), the control unit 136 sends the matched encrypted text E The secret value s _n corresponding to ^j _KG (E _KH (s _{n, 1} )) is sent to the read-write unit 135, and the read-write unit 135 extracts the corresponding encrypted text E ^j _KG (E _KH (s _{n, 1} )), data _n such as ID information id _n and physical distribution information corresponding to the secret value sn, ₁ are sent to the communication unit 132 (step S81). Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, and writes the physical distribution information pd into the database memory 131 in association with the secret value _sn,1 (step S81). The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S82).

In addition, the encrypted text E ^j _KH (s _{n, 1} ) calculated in the process of step S74 in the backend device 530 may be stored in the memory 136a and used in step S74 of the next cycle. That is, use the recorded E ^j _KH (s _{n, 1} ) to find the encrypted text E ^j+1 _KH (s _{n, 1} ) through E _KH (E ^j _KH (s _{n, 1} )), and then store the value in the memory Also available in 136a. In this case, the number of encryption calculations performed by the hash calculation unit 533 can be reduced, and the calculation efficiency of the backend device 530 can be improved. Furthermore, in the back _- end device 530, E ^j _KH (s _{n, 1} ) (j∈{1, . In this case, the computing efficiency of the backend device 530 can be improved.

Furthermore, in Embodiment 5, the common key encryption function E using the common key KH is treated as "the first function F1 of the hard-to-reverse image", and the common key encryption function E using the common key KG is treated as The "second function F2 that disturbs the relationship between the elements of the domain and their mappings" is processed. Furthermore, in Embodiments 1 to 4 described above or Embodiments 6 to 11 described later, at least one of the first function F1 and the second function F2 is performed as a common key encryption function E using a common key KH or KG. Processing is also possible.

Thus, in Embodiment 5, the secret value sk _,i is updated using the common key encryption function. Therefore, even if the secret value _sk,i is leaked from the tag device 510, an attacker cannot trace the distribution process of the tag device 510 based on the secret value _sk,i and the communication history. Furthermore, since it is not necessary to provide a random number generating circuit in the tag device 510, the cost of the tag device 510 can be reduced. Furthermore, if a common-key encryption function simpler than a hash function (less computational complexity) can be used, the processing load of the tag device 510 and the back-end device 530 can be reduced.

[Example 6]

Embodiment 6 is a modified example of Embodiment 1. It is different from Embodiment 1 in that the hash value obtained by combining the secret value sk _,i and the bit of the first inherent value w _k inherent in the tag is used as the tag output information.

FIG. 11 is a diagram illustrating an overall configuration of an automatic label recognition system 600 in Embodiment 6, and FIG. 12 is a flowchart for explaining the processing of Embodiment 6. As shown in FIG. In addition, in FIG. 11, the part common to Example 1 is given the code|symbol common to Example 1. As shown in FIG. Hereinafter, using these figures, the functional configuration and processing method of the sixth embodiment will be described.

<preprocessing>

The difference from Embodiment 1 is that the secret value memory 611 of each tag device 610 stores the secret value sk _,i (corresponding to the "first secret value") and the intrinsic value w _k corresponding to each tag ID information id _k (equivalent to "the first inherent value"), in the database memory 631 of the back-end device 630, each tag ID information id _n (n ∈ {1, ..., m}) and its corresponding secret value s _{n, 1} (equivalent to "second secret value"), intrinsic value w _n (equivalent to "second intrinsic value"), and data _n such as logistics information are stored correspondingly. In addition, as the intrinsic value, for example, tag ID information can be used.

<Handling of Label Device>

Hereinafter, the processing when the reading device 620 is made to read the tag device 610 for the ith (i is a natural number) time will be described.

First, in the hash operation unit 612, the secret value s _{k, i} and the intrinsic value w _k are extracted from the secret value memory 611 (step S101), and the bits of the secret value s _{k, i} and the intrinsic value w _k are calculated. Output information G(s _{k, i} |w _k ) in combination with tags using the hash function G (step S102 ). Then, in the interface 114, the tag output information G(s _{k, i} |w _k ) is transmitted to the reading device 120 wirelessly or by wire (step S103).

Next, in the hash calculation unit 113, a hash value H(sk _,i ) using the hash function H for the secret value _sk,i extracted from the secret value memory 611 is calculated (step S104), and the The hash value H(s _{k, i} ) is overlaid on the secret value _{sk, i of the secret value memory 611 as a new secret value sk, i+1} (delete the secret value _{sk , i} of the secret value memory 611 and replace it with Store the secret value _sk,i+1 : step S105).

<Handling of reading device>

The reader 120 receives the tag output information G(s _{k, i} |w _k ) transmitted from the tag device 610 through the interface 122 (step S106 ), and sends it to the communication unit 123 . The communication unit 123 extracts the logistics information pd from the logistics information memory 121 (step S107), and sends the logistics information pd and the hash value H(s _{k, i} |w _k ) to the backend device 630 through the network 140 (step S108).

<Handling of back-end devices>

The back-end device 630 receives the distribution information pd and the label output information G(s _{k, i} |w _k ) transmitted from the reading device 120 in the communication unit 132 (accept input: step S109). In addition, the received distribution information pd and label output information G(s _{k, i} |w _k ) are stored in the memory 136a.

Next, in the control unit 136, 0 is substituted into the parameters j,n and stored in the memory 136a (step S110). Then, the control unit 136 refers to the value of j, n in the memory 136a, and uses a group of second secret values _{sn, 1} and the second A hash value H(H ^j (s _{n, 1} )|w _k ) is calculated for the intrinsic value w _n (step S111 ). In addition, this H ^j (s _n,1 ) may be calculated in advance and stored in the database memory 631 . In this case, the calculation load on the backend device 630 can be reduced.

Next, in the comparison unit 134, G(H ^j (s _{n, 1} ) | w _n ) is acquired from the hash operation unit 633, and the label output information G (s _{k, i} |w _k ) is acquired from the memory 136a, and compared with them (step S112).

Here, when these values do not match (step S113), the control unit 136 substitutes j+1 into j in the memory 136a (step S114), and determines whether j exceeds a predetermined maximum value j _max (step S115). Here, when j is less than or equal to the maximum value j _max , the process returns to step S111, and when j exceeds the maximum value j _max , n+1 is substituted into n in the memory 136a in the control unit 136, and 0 is substituted into j (step S116), judge whether n exceeds the maximum value n _max (step S117). Here, when n is equal to or less than the maximum value n _max , the process returns to step S111, and when n exceeds the maximum value n _max , the process ends in error (step S118).

On the other hand, in the judgment of step S113, when the tag output information G(s _{k, i} |w _k ) and the hash value G(H ^j (s _{n, 1} )|w _n ) coincide, the control unit 136 gives the value of n to the read-write unit 135, and the read-write unit 135 uses this n to extract from the database memory 631 the corresponding hash value G(H ^j (s _{n, 1} )|w _n ), id _n and data _n corresponding to the secret value s _{n, 1} and the unique value w _n are sent to the communication unit 132 . Then, the read/write unit 135 receives the distribution information pd from the memory 136a, and compares the distribution information pd with the secret value _sn,1 corresponding to the matched hash value G(H ^j (s _n,1 )|w _n ). Corresponding to the intrinsic value w _n , it is written into the database memory 631 (step S119).

The id _n and data _n sent to the communication unit 132 are sent to the reading device 120 via the network 140 (step S120), and are received and output by the communication unit 123 of the reading device 120 (step S121).

<Features of Embodiment 6>

In Embodiment 6, the tag output information G(s _{k, i} |w _k ) output from each tag device 610 is the hash of the bit combination of the secret value sk _{, i} and the inherent value w _k inherent to each tag device 610 value. And, the secret value _{sk, i} of each tag device is sequentially updated with the hash value H( _{sk, i} ). Therefore, even if the tag output information G(s _{k, i} |w _k ) is the same (conflict) between different tag devices, since the intrinsic value w _k is different for each tag device, if the secret value _sk of each tag device _{, i} is updated, then due to the collision difficulty of the hash function, the collision is eliminated with a high probability. In this way, the conflict of the tag output information G(s _{k, i} |w _k ) of the tag device 610 can be prevented from continuing, and the back-end device 630 can be prevented from being unable to output the information G(s _{k, i} |w _k ) from the tag to a single specific tag. ID information.

<Example 7>

Embodiment 7 is a modified example of Embodiment 6, and differs from Embodiment 6 in that each tag device shares a secret value. Hereinafter, the difference from Example 1 and Example 6 will be mainly described.

FIG. 13 is a diagram illustrating an overall configuration of an automatic tag identification system 700 in Embodiment 7. As shown in FIG. In addition, in this figure, the part common to Example 1 is given the code|symbol common to Example 1. Furthermore, FIG. 14 is a flowchart for explaining the processing of the seventh embodiment. Hereinafter, using these figures, the functional configuration and processing method of the seventh embodiment will be described.

<preprocessing>

Generate a certain random number s ₁ ∈ {0, 1} ^t for each ID (id _k (k=1,...,m)) corresponding to each tag device 710, and use it as a secret value s ₁ (of s ₁ The initial value, corresponding to the “first secret value”) is stored in the secret value memory 711 of each tag device 710 . And _, for each tag ID information (id _k (k=1, . in memory 711.

Furthermore, the same secret value _s1 as the secret value _s1 stored in each tag device 710 is stored in the database memory 731 of the backend device 730 as a "second secret value". Furthermore, in the database memory 731 , each intrinsic value w _n is stored in association with the tag ID information id _n of the corresponding tag device 710 and data _n such as logistics data.

Furthermore, the hash value s _{j+2 =} H ^j+1 (s ₁ ) (j=0, .. ., j _max ). Each calculated hash value s _j+2 is stored in the database memory 731 .

<Handling of Label Device>

Hereinafter, the processing when the reading device 720 is made to read the tag device 710 for the ith (i is a natural number) time will be described.

First, in the hash calculation unit 712, the secret value s _i and the unique value w _k are extracted from the secret value memory 711 (step S131), and the hash of the bit combination of the secret value s _i and the unique value w _k is calculated. Value label output information G(s _i |w _k ) (step S132). Then, in the interface 114, the tag output information G(s _i |w _k ) is transmitted to the reading device 120 wirelessly or by wire (step S133).

Next, in the hash calculation unit 113, the hash value H( _si) for the secret value _si extracted from the secret value memory 711 is calculated (step S134), and the hash value H(si ₎ is used as The new secret value s _i+1 is overwritten on the secret value s _i in the secret value memory 711 (step S135).

<Handling of reading device>

The same as in Embodiment 1 (steps S136 to S138).

<Handling of back-end devices>

The back-end device 730 receives the distribution information pd and the label output information G(s _i |w _k ) transmitted from the reading device 120 in the communication unit 132 (step S139). In addition, the received distribution information pd and label output information G(s _i |w _k ) are stored in the memory 136a.

Next, in the control unit 136, 1 is substituted into the parameters j,n and stored in the memory 136a (step S140).

Then, in the hash operation unit 733 (corresponding to the “third operation unit”), the unique value w _n extracted from the database memory 731 and the secret value s ₁ or the hash value s _j+2 (in the hash operation unit The hash value s _j+2 calculated in step 736 (calculated in advance) calculates the hash value G(s _j+1 |w _k ) (step S141).

Next, in the comparison unit 134, G(s _j+2 |w _n ) (corresponding to “the calculation result in the third calculation unit”) is acquired from the hash calculation unit 733, and the label output information G(s _i |w _k ), and compare them (step S142).

Here, when these values do not match (step S143), the control unit 136 substitutes j+1 into j in the memory 136a (step S144), and determines whether j exceeds a predetermined maximum value j _max (step S145). Here, when j is equal to or less than the maximum value j _max , the process returns to step S141, and when j exceeds the maximum value j _max , n+1 is substituted into n in the memory 136a in the control unit 136, and 0 is substituted into j (step S146), judge whether n exceeds the maximum value n _max (step S147). Here, when n is equal to or less than the maximum value n _max , the process returns to step S141, and when n exceeds the maximum value n _max , the process ends in error (step S148).

On the other hand, in the judgment of step S143, if the label output information G(s _i |w _k ) matches the hash value G(s _j+2 |w _n ), under the control of the control unit 136, In the reading/writing unit 135, the id _n and _data n corresponding to the unique value _{w n corresponding} to the matched hash value G(s _j+2 |wn ) are extracted from the database memory 731 and transmitted to the communication section 132 . Furthermore, the read/write unit 135 receives the distribution information pd from the communication unit 132, associates the distribution information pd with the unique value w _n corresponding to the matching hash value G(s _j+2 |w _n ), and writes it into the database memory 731 (step S149).

The id _n and data _n sent to the communication unit 132 are sent to the reading device 120 via the network 140 (step S150), and are received and output by the communication unit 123 of the reading device 120 (step S151).

<Features of Embodiment 7>

In Embodiment 7, the secret value s ₁ shared by each tag device 710 is used. Therefore, the secret value s _j+1 used in the process of step S141 of the backend device 730 can be shared among the tag ID information id _n . As a result, the amount of computation in the back-end device 730 can be greatly reduced, and efficient retrieval can be performed.

Specifically, when the number of times of hashing by the hashing device 730 (the number of times of updating the secret value of the tag device 710 ) is j, in Embodiment 1, 2mj times of hashing operations are required. In contrast, in the seventh embodiment, it is possible to suppress hash operations to mj+j times.

Furthermore, the tag device 710 outputs the tag output information G(s _i |w _k ) and the update times rn of the secret value _si at the same time, and if the update times rn is given to the back-end device 730 (see Embodiment 4), the latter The number of hash operations in the end device 730 is reduced to m+j times.

[Example 8]

Embodiment 8 is a modified example of Embodiment 1, and differs from Embodiment 1 in that a combination of elements is allocated as a value unique to each tag device. Thereby, a part of the elements allocated to each tag device is shared among a plurality of tag devices. As a result, the total amount of calculations required for identification processing of the tag device can be reduced.

FIG. 15 is a diagram illustrating an overall configuration of an automatic tag recognition system 800 in Embodiment 8. As shown in FIG. In this figure, the parts common to Example 1 are given the same code|symbol as Example 1. 16A is an example of data stored in the secret value memory 811 of the tag device 810 , and FIG. 16B is an example of data stored in the database memory 831 of the backend device 830 . Furthermore, FIGS. 17 and 18 are flowcharts for explaining the processing in the eighth embodiment.

Hereinafter, using these figures, the functional configuration and processing method of the seventh embodiment will be described. In addition, the description of the items common to the first embodiment will be omitted.

<preprocessing>

For example, a random number generator (not shown) is used to generate a set of initial values assigned to elements of each tag device

(b _1,1,0 ,...b _1,j,0 ,...b _1,ρ,0 )...( _bu,1,0 ,...b _u,j,0 ,... b _{u, ρ, 0} )...(b _{d, 1,} 0 , b _{d, j, 0} , ... b _{d, ρ, 0} ).

In addition, the set of elements in each "()" is called a subgroup α _u (u∈{1, . . . , d}).

Here, j is a natural number of 1≤j≤ρ (j∈{1,...,ρ}), and u is a natural number of 1≤u≤d (u∈{1,...,d}). Furthermore, in Embodiment 8, one secret value is formed by combining a plurality of elements, but d (d≥2) is the number of elements constituting the one secret value. In addition, m is a number equal to or greater than the total number of tag devices 810 (the total number of required secret values), and m= ^ρd is a number that is a natural number.

Next, the combination of each element generated in this way is distributed to each tag device 810 . Specifically, one element is selected from each of the d types of subgroups α _u constituting the set of initial values of the above elements, and the combination of the selected d initial elements f _u,0 (f _1,0 ,. .., f _{u, 0} , ..., f _{d, 0} ) are allocated to each tag device 810 (f _1,0 ∈{b _1,1,0 ,..,...,b _1,j,0 ,. ..,..., _b1,ρ,0 },...,fu _,0 ∈{bu _,1,0 ,...,...,bu _,j,0 ,...,..., _{bu, ρ,0} },...,fd _,0 ∈ {bd _,1,0 ,...,...,bd _,j,0 ,...,...,bd _,ρ,0 }). In addition, this allocation is performed so that different tag devices 810 are not in the same combination, and (f _1,0 , ..., f _{u, 0} , ..., f _{d, 0} ) combination. Moreover, a combination of multiple initial elements f _{u, 0} may also be associated with one tag device 810. In this case, (f _1,0 ,. .., f _{u, 0} , ..., f _{d, 0} ). In addition, at least some of the elements constituting (f _1,0 , . _{. .} , fu _{, 0 ,} .

All generated combinations (f ₁ , 0 , ..., f _{u, 0} , ..., f _{d, 0} ) (d (d≥2) initial elements f _{u, 0} (u∈{1,. . . , d})) respectively correspond to the assigned tag ID information id _n of each tag device 810 and data data _n corresponding to each tag device 810 , and are stored in the database memory 831 of the backend device 830 . In addition, n is a value corresponding to each tag device, and corresponds to a character k in the following table of tag output information a _k,i (described later) output from each tag device. That is, the combination of d initial elements f _u,0 stored in the database memory 831 becomes the total number of tag devices 810 . Furthermore, when one label device 810 corresponds to a plurality of combinations of initial elements f _u,0 , the number of combinations of d initial elements f _u,0 stored in the database memory 831 is greater than or equal to the total number of label devices 810.

Furthermore, the generated combination of initial elements (f _1,0 ,...,f _u,0 ,...f _d,0 ) ("d (d≥2) elements e _{u, vu} (u∈ The combination of {1,...,d}) corresponds to each tag ID information id _k ". Among them, vu is an integer greater than or equal to 0 that represents the update times of e _{u, vu} . Elements e _{u, vu} The following table uv represents v _u .) is stored in the secret value memory 811 of each assigned tag device 810 . In addition, below, the combination of initial elements stored in the secret value memory 811 of each tag device 810 is expressed as (e _1,0 ,..., _eu,0 ,..., _ed,0 ).

The example in FIG. 16 exemplifies allocation of initial elements in the case of d=2, ρ=3, and m=9.

As shown in FIG. 16B , in the case of this example, in the database memory 831 of the back-end device 830, the initial element combination 831aa((f _1,0 f _2,0 )(f _1,0 ∈{b _{1, 1, 0} , b _{1, 2, 0} , b 1, _{3, 0} }, f _{2, 0} ∈ {b 2, _{1, 0} , b _{2, 2, 0} , b _{2, 3,} 0 })) and labels ID information 831ab(id _n (n ∈ {1, . . . , 9}) and data 831ac (data _n (n ∈ {1, . . . , 9})) are stored in association.

Moreover, as shown in FIG. 16A, the secret value memory 811 of the tag device 810 stores a combination 811a of a group of initial elements corresponding to the tag information id ((e _1,0 , e _2,0 )=(b _{1,2 ,0} ,b _2,2,0 )). In addition, part of the above-mentioned elements _{eu, vu} stored in the secret value memory 811 is also stored in the secret value memory of the other tag device as an element corresponding to another tag device.

<Handling of Label Device>

Hereinafter, the processing when causing the reading device 20 to read the tag device 810 for the ith (i is a natural number) time will be described.

First, in the hash operation unit 812 (corresponding to the “second operation unit”), d elements e _{u, vu} are extracted from the secret value memory 811 (step S161), and a combination value ( The secret value s _k,i ) uses the hash function G to output label information a _k,i =G(s _k,i ) (step S162). Here, k is a value corresponding to each label device, and i is a natural number indicating the number of outputs in the output unit. Moreover, in this embodiment, set the secret value _sk,i =e _1,v1 |...|e _u,vu |...|e _d,vd , and set the label output information a _k,i =G(e _{1 , v1} |...|e _{u, vu} |...|e _{d, vd} ), but the bit arrangement sequence of each element e _{u, vu} is not limited to this.

The generated label output information a _k,i is sent to the interface 114, and the interface 114 outputs the label output information a _k,i (step S163).

Afterwards, in the hash operation unit 813 (corresponding to the "first operation unit"), at least a part of the elements e _{u', vu'} (u'∈{1,...,d}) are extracted from the secret value memory 811 ) and calculate the hash value H( _{eu', vu') of the extracted elements e u', vu'} (step S164), and use the hash value H(e _{u', vu'} ) as the new element e _{u ', vu'+1} are overwritten and stored in the secret value memory 811 (step S165). In addition, any selection method of u'∈{1, . . . , d} may be used. For example, a method of selecting a different u' every time the tag device 810 communicates can be exemplified, and a method of selecting another u' for one u' at the time when all updates of elements eu _{' and vu'} are completed, and simultaneously selecting a method greater than equal to two u' methods etc.

<Handling of reading device>

The reader 120 receives the tag output information a _k,i transmitted from the tag device through the interface 122 (step S166 ), and sends it to the communication unit 123 . The communication unit 123 extracts the logistics information pd from the logistics information storage 121 (step S167), and sends the logistics information pd and label output information a _k,i to the back-end device 830 through the network 140 (step S168).

<Handling of back-end devices>

The tag output information a _{k, i} and distribution information pd transmitted from the reading device 120 are received by the communication unit 132 and stored in the memory 136a (step S169).

Using this as a trigger, the control unit 136 substitutes 1 for n and stores it in the memory 136a (step S170), selects a combination of d w _u as follows, and stores the combination in the memory 136a (step S171).

(w ₁ ,...,w _d )∈S _w ={w ₁ ,...,w _d |w _u ∈[0,j _max ]}

(Wherein, [α, β] represents a set of integers greater than or equal to α and less than or equal to β.)

Next, the control unit 136 refers to the combination of n and d w _u in the memory 136a, and further refers to the hash value memory 838, and checks the d initial elements f _{u , 0} (u∈{1, ..., d}) whether the hash value H ^wu (fu _{, 0} ) using the hash function H w _u times is stored in the hash value memory 838 (whether the generation is complete) (step S172). In addition, the superscript wu of H ^wu (fu _{, 0} ) means w _u .

Here, when it is determined that there is a value that has not yet been calculated in the hash value H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n , the hash calculation unit 837 extracts the above-mentioned " The hash value H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n corresponds to the initial element f _{u, 0} corresponding to the value that has not yet been operated, and uses w _u for the initial element f _{u, 0} second hash function H and calculate the hash value H ^wu (fu _{, 0} ) (step S173). The calculated hash value H ^wu (fu _{, 0} ) is stored in the hash value memory 838 (step S174), and the process returns to step S172.

On the other hand, in the judgment of step S172, when it is judged that the hash values H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n have all been generated, the control unit 136 refers to n, d in the memory 136a. The combination of w _u makes the hash operation unit 833 (equivalent to the “third operation unit”) extract from the hash value memory 838 d initial elements f _u,0 (u∈) corresponding to the tag ID information id _{n {} ^{1 ,} _{. _ 0} ) bit combination using the calculated value c of the hash value G (step S176). In addition, as the calculation value c, for example, c=G(H ^w1 (f _1,0 )|... |H ^wu (f _u,0 )|...|H ^wd (f _d,0 )) can be exemplified, but each hash The bit arrangement order of the value H ^wu (fu _{, 0} ) is not limited to this. However, the order needs to correspond to the bit arrangement order of the elements e _{u and vu} in the hash calculation unit 812 of the tag device 810 .

Next, in the comparison unit 134, the tag output information a _k,i is read from the memory 136a, the above-mentioned calculation value c is received from the hash calculation unit 833, and they are compared to determine whether c= _ak,i (step S177) . In this example, compare the hash value c=G(H ^w1 (f _{1, 0} )|…|H ^wu ( _{fu, 0} )|…|H ^wd (f _{d, 0} )) and the label output information a _{k , i} .

Here, when it is determined that they do not match, the control unit 136 refers to the memory 136a and determines whether or not all the d combinations (w ₁ , . . . , w _d )εS _w have been selected (step S178). Here, in the case where it is judged that there is a combination pattern that has not been selected yet _{, a} new combination (w ₁ , . For this new combination and n, the processes after step S172 are executed.

On the other hand, when all combinations are selected by the determination in step S178, the control unit 136 refers to n in the memory 136a to determine whether n=m (step S180). Here, when it is judged not that n=m, the control unit 136 updates n in the memory 136a with n+1 (step S181), and executes the processing after step S172. On the other hand, when it is judged that n=m, the process ends in error (step S182).

In addition, the processing of steps S172 to 181 is under the control of the control unit 136. If the label output information a _{k, i} and the calculated value c do not match, at least part of the values of n and w _u will be changed, which is equivalent to performing the hash calculation unit again. 833 and the processing in the comparing unit 134.

On the other hand, in step S177, when it is judged that the hash value c matches the tag output information a _k,i , the read/write unit 135 selects from the database memory 831 the information corresponding to The tag ID information id _n corresponding to the combination of multiple initial elements f _{u and 0} of the hash value c is extracted, and the tag ID information id _n and corresponding data data _n are extracted and sent to the communication unit 132 . Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, and additionally writes the physical distribution information pd into the database memory 831 as data data _n corresponding to the tag ID information id _n (step S183).

The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S184), and are received and output by the communication unit 123 of the reader 120 (step S185).

<Features of Embodiment 8>

[efficiency]

The calculation of the hash value c by the hash calculation unit 838 of the backend device 830 requires the calculation of the hash value H ^wu ( _{fu, 0} )= _{fu, vu} . In Embodiment 8, since multiple tag devices 810 share e _{u, vu} , if the hash value H ^wu (fu _{, 0} ) calculated for the calculation of the hash value c corresponding to any tag device 810 =f _{u, vu} is stored in the hash value memory 838, and this element f _{u, vu} can also be used in the calculation of the hash value c corresponding to another tag device 810. Accordingly, the number of tag devices 810 that can be supported can be increased without increasing the number of hash values H ^wu (fu _{, 0} ) to be calculated. Specifically, initial elements unique to ^ρd tag devices can be allocated using d*ρ elements.

Furthermore, since the communication data is constituted only by the operation of the hash function, the circuit scale in the tag device 810 is small compared with the conventional method of generating random numbers, and is suitable for applications requiring low cost.

[Untraceability]

In Embodiment 8, the tag output information a _k,i =G(s _k,i ) is used for communication. Due to the unrecognizability of the hash value, for an attacker who does not know the secret value, the tag output information a _k,i =G(s _k,i ) is regarded as a purely random number. Therefore, the attacker cannot know whether the tag output information a _k,i =G(s _k,i ) and a _k,i+1 =G(s _k,i+1 ) are output from the same tag device 810 value, and the distribution process of the tag device 810 cannot be traced.

[Forward Safe]

In Embodiment 8, the secret value in the secret value memory 811 used for communication is updated by the hash function H. Furthermore, due to the unidirectionality of the hash function, even if the elements e _{u, vu} are leaked such as when the tag device 810 is tampered with, the attacker cannot obtain the past elements e _{u, vu -Δvu from the elements e u, vu} . Therefore, even if each element _{eu, vu} is leaked, the attacker cannot obtain the correspondence between each acquired element _{eu, vu} and the communication history, and cannot trace the tag device 810 .

[Tracking Possibility]

On the other hand, according to the hash function G, the collision difficulty of H (the hash value of different values is difficult to take the same value), the back-end device 830 that knows each element f _{u, vu} can track the circulation process of the tag device 110 .

In addition, in Embodiment 8, the set of initial elements generated in the backend device 830 is

(b _1,1,0 ,...b _1,j,0 ,...b _1,ρ,0 )...( _bu,1,0 ,...b _u,j,0 ,... b _{u, ρ, 0} )...(b _{d, 1,} 0 , ... b _{d, j, 0} , ... b _{d, ρ, 0} ).

That is, p initial elements b are generated for each u (u∈{1, . . . , d}). However, the number of initial elements b generated for each u (u∈{1, . . . , d}) may be different.

In addition, in the hash calculation unit 837 of the backend device 830, the hash value H ^wu ( _{fu, 0} ) (u∈{1, . . . , d }) and stored in the hash value memory 838.

[Example 9]

Embodiment 9 is a modified example of Embodiment 8. The secret value memory of the tag device and the database memory of the back-end device also store the intrinsic value inherent to each tag device, and the bits including each element e _{u, vu} and the intrinsic value γ _k It is different from the eighth embodiment in that the combined hash value a _k,i =G(s _k,i ) of the columns is output as the label. Thereby, it is possible to prevent a situation where the secret value of a specific tag device is obtained and the tag device is tracked based on the elements e _{u, vu} gathered by interfering with other tag devices.

Hereinafter, only the points of difference from the eighth embodiment will be described, and descriptions of items common to the eighth embodiment will be omitted.

FIG. 19 is a diagram illustrating an overall configuration of an automatic tag recognition system 900 in Embodiment 9. As shown in FIG. 20A is an example of data stored in the secret value memory 911 of the tag device 910 , and FIG. 20B is an example of data stored in the database memory 931 of the backend device 930 . In addition, in FIG. 19 , the same reference numerals as in FIG. 2 are assigned to the common functional configurations as in the first embodiment, and the same reference numerals as in FIG. 15 are assigned to the common functional configurations in the eighth embodiment, and their descriptions are omitted. Furthermore, only one label device 910 is illustrated in FIG. 19 , but a plurality of label devices 910 actually exist.

Hereinafter, the functional configuration and processing method of Embodiment 9 will be described using these figures.

<preprocessing>

The difference from Embodiment 8 is that the secret value memory 911 of the tag device 910 also stores the intrinsic value γ _k , and d (d≥2) initial elements f _{u are stored in the database memory 931 of the backend device 930,} The combination of ₀ (u∈{1,...,d}), the inherent value γ _n unique to each tag device, and the tag ID information id _n of each tag device (n is a value corresponding to each tag device) are stored in correspondence. In addition, the intrinsic values γ _k and γ _n are, for example, random values.

The example in FIG. 20 exemplifies the assignment of the combined intrinsic values in the case of d=2, ρ=3, and m=9.

As shown in FIG. 20B , in this example, in the database memory 931 of the backend device 930, the combination of initial elements 931aa((f _1,0 f _2,0 )(f _1,0 ∈ {b _{1,1, 0} , b _{1, 2, 0} , b 1 _{, 3, 0} }, f _{2, 0} ∈ {b 2, ₁ , 0 , b _{2, 2} , 0 , b 2, _3, 0 })), tag ID information 931ab(id _n (n∈{1,...,9}), data 931ac(data _n (n∈{1,...,9})) and intrinsic value 931ad(γ _k , k ∈ {1, ..., 12}) corresponding storage. And, as shown in Figure 20A, the combination 911a ((e _{1.0, e2, 0} )=(b _{1, 2, 0, b2, 2, 0} )) and an intrinsic value 911b (γ _k =γ ₅ ).

<Handling of Label Device>

Hereinafter, the processing when the reading device 120 is made to read the tag device 910 for the ith (i is a natural number) time will be described.

First, in the hash operation unit 912 (corresponding to the “second operation unit”), each element e _{u, vu} and the eigenvalue γ _k are extracted from the secret value memory 911, and each element e _{u, vu} including the extraction is calculated. And the tag output information a _k,i =G(s _k,i ) of the hash value of the combined value of the bit sequence of the intrinsic value γ _k (secret value sk _,i ). In Embodiment 9, set the secret value s _k,i =γ _k |e _1,v1 |...|e _u,vu |...|e _d,vd , and set the label output information a _k,i =G( γ _k |e _{1, v1} |...|e _{u, vu} |...|e _{d, vd} )

Thereafter, as in the eighth embodiment, the tag output information a _k,i is output, and the elements of the hash value memory 911 are updated.

<Handling of reading device>

Same as in Example 8.

<Handling of back-end devices>

The difference from the eighth embodiment is that instead of the processing of step S176 in the eighth embodiment (FIG. 18), the hash calculation unit 933 (corresponding to the "third calculation unit") reads the unique value γ _n from the database memory 931, And calculate the hash value c of the combined value of the bit sequence including the hash value H ^wu (fu _{, 0} ) and the intrinsic value γ _n . In this example, c=G(H ^w1 (f _1,0 )|...|H ^wu (fu _,0 )|...|H ^wd (f _d,0 )) is calculated. Other than that, it is the same as in Example 8.

<Features of Embodiment 9>

[Untraceability]

In Embodiment 9, the label output information a _k,i =G(s _k,i ) including the hash value of the combination of each element e _{u, vu} and the bit sequence of the intrinsic value γ _k is used as the output of the label device 910 . Here, the unique value γ _k is a value unique to each tag device 910 . Therefore, even if a certain tag device is tampered with, the past tag output information of other tag devices that share elements e _{u and vu} cannot be obtained from the hash value of the data stored therein. Therefore, an attacker cannot track other tag devices.

[Example 10]

Embodiment 10 is a modified example of the mode of embodiment 8. The diverse value z of the value of t types (t≥2) is stored in the diverse value memory of the tag device, and each element e _{u, vu} and any element extracted from the secret value memory The hash value a _{k , i} =G(s _{k, i ) of the bit combination value (secret value s k, i} ) of the diverse value z of z is used as the output information, and the secret value memory is updated every t times of communication. Different from Example 8.

Hereinafter, only the points of difference from the eighth embodiment will be described, and descriptions of items common to the eighth embodiment will be omitted.

FIG. 21 is a diagram illustrating an overall configuration of an automatic tag identification system 1000 in Embodiment 10. As shown in FIG. 22 is a flowchart for explaining the processing of the tag device 1010 , and FIG. 23 is a flowchart for explaining the processing of the backend device 1030 . In addition, in FIG. 21, the same code|symbol as Example 2, 15 is attached|subjected to the functional structure common to Example 1, Example 8. Furthermore, in FIG. 21 , only one label device 1010 is illustrated, but actually a plurality of label devices 1010 exist.

Hereinafter, the functional configuration and processing method of this embodiment will be described using these figures.

<preprocessing>

The difference with Embodiment 8 is that in the diverse value generating unit 1015 of the tag device 1010, a diverse value z of values of t types (t≥2) is generated, and stored in a diverse value memory 1016 (equivalent to "the first Multivariate value memory"), and the database memory 1031 (equivalent to "second diverse value memory") of the back-end device 1030 stores the multivariate value z of t types (t≥2) common to each tag device 1010.

In addition, as the diverse value generation unit 1015, a counter that counts z=1...t, and a hash that performs operations of z=H(seed, x), x∈{1,...,t} can be exemplified. The computing device is a hash computing device or the like that performs the computation of z=H ^x (seed), x∈{1, . . . , t}. Here, seed represents an initial value. Hereinafter, the multivariate value z is expressed as z=π(x), and the count value x∈{1, . . . , t}. Furthermore, it is preferable that the various values z=π(x) corresponding to each x∈{1, . . . , t} do not agree.

Furthermore, the generation and storage of the diverse value z is not necessarily performed in the preprocessing, but may be performed during the communication processing of the tag device 1010 or the retrieval processing of the backend device 1030 .

<Handling of Label Device>

Hereinafter, the processing when causing the reading device 120 to read the tag device 1010 for the ith (i is a natural number) time will be described. In addition, when the initial value (i=1) of the count value x is 1, the count value x is stored in the memory 115 a under the control of the control unit 115 .

First, in the hash calculation unit 1012 (corresponding to the “second calculation unit”), each element e _{u, vu} is extracted from the secret value memory 1011, and any various value z is extracted from the various value memory 1016 (in this In an example, z=π(x)) (step S191). Then, the hash operation unit 1012 calculates the hash function _{a k,i} =G(s _{k ,i ) of the bit combination value (secret value s k,i} ) of each extracted element e _u,vu and the diversity value z as a label. The information is output (step S192). In this example, set the secret value sk _{, i} = e _{1, v1} |...|e _{u, vu} |...|e _{d, vd} |z, and set the label output information a _{k, i} = G(e _{1 , vl} |...|e _{u, vu} |...|e _{d, vd} |z). In addition, the order of bit arrangement of each element e _{u, vu} and the variety value z, and the number of bit-combined variety values z are not limited thereto. Furthermore, when the various values z=π(x) corresponding to x∈{1,...,t} do not match, the hash calculation unit 1012 generates label output information while the elements of the secret value memory 1011 are not updated. The diversity value z used for a _k,i is different for each communication.

The generated label output information a _k,i is sent to the interface 114, and the interface 114 outputs the label output information a _k,i (step S193).

Thereafter, in the control unit 115, the calculation (cumulation) of x←x+1 is performed (step S194), and it is judged whether or not x>t (step S195). Here, if it is judged not to be x>t, the processing of the tag device 1010 ends while the value of x is held in the memory 115a.

On the other hand, when it is determined that x>t, the control unit 115 sets the counter value x of the memory 115a to x←1 (step S196), and the hash operation unit 1013 retrieves the value from the secret value memory 1011 Extract at least a part of e _{u', vu'} (u'∈{1,...,d}), and calculate the hash value H(e _{u', vu'} ) of the extracted e _{u', vu'} ( Step S197). Then, in the hash value calculation unit 1013, the hash value H( _{eu', vu'} ) is overwritten on the secret value memory 1011 as new e _{u', vu'+1} (step S198). In addition, any selection method of u'∈{1, . . . , d} may be used.

<Handling of reading device>

Same as in Example 8.

<Handling of back-end devices>

The tag output information a _{k, i} and distribution information pd transmitted from the reader 120 are received by the communication unit 132 and stored in the memory 136a (step S201).

Using this as a trigger, the control unit 136 substitutes 1 for n and stores it in the memory 136a (step S220), selects a combination of d w _u as follows, and stores the combination in the memory 136a (step S203).

(w ₁ ,...,w _d )∈S _w ={w ₁ ,...,w _d |w _u ∈[0,j _max ]}

Next, the control unit 136 refers to the combination of n and d w _u in the memory 136a, and further refers to the hash value memory 838, and checks the d initial elements f _{u , 0} (u∈{1, ..., d}) whether the hash value H ^wu (fu _{, 0} ) using the hash function H w _u times is stored in the hash value memory 838 (whether the generation is completed) (step S204 ). In addition, the superscript wu of H ^wu (fu _{, 0} ) means w _u .

Here, when it is determined that the hash value H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n has a value that has not yet been calculated, the hash calculation unit 837 extracts the above-mentioned " The hash value H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n corresponds to the initial element f _{u, 0} corresponding to the value that has not yet been operated, and uses w _u for the initial element f _{u, 0} second hash function H and calculate the hash value H ^wu (fu _{, 0} ) (step S205). The calculated hash value H ^wu (fu _{, 0} ) is stored in the hash value memory 838 (step S206), and the process returns to step S204.

On the other hand, in the judgment of step S204, when it is judged that the hash values H ^wu (fu _{, 0} ) corresponding to the tag ID information id _n have all been generated, the control unit 136 refers to n, d in the memory 136a. The combination of w _u makes the hash operation unit 1033 (equivalent to the “third operation unit”) extract from the hash value memory 838 d initial elements f _u,0 (u∈) corresponding to the tag ID information id _n {1, . . . , d}) respectively use the hash value H ^wu (fu _{, 0} ) of the first function F1 w _u times (step S207 ). Then, the control unit 136 sets the counter value x′ to 1 and stores it in the memory 136 a (step S208 ), and extracts a variety value z=π(x′) from the database memory 1031 and sends it to the hash operation unit 1033 . Then, the hash operation unit 1033 calculates an operation value c obtained by using the hash value G for the bit combination value of the hash value H ^wu (fu _,0 ) and the diversity value z (step S209 ). In addition, as the calculated value c, for example, c=G(H ^w1 (f _1,0 )|...|H ^wu (f _u,0 )|...|H ^wd (f _d,0 )|z) can be exemplified, but each The bit arrangement order of the hash value H ^wu (fu _{, 0} ) and the various values z, and the number of the various values z combined with bits are not limited thereto. However, the order needs to correspond to the bit arrangement order of each element in the hash calculation unit 1012 of the tag device 1010 .

Next, in the comparison unit 134, the tag output information a _k,i is read from the memory 136a, the above-mentioned calculation value c is received from the hash calculation unit 1033, and they are compared to determine whether c=a _k,i (step S210) . In this example, compare the hash value c=G(H ^w1 (f _{1, 0} )|…|H ^wu ( _{fu, 0} )|…|H ^wd (f _{d, 0} )|z) and the label output information a _{k, i} .

Here, when it is judged that these do not match, the control part 136 judges whether x' of the memory 136a is t (step S211). Here, when x'=t is not the case, the control unit updates x' in the memory 136a with x'+1 and executes the processing after step S209 (step S323). On the other hand, when it is judged that x'=t Next, the control unit refers to the memory 136a to judge whether or not all the d combinations (w ₁ , . . . , w _d )εS _w have been selected (step S213).

Here, when it is judged that there are combinations that have not been selected yet, the control unit 136 selects new combinations (w ₁ , . . . , w _d )∈S _w and stores them in the memory 136a (step S214 ), for the new combination and n, the processing after step S204 is executed. On the other hand, in the judgment of step S213, when all the combinations are selected, the control unit 136 refers to n of the memory 136a and judges whether or not n=m (step S215). Here, when it is judged that n=m is not, the control unit 136 updates n in the memory 136a with n+1 (step S216), and executes the processing after step S204. On the other hand, when it is judged that n=m, the processing is ended by mistake (step S217).

In addition, in the processing of steps S204 to 216, under the control of the control unit 136, if the label output information a _{k i} does not match the calculated value c, it is equivalent to changing at least a part of the values of n, w _u , and z, and then hashing Processing in the calculation unit 1033 and the comparison unit 134 .

On the other hand, in step S210, if it is determined that the hash value c matches the tag output information a _k,i , the read/write unit 135 selects from the database memory 1031 the information corresponding to The tag ID information id _n corresponding to the combination of multiple initial elements f _{u and 0} of the hash value c is extracted, and the tag ID information id _n and corresponding data data _n are extracted and sent to the communication unit 132 . Then, the read/write unit 135 receives the physical distribution information pd from the memory 136a, and additionally writes the physical distribution information pd into the database memory 1031 as data data _n corresponding to the tag ID information id _n (step S218). The tag ID information id _n and data data _n sent to the communication unit 132 are sent to the reader 120 via the network 140 (step S219 ).

<Features of Embodiment 10>

[Untraceability]

The labeling device 1010 of this embodiment outputs the information a _k,i using the hash value of the element eu _,vu and the bit-combined value of the diversity value z as a label. Therefore, it is possible to change the output value by changing the diversity value z without updating the element e _{u, vu} . Furthermore, due to the unidirectionality of the hash function, it is impossible to correlate such a changed output value. Furthermore, since the multivariate value z is a value of t types, the tag device can perform communications that are difficult to trace up to t times without updating the elements e _{u, vu} .

[efficiency]

The tag device 1010 of this embodiment updates only the elements e _{u, vu} of the sequential secret value memory 11 for t times of communication. Therefore, it is possible to reduce the update processing calculation amount of the tag device 1010 to 1/t.

Furthermore, the comparison process between the hash value c of the backend device 1030 and the label output information a _k,i can be performed T times at most each time without changing the combination of the hash value H ^wu (fu _,0 ). Therefore, even when the allowable number of communications of the tag device 210 (the maximum number of calls from the reading device 120 to the tag device 1010) is increased, the hash processing in the backend device 1030 does not increase much.

[Example 11]

Embodiment 11 is a modified example of Embodiment 10. In the multi-value memory of the tag device, a multi-value that takes the value of t _u type (t _u ≥ 2) is stored for each u (u ∈ {1, ..., d}) z _u , the label output information a _{k ,i} =G(e _1,v1 |z ₁ |…|e _{d , vd} |z _d ) as the output value, which is different from Embodiment 10. In addition, the elements e _{u and vu} corresponding to each u (u∈{1,...,d}) of the secret value memory are updated once every t _u communication, but in the eleventh embodiment, each element e The communication time point when _{u and vu} are updated is shifted. When the tag device outputs the tag output information a _{k, i} each time, one of the elements e _{u', vu'} (u'∈{1, .. ., d}) is updated. Therefore, even if the tag device is tampered with at any time of communication, the tag device cannot be tracked.

Hereinafter, only the points of difference from Embodiment 1 and Embodiment 10 will be described, and descriptions of matters common to the aspects of Embodiment 1 and Embodiment 10 will be omitted.

FIG. 24 is a diagram illustrating an overall configuration of an automatic tag identification system 1100 in Embodiment 11. As shown in FIG. Furthermore, FIG. 25 is a flowchart for explaining the processing of the tag device 1110 , and FIG. 26 is a flowchart for explaining a part of the processing of the backend device 1130 . In addition, in FIG. 24, the same code|symbol as Example 2, 15 is attached|subjected to the functional structure common to Example 1, Example 8. Furthermore, in FIG. 24 , only one label device 1110 is illustrated, but actually a plurality of label devices 1110 exist.

Hereinafter, the functional configuration and processing method of this embodiment will be described using these figures.

<preprocessing>

The difference from Embodiment 10 is that, in _{the multi-value generating unit 1115 of the tag device 1110, a value of tu type (t u ≥} 2) is set for each u (u∈{1,...,d}). The multi-value z _u of the value, and store it in the multi-value storage 1116 (equivalent to "the first multi-value storage"), and in the database storage 1131 of the back-end device 1130 (equivalent to the "second multi-value storage") ”) stores a variety of values z _u that take values of the type t _u (t _u ≥ 2) for each u (u∈{1, . . . , d}). In addition, the various values z _u stored in the database memory 1131 are the same as the various values z _u stored in each tag device 1110 .

In addition, as the diverse value generation unit 1115, a counter that counts z _u =1...t for each u(u ∈ {1,...,d}) can be exemplified, and z _u =H(seed, x _u ), x _u ∈ {1, ..., t _u } operation hash operation device, performing z _u = H ^xu (seed), x _u ∈ {1, ..., t _u } operation Hash operation device, etc. Hereinafter, the multivariate value z _u is expressed as z _u =π _u (x _u ), x _u ∈ {1, . . . , t _u }. Moreover, for the same u, it is better to set π _u so that the various values z _u =π _u (x _u ) corresponding to each x _u ∈ {1,...,t _u } are inconsistent.

Furthermore, in Embodiment 11, each x _u is set to x _u =i+ε _u (u∈{1,...,d}). Here, i represents the number _of times of communication of the tag device 1110, and _εu represents a constant (integer of _{0≤εu≤rmax} ) indicating a deviation from i of each x _u . Here, r _max is the maximum value of the calling times from the reading device 120 to the tag device 1110 .

Furthermore, in Embodiment 11, ε _u and t _u are set so that any x _u is always x _u =t _u at all communication timings. For example, set t _u for each u(u∈{1,...,d}) to the same value, and set each ε _u so that ε _u (u∈{1,...,d}) The set of becomes the whole set of natural numbers less than t _u .

In addition, generation and storage of the diverse value z _u are not necessarily performed in the pre-processing, but may be performed during the communication processing of the tag device 1110 or the retrieval processing of the back-end device 1130 .

<Handling of Label Device>

Hereinafter, the processing when causing the reading device 120 to read the tag device 1110 for the ith (i is a natural number) time will be described. In addition, the initial value (i=1) of the count value x _u (u∈{1, ..., d}) is 1+ε _u , and each count value x _u is stored in the memory 115a under the control of the control unit 115 .

First, in the hash calculation unit 1112 (corresponding to the “second calculation unit”), each element e _{u, vu} is extracted from the secret value memory 1111, and any various value z _u is extracted from the various value memory 1116 (in In this example, z _u =π _u (x _u )) (step S231). Then, the hash calculation unit ₁₁₁₂ calculates the tag output information a _{k ,i} =G( e _{1, v1} |z ₁ |...|e _{d, vd} |z _d ) (step S232). In addition, when π _u is set such that various values z _u =π _u (x _u ) corresponding to each x _u ∈ {1,...,t _u } do not match for the same u, the secret value While the elements of the memory 1111 are not being updated, the various values z _u used by the hash calculation unit 1112 to generate the tag output information a _k, i are different for each communication. Also, the order of combining bits in the secret value s _k,i =e _1,v1 |z ₁ |...| _ed,vd |z _d is not particularly limited thereto. The generated label output information a _k,i is sent to the interface 114, and the interface 114 sends the label output information a _k,i (step S233).

Thereafter, in the control unit 136, the calculation of x _u ← x _u + 1 (u∈{1, . . . , d}) is performed on x _u in the memory 136a (step S234). Here, in the eleventh embodiment, ε _u and t _u are set so that any x _u is always x _u =t _u at all communication timings. Therefore, by the operation of x _u ← x _u +1, any x _u must be x _u >t _u . Next, the control unit 136 substitutes 1 into the x _u where x _u >t _u (step S235). In addition, in this embodiment, u corresponding to this x _u is set to u'.

Next, in the hash operation unit 813, a part of elements e _{u', vu'} (elements corresponding to the aforementioned u'∈{1,...,d}) are extracted from the secret value memory 1111, and the extracted Hash value H( _{eu', vu'} ) of elements e _{u', vu'} (step S236). Then, in the hash calculation unit 813, the hash value H( _{eu', vu'} ) is overwritten on the secret value memory 1111 as a new element _{eu', vu+1} (step S237), and the tag device is terminated. 1110 processing.

Through the above processing, each time the interface 114 outputs the label output information a _k,i , in the hash operation unit 813, at least one element e _{u', vu'} (u'∈{1, ..., d}), and calculate the hash value H(eu _{', vu') of the extracted elements e u ', vu'} , and update the secret value memory 1111.

<Handling of reading device>

The same as the first embodiment.

<Handling of back-end devices>

Embodiment 11 differs from Embodiment 10 in that the processing of FIG. S26 is performed instead of the processing of steps S208 to S213 shown in FIG. 23 .

That is, after the process of step S207, the control unit 136 selects combinations of (x ₁ , . . . , x _d )∈S _x as follows, and stores them in the memory 136a (step S241).

(x ₁ ,...,x _d )∈S _x ＝{x ₁ ,...,x _d |x _u ∈[0,t _u ]}

Then, the control unit 136 refers to the combination of (x ₁ , ..., x _d )∈S _x in the memory 136a, and extracts d diverse values z _u =π(x _u )(u∈ {1,...,d}) and sent to the hash operation unit 1133. The hash operation unit 1133 calculates an operation value c obtained by using the hash value G for the bit combination value of the hash value H ^wu (fu _{, 0} ) and the diversity value z _u (step S242). In addition, as the calculated value c, for example, c=G(H ^w1 (f _1,0 )|z ₁ |...|H ^wu (f _u,0 )|z _u ...|H ^wd (f _d,0 )| z _d ), but the order of bit arrangement of each hash value H ^wu (fu _{, 0} ) and diversity value z _u is not limited to this. However, the order must correspond to the bit arrangement order of each element of the hash calculation unit 1112 of the tag device 1110 .

Next, in the comparison unit 134, the tag output information a _k,i is read from the memory 136a, the above-mentioned calculation value c is received from the hash operation unit 1133, and they are compared to determine whether c=a _k,i (step S243 ). In this example, compare the hash values c=G(H ^w1 (f _1,0 )|z ₁ |...|H ^wu (f _u,0 )|z _u ...|H ^wd (f _d,0 )|z _d ) and label output information a _{k, i} .

Here, when it is determined that they do not match, the control unit 136 refers to the memory 136a to determine whether or not all combination patterns (x ₁ , . . . , x _d )εS _x have been selected (step S244). Here, when it is determined that not all combination patterns (x ₁ , ..., x _d )∈S _x have been selected, the control unit 136 selects a new combination (x ₁ , ..., x _d )∈S _x , and store them in the memory 136a, the processing after step S242 is executed. On the other hand, when it is judged by the judgment in step S244 that all combination patterns (x ₁ , ..., x _d )∈S _x have been selected, the process proceeds to step S213 in FIG. 23 . On the other hand, when it is determined in the process of step S243 that c= _ak,i , the process proceeds to step S218 of FIG. 23 .

[efficiency]

The comparison process between the hash value c of the back-end device 1130 and the tag output information a _k,i is performed at most t ₁ +t ₂ +...+t _d-1 +t _d times each time without changing the hash value H ^wu (fu _{, 0} ) combinations. Therefore, even in the case where the allowable number of communications of the tag device 1110 (the maximum number of calls from the reading device 120 to the tag device 1110 ) is increased, the processing in the backend device 1130 does not increase so much.

[Untraceability]

The labeling device 1110 of _Embodiment 11 updates any element e _{u', vu'} (u'∈{1,. . . , d}). Therefore, even if the tag device 1110 is tampered with and the elements e _{u', vu'} in the secret value memory 1111 are leaked to the attacker, due to the unidirectional nature of the hash function, the attacker cannot obtain the elements e _{u', vu} before the update Correlation of _'-t and updated elements e _{u', vu'} . Therefore, an attacker cannot obtain the correlation between the element obtained from the secret value memory 1111 and the output value output from the tag device in the past. Thus, tracking of the tag device 1110 can be prevented.

Furthermore, in Embodiment 11, even if the tag device 1110 is tampered with and various values z _u are leaked, any elements eu _{', vu'} stored in the secret value memory 1111 are overwritten and updated. In this way, it is possible to minimize the influence when the tag device 1110 is tampered with.

In addition, in Embodiment 11, ε _u and t _u are set so that any x _u is always x _u =t _u at all communication timings. In other words, for example, assuming t _i =t ₂ =...=t _d , the counter x _u corresponding to the elements e _{u, vu} is shifted one by one (x _u =i+u/d).

However, instead of making all t _u (u∈{1,...,d}) equal, the counter x _u corresponding to each element e _{u, vu} deviates every time the largest t _u is divided into d equal intervals also can. In this case, the property of complete forward security may not be satisfied, but at least the influence of the intervention can be suppressed.

[Example 12]

Example 12 is a modified example of Example 11. Similar to the eleventh embodiment, in the twelfth embodiment, the communication timing at which the elements e _{u and vu} are updated is also shifted. However, in Embodiment 12, when the labeling device outputs the label output information a _k,i every time ∑ _u=1 ^d t _u times, it extracts any element e _{u', vu'} , and calculates the extracted element e _u The hash value H(e _{u', vu'} ) of _{', vu'} .

Specifically, the tag device of Embodiment 12 accumulates a counter x _u ∈ {1, ..., t _u } corresponding to any one of d elements e _{u, vu} for each access from the outside (for example, Add 1 each time in the order of e _{1, v1} ... e _{d, vd} ). Here, since the counter x _u corresponds to the diverse value z _u constituting the tag output information a _k,i =G(e _{1, v1} | z ₁ ... | e _{d, vd} | z _d ), the tag device does not update each elements e _{u, vu} , and label output information a _{k, i} of different values can be output ∑ _u=1 ^d t _u times. In this embodiment, any element e _{u, vu} is updated when the tag output information a _k,i is output every time Σ _u=1 ^d t _u times, thereby maintaining the diversity of the output value of the tag device, and at the same time Minimizes the amount of updating calculations for tag devices.

Hereinafter, differences from Embodiments 1 and 11 will be described, and descriptions of matters common to Embodiments 1 and 11 will be omitted.

Fig. 27 is a flowchart for explaining the processing of the label device according to the twelfth embodiment. In addition, the overall functional structure is the same as that of Embodiment 11 (FIG. 24).

Hereinafter, the processing method of this embodiment will be described using these figures.

<preprocessing>

In Embodiment 11, set x _u =i+ε _u (u∈{1,...,d}), set ε _u and t _u at all communication time points, so that any x _u must be x _u =t _u , but in Example 12, such a limitation is not particularly imposed.

<Handling of Label Device>

Hereinafter, the processing when the reading device 20 is made to read the tag device 310 for the ith time will be described. In addition, the initial value (i=1) of the count value x _u (u∈{1, . . . , d}) is 1, and the initial values of u′ and u′ are also 1. In addition, u' corresponds to the updated element e _{u', vu'} , and u" corresponds to the count value x _u" of the accumulated element e _{u', vu'} . Furthermore, each parameter is stored in the memory 136 a under the control of the control unit 136 .

First, in the hash operation unit 1112, each element e _{u, vu} is extracted from the secret value memory 1111, and any various value z _u is extracted from the various value memory 1116 (in this example, z _u = π _u ( x _u )) (step S241). Then, the hash operation unit 1112 calculates the tag output information a _{k ,i =} G(e _1,v1 |z ₁ |...| _{ed , vd} |z _d ) (step S242).

The generated label output information a _k,i is sent to the interface 114, and the interface 114 sends the label output information a _k,i (step S243).

Afterwards, in the control unit 136, the calculation of x _{u ”} ← x _u” + 1 (u” ∈ {1, . _u" >t _u" (t _u" is the maximum value of x _u" ) (step S245). Here, when it is judged not to be x _u" >t _u", the processing of the labeling device 1110 ends.

On the other hand, when it is judged that x _u" >t _u" , the control unit 136 substitutes u"+1 into u" in the memory 136a (step S246), and judges whether u">d (step S247) Here, if u">d is not the case, the processing of the tag device 1110 is terminated, and in the case of u">d, the hash operation unit 813 extracts the elements e _{u', vu} from the secret value memory 1111 _' (corresponding to the elements of u'∈{1,...,d} above), and calculate the hash value H(eu _{', vu'} ) of the extracted elements e _{u', vu'} (step S248). Then, in the hash operation unit 813, the hash value H( _{eu', vu'} ) is overwritten and stored in the secret value memory 1111 as a new element _{eu', vu'+1} (step S249).

Afterwards, for example, in the hash operation unit 813, the calculation (number of updates) of vu'←vu'+1 is performed (step S250), and it is judged whether vu' exceeds the maximum value of the update times of elements e _{u', vu'} (max) (step S251). Here, if it is judged not to be vu'>max, the processing of the labeling device 1110 ends, and if vu'>max, the control unit 136 performs u'←u'+1 (update target element change) and vu'←0 (resetting the update count of the element to be updated) (step S252), and these results are stored in the memory 136a, and the processing in the tag device 1110 ends.

Through the above processing, every time the interface 114 outputs the label output information a _k,i for Σ _u=1 ^d t _u times, in the hash calculation unit 813, any element e _{u′ is extracted from the secret value memory 1111, vu'} , calculate the hash value H(e _{u ', vu' ) of the extracted elements e u', vu'} , and update the secret value memory 11.

<Handling of reading device>

Same as in Example 8.

<Handling of back-end devices>

Same as in Example 11.

<Features of Embodiment 12>

[efficiency]

In the twelfth embodiment, since any element e _{u', vu'} is updated every time the tag device 1110 performs Σ _{u = 1} ^d t _u communications, it is possible to reduce the computational load of update processing of the tag device 1110. In other words, in this embodiment, Σ _u=1 ^d t _u diverse values are replaced each time of communication, and the label output information a _k,i (e _1,v1 |z ₁ |...|e _d,vd |z _d ). Therefore, in Σ _{u = 1} ^d t _u times of communication, the diversity of the output value of the tag device can be ensured without updating the elements eu _{, vu} . Furthermore, by updating any element e _{u', vu'} every time Σ _{u = 1} ^d t _u communication, it is possible to ensure the diversity of output values in the next Σ _{u = 1} ^d t _u communication. In addition, the updating of the elements _{eu', vu'} may be performed once every Σu ₌₁ ^d _tu communication, so the amount of updating computation of the tag device 1110 can be kept to a minimum.

[Untraceability]

The tag device 1110 of this embodiment updates the secret value memory 1111 every time the interface 1114 outputs tag output information a _k,i times Σ _u=1 ^d t _u times. Therefore, even if the tag device 1110 is tampered with, and the elements e _{u' and vu'} in the secret value memory 1111 are leaked to the attacker, the number of past output values of the tag device 1110 that the attacker can know is less than Σ _u=1 ^d t _u . Thereby, the amount of update calculation processing of the tag device 1110 can be reduced, and tracking of the tag device 1110 can be suppressed.

[Example 13]

Embodiment 13 is a modified example of Embodiments 1 to 4 and 6 to 12, and is characterized in that two types of hash function G(x) and hash function H(x) are used.

Hereinafter, only the hash functions H(x), G(x) will be described.

<No1>

The hash function G(x) in this example is hash(1|x) when r is set as a natural number and hash is set as a hash function of {0, 1} ^* → {0, 1} ^r , The hash function H(x) is hash(0|x). In addition, α|β indicates a bit combination of α and β. Furthermore, the hash function G(x) may be hash(0|x), and the hash function H(x) may be hash(1|x).

<No2>

The hash function H(x) (first function F1) in this example is a hash function where r and s are set as natural numbers, and hash is set to {0, 1} ^* → {0, 1} ^r , set to hash(p|x) in the case of p ∈ {0, 1} ^s . Furthermore, the hash function G(x) (second function F2) is hash(q|x) when p∈{0,1} ^s and p≠q.

<No3>

The hash function H(x) (the first function F1) in this example is set to p∈{0, 1} ^s , and the padding of p to x (the padding of p for x) is set to pad( hash(pad(x, p)) in the case of x, p). Furthermore, the hash function G(x) (second function F2) assumes p∈{0, 1} ^s and p≠q, and sets the padding of p to x (padding of p to x) to hash(pad(x,q)) in the case of pad(x,p). In addition, p or q is not particularly limited to the filling position (position of the bit string) of x. For example, p or q may be combined before or after x, or p or q may be inserted in the middle of the bit sequence of x.

<No4>

The hash function H(x) (first function F1) of this example is hash(x) in the case where hash is set to {0, 1} ^* →{0, 1} ^r hash function, hash The function G(x) (second function F2 ) is hash(rx) in which rx is bit-reversed of x.

<Effect of Example 13>

In this embodiment, only one type of hash function is used, and two types of hash operations G(x), H(x) can be realized without losing its characteristics (unidirectionality, random value output). Thereby, the circuit scale constituting the hash function can be reduced. As a result, the scale of the circuit in the label device can be reduced and the cost of the label device can be realized.

[Second Embodiment]

<structure>

Next, a second embodiment of the present invention will be described.

In this form, the update device installed outside the tag device updates the privileged ID information stored in the tag device with new privileged ID information whose correlation is difficult to ascertain at predetermined timing.

<structure>

FIG. 28 is a block diagram illustrating a schematic configuration of this embodiment.

As shown in FIG. 28 , the update system 1500 of this embodiment has a tag device 1510 and a security server device 1560 installed outside it.

The tag device 1510 has: a secret value storage, which stores hidden ID information that hides the inherent ID information of each tag device; a read-write unit 1512, electrically connected to the secret value storage; and a first output unit 1513 and a second input unit 1514, connected to The read/write unit 1512 is electrically connected.

Furthermore, the security server device 1560 has: a first input unit 1561 ; an update unit 1562 electrically connected to the first input unit 1561 ; and a second output unit 1563 connected to the update unit 1562 .

<Update processing of anonymity ID>

The update of the anonymity ID is performed as follows.

First, at a predetermined timing, the tag device 1510 reads out the hidden ID information sid _h stored in the secret value memory 1511 in the read/write unit 1512, and in the first output unit 1513, sends a message to the external ID of each tag device. The security server device 1560 outputs the hidden ID information sid _h .

The security server device 1560 accepts the input of the privileged ID information sid _h through the first input unit 1561 . Then, in the update unit 1562, new privileged ID information sid _{h ′} whose correlation with the privileged ID information sid h is difficult to grasp is generated, and in the second output unit 1563, the new privileged ID information sid _h is output to the tag device 1510. '.

The tag device 1510 receives input of new privileged ID information sid _h ' in the second input unit 1514, and stores the new privileged ID information sid _h ' in the secret value memory 1511 in the read/write unit 1512.

[Example 14]

FIG. 29 is a conceptual diagram illustrating the overall configuration of an update system 2000 in Embodiment 14.

As illustrated in this figure, the update system 2000 has: a tag device 2010 such as a wireless tag device attached to a commodity; a client device 2020; a back-end device 2050 that manages distribution information associated with a plain text ID; The security server device 2060 (the server device that performs the re-blind processing of the privileged ID transmitted through the network, corresponds to the "update device") such as the restoration of the privileged ID or the re-cloaking process of the privileged ID. Furthermore, the client device 2020, the backend device 2050, and the security server device 2060 are communicably connected via a network 2070 such as the Internet. In addition, the client device 2020 includes the function as the reading device described in the first embodiment. Furthermore, in the first embodiment, the effects realized by the tag device, the reader device, and the backend device are realized by the tag device 2010 , the client device 2020 , the backend device 2050 , and the security server device 2060 . Moreover, for the sake of simplicity of description, the tag device 2010, the client device 2020, the back-end device 2050, and the security server device 2060 are illustrated in the figure, but generally there may be a plurality of tag devices, and the client device, the back-end device and the There are multiple security server devices.

The client device 2020 of this example first reads the privileged ID from the tag device 2010 and sends it to the security server device 2060 . The secure server device 2060 recovers the ID from the shielded ID and sends the ID back to the client device 2020. The client device 2020 having received the ID accesses the backend device 2050 to request writing of information such as the ID, reading date, reading position, temperature, etc., or acquisition of information related to the ID. Furthermore, it is assumed that a proxy model is utilized: the client device 2020 sends the anonymized ID to the security server device 2060 , and the security server device 2060 directly accesses the backend device 2050 . Furthermore, the characteristic part of the present embodiment is that the security server device 2060 and other devices installed outside the tag device 2010 re-blind the anonymized ID in the tag device 2010 (update the anonymized ID to another anonymized ID).

FIG. 30 is a block diagram illustrating the functional structure of the update system 1 in this embodiment.

<label device>

The tag device 2010 of this example includes: a secret value memory 2011, a read-write unit 2012 (equivalent to a “first read-write unit”), an interface 2013 (equivalent to a “first output unit” and a “second input unit”), a memory 2014a And the control unit 2014.

Here, the secret value storage 2011 and the storage 2014a are, for example, EEPROM (Electronically Erasable and Programmable Read Only Memory), FeRAM (Ferroelectric Random Access Memory), flash memory, NV (Nonvolatile) RAM and other readable and writable RAM (Random Access Memory). Furthermore, the read/write unit 2012 is hardware for reading and writing data at predetermined addresses in the secret value memory 2011 under the control of the control unit 2014 . Furthermore, the control unit 2014 is, for example, an integrated circuit configured to control the overall processing of the label device 2010 .

The interface 2013 is hardware for inputting and outputting data to the client device 2020 via wireless or wired. Specifically, the interface 2013 has, for example, an encoding/decoding circuit for encoding/decoding by NRZ code, Manchester encoding, Miller code, or unipolar RZ encoding, etc.; a modulation/demodulation circuit for performing encoding/decoding by ASK (Amplitude Shift Keying) or PSK (Phase Shift Keying) or FSK (Frequency Shift Keying) for modulation and demodulation; and antennas such as dipole antennas, microstrip antennas, loop antennas, or cored coils, using frequencies in the long wave band or ISM band (Industry Science Medical band) Send and receive signals. In addition, the communication method utilizes, for example, an electromagnetic induction method or a radio wave method.

Furthermore, the secret value memory 2011 is electrically connected to the read/write unit 2012 , and the read/write unit 2012 is electrically connected to the interface 2013 . Furthermore, although omitted in this figure, the control unit 2014 is electrically connected to each part of the label device 2010 .

<client device>

The client device 2020 of this example has an interface 2022 , a communication unit 2021 , a memory 2024 a , and a control unit 2024 .

The logistics information memory 121 is, for example, a magnetic recording device such as a hard disk device and a floppy disk, an optical disk device such as DVD-RAM (Random Access Memory), CD-R (Recordable)/RW (ReWritable), or an opto-magnetic recording device such as MO (Magneto-Optical disc). Devices, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), semiconductor memory such as flash memory, etc. The interface 2022 is, for example, the same hardware as the interface 2013 . The communication unit 2021 is, for example, a LAN card, a modem, a terminal adapter, etc., and the control unit 2023 is, for example, a CPU (Central Processing Unit) of a CISC (Complex Instruction Set Computer) method or a RISC (Reduced Instruction Set Computer) method having a memory 2023a.

Furthermore, it is electrically connected to the interface 22 and the communication unit 2021 , and although omitted in the figure, the control unit 2024 is electrically connected to various parts of the client device 2020 .

<update device>

The security server device 2060 has: a communication unit 2062 (corresponding to a "first input unit" and a "second output unit"), a random number generation unit 2063, a reading and writing unit 2064 (corresponding to a "second reading and writing unit"), a secret ID The memory 2061, the memory 2065a, and the control unit 2065. In addition, the random number generator 2063, the read/write unit 2964, and the privileged ID memory 2061 constitute an "update unit". Specifically, the security server 2060 is configured by causing a well-known Neumann computer to execute a predetermined program, and the computer is connected to external devices such as a CPU, RAM, ROM (Read Only Memory), magnetic recording device, or optical disk device through a bus. Storage device, LAN card or modem or terminal adapter, etc. Further, the CPU reads out the program stored in the RAM and executes processing according to it, thereby realizing each processing function shown below.

<processing>

Fig. 31 is a flowchart for explaining the processing procedure of the present invention. Hereinafter, the functional configuration and processing of this embodiment will be described using FIGS. 29 to 31 . In addition, the tag device 2010, the client device 2020, and the security server device 2060 execute respective processes under the control of the control units 2014, 2023, and 2065, respectively. Furthermore, the data to be processed is stored in the memory 2014a, 2023a, or 2065a one by one, and is called when processing such as calculation is performed, and its description will be omitted below.

<preprocessing>

The hidden ID information in this example is a random value r _h corresponding to the tag ID information id _h . The secret value memory 2011 of the tag device 2010 stores a random value r _h corresponding to the tag ID information id _h inherent to the tag device 2010 as the hidden ID information sid _h . Moreover, the hidden ID memory 2061 of the security server device 2060 stores tag ID information id ₁ , ..., id _m corresponding to each tag device 2010, and random values r ₁ , ... corresponding to these tag ID information. , the hidden ID information of _rm . In addition, h is a natural number greater than or equal to 1 and less than or equal to m, and serves as a number corresponding to each tag device 2010 . Also, m is the total number of tag devices.

<Hidden ID information update process>

First, mutual authentication is performed between the client device 2020 and the secure server device 2060 using any authentication technique. Furthermore, the communication between the client device 2020 and the security server device 2060 is encrypted by any encryption technique.

The update process of the hidden ID information sid _h is triggered by the following situations, for example, when passing through a place that must be passed when going out, such as a porch, or the number of times of use of the hidden ID information stored in the tag device 2010 (the count value reaches a predetermined value), etc. . With this trigger, first, the client device 2020 transmits a read instruction to the tag device 2010 through the interface 2022 (step S301 ). The reading instruction is received by the interface 2013 of the tag device 2010, and as a trigger, the read/write unit 2012 extracts the concealed ID information sid _h from the secret value memory 2011 (step S302). The extracted privileged ID information sid _h is sent (output) from the interface 2013 to the client device 2020 (step S303). The privileged ID information sid _h is received by the interface 2022 of the client device 2020, and is transmitted from the communication unit 2021 to the security server device 2060 through the network 2070 simultaneously with the privileged ID information update request (encrypted request) (step S304).

Information such as the privileged ID information (sid _h ) is received (input accepted) by the communication unit 2062 of the security server device 2060 (step S305 ), and is sent to the read/write unit 2064 . Then, using this as a trigger, the random number r _h ' as a random value is generated in the random number generator 2063 (corresponding to the "random value generator") (step S306).

In addition, this random number r _h ′ is generated so as not to be the same as the value of the privileged ID information in the privileged ID memory 2061 . Then, this generation is performed using, for example, a pseudorandom number generation algorithm based on a calculation amount theory constituted by a unidirectional hash function such as SHA-1, and the generated random number r _h ′ is sent to the read/write unit 2064. The read-write unit 2064 retrieves (selects) the tag ID information id _h corresponding to the hidden ID information sid _h from the hidden ID memory 2061, and uses the random number r _h ' (equivalent to a "random value") as the new hidden ID information sid _h ' corresponds to the tag ID information id _h , and is stored in the hidden ID memory 2061 (step S307). Then, the reading/writing unit 2064 transmits the new privileged ID information sid _h '=r _h ' to the communication unit 2062, and the communication unit 2062 transmits the new privileged ID information sid _h to the client device 2020 via the network 2070 (equivalent to " Output ") to the label device (step S308).

The transmitted new privileged ID information sid _h ' is received by the communication unit 2021 of the client device 2020, and is transmitted to the tag device 2010 through the interface 2022 (step S309). The tag device 2010 receives this new random number r _h ' through the interface 2013 (accepts input) and sends it to the read/write unit 2012. The read/write unit 2012 sends the new hidden ID information sid _h ' to the secret value memory 2011, and stores it therein (step S310). Afterwards, the tag device 2010 sends the new concealed ID information sid _h ' to the backend device 2050 through the reading device in response to a reading request from the reading device (not shown). The backend device 2050 sends the received concealed ID information sid _h ′ to the database storage 1131 , and the database storage 1131 receives the information by the communication unit 2062 and sends it to the read-write unit 2064 . The read-write unit 2064 retrieves a random value consistent with the hidden ID information sid _h ' from the hidden ID memory 2061, and reads out the tag ID information id _h corresponding to the consistent random value r _h and sends it to the communication unit 2062, and the communication unit 2062 sends it to backend device 2050.

<Features of Embodiment 14>

In this embodiment, the privileged ID information stored in the tag device 2010 can be updated at any timing. Therefore, it is possible to avoid privacy violation by tracking the tag device 2010 based on the commonality of concealed ID information remaining in the communication history and the like. Moreover, since the random value is used as the privileged ID information, an attacker cannot know the relevance of the privileged ID information before and after the update. Therefore, tracking prevention of the tag device 2010 can be stably realized. Furthermore, since the security server device 2060 outside the tag device 2010 performs complicated re-cloaking processing, it is not necessary to provide circuits and the like necessary for re-cloaking processing in the tag device 2010 itself. As a result, the cost of the label device 2010 itself can be kept low.

[Example 15]

This embodiment is a modified example of the fourteenth embodiment, and differs from the fourteenth embodiment in that the encrypted text by the common key encryption method is used as the confidentiality ID information. Hereinafter, the difference from Example 14 will be mainly explained.

FIG. 32 is a block diagram illustrating the functional configuration of the update system 2100 in this embodiment, and FIG. 33 is a flowchart for explaining the processing procedure. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In addition, in FIG. 32 , the same reference numerals as in FIG. 30 are assigned to the configurations common to those of the fourteenth embodiment. Furthermore, the security server device 2160 executes each process under the control of the control unit 2065 . Furthermore, the key memory 2161, the read/write unit 2064, the ID extraction unit 2166, the encryption unit 2167, and the random number generation unit 2063 constitute an "update unit".

<preprocessing>

The privileged ID information in this form is information having the first encrypted text encrypted by a common key encryption method such as AES and the key ID information corresponding to the common key encrypted using this encryption. In this example, the hidden ID information of the tag device 2110 is set to sid _h =(ek _j (id _h |r), kid _j ). In addition, h is a natural number greater than or equal to 1 and less than or equal to n, and is a number corresponding to each key. Here, m represents the total number of tag devices, and n represents the total number of keys. Moreover, k _j represents the jth common key, kid _j represents the key ID information corresponding to the common key k _j , r represents a random number, and ek(α) represents the use of the common key k through the common key encryption method The cipher text encrypted with α, α|β represents the bit combination of α and β.

The hidden ID information sid _h =(ek _j (id _h |r), kid _j ) corresponding to the tag ID information id _h is stored in the secret value memory 2111 of the tag device 2110 in this example. Moreover, the key memory 2161 of the security server device 2160 (equivalent to "update device") stores each key ID information (kid ₁ , ..., kid _n ) and common keys (k ₁ , ..., k _n ). Furthermore, information on the size (bit length) and stuffing position of the random number r in sid _h =(ek _j (id _h |r), kid _j ) is stored in the memory 2065a.

In addition, in this example, the total number m of tag devices is sufficiently larger than the total number n of keys (m>>n), and the same key ID information is assigned to unrelated tag devices. That is, for example, instead of assigning the same key ID information to tag devices attached to products of the same type, the same key ID information is assigned to tag devices attached to unrelated products. Thereby, it is possible to prevent the type of product or the individual product from being specified from the key ID information.

<Anonymous ID update processing>

As in the fourteenth embodiment, first, the client device 2020 transmits a reading instruction to the tag device 2110 (step S320). The tag device 2110 extracts the privileged ID information (sid _h =(ek _j (id _h |r), kid _j )) from the secret value memory 2111 (step S321), and transmits it to the client device 2020 (step S322). The client device 320 having received this information transmits the privileged ID information sid _h and an update request to the security server device 2160 at the same time (step S323).

Information such as the hidden ID information sid _h is received in the communication unit 2062 of the security server device 2160 (step S324), and the first encrypted text ek _j (id _h | r) constituting the hidden ID information sid _h is sent to the ID extraction In the unit 2266, the key ID information kid _j is sent to the read/write unit 2064. Furthermore, kid _j is also recorded in the memory 2065a.

The read/write unit 2064 that has received the key ID information (kid _j ) extracts the common key k _j corresponding to the key ID information kid _j from the key memory 2161, and sends it to the ID extraction unit 2166 (step S326). The ID extraction unit 2166 having received the key decodes the first encrypted text (ek _j (id _h |r)) using the common key k _j , and extracts the tag ID information id _h . That is, the ID extracting section 2166 calculates (id _h | r) by id _h = dk _j (ek _j (id _h | r)), using information about the size of the random number r stored in the memory 2065 a and its filling position to extract id _h (step S326). Here, dk(α) denotes decoding of encrypted text α by common key k. In addition, the calculated tag ID information id _h is sent to the encryption unit 2167 at the same time as the common key k _j (step S327). The encryption unit 2167 generates (calculates) the second encrypted text using the transmitted common key k _j , tag ID information id _h , random number r′, and information on the size of the random number and its padding position stored in the memory 2065 a (ek _j (id _h |r')) (the second encrypted text whose correlation with the first encrypted text is difficult to ascertain) is sent to the communication unit 2062 (step S328).

The communication unit 2062 uses the transmitted encrypted text (ek _j (id _h |r')) and the key ID information kid _j in the memory 2065a as new concealed ID information (sid _h '=(ek _j (id _h |r') ), kid _j )) send (output) (step S329).

The transmitted new privileged ID information sid _h ' is received by the client device 2020 via the network 2070 as in the fourteenth embodiment, and is transmitted to the tag device 2110 (step S330). The tag device 2110 receives the new concealed ID information sid _h ' in the interface 2013, and is stored in the secret value memory 2111 by the read-write unit 2012 (step S331), and the new hidden ID information sid h ' is sent to the read request from the reading device afterwards. The hidden ID information sid _h ' of is sent to the backend device 2050 through the reading device. The backend device 2050 sends the received hidden ID information sid _h ' to the security server device 2160, and the security server device 2160 receives it through the communication unit 2062. Thereafter, the security server device 2160 decodes the tag ID information through the same procedure as steps S324 and S325 , and transmits it to the backend device 2050 through the communication unit 2062 and the network 2070 .

<Features of Embodiment 15>

In this embodiment, since the information including the encrypted text by the common key encryption method is used as the privileged ID information, an attacker who does not know the common key cannot know the relationship between the privileged ID information before and after the update. Therefore, tracking prevention of the tag device 2010 can be stably realized.

In addition, in this embodiment, the encrypted text of the random number and the bitwise addition (exclusive logic sum) of the ID constitutes the hidden ID information, but as long as there is the property of probabilistic encryption (that is, the same ID is encrypted with the same key, The properties of different encrypted texts can be output), and the hidden ID information can also be formed by other methods. This point is also the same as in Example 16.

[Example 16]

The sixteenth embodiment is a modified example of the fourteenth embodiment, and differs from the fourteenth embodiment in that the encrypted text by the public key encryption method is used as the confidential ID information. Hereinafter, the difference from Example 14 will be mainly explained.

FIG. 34 is a block diagram illustrating the functional configuration of the update system 2200 in this embodiment, and FIG. 35 is a flowchart for explaining the processing procedure. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In addition, in FIG. 34, the same code|symbol as Example 14 is attached|subjected to the structure common to Example 14. As shown in FIG. Furthermore, the read/write unit 2064, the key memory 2261, the ID extraction unit 2266, the encryption unit 2267, and the random number generation unit 2063 constitute an "update unit".

<preprocessing>

The privileged ID information in this embodiment is information having a first encrypted text encrypted by a public key encryption method such as RSA and key ID information corresponding to the encrypted public key. In this example, the hidden ID information of the tag device 2210 is set as sid _h =(epk _j (id _h |r), kid _j ). In addition, pk _j represents the jth public key, kid _j represents the key ID information corresponding to the public key k _j , and epk(α) represents the encryption of α using the public key pk through public key encryption. encrypted text.

The privileged ID information (sid _h =(epk _j (id _h |r), kid _j )) is stored in the secret value memory 2211 of the tag device 2110 of this example. Moreover, in the key memory 2261 of the security server device 2260 (corresponding to the "update device"), each key ID information (kid ₁ , ..., kid _n ) and the common key (sk ₁ , ..., sk _n ) and public keys (pk ₁ , ..., pk _n ) (key pair (sk _j , pk _j )). Furthermore, information on the size (bit length) and stuffing position (bit position) of the random number r in sid _h =(epk _j (id _h |r), kid _j ) is stored in the memory 2065a.

In addition, as in the fifteenth embodiment, in this example, the same privileged ID information is assigned to unrelated tag devices. Thereby, it is possible to prevent the item type and individual item from being specified from the key ID information.

<Anonymous ID update processing>

As in the fourteenth embodiment, first, the client device 2020 transmits a reading instruction to the tag device 2210 (step S340). The tag device 2210 extracts the privileged ID information (sid _h =(epk _j (id _h |r), kid _j )) from the secret value memory 2211 (step S341), and transmits it to the client device 2020 (step S342). The client device 2020 having received this information transmits the privileged ID information sid _h and an update request to the security server device 2260 at the same time (step S343).

Information such as the hidden ID information sid _h is received in the communication unit 2062 of the security server device 2260 (step S344), and the first encrypted text epk _j (id _h | r) constituting the hidden ID information sid _h is sent to the ID extraction part 266, the key ID information kid _j is sent to the read/write part 2064. Furthermore, key ID information kid _j is also recorded in the memory 2065a.

The read-write unit 2064 that has received the key ID information kid _j extracts the key sk _j and the public key epk _j (key pair) corresponding to the key ID information kid _j from the key memory 2261, and converts the key sk _j is sent to the ID extraction unit 2266, and the public key epk _j is sent to the encryption unit 2267 (step S345). The ID extraction unit 2266 having received the key sk _j decodes the first encrypted text (epk _j (id _h |r)) using the key sk _j , and extracts the tag ID information id _h . That is, (id _h | r) is calculated by id _h = dsk _j (epk _j (id _h | r)), and id _h is calculated using information on the size of the random number r in the memory 2065a and its filling position (step S346). Here, dsk(α) denotes decoding of encrypted text α by key sk. In addition, the calculated tag ID information id _h is sent to the encryption unit 2267 . Then, the random number generation unit 2063 generates a random number r', and sends it to the encryption unit 2267 (step S347). The encryption unit 2267 generates ( _calculates ) an encrypted text (epk _j (id _{h r} ' )) (the second encrypted text whose relationship with the first encrypted text is difficult to grasp) is sent to the communication unit 2062 (step S348).

The communication unit 2062 uses the transmitted second encrypted text (epk _j (id _h |r')) and the key ID information kid _j in the memory 2065a as new concealed ID information sid _h '=(ek _j (id _h |r '), kid _j ) are sent (output) (step S349).

The transmitted new privileged ID information sid _h ' is received by the client device 2020 via the network 2070 as in the fourteenth embodiment, and is transmitted to the tag device 2210 (step S350). The tag device 2210 stores the new hidden ID information sid _h ' in the secret value memory 2211 in the read/write unit 2012 (step S351). Then, for subsequent reading requests from the reading device, the new concealed ID information sid _h ' is sent to the back-end device 2050 through the reading device. The backend device 2050 sends the received concealed ID information sid _h ' to the security server device 2260, and the security server device 2260 receives it through the communication unit 2062. Thereafter, the security server device 2260 decodes the tag ID information through the same procedure as steps S345 and 346 , and transmits it to the backend device 2050 through the communication unit 2062 and the network 2070 .

<Features of Embodiment 16>

In this embodiment, since the information including the encrypted text by the public key encryption method is used as the privileged ID information, an attacker who does not know the key cannot know the relationship between the privileged ID information before and after the update. Therefore, the tracking prevention of the tag device 2210 can be stably realized.

<Example 17>

This embodiment is a modified example of the fourteenth embodiment, using encryption with the property of re-encryption (encryption property in which other encrypted text can be generated using only the encrypted data and the public key. Decryption is performed using the same key.) The algorithm updates the hidden ID information, which is different from the fourteenth embodiment. Hereinafter, the difference from Example 14 will be mainly explained.

FIG. 36 is a block diagram illustrating the functional configuration of the update system 2300 in this embodiment, and FIG. 37 is a flowchart for explaining its processing procedure. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In addition, in FIG. 36, the same code|symbol as Example 14 is attached|subjected to the structure common to Example 14. As shown in FIG. Furthermore, the security server device 2360 executes each process under the control of the control unit 2065 . Furthermore, the key memory 2361, the read/write unit 2064, the random number generator 2063, the remainder multiplication unit 2366, and the remainder power calculation unit 2367 constitute an "update unit".

<preprocessing>

The privileged ID information in this form is information having the first encrypted text passed through the encryption algorithm (public key encryption method) having the property of re-encryption and the key ID information corresponding to the encrypted public key. In this example, use ElGamal encryption (for example, refer to Okamoto Ryuaki, Yamamoto Hiroshi, "Modern Cipher", 1998, p118-119.) The hidden ID information of the tag device 2310 is set as sid _h =(g ^r mod p, id _h pk _j ^r mod p, kid _j ). In addition, g represents a public generator, p represents a sufficiently large prime number, r represents an arbitrary integer greater than or equal to 0 and less than p-1, pk _j = g ^xj mod p represents the jth public key, and sk _j represents the jth public key A key, (g ^r mod p, id _h pk _j ^r mod p, kid _j ) represents the encrypted text. In addition, the superscript "skj" of pk _j =g ^skj mod p means "pk _j ". In addition, in the following description and drawings, "mod p" is omitted and described.

The confidentiality ID information sid _h =(g ^r , id _h ·pk _j ^r , kid _j ) is stored in the secret value memory 2311 of the tag device 2310 of this example. Moreover, each key ID information (kid ₁ , ..., kid _n ) and public keys (pk ₁ , ..., pk _n ). Furthermore, the generator g is stored in the memory 2065a.

In addition, in this example, the same key ID information is assigned to unrelated tag devices. Thereby, it is possible to prevent the type of product or the individual product from being specified from the key ID information.

<Anonymous ID update processing>

As in the fourteenth embodiment, first, the client device 2020 transmits a read instruction to the tag device 2310 (step S360). The tag device 2310 extracts privileged ID information sid _h =(g ^r , id _h ·pk _j ^r , kid _j ) from the secret value memory 2311 (step S361), and transmits it to the client device 2020 (step S362). The client device 2020 having received this information transmits the privileged ID information sid _h and an update request to the security server device 2260 at the same time (step S363).

Information such as the privileged ID information sid _h is received by the communication unit 2062 of the security server device 2360 (step S364), and (g ^r , id _h ·pk _j ^r ) constituting the privileged ID information sid _h is sent to the remainder multiplication operation. The kid _j is sent to the read/write unit 2064 by the unit 2366 (constituting the “encryption unit”). Furthermore, kid _j is also recorded in the memory 2065a.

The read/write unit 2064 that has received the key ID information kid _j extracts the public key pk _j corresponding to the key ID information kid _j from the key memory 2361, and sends it to the remainder exponentiation unit 2367 (constituting the “encryption unit”). ") (step S365). Using this as a trigger, the random number generation unit 2063 generates a random number r′ greater than or equal to 0 and less than p−1, and sends it to the remainder exponentiation unit 2367 (step S366 ). The remainder exponentiation unit 2367 uses the generator g in the memory 2065a, the received public key pk _j and the random number r' to perform (g ^r ', pk _j ^r ') calculation, and sends the result to the remainder multiplication unit 2366 (step S367). The remainder multiplication unit 2366 uses the received (g ^r ', pk _j ^r ') and (g ^r , id _h , pk _j ^r ) to calculate (g ^r+r ', id _h , pk _j ^r+r '), The calculation result is sent to the communication unit 2062 as a new encrypted text (second encrypted text) (step S368).

The communication unit 2062 transmits the encrypted text (g ^r+r ', id _h pk _j ^r+r ') (the second encrypted text whose correlation with the first encrypted text is difficult to grasp) and the key ID stored in the memory 2065a. The information kid _j is sent (output) as new privileged ID information (sid _h '=(ek _j (id _h |r'), kid _j )) (step S369).

The transmitted new privileged ID information sid _h ' is received by the client device 2020 via the network 2070 as in the fourteenth embodiment, and is transmitted to the tag device 2310 (step S370). Then, the tag device 2310 stores the new privileged ID information sid _h ' in the secret value memory 2311 in the read/write unit 2012 (step S371). Then, the tag device 2310 responds to the read request with the new privileged ID information (sid _h ').

<Features of Embodiment 17>

In this embodiment, since the privileged ID information is updated using an encryption algorithm having a re-encryption property, the privileged ID information can be updated without decoding the plain text ID. Therefore, the ID will not be intercepted during the update process of the concealed ID information, and the tracking prevention of the tag device 2310 can be stably realized.

In addition, in this embodiment, the public key (pk ₁ , . . . , pk _n ) is stored in the key memory 2361 of the security server device 2360, but the security server device 2360 does not hold the public key (pk ₁ , .. ., pk _n ) and public keys (pk ₁ , . . . , pk _n ) may be acquired from a predetermined public key server.

Furthermore, although ElGamal encryption is used in this embodiment, other algorithms such as high-order remainder encryption may be used as long as the encryption algorithm has the property of re-encryption.

Furthermore, as a modification of Embodiment 16 and Embodiment 17, the tag ID information is encrypted with a common key, and the encrypted text of the common key and the tag ID information is encrypted using the public key of the above-mentioned public key encryption method. Information can also be used as anonymized ID information (hybrid encryption). In this case, the security server device decodes the privileged ID information with the key corresponding to the public key to obtain the common key, and decodes the encrypted text of the tag ID information using the common key to obtain the tag ID information. Afterwards, the security server device generates other encrypted text from the tag ID information by common key encryption, and further encrypts the common key and the encrypted text by public encryption. Then, the new privileged ID information is stored in the secret value memory of the tag device in the same manner as in the sixteenth embodiment.

[Example 18]

In the eighteenth embodiment, the security server device is changed when the privacy ID information is updated. Hereinafter, the difference from Example 14 will be mainly explained.

FIG. 38 is a conceptual diagram illustrating an overall configuration of an update system 2400 of the present embodiment. In addition, in FIG. 38, the same code|symbol as Example 14 is attached|subjected to the structure common to Example 14. As shown in FIG.

As illustrated in this figure, the update system 2400 includes a tag device 2410, a client device 2020 (corresponding to an "update request device"), a plurality of security server devices 2460-1~v (corresponding to an "update device"), and subsequent The end device 2050 can be communicatively connected via the network 2070 .

FIG. 39 is a block diagram illustrating the functional configuration of the update system 2400 in this embodiment, and FIG. 40 is a flowchart for explaining the processing. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In addition, in FIG. 39, the same code|symbol as Example 14 is attached|subjected to the structure common to Example 14. As shown in FIG. Furthermore, in order to simplify the description, only two security server devices 2460-1 and 2460-2 are shown in Figs. 38 and 39, but the system may be constituted by two or more security servers. Furthermore, in FIG. 39, only the processing functions and data necessary for the description are described, but the security server apparatuses 2460-1 and 2460-2 may mutually share their respective processing functions and data. Each process is performed under the control of the security server apparatuses 2460-1, 2460-2 and the control units 2465-1, 2465-2.

<preprocessing>

The privileged ID information in this embodiment is information having encrypted text by the public key encryption method and key ID information corresponding to the public key used for the encryption. In this example, the hidden ID information of the tag device 2410 is set as sid _h =(epk _j (id _h ), kid _j ).

The confidentiality ID information sid _h =(epk _j (id _h ), kid _j )) is stored in the secret value memory 2411 of the tag device 2410 of this example. Furthermore, the key memory 2461-1 of the security server device 2460-1 stores each key ID information (kid ₁ , ..., kid _n ) and keys (sk ₁ , ... , sk _n ). Furthermore, in the key memory 2461-2 of the security server device 2460-2, each key ID information (kid ₁ , . . . , kid _n ) and public keys (pk ₁ , .. ., pk _n ).

In addition, in this example, the same privileged ID information is assigned to unrelated tag tag devices. Thereby, it is possible to prevent the item type and individual item from being specified from the key ID information.

<Anonymous ID update processing>

As in the fourteenth embodiment, first, the client device 2020 transmits a reading instruction to the tag device 2410 (step S380). The tag device 2410 extracts the privileged ID information (sid _h =(epk _j (id _h ), kid _j )) from the secret value memory 2411 (step S381), and transmits it to the client device 2020 (step S382). The client device 2020 having received this information transmits the privileged ID information sid _h extracted from the tag device 2410 and a decryption request to the security server device 2460 at the same time in the communication unit 2021 (corresponding to the "first ID output unit"). -1 (step S383). In addition, the security server device 2460-1 is a security server device that manages the privileged ID information stored in the tag device 2410 at this point in time.

Information such as the hidden ID information sid _h is received by the communication unit 2462-1 (corresponding to the "first input unit") of the security server device 2460-1 (step S384), and the epk _{j (} id _h ) is sent to the ID extracting unit 2466-1, and kid _j is sent to the reading/writing unit 2464-1. The read/write unit 2464-1 that has received the key ID information kid _j extracts the key sk _j corresponding to the key ID information kid _j from the key memory 2461-1, and sends the key sk _j to the ID extraction unit 2466-1 (step S385). The ID extraction unit 2466-1 having received the key sk _j decodes the encrypted text (epk _j (id _h )) using the key sk _j , and obtains the tag ID information id _h (id _h =dsk _j (epk _j (id h ) _h ))) (step S386). The obtained tag ID information id _h is sent to the communication unit 2462-1 (corresponding to the "second output unit"), and from there it is sent (output) to the client device 2020 via the network 2070 (step S387).

The tag ID information id _h output from the security server device 2460-1 is received (input accepted) in the communication unit 2021 of the client device 2020 (step S388). After that, the communication unit 2021 transmits (outputs) the tag ID information id _h to the arbitrarily selected security server device 2460-2, and requests an update of the privileged ID information (step S389).

The communication part 2462-2 (corresponding to "the third input part") of the security server device 2460-2 receives the tag ID information id _h sent via the network 2070 (accepts input) and sends it to the encryption part 2467-2 (step S390) . Then, this triggers the key selection unit 2468-2 to select a key and transmits the information to the read/write unit 2464-2 (step S391). In this example, the key selection unit 2468-2 selects an arbitrary (random number, etc.) key number i from natural numbers greater than or equal to 1 and less than or equal to n, and sends the key number i to the read/write unit 2464- 2. The read/write unit 2464-2 extracts the key ID information kid _i and public key _pki corresponding to the received key number i from the key memory 2461-2, and sends them to the encryption unit 2467-2 (step S392). The encryption unit 2467-2 encrypts (conceals) the tag ID information id _h using the received decryption key pk _i (epk _j (id _h )), and generates a new concealed ID composed of the encrypted text and the key ID information kid _i Information (sid _h '=(epk _j (id _h ), kid _i )) (step S393). The generated privileged ID information sid _h ' is sent to the communication unit 2462-2, and the communication unit 2462-2 (corresponding to the "third output unit") transmits (outputs) the privileged ID information sid _h ' to the client via the network 2070 device 2020 (step S394).

The client device 2020 receives this (privileged ID information sid _h ') in the communication unit 2021 (corresponding to the "second input unit") (accepts input) (step S396). The tag device 2410 stores the new hidden ID information sid _h ' in the secret value memory 2411 (step S397), and responds to the new hidden ID information sid _h ' for subsequent read requests. Thereafter, the security server device 2460-2 becomes a security server device that manages the privileged ID information stored in the tag device 2410. Therefore, decoding of this new privileged ID information sid _h ' is performed in the security server device 2460-2 thereafter, and the tag ID information id _h as a result of the decoding is transmitted to the client device 2020, the backend device 2050, and the like. The decryption of the privileged ID information sid _h ' in the security server device 2460-2 is performed using the key sk _i (the key corresponding to the kid _i : not shown) stored in the key memory 2461-2.

<Features of Embodiment 18>

In Embodiment 18, the security server device 2460-1 that manages the hidden ID information of the tag device 2410 decodes the hidden ID information, and then generates new hidden ID information through other security server devices 2460-2, and updates the hidden ID information stored in the tag device. Anonymized ID information in 2410. In other words, the update of the privileged ID information and the change of the security server device that manages the privileged ID information of the tag device 2410 are performed simultaneously. This prevents the update history information of the anonymized ID information from being concentrated in one security server device, and reduces the risk of information leakage from the security server device or fraudulent behavior of a maliciously set security server device. Furthermore, by setting the changed security server device as a local device that cannot be accessed by the public, further high security can be realized.

Also, the update system of this embodiment may be configured using a common key encryption method instead of the public key encryption method.

Furthermore, as in the fourteenth embodiment, the update system of the present embodiment may be constituted by using a random value as the confidentiality ID information. In this case, in the new secure server device, a random value is generated instead of the encryption described above, and the generated random value (=privileged ID) and ID are newly added to the privileged ID memory as in the fourteenth embodiment.

[Example 19]

In the nineteenth embodiment, the client device performs re-privilege processing of the privileged ID information. That is, the client device functions as an update device. In this case, the client device performs re-privilege processing of directly read privileged ID information.

FIG. 41 is a block diagram illustrating the functional configuration of the update system 2500 of this embodiment, and FIG. 42 is a flowchart for explaining the processing procedure. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In FIG. 41 , the same reference numerals as those in the fourteenth embodiment are assigned to the structures common to those in the fourteenth embodiment. The following description will focus on the differences from Example 14.

<preprocessing>

The privileged ID information in this embodiment is information having an encrypted text of an encryption algorithm ( ) having a re-encryption property and key ID information corresponding to a public key used for the encryption. In this example, the hidden ID information of the tag device 2410 is set to sid _h =(g ^r , id _h ·pk _j ^r , kid _j ).

The confidential value memory 2411 of the tag device 2410 of this example stores the privileged ID information (sid _h =(g ^r , id _h ·pk _j ^r , kid _j ))). Moreover, the key ID information (kid ₁ , ..., kid _n ) and public keys (pk ₁ , ..., pk _n ). Furthermore, the generator g is stored in the memory of the remainder exponentiation unit 2527 .

In addition, in this example, the same privileged ID information is assigned to unrelated tag tag devices. Thereby, it is possible to prevent the item type and individual item from being specified from the key ID information.

<Hidden ID update processing>

The client device 2520 executes the following processing under the control of the control unit 2023 .

As in the fourteenth embodiment, first, the client device 2520 transmits a reading instruction to the tag device 2510 (step S400). The tag device 2520 extracts the privileged ID information (sid _h =(g ^r , id _h ·pk _j ^r , kid _j )) from the memory 2511 (step S401), and sends it to the client device 2520 (step S402).

The privileged ID information sid _h is received by the interface 2022 of the client device 2520 (step S403), and the encrypted text (g ^r , id _h ·pk _j ^r ) constituting the privileged ID information sid _h is sent to the remainder multiplication unit 2528 (constitute "encryption unit"), kid _j is sent to read/write unit 2525. The kid _j is recorded in the memory 2023a.

The read-write unit 2525 that has received the key ID information kid _j extracts the public key pk _j corresponding to the key ID information kid _j from the key memory 2524, and sends it to the remainder exponentiation unit 2527 (constituting the “encryption unit”). ") (step S404). Using this as a trigger, the random number generation unit 2526 generates a random number r′ greater than or equal to 0 and less than p−1, and sends it to the remainder exponentiation unit 2527 (step S405 ). The remainder exponentiation unit 2527 performs (g ^r ', pk _j ^r ') operation on the generator g in its own memory, the received public key (pk _j ) and the random number r', and sends the result to the remainder The multiplication unit 2528 (step S406). The remainder multiplication unit 2528 uses the received (g ^r , pk _j ^r ') and (g ^r , id _h pk _j ^r ) to calculate (g ^r+r ', id _h pk _j ^r+r '), and The calculation result is sent to the interface 2022 as a new encrypted text (step S407). Then, the interface 2022 uses the sent encrypted text (g ^r+r ', id _h pk _j ^r+r ') and the key ID information kid _j in the memory of the interface 2022 as new hidden ID information (sid _h '= ((g ^r+r ', id _h ·pk _j ^r+r ', kid _j )) is sent (output) (step S408).

The transmitted new secret ID information sid _h ' is received by the interface 2013 of the tag device 2510, and stored in the memory 2511 via the read/write unit 2012 (step S409). Afterwards, the tag device 2510 responds to the read request with the new concealed ID information sid _h '.

<Features of Embodiment 19>

In the nineteenth embodiment, the client device 2520 re-blinds ID information in the tag device 2510 . Here, the client device 2520 re-privileges only the privileged ID information directly read from the interface 2022 . Therefore, leakage of information to a third party can be suppressed, and higher security can be ensured.

In addition, in this embodiment, the public key ( _{pk 1 ,} . , ..., pk _n ) to obtain and use public keys (pk ₁ , ..., pk _n ) from a predetermined public key server.

Furthermore, the client device 2520 may apply the configuration of any one of the security server devices in the modes of the fourteenth to sixteenth embodiments to execute the processing of the present embodiment.

[Example 20]

Next, Example 20 will be described.

In this embodiment, a plurality of privileged ID information is acquired in a client device (corresponding to an "update requesting device"), and the privileged ID information in the tag device is updated using the privileged ID information selected therefrom.

FIG. 43 is a block diagram illustrating the functional configuration of update system 2600 in this embodiment, and FIG. 44 is a flowchart for explaining its processing procedure. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In FIG. 43, the same reference numerals as in the fourteenth embodiment are given to the structures common to the fourteenth embodiment. Furthermore, the following description will focus on the differences from the fourteenth embodiment.

<preprocessing>

First, the communication unit 2021 (corresponding to the “privileged ID input unit”) of the client device 2620 receives multiple types of privileged ID information (sid _h −1, . . . , p) transmitted via the network 2070 (accept input ) (step S410). The multiple types of concealed ID information (sid _h -1, ..., p) are repeated multiple times from any method in embodiment 14 to embodiment 17, or the security server device 2660 sends multiple types of information once. Information obtained by hiding ID information. Furthermore, when using the method of the fourteenth embodiment, the privileged ID memory of the security server device 2660 needs to hold a plurality of privileged ID information (sid _h -1, . . . , p) for one tag ID information. On the other hand, when using the methods of Embodiment 15 to Embodiment 17, the information stored in the security server device 2660 may be the same as that of Embodiment 15 to Embodiment 17.

The communication unit 2021 sends these privileged ID information (sid _h -1, . . . , p) to the read/write unit 2624, and the read/write unit 2624 stores them in the privileged ID memory 2625 (step S411).

<Anonymous ID update processing>

The client device 2620 executes the following processing under the control of the control unit 2023 .

First, in the control unit 2023, it is judged whether or not there is a predetermined trigger (timing) to update the privilege ID (step S412). As this trigger, for example, the privileged ID information is read from the tag device 2610, or the count value indicating the number of times the privileged ID information in the tag device 2610 is used reaches a predetermined value. Here, if there is no predetermined trigger, the judgment in step S412 is continued, and if there is a predetermined trigger, the read/write unit 2624 (corresponding to the “privileged ID extraction unit”) extracts the ID from the privileged ID memory 2625. A hidden ID information sid _h -j (step S413). The selection of the concealed ID information sid _h -j can be done randomly, for example, or can be selected in the order of sid _h -1, sid _h -2, ..., and return to sid _h - again after sid _h -p 1. The extracted private ID information sid _h -j is sent from the read/write unit 2624 to the interface 2022 (corresponding to the “private ID output unit”), and then sent (output) to the tag device 2610 (step S414).

The tag device 2610 receives the privileged ID information sid _h -j through the interface 2013 (step S415), and stores it in the secret value memory 2611 via the read/write unit 2012 (step S416). Afterwards, the tag device 2610 responds to the new covert ID information sid _h ' to the read request from the reading device.

<Features of Embodiment 20>

In this embodiment, a plurality of types of privileged ID information are stored in advance in the client device 2620, and the privileged ID information of the tag device 2610 is updated with the privileged ID information selected therefrom. Here, the selection of the privileged ID information used for updating is performed within the client device 2620 , and the transmission is performed locally between the client device 2620 and the tag device 2610 . Therefore, leakage of information to a third party can be suppressed, and higher security can be ensured. Furthermore, if multiple types of privileged ID information are sent from the secure server device 2660 to the client device 2620 at one time, the number of accesses to the secure server device 2660 can be reduced, so the performance of the system accompanying the update process of the privileged ID information can be reduced. decline.

The timing of selecting and storing the privileged ID information is not limited to the above, and after all the privileged ID information stored in the client device 2620 is exhausted, multiple types of privileged ID information are acquired again from the security server device 2660, and Storage in the client device 2620 is also possible.

[Example 21]

Next, Example 21 will be described.

This embodiment is a modified example of the twentieth embodiment, and differs from the twentieth embodiment in that the client device acquires the privileged ID information output from a plurality of security server devices ("update devices").

FIG. 45 is a block diagram illustrating the functional structure of the update system 2700 in this embodiment. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In FIG. 45 , the same reference numerals as those in Embodiment 14 or Embodiment 20 are given to the structures common to Embodiment 14 or Embodiment 20. In addition, the following description will focus on the differences from the twentieth embodiment.

<preprocessing>

The only difference from Embodiment 20 is that the client device 2620 receives multiple types of anonymized ID information (sid _h -1, . . . , p). In addition, the concealment of the IDs in the plurality of security server apparatuses 2760-1, 2760-2, . . . , 2760-p uses, for example, the method of the eighteenth embodiment.

<Anonymous ID update processing>

Same as Example 20.

<Features of Embodiment 21>

In this embodiment, the client device 2620 acquires the privileged ID information generated by the plurality of security server devices 2760-1, 2760-2, . . . , 2760-p. Therefore, it is possible to prevent the update history of the anonymized ID information from being concentrated in one secure server device, and higher security can be realized.

Moreover, as described above, in Embodiment 20, in the case of generating privileged ID information using the method of Embodiment 14, a plurality of privileged ID information ( sid _h -1,...,p). However, in the present embodiment, even when the privileged ID information is generated by the method of the fourteenth embodiment, the privileged ID information managed by each security server device only needs one privileged ID information for one key ID information. This simplifies the management of anonymous ID information.

[Example 22]

Next, Example 22 will be described.

This embodiment is a modified example of the twentieth and twenty-first embodiments, and stores the obtained plurality of privileged ID information in the tag device instead of in the client device.

FIG. 46 is a block diagram illustrating the functional structure of the update system 2800 in this embodiment. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In FIG. 46, the same reference numerals as those in the fourteenth embodiment are given to the structures in common with the fourteenth embodiment. Furthermore, the following description will focus on the differences from Example 14, Example 20, and Example 21.

<preprocessing>

First, the communication unit 2021 of the client device 2020 receives a plurality of types of privileged ID information (sid _h -1, . . . , p) transmitted via the network 2070 . The received multiple types of privileged ID information (sid _h -1, . . . , p) are sent to the interface 2022, and are sent to the tag device 2810 from there.

The tag device 2810 receives multiple types of hidden ID information (sid _h -1, . Ministry 2012. The read-write unit 2012 stores them in the hidden ID memory 2811. The hidden ID information (sid _h -1, ..., p) can be output from one security server device, or can be output from multiple security server devices. Information.

<Anonymous ID update processing>

Under the control of the control unit 2014, the read/write unit 2012 (corresponding to the “hidden ID extracting unit”) of the tag device 2810, for example, takes a reading instruction from the reading device as a trigger (timing), and randomly selects any ID from the hidden ID memory 2811. A covert ID information (sid _h -j) is randomly (for example, randomly) extracted and sent from the interface 2013. The sent hidden ID information (sid _h -j) is used for processing in the backend device as described in Embodiment 14.

<Features of Embodiment 22>

In this embodiment, a plurality of concealed ID information (sid _h -1, . . . , p) are stored in the tag device 2810, and one concealed ID information (sid _h -j) selected from them is used. Thereby, the privileged ID information used for acquisition of the ID information etc. will not be the same every time, and tracking of the tag apparatus 2810 can be suppressed. Moreover, since the tag device 2810 itself stores a plurality of types of hidden ID information (sid _h -1, ..., p), even if the client device 2020 cannot be accessed (for example, there is no client device 2020 During the reading process in the reading device of the function), the privileged ID information used can also be updated.

[Example 23]

In this embodiment, a secret value memory is provided in the tag device, and the secret value memory has a read-only area for storing key ID information and a rewritable area for storing first hidden ID information. Then, at the time of re-blinding of the privileged ID information, the key ID information and the first privileged ID information are extracted from the privileged ID memory and output.

The updating device accepts the input of the key ID information and the first hidden ID information, and extracts the key corresponding to the key ID information. Then, using the extracted key and the first privileged ID information, second privileged ID information whose association with the first privileged ID information is difficult to grasp is generated, and the second privileged ID information is output.

The tag device accepts the input of the second concealed ID information, and stores the input second concealed ID information in the rewritable area of the concealed ID memory.

Here, only the privileged ID information is updated by the updating device. Moreover, only the hidden ID information in the rewritable area is rewritten in the tag device, and the key ID information in the read-only area remains unchanged. Therefore, even if the hidden ID information in the rewritable area is rewritten into the hidden ID information corresponding to a different tag device, the key ID information used in the decoding process of the hidden ID information is the key ID information of the original key ID information. as is. Therefore, the decoding server selected when decoding the rewritten privileged ID information is, for example, a decoding server selected based on the original key ID information, and the decoding process of the rewritten privileged ID information may not be properly performed. Furthermore, even in the case of a common decoding server, the key used for the decoding process of the rewritten privileged ID information is a key corresponding to the original key ID information. Therefore, this decoding result is also abnormal.

Hereinafter, this embodiment will be described with reference to the drawings.

FIG. 47 is a conceptual diagram of the overall configuration of the update system 3000 of the present exemplary embodiment.

As illustrated in this figure, the update system 3000 includes a tag device 3010 such as a wireless tag attached to a product, etc., a client device 3020, a back-end device 3050 that manages distribution information related to a plain text ID, etc., and performs ID concealment. A security server device 3060 for re-confidentialization of information, and a security server device 3070 for restoring IDs. Furthermore, the client device 3020, the backend device 3050, and the security server devices 3060 and 3070 can be communicatively connected via a network 3080 such as the Internet. In addition, in order to simplify the description, in this figure, each of the tag device 3010, the client device 3020, the back-end device 3050, and the security server device 3060, 3070 is illustrated as an example, but usually there are multiple tag devices, and the client device, the back-end device There may also be multiple devices and security servers. Furthermore, instead of the security server devices 3060 and 3070, a security server device having both functions of the security server devices 3060 and 3070 may be used.

The client device 3020 of this example reads the privileged ID information from the tag device 10 and sends it to the security server device 3070 . The secure server device 3070 will recover the ID from the concealed ID information and send the ID back to the client device 3020. The client device 3020 having received the ID accesses the backend device 3050 to request writing of information such as date and time, reading position, temperature, etc., or acquisition of information related to the ID. In addition, a proxy model utilization method is conceivable in which the client device 3020 sends the anonymized ID information to the security server device 3070, and the security server device 3070 can directly access the backend device 3050.

And, at a predetermined timing, the privileged ID information in the tag device 3010 is re-cloaked in the security server device 3060 (updates the privileged ID information to other privileged ID information), and the privileged ID information in the tag device 3010 is updated. Since the update timing of the privacy ID information can be reliably ensured, the client device 3020 can be installed, for example, on the porch of a home. In this case, every time the user holding the tag device passes through the hallway, the client device 3020 reads the concealed ID information of the tag device 3010, and the security server device 3060 re-cloaks it and writes it into the tag device again.

Then, the characteristic part of this embodiment is that the tag device 3010 is equipped with a concealed ID memory, and the concealed ID memory has a read-only area for storing key ID information and a rewritable area for storing concealed ID information, as well as a write-only area for hiding the concealed ID information. The rewritable area is entered, but the read-only area storing the key ID information is not updated. Key ID information is not included in the key ID information stored in the rewritable area.

<Functional structure and processing>

FIG. 48 is a diagram illustrating the functional configuration of the update system 3000 in this embodiment, and FIGS. 49 and 50 are flowcharts illustrating the processing procedures thereof. Hereinafter, the functional configuration and processing of this embodiment will be described using these figures. In addition, the description of the back-end device after FIG. 48 is omitted. Furthermore, the tag device 3010, the client device 3020, and the security server devices 3060 and 3070 execute respective processes under the control of the control units 3014, 3023, 3065 and 3075, respectively. Furthermore, the data to be processed is stored in the memory 3014a, 3023a, 3065a, or 3075a one by one, and is called when processing such as calculation is performed, and the description thereof will be omitted below.

<preprocessing>

In this method, an encrypted text using an encryption algorithm (public key encryption method) having a re-encryption property is used as the privileged ID information. In this example, elliptic ElGamal encryption is used.

As illustrated in FIG. 48, the tag device 3010 of this example has a secret value memory 3011 having a read-only area 3011a and a rewritable area 3011b. Here, as the secret value memory 3011, a rewritable memory such as a rewritable ROM (Read Only Memory) such as EEPROM is used, and the predetermined area may be allocated to the read-only area 3011a and the rewritable area 3011b, or a non-rewritable memory such as a ROM may be used. The memory constitutes the read-only area 3011a, and a rewritable memory such as EEPROM constitutes the rewritable area 3011b. Further, key ID information kid _j of the specific key sk _j and public key pk _j is stored (recorded) in the read-only area 3011a, and hidden ID information sid _h =(g ^r , id _h · pk _j ^r ).

Moreover, the generator g is stored in the memory 3065a of the security server device 3060 ("updating device"), and each key ID information (kid ₁ , . . . , kid _n ), keys (sk ₁ , . . . , sk _n ), and public keys (pk ₁ , . . . , pk _n ).

In this example, the total number m of tag devices is sufficiently larger than the total number n of keys (m>>n), and the same key ID information is assigned to unrelated tag devices. That is, for example, the same key ID information is not assigned to tag devices attached to products of the same type, but the same key ID information is assigned to tag devices attached to unrelated products. Thereby, it is possible to prevent the type of product, individual product, etc. from being uniquely identified from the key ID information.

<Concealed ID decoding processing>

First, the decoding process of the key ID information performed when requesting the backend device 3050 to acquire information related to the ID, etc. will be described.

First, mutual authentication is performed between the client device 3020 and the secure server device 3070 using any authentication technique. In addition, the communication between the client device 3020 and the security server device 3070 is encrypted by any encryption technique.

Next, the client device 3020 sends a reading instruction to the tag device 3010 through the interface 3022 (step S501 ). The reading instruction is received in the interface 3013 of the tag device 3010. Triggered by this, the read-write unit 3012 extracts the key ID information kid _j from the read-only area 3011a of the secret value memory 3011, and extracts the key ID information kid j from the rewritable area 3011b. Conceal ID information sid _h (step S502). The extracted privileged ID information sid _h and key ID information kid _j are sent to the client device 3020 through the interface 3013 (step S503 ), and are received in the interface 3022 of the client device 3020 . For example, the client device 3020 determines the address of the security server device 3070 from the received key ID information kid _j , and transmits the hidden ID information sid _h and the key ID information kid _j to the security server device 3070 from the communication unit 3021 through the network 3080. (step S504).

The transmitted privileged ID information sid _h and key ID information kid _j are received (input accepted) in the communication unit 3072 (corresponding to the “hidden ID input unit”) of the security server device 3070 (step S505), and the secret ID information sid _h The key ID information kid _j is sent to the reading unit 3073 . The reading unit 3073 (corresponding to the "key extracting unit") extracts the key sk _j corresponding to the transmitted key ID information kid _j from the key memory 3071, and sends it to the decoding unit 3074 (step S506). The decoding unit 3074 calculates tag ID information _id h that decodes the privileged ID information sid _h using the transmitted privileged ID information sid _h and the key sk _j . In this example, the calculation of id _h = (id _h ·pk _j ^r )/(g ^r ) ^skj is performed to calculate the tag ID information id _h . The exponent "skj" in this formula represents "sk _j ". The calculated tag ID information id _h is sent to the communication unit 3072, and from there to the client device 3020 via the network 3080 (step S508). The client device 3020 receives the transmitted tag ID information id _h in the communication unit 3021 (step S509 ), and uses the tag ID information id _h for subsequent inquiries to the backend device 3050 .

<Anonymous ID update processing>

Next, the update processing of the privileged ID information in this embodiment will be described.

First, mutual authentication is performed between the client device 3020 and the secure server device 3060 using any authentication technique. In addition, the communication between the client device 3020 and the security server device 3060 is encrypted by any encryption technique.

The update process of the private ID information in this example is performed at an arbitrary timing, for example, when passing through a place such as a porch or the like when going out, or the number of times the private ID information stored in the tag device 3010 is used (the count value reaches a predetermined value), etc. . By this trigger, the client device 3020 transmits a read instruction to the tag device 3010 through the interface 3022 (step S511 ). The reading instruction is received in the interface 3013 of the tag device 3010, and as a trigger, the read/write unit 3012 (corresponding to the “hidden ID extraction unit”) extracts the key ID from the read-only area 3011a of the secret value memory 3011 information kid _j , extract hidden ID information sid _h from the rewritable area 3011b (step S512). The extracted hidden ID information sid _h and key ID information kid _j are sent (output) to the client device 3020 through the interface 3013 (corresponding to the "key ID extraction part") (step S513), and the interface of the client device 3020 Received in 3022. The client device 3020 transmits the received privileged ID information sid _h and key ID information kid _j to the security server device 3060 through the communication unit 3021 and the network 3080 (step S514).

The secure server device 3060 receives (accepts input) the privileged ID information sid _h and the key ID information kid _j in the communication unit 3061 (corresponding to the “privileged ID input unit”) (step S515), and transfers the privileged ID information (sid _h =(g ^r , id _h ·pk _j ^r )) is sent to the remainder multiplication unit 3064 (constituting a "privileged ID update unit"). Then, the communication unit 3061 (corresponding to the “key extraction unit”) transmits the key ID information kid _j and the public key acquisition request to the security server device 3070 through the network 3080 at the same time.

The security server device 3070 receives these in the communication unit 3072 and transmits the key ID information kid _j to the reading unit 3073 . The reading unit 3073 extracts the public key pk _j corresponding to the key ID information kid _j from the key memory 3071 , and sends the extracted public key pk _j back to the security server device 3060 through the communication unit 3072 and the network 3080 .

The security server device 3060 receives (extracts) the public key pk _j in the communication unit 3061, and sends it to the remainder exponentiation unit 3063 (constituting a "privileged ID update unit") (step S516). Then, for example, triggered by this, the random number generation unit 3062 generates a random number r′ greater than or equal to 0 and smaller than p−1, and sends it to the remainder exponentiation unit 3063 (step S517 ). The remainder exponentiation unit 3063 uses the generator g in the memory 3065a, the received public key pk _j and the random number r' to perform (g ^r ', pk _j ^r ') calculation, and sends the result to the remainder multiplication unit 3064 (step S518). The remainder multiplication unit 3064 uses the received (g ^r ', pk _j ^r ') and (g ^r , id _h pk _j ^r ) to calculate (g ^r+r ', id _h pk _j ^r+r '), The calculation result (encrypted text) is sent to the communication unit 3061 as new privileged ID information (step S519). The communication unit 3061 transmits the privileged ID information (sid _h '=(ek _j (id _h |r'), kid _j )) (private ID information whose correlation with the privileged ID information (sid _h ) before the update is difficult to grasp (sid _h ')) is sent (output) to the client device 3020 through the network 3080 (step S520).

The transmitted new privileged ID information sid _h ' is received by the communication unit 3021 of the client device 3020, and is transmitted to the tag device 3010 through the interface 3022 (step S521). The tag device 3010 receives (accepts input) the new hidden ID information sid _h ' in the interface 3013 (equivalent to the "hidden ID input part") (step S522), and reads and writes the new hidden ID information sid _h ' stored in the rewritable area 3011b in the rewritable area 3011b (step S523). Then, the tag device 3010 responds to the read request with the new privileged ID information sid _h '.

<Features of Embodiment 23>

In this embodiment, a secret value memory 3011 is provided in the tag device 3010. The secret value memory 3011 has a read-only area 3011a for storing key ID information and a rewritable area 3011b for storing hidden ID information. The hidden ID information in the rewritable area 3011b is hidden and updated again. Therefore, when the privileged ID information of another tag device is written in the rewritable area 3011b during the re-privilege process of the privileged ID information, such an inappropriateness/error can be detected.

For example, in FIG. 48 , ^{it is considered that the hidden ID information (g r} _, ID ₂ · pk ₁ ^r ). Even in this case, the key ID information stored in the read-only area 3011a is usually kid _j , which is the key ID information extracted from the key memory 3071 by the reading unit 3073 during the decoding process of the security server device 3070 . sk _j corresponding to the key ID information kid _j . Therefore, the decoding result in the decoding unit 3074 is (id _h ·pk _j ^r )/(g ^r ) ^skj =(id _h ·(g ^skl ) ^r )/(g ^r ) ^skj =ID ₂ ·g ^skl /g ^skj , the operation result is abnormal data. Therefore, the decoding result becomes abnormal data, and it is possible to detect that the privileged ID information of another tag device has been written.

Furthermore, access control of the rewritable area 3011b by password etc. is not performed, and unauthorized rewriting of the confidentiality ID information, etc. can be prevented, so that the cost of the control circuit can also be suppressed, and complicated password management for access control, etc. are not required.

That is, it is possible to update the privileged ID information at an arbitrary timing more reliably, securely, and at low cost, and to protect the privacy of the tag device 3010 .

In addition, in this embodiment, generation and update of privileged ID information are performed using elliptic ElGamal encryption, but encryption having the property of re-encryption or the re-privilege method disclosed in Patent Application Publication No. 2003-359157 may also be used. Furthermore, the security server devices 3060 and 3070 may be integrated, and the security server device 3060 may further have a memory for a public key.

[Example 24]

This embodiment is a modified example of Embodiment 23. By confirming whether the decoding result of the concealed ID information is inconsistent with the format of the ID, it is confirmed whether the concealed ID information output from the tag device is correct. Hereinafter, the difference from the twenty-third embodiment will be mainly described, and the description of the items common to the twenty-third embodiment will be omitted.

FIG. 51 is a diagram illustrating a functional configuration of a security server device 3170 (corresponding to "decoding device") in this embodiment, and FIG. 52 is a diagram illustrating a format of tag ID information 3200 in this embodiment. Moreover, FIG. 53 is a flowchart for explaining the processing procedure of the security server apparatus 3170. In FIG. 51, the same reference numerals as those in the twenty-third embodiment are assigned to the functional configurations in common with the twenty-third embodiment.

<Overall structure · Hardware structure>

Except that the security server device 3070 is replaced with the security server device 3170, it is the same as the embodiment 23.

<preprocessing>

The difference from Embodiment 23 is that the effective value of each field of ID is stored in the effective value memory 3176 of the security server device 3170 . Others are the same as in Example 23.

<Concealed ID decoding processing>

The difference from Embodiment 23 is that the security server device 3170 performs the processing illustrated in FIG. 53 instead of the processing of the security server device 3070 (FIG. 49: steps S505 to S508). Hereinafter, the processing of the security server device 3170 will be described, and the description of other processing will be omitted.

Similar to Embodiment 23, the privileged ID information sid _h and the key ID information kid _j transmitted from the client device 3020 are received by the communication unit 3072 (corresponding to the "privileged ID input unit") of the security server device 3170 (accept input). ) (step S531), the privileged ID information sid _h is sent to the decoding unit 3074 (corresponding to the “ID calculation unit”), and the key ID information kid _j is sent to the reading unit 3073. The reading unit 3073 (corresponding to the "key extracting unit") extracts the key sk _j corresponding to the transmitted key ID information kid _j from the key memory 3071, and sends it to the decoding unit 3074 (step S532). The decoding unit 3074 calculates tag ID information _id h that decodes the privileged ID information sid _h using the transmitted privileged ID information sid _h and the key sk _j .

The calculated privileged ID information sid _h is sent to the ID structure checking unit 3177, where the structure of the privileged ID information sid _h is checked (step S534). As shown in Figure 52, the ID 3200 of this example has a header (header) (h) 3204, a version code (vc) 3202, a manufacturer code (mc) 3202, a product code (pc) 3204, and a serial code (sc) 3205. fields. The effective value memory 3176 stores the effective value that the value of each field can take, and the ID structure inspection unit 3177 compares the value of each field of the tag ID information id _h obtained with the effective value extracted from the effective value memory 3176, and checks the received tag Whether each field value of the ID information id _h is within the range of valid values. Here, when the verification is successful (step S535), the ID structure verification unit 3177 transmits the tag ID information id _h to the communication unit 3072, and the communication unit 3072 transmits the tag ID information id _h to the client device 3020 (step S536). . On the other hand, when the verification is unsuccessful (step S535), the ID structure verification unit 3177 discards the tag ID information id _h and ends the processing.

<Features of Embodiment 24>

In the present embodiment, in the ID structure checking unit 3177 of the security server device 3170, it is checked whether the decoded tag ID information id _h contradicts a predetermined ID format. Thereby, it is possible to reliably detect the data abnormality of the decoding result of the privileged ID information caused by writing the privileged ID information of another tag device in the rewritable area of the tag device.

[Example 25]

This embodiment is a modified example of Embodiment 23. When performing the re-confidential processing of concealed ID information, a key is used for key ID information and concealed concealed ID information, and authentication information such as a digital signature and MAC is attached. It is different from Example 23. Hereinafter, the difference from the twenty-third embodiment will be mainly described, and the description of the items common to the twenty-third embodiment will be omitted.

FIGS. 54 and 55 are diagrams illustrating the functional configuration of the update system 3300 in this embodiment, and FIGS. 56 and 57 are flowcharts illustrating the processing procedures thereof. In addition, in FIGS. 54 and 55 , the same functional configurations as those in the twentieth embodiment are assigned the same reference numerals as in the twentieth embodiment.

<Overall structure · Hardware structure>

Except that the tag device 3010 is replaced by a tag device 3310, the security server device 3060 is replaced by a security server device 3360 (equivalent to "updating device"), and the security server device 3070 is replaced by a security server device 3370 (equivalent to "decoding device") Other than that, it is the same as in Example 23.

<preprocessing>

The difference from Embodiment 23 is that the hidden ID information sid _h and digital signature (equivalent to "verification information") σ are stored in the rewritable area 3311b of the secret value memory 3311 of the tag device 3310, and the key memory of the security server device 3360 3366 stores the key sk and public key pk used for the digital signature. Others are the same as in Example 23.

<Anonymous ID update processing>

Next, the update processing of the privileged ID information in this embodiment will be described.

First, the client device 3020 transmits a reading instruction to the tag device 3310 through the interface 3022 (step S541). The read instruction is received in the interface 3013 of the tag device 3310, and as a trigger, the read-write unit 3012 extracts the key ID information kid _j from the read-only area 3011a of the secret value memory 3311, and extracts the key ID information kid j from the rewritable area 3311b. Extract hidden ID information sid _h (step S542). The extracted privileged ID information sid _h and key ID information kid _j are sent to the client device 3020 through the interface 3013 (step S543 ), and are received in the interface 3022 of the client device 3020 . The client device 3020 transmits the privileged ID information sid _h and key ID information kid _j to the security server device 3360 through the communication unit 3021 and the network 3080 (step S544).

The secure server device 3360 receives the privileged ID information sid _h and the key ID information kid _j in the communication unit 3061 (step S545), and transmits the privileged ID information (sid _h =(g ^r , id _h ·pk _j ^r )) to Remainder exponentiation unit 3064 . Then, as in the twenty-third embodiment, the communication unit 3061 transmits the key ID information kid _j to the security server device 3370, and acquires (receives) the public key pk _j extracted there (step S546). The public key pk _j is sent to the remainder exponentiation unit 3063 , and the random number r′ generated by the random number generation unit 3062 (step S547 ) is also sent to the remainder exponentiation unit 3063 . The remainder power operation unit 3063 performs (g ^r ', pk _j ^r ') operation, and sends the result to the remainder multiplication operation unit 3064 (step S548), and the remainder multiplication operation unit 3064 operates (g ^r+r ', id _h · pk _j ^r+r '), and send the calculation result to the communication unit 3061 and the signature generation unit 3368 as new privileged ID information (step S549). Triggered by this, the reading unit 3367 extracts the key sk from the key memory 3366, and sends it to the signature generating unit 3368 (step S550). The signature generation unit 3368 (equivalent to the "verification information generation unit") also receives the key ID information kid _j from the communication unit 3061, and generates, for example, g ^r+r ', _id ·pk _j ^r+r ', bit j of kid _j Combine data (g ^r+r '|id _h pk _j ^r+r '|kid _j ), and generate a digital signature (equivalent to "verification information") that encrypts the bit-combined data with key sk σ'=E _sk (g ^r+r '|id _h ·pk _j ^r+r '|kid _j ) (step S551). The generated new digital signature σ' is sent to the communication unit 3061, and the communication unit 3061 (equivalent to the “hidden ID output unit”) sends the new hidden ID information (sid _h '=(g ^r+r ', id _h ·pk _j ^r+r ')) and the new digital signature σ' are transmitted (output) to the client device 3020 via the network 3080 (step S552).

The transmitted new privileged ID information sid _h ' and digital signature σ' are received by the communication unit 3021 of the client device 3020, and are transmitted to the tag device 3310 through the interface 3022 (step S553). The tag device 2310 receives (accepts input) the new hidden ID information sid _h ' and the digital signature σ' in the interface 3013 (equivalent to the "key ID input part") (step S554), and sends the new hidden ID information The sid _h ' and the digital signature σ' are stored in the rewritable area 3311b of the secret value memory 3311 (step S555). Then, the tag device 3310 responds to the read request with the new concealed ID information sid _h ' and the digital signature σ'.

<Concealed ID decoding processing>

Next, the decoding process of the privileged ID information in this embodiment will be described.

First, the client device 3020 sends a reading instruction to the tag device 3310 through the interface 3022 (step S561). The read instruction is received in the interface 3013 of the tag device 3310, and as a trigger, the read-write unit 3012 extracts the key ID information kid _j from the read-only area 3011a of the secret value storage 3311, and extracts the key ID information kid j from the rewritable area 3311b Extract concealed ID information sid _h ' and digital signature σ' from (step S562). The extracted concealment ID information sid _h ', digital signature σ', and key ID information kid _j are sent to the client device 3020 through the interface 3013 (step S563), and are received in the interface 3022 of the client device 3020. The client device 3020 transmits these pieces of information to the security server device 3370 via the network 3080 in the communication unit 3021 (step S564).

The transmitted privileged ID information sid _h ', digital signature σ', and key ID information kid _j are received (input accepted) by the communication unit 3072 (corresponding to the "privileged ID input unit") of the secure server device 3370 (step S565) , the digital signature σ' is sent to the signature verification unit 3370, the hidden ID information sid _h is sent to the decoding unit 3074 (equivalent to the “ID calculation unit”) and the signature verification unit 3376, and the key ID information kid _j is sent to the reader Section 3073 and signature verification section 3376.

Furthermore, the communication unit 3072 sends a public key acquisition request to the security server device 3360 through the network 3080, and the security server device 3360 that receives the request through the communication unit 3061 extracts the public key from the key memory 3366 in the reading unit 3367. pk returns the public key pk via the communication unit 3061 and the network 3080 . The public key pk is received by the communication unit 3072 of the security server device 3370 (step S566 ), and sent to the signature verification unit 3376 .

The signature verification unit 3376 decodes the received digital signature σ' using the public key pk, and generates (D _pk (σ')), g ^r+r ', id _h pk _j ^r+r ', kid _j Bit bound data (g ^r+r '|id _h · pk _j ^r+r '|kid _j ). Then, according to whether D _pk (σ') is equal to (g ^r+r '|id _h ·pk _j ^r+r '|kid _j ), the digital signature σ' is verified (step S567). Here, if D _pk (σ')=(g ^r+r '|id _h ·pk _j ^r+r '|kid _j ), the verification fails and the process ends. On the other hand, in the case of D _pk (σ')=(g ^r+r '|id _h pk _j ^r+r '|kid _j ), the reading unit 3073 (corresponding to the "key extraction unit" ) Extract the key sk _j corresponding to the sent key ID information kid _j from the key memory 3071, and send it to the decoding unit 3074 (step S568). The decoding unit 3074 _calculates the tag ID information _{id h ( id h =} (id _h pk _j ^r+r ')/(g ^{r +r} ') ^skj ) (step S569). In addition, the exponent "skj" in this formula represents "sk _j ". The calculated tag ID information id _h is sent to the communication unit 3072, and from there to the client device 3020 via the network 3080 (step S570). The client device 3020 receives the transmitted tag ID information id _h in the communication unit 3021 (step S571 ), and uses the tag ID information id _h for subsequent inquiries to the backend device 3050 .

<Features of Embodiment 25>

In this embodiment, during the re-concealment process, in the security server device 3360, a digital signature σ'=E _sk (g ^r+r '|id _h ·pk _j ^r+r '|kid _j ) is generated, and after decoding During processing, the digital signature σ' is checked in the security server device 3370 . Therefore, the legitimacy of the re-confidentialed ID information can also be verified by the digital signature during the decoding process, and it is possible to more reliably detect that wrong privileged ID information is stored in the tag device 3310 .

In this embodiment, the digital signature σ' is generated in the security server device 3360, but the security server device 3370 or a notary office server may instead generate the digital signature σ'.

[Example 26]

This embodiment is a modified example of the twenty-third embodiment, and differs from the twenty-third embodiment in that only information in which only information unique to each tag device is concealed among the information constituting the tag ID information is concealed. Hereinafter, the difference from the twenty-third embodiment will be mainly described, and the description of the items common to the twenty-third embodiment will be omitted.

FIG. 58 is a diagram illustrating the functional configuration of the tag device 3410 in this embodiment. In addition, in FIG. 58, the same code|symbol as Example 23 is attached|subjected to the functional structure common to Example 23.

<Overall structure · Hardware structure>

It is the same as Example 23 except that the labeling device 3010 is replaced with the labeling device 3410 .

<preprocessing>

The difference from the twenty-third embodiment is that among the information constituting the tag ID information, only the information unique to each tag device is concealed as the concealed ID information sid _h . In the case of using the tag ID information of the data structure illustrated in FIG. 52 , the sequence code (sc) 3205 is information unique to each tag device, and the concealed ID information is sid _h =(g ^r , sc _h ·pk _j ^r ). And, this privileged ID information (sid _h =(g ^r , sc _h ·pk _j ^r )) is stored in the rewritable area 3411b of the secret value memory 3411 of the tag device 3410. Moreover, information common to products such as the version code (vc) 3202, the manufacturer code (mc) 3202, and the product code (pc) 3204 constituting the tag ID information is encrypted (E(vc), E(mc), E(pc )) is stored in the read-only area 3411a of the secret value storage 3411, which is also different from the twenty-third embodiment. In addition, probabilistic encryption is used for encryption of information common to products such as the version code (vc) 3202, so that different encrypted texts can be obtained for the same product.

<processing>

The privileged ID decoding process and privileged ID update process in this example are the same as those in the twenty-third embodiment except that the privileged ID information is set to sid _h = (g ^r , sc _h ·pk _j ^r ). Also, when making an inquiry to the backend device 3050, etc., the read/write unit 3012 extracts E(vc), E(mc), E(pc), etc. from the read-only area 3411a of the secret value memory 3411 as necessary, and It is also different from the first embodiment in that it is sent to the backend device 3050 through the interface 3013, the client device 3020, and the like.

<Features of Embodiment 26>

In this embodiment, since only the information unique to each tag device is concealed as the concealed ID information, it is possible to reduce the number of persons subject to concealment processing compared with the case of concealed ID information that conceals information common to each product. The amount of data, and can reduce the amount of calculation and communication.

In addition, this invention is not limited to each above-mentioned embodiment or an Example. For example, the present invention can also be implemented by combining the various embodiments, or the various processes described above can be executed not only in time series as described, but also in parallel or individually according to the processing capability or needs of the device performing the processing. In addition, it can change suitably in the range which does not deviate from the summary of this invention.

Furthermore, when the above-mentioned configurations are realized by a computer, the processing contents of the functions of each device are described in a program. And, by executing the program by the computer, the processing functions are realized on the computer.

A program describing the content of the processing may be prerecorded on a computer-readable recording medium. As the computer-readable recording medium, for example, it may be a memory such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, a hard disk device, a floppy disk, or a magnetic tape may be used as the magnetic recording device. DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable)/RW (ReWritable), etc. can be used as optical-magnetic recording devices. MO (Magneto-Optical disc), etc., EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) etc. can be used as semiconductor memory.

Furthermore, distribution of the program can be performed, for example, by selling, transferring, or lending a portable recording medium such as DVD or CD-ROM on which the program is recorded. Furthermore, the program is stored in the storage device of the server computer, and the program is distributed from the server computer to other computers via a network.

A computer that executes such a program temporarily stores, for example, a program recorded on a removable recording medium or a program transferred from the computer in its own storage device. Then, when processing is executed, the computer reads a program stored in its own recording medium, and executes processing according to the read program. Furthermore, as another embodiment of the program, the computer may directly read the program from a removable recording medium and execute processing according to the program, and further, each time the program is transferred from the server computer to the computer, the Perform processing in accordance with accepted procedures. Furthermore, the above processing may be executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition without transferring the program from the server computer to the computer. The program in this form includes information (data, etc., which are not direct commands to the computer but have properties that prescribe the processing of the computer) that conforms to the program and is used for computer processing.

The industrial applicability is that according to the present invention, for example, it is possible to suppress the tracking of the distribution process of the tag device based on the output information of the tag device in RFID.

Claims (19)

1. A label privacy protection method prevents the user's private information from being obtained according to the information output by the label device, and is characterized in that, Concealed ID information sid _h in which each tag ID information id _h is concealed is stored in the secret value memory of each tag device, Each of the tag devices reads the privileged ID information sid _h stored in the secret value memory in the read/write unit, and outputs the privileged ID information to an updating device provided outside the respective tag devices in the first output unit. sid _h , The updating device accepts input of the privileged ID information sid _h in the first input unit, generates new privileged ID information sid h _' whose correlation with the privileged ID information sid _h is difficult to grasp in the update unit, and outputs in the second output output the above-mentioned new hidden ID information sid _h ' to each of the above-mentioned tag devices in the section, Each of the tag devices receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the read/write unit. 2. A label privacy protection method prevents the user's private information from being obtained according to the information output by the label device, and is characterized in that, The hidden ID information sid _h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device h, where h∈{1,...,m}, m is the total number of tag devices, and the hidden ID information sid _h is a random value r _h , The above-mentioned each tag ID information id h correspondingly stored in the hidden ID memory of the update device outside the above-mentioned each tag device _h , and the hidden ID information sid _h corresponding to the tag ID information id _h , the hidden ID information sid _h is random value r _h , Each tag device h reads the privileged ID information sid _h stored in the secret value memory in the first read/write unit, outputs the privileged ID information sid _h to the update device in the first output unit, The updating device accepts input of the hidden ID information sid _h in the first input unit, generates a new random value r _h ' in the random value generating unit, and selects from the hidden ID memory in the second reading and writing unit. The tag ID information id _h corresponding to the input hidden ID information sid _h is stored in the hidden ID memory corresponding to the new random value r _h ' as the new hidden ID information sid _h ', and in the second In the output unit, the above-mentioned new hidden ID information sid _h ' is output to each of the above-mentioned tag devices h, Each of the tag devices h receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the first read/write unit. 3. A label privacy protection method prevents the user's private information from being obtained according to the information output by the label device, and is characterized in that, The hidden ID information sid _h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device h. The hidden ID information sid _h has the first encrypted text of the common key encryption method and the common key used for the encryption. Key ID information kid _j of key K _j , where, h∈{1,...,m}, m is the total number of tag devices, j∈{1,...,n}, n is the total number of keys , Correspondingly store each key ID information kid _j and each common key k _j in the key memory of the update device installed outside the above-mentioned each tag device h, Each tag device h reads the privileged ID information sid _h stored in the secret value memory in the first read/write unit, outputs the privileged ID information sid _h to the update device in the first output unit, The updating device accepts the input of the privileged ID information sid _h in the first input unit, and extracts the key ID information kid _j included in the privileged ID information sid _h from the key memory in the second read/write unit. Corresponding to the above-mentioned common key k _j , in the ID extraction part, use the above-mentioned common key k _j extracted by the above-mentioned second reading and writing part to decode the above-mentioned first encrypted text, and extract the tag ID information id _h , and in the encryption part , using the tag ID information id _h extracted by the ID extracting unit and the common key k _j used for the extraction to generate a second encrypted text whose correlation with the first encrypted text is difficult to grasp, and output the second encrypted text to the second output unit Outputting new concealed ID information sid h ' with the above-mentioned second encrypted text and the above-mentioned key ID information kid _j of the common key k _j to each of the above-mentioned tag devices _h , Each of the tag devices h receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the first read/write unit. 4. A label privacy protection method, preventing the user's private information from being obtained according to the information output by the label device, characterized in that, The hidden ID information sid _h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device h, and the hidden ID information sid _h has the first encrypted text and key pair (sk _j , pk _j ) key ID information kid _j , where, h∈{1,...,m}, m is the total number of tag devices, sk _j is the key, pk _j is the public key, j∈{1, ..., n}, where n is the total number of keys, Correspondingly store each key ID information kid _j and each key pair (sk _j , pk _j ) in the key memory of the update device installed outside the above-mentioned each tag device h, Each tag device h reads the privileged ID information sid _h stored in the secret value memory in the first read/write unit, outputs the privileged ID information sid _h to the update device in the first output unit, The update device accepts input of the privileged ID information sid _h in the first input unit, and extracts the privileged ID information sid _h input into the first input unit from the key memory in the second read/write unit. The key pair (sk _j , pk _j ) corresponding to the above-mentioned key ID information kid _j , in the ID extracting part, use the above-mentioned key sk _j extracted by the above-mentioned second reading and writing part to decode the above-mentioned first encrypted text, And extract the above-mentioned tag ID information id _h , in the encryption part, use the above-mentioned tag ID information id _h extracted by the above-mentioned ID extraction part and the above-mentioned public key pk _j extracted by the above-mentioned second reading and writing part to generate a key that is difficult to grasp and the above-mentioned first In the second encrypted text related to the encrypted text, the second output unit outputs the key ID information kid _j having the second encrypted text and the key pair (sk _j , pk _j ) to each tag device h The new hidden ID information sid _h ', Each of the tag devices h receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the first read/write unit. 5. A label privacy protection method, preventing the user's private information from being obtained according to the information output by the label device, characterized in that, The hidden ID information sid _h corresponding to each tag ID information id _h is stored in the secret value memory of each tag device h, and the hidden ID information sid _h has the first encrypted text of the re-encryptable public key encryption method and the public key Key ID information kid _j of key pk _j , where, h∈{1,...,m}, m is the total number of tag devices, j∈{1,...,n}, n is the total number of keys , Correspondingly store each key ID information kid _j and each public key pk _j in the key memory of the update device installed outside the above-mentioned each tag device h, Each tag device h reads the privileged ID information sid _h stored in the secret value memory in the first read/write unit, outputs the privileged ID information sid _h to the update device in the first output unit, The update device accepts input of the privileged ID information sid _h in the first input unit, and extracts the privileged ID information sid _h input into the first input unit from the key memory in the second read/write unit. The above-mentioned public key pk _j corresponding to the above-mentioned key ID information _{kid j} , in the encryption part, uses the above-mentioned public key pk j extracted by the above-mentioned second reading and writing part, and converts the above-mentioned first public key included in the above-mentioned concealed ID information sid _h to An encrypted text is re-encrypted to generate a second encrypted text that is difficult to grasp the relevance of the first encrypted text, and output the second encrypted text and the above-mentioned public key pk _j to each tag device h in the second output unit. The new hidden ID information sid _h ' of the above key ID information kid _j , Each of the tag devices h receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the first read/write unit. 6. A label privacy protection method, preventing the user's private information from being obtained according to the information output by the label device, characterized in that, The secret value memory of each tag device h stores concealed ID information sid _h that hides each tag ID information id _h , wherein, h∈{1,...,m}, m is the total number of tag devices, Each of the above tag devices h reads the above-mentioned privileged ID information sid _h stored in the above-mentioned secret value memory in the first read/write unit, and transmits to the first updating device installed outside the above-mentioned each tag device h in the first output unit. Output the above hidden ID information sid _h , The above-mentioned first updating device accepts the input of the above-mentioned concealed ID information sid _h in the first input unit, in the ID extracting unit, obtains the tag ID information id _h based on the above-mentioned concealed ID information sid _h , and in the second output unit, Output the above-mentioned tag ID information id _h at the second updating device outside each of the above-mentioned tag devices h, The above-mentioned second updating device accepts the input of the above-mentioned tag ID information id _h in the third input part, and in the encryption part, generates new concealed ID information sid _h ' with the above-mentioned tag ID information id _h concealed, and in the third In the output unit, the above-mentioned new hidden ID information sid _h ' is output to each of the above-mentioned tag devices h, Each of the tag devices h receives input of the new privileged ID information sid _h ' in the second input unit, and stores the new privileged ID information sid _h ' in the secret value memory in the first read/write unit. 7. An update device for updating the concealed ID information of the label device, characterized in that, set on the outside of the above labeling device, It has: a concealed ID memory, correspondingly storing each tag ID information id _h and concealed ID information _{sid h} corresponding to the tag ID information id h, and the concealed ID information sid _h is a random value r _h ; The first input unit accepts the input of the concealed ID information sid _h output from the tag device; The random value generation unit generates a new random value r _h '; The second reading and writing unit is connected to the hidden ID memory, selects the tag ID information id _h corresponding to the hidden ID information sid _h input to the first input unit from the hidden ID memory, and uses the new random value r _h 'is correspondingly stored in the hidden ID storage as new hidden ID information sid _h '; and The second output unit outputs the new privileged ID information sid _h ' to the tag device. 8. An update device for updating the hidden ID information of the tag device h, characterized in that, set on the outside of the above-mentioned labeling device h, It has: a key memory, correspondingly storing each key ID information kid _j and each common key k _j of the common key encryption method, wherein, j∈{1,...,n}, n is the total number of keys; The first input unit accepts the input of the hidden ID information sid _h , the hidden ID information sid _h has the first encrypted text and the key ID information kid _j of the common key k _j used for the encryption, the first encrypted text A common key encryption method corresponding to the tag ID information id _h ; The second read-write unit is connected to the key storage, and extracts the common key k _j corresponding to the key ID information kid _j included in the concealed ID information sid _h from the key storage; The ID extraction unit decodes the first encrypted text by using the common key k _j extracted by the second reading and writing unit, and extracts the tag ID information id _h ; An encryption unit that uses the tag ID information id _h extracted by the ID extraction unit and the common key k _j used for the extraction to generate a second encrypted text whose correlation with the first encrypted text is difficult to grasp; and The second output unit outputs new privileged ID information sid _h ' having the second encrypted text and the key ID information kid _j of the common key k _j to the tag device h. 9. An update device for updating the hidden ID information of the tag device h, characterized in that, set outside the above-mentioned labeling device h, It has: key memory, correspondingly storing each key ID information kid _j and key pair (sk _j , pk _j ), where j∈{1,...,n}, n is the total number of keys, sk _j is the key, pk _j is the public key; The first input unit accepts the input of the hidden ID information sid _h , the hidden ID information sid _h has the first encrypted text and the key ID information kid _j of the public key pk _j used for the encryption, the first encrypted text Public key encryption method corresponding to tag ID information id _h ; The second read/write unit is connected to the key memory, and extracts the key corresponding to the key ID information kid _j included in the hidden ID information sid _h input to the first input unit from the key memory. pair(sk _j , pk _j ); The ID extracting part decodes the above-mentioned first encrypted text by using the above-mentioned key sk _j extracted by the above-mentioned second reading and writing part, and extracts the above-mentioned tag ID information id _h ; The encryption unit uses the tag ID information id _h extracted by the ID extraction unit and the public key pk _j extracted by the second reading/writing unit to generate a second encrypted text whose relationship with the first encrypted text is difficult to grasp. ;as well as The second output unit outputs new privileged ID information sid _h ' having the second encrypted text and the key ID information kid _j corresponding to the key pair (sk _j , pk _j ) to the tag device h. 10. An updating device for updating the concealed ID information of the tag device h, characterized in that, set outside the above-mentioned labeling device h, It has: a key storage, correspondingly storing each key ID information kid _j and each public key pk _j , where j∈{1,...,n}, n is the total number of keys; The first input unit accepts the input of the hidden ID information sid _h , the hidden ID information sid _h has the first encrypted text and the key ID information kid _j of the public key pk _j , the first encrypted text corresponds to the tag ID Re-encryptable public key encryption of message id _h ; The second read-write unit is connected to the key memory, and extracts from the key memory the public key corresponding to the key ID information kid _j included in the concealed ID information sid _h input to the first input unit. key pk _j ; The encryption unit re-encrypts the first encrypted text included in the hidden ID information sid _h by using the public key pk _j extracted by the second reading/writing unit, and generates a second encrypted text whose relationship with the first encrypted text is difficult to grasp. Two encrypted texts; and The second output unit outputs new privileged ID information sid _h ' having the second encrypted text and the key ID information kid _j of the public key pk _j to the tag device h. 11. The updating device according to any one of claims 8 to 10, characterized in that, The key ID information kid _j is information shared by a plurality of unrelated tag devices. 12. An update entrusting device that entrusts an update device to update the privacy ID of a tag device, wherein: located on the outside of the labeling device, It has: a concealed ID input unit for inputting a plurality of concealed IDs corresponding to re-encryptable encrypted text of the same tag ID information id _h ; Concealed ID storage, storing the above-mentioned concealed IDs of multiple types input; a hidden ID extraction unit connected to the aforementioned hidden ID storage, and extracts a hidden ID from the hidden ID storage at a prescribed timing; and The privileged ID output unit outputs the extracted privileged ID to the tag device. 13. A label privacy protection method, preventing the user's private information from being obtained from the information output from the label device, characterized in that, The key ID and the key are correspondingly stored in the key storage; The tag device above has a concealed ID memory, and the concealed ID memory has a read-only area storing the key ID, and a rewritable area storing the first concealed ID, The tag device extracts the key ID and the first privileged ID from the privileged ID memory in the read/write unit, and outputs the extracted key ID and the first privileged ID to the updating device in the first output unit, The update device accepts the input of the key ID and the first confidential ID in the first input unit, and in the first key extracting unit, extracts from the key memory the key corresponding to the key ID input to the first input unit. As for the key of the key ID, in the secret ID update part, using the key extracted by the first key extracting part and the first secret ID input to the first input part, a key that is difficult to grasp is generated. A second hidden ID related to a hidden ID, outputting the second hidden ID in the second output unit, The tag device receives input of the second privileged ID in the second input unit, and stores the second privileged ID in the rewritable area of the privileged ID memory in the read/write unit. 14. label privacy protection method as claimed in claim 13, is characterized in that, The update device further includes a verification information generating unit that generates verification information for the second privileged ID, The second output unit of the update device outputs the second privileged ID and the verification information, The second input unit of the tag device accepts input of the second confidential ID and the verification information, The read-write unit of the tag device stores the second privileged ID and the verification information in the rewritable area of the privileged ID memory. 15. label privacy protection method as claimed in claim 13, is characterized in that, The above-mentioned tag device extracts the above-mentioned key ID from the read-only area of the above-mentioned hidden ID memory in the read-write unit, extracts the third hidden ID from the above-mentioned rewritable area, and outputs the extracted above-mentioned ID to the decoding device in the first output unit. key ID and the above-mentioned third hidden ID, The decoding device accepts input of the key ID and the third confidential ID in the third input unit, and extracts the key input to the third input unit in the second key extracting unit from the key memory. For the key corresponding to the ID, the ID is calculated in the ID calculation unit using the hidden ID input to the third input unit and the key extracted by the second key extraction unit, and the calculated ID is checked in the ID structure checking unit. The structure of the ID. 16. A label device for automatic label identification system, characterized in that, It has: hidden ID storage, with a read-only area for storing the key ID and a rewritable area for storing the first hidden ID; The reading and writing unit extracts the key ID and the first hidden ID from the hidden ID storage; a first output unit that outputs the extracted key ID and the first secret ID; and The second input unit accepts the input of the second confidential ID which is difficult to grasp the relationship with the first confidential ID, The read/write unit stores the input second privileged ID in the rewritable area of the privileged ID memory. 17. The labeling device of claim 16, wherein: The second input unit also accepts input of verification information for the second concealed ID, The read/write unit also stores the input verification information in the rewritable area of the confidential ID memory. 18. The labeling device of claim 16, wherein: The confidentiality ID described above is information in which only information unique to each tag device is concealed among the information constituting the ID. 19. The labeling device of claim 16, wherein: The same key ID is assigned to unrelated tag devices.

Images