Tag privacy protection method, tag device, backend apparatus, updater, update solicitor and record medium carrying such programs in storage

• US 7,661,132 B2
• Filed: 09/27/2004
• Issued: 02/09/2010
• Est. Priority Date: 09/26/2003
• Status: Active Grant

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Suzuki, Koutarou, Ohkubo, Miyako, Kinoshita, Shingo
• Primary Examiner(s): Revak; Christopher A
• Application Number:
  US10/537,915
• Publication Number:
  US 20060080732A1
• Time in Patent Office: 1,961 Days
• Field of Search: None
• US Class Current: 726/18
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/73 by creating or determining hardware identification, e.g. serial numbers
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A tag device causes a second calculator to read a confidential value from a confidential value memory and to apply a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to generate tag output information. The tag device delivers the tag output information to a backend apparatus. Subsequently, a first calculator reads out at least part of elements of the confidential value from the confidential value memory, and applies a first function F1, an inverse image of which is difficult to obtain, and a result of such calculation is used to update a confidential value in the confidential value memory by overwriting.

Claims

1. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, comprising:

delivering tag output information from an output section of the tag device, the tag output information corresponding to a confidential value stored in a confidential value memory of the tag device, the confidential value being a mapping of tag ID information;

and

reading out the confidential value or elements thereof from the confidential value memory, applying a first function to the confidential value or the elements thereof to generate a new confidential value, an inverse image of the first function being difficult to obtain, and updating the confidential value in the confidential value memory with the new confidential value by overwriting in a first calculator of the tag device, the new confidential value differing from the confidential value, and both the new confidential value and the confidential value corresponding to the identical tag ID information.

2. A tag privacy protection method according to claim 1, further comprising:

reading out the confidential value from the confidential value memory, and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to the confidential value read out in a second calculator of the tag device;

wherein

the tag output information is a result of such calculation.

3. A tag privacy protection method according to claim 2 in which at least one of the first function F1 and the second function F2 is a hash function.

4. A tag privacy protection method according to claim 2 in which the first function F1 is a hash function H(x)=hash(p|x) where hash represents a hash function for {0, 1}*→

{0, 1}^r, p∈

{0, 1}^s and r and s are natural numbers and in which the second function F2 is a hash function G(x)=hash(q|x) where q∈

{0, 1}^s for p.

5. A tag privacy protection method according to claim 2 in which the first function F1 is a hash function H(x)=hash(pad(x, p)) where hash represents a hash function for {0, 1}*→

{0, 1}^s, p∈

{0, 1}^s, pad(x, p) represents a padding of p to x and r and s are natural numbers and in which the second function F2 is a hash function G(x)=hash(pad(x, q)) where pad(x, q) represents a padding of q to x and q∈

{0, 1}^s for p≠

q.

6. A tag privacy protection method according to claim 2 where the first function F1 is a hash function H(x) for {0, 1}*→

{0, 1}^r and r is a natural number and in which the second function F2 is a hash function G(x)=F(rx) where rx represents a bit inversion of x.

7. A tag privacy protection method according to claim 2 in which at least one of the first function F1 and the second function F2 is a common key encryption function.

8. A tag privacy protection method according to claim 2 in which the first function F1 and the second function F2 are an identical common key encryption function, to which different common keys are applied.

9. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which a first confidential value s_{k, i}, corresponding to each tag ID information id_k is stored in a confidential value memory of each tag device k where k∈

{1, . . . , m} and m represents a total number of tag devices, and in which each tag ID information id_n (n ∈

{1, . . . , m} and a corresponding second confidential value s_{n, 1} are stored in a database memory of a backend apparatus in a manner relating to each other;

comprising;

reading out the first confidential value s_{k, i} from the confidential value memory, and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to generate tag output information F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information F2(s_{k, i}) from an output section of the tag device;

and reading out the first confidential value s_{k, i}from the confidential value memory, applying thereto a first function F1, an inverse image of which is difficult to obtain, and saving a result of such calculation F1(s_{k, i}) as new first confidential value s_{k, i+1} in the confidential value memory by overwriting in a first calculator of the tag device;

accepting an input of the tag output information F2(s_{k, i}) at an input section of the backend apparatus;

reading out the second confidential value s_{n, 1} from the database memory, applying to each second confidential value s_{n, 1}read out j times where j∈

{0, . . . , j_max}, the first function F1 and subsequently applying the second function F2 thereto in a third calculator of the backend apparatus;

comparing the tag output information F2(s_{k, i}) against the result of calculation F2(F1^j(s_{n, 1})) in a comparator of the backend apparatus;

in the event the tag output information F2(s_{k, i}) does not match the result of calculation F2 (Fl^j(s_{n, 1})), the processings in the third calculator and the comparator being executed again by changing the value of at least one of n and j;

and extracting by a reader of the backend apparatus the tag ID information id_n which is related to the second confidential value s_{n, 1} corresponding to the matched result of calculation F2(F1^j(s_{n, 1})) from the database memory when the tag output information F2(s_{k, i}) matches the result of calculation F2(F1^j(s_{n, 1})).

10. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which a first confidential value s_{k, i} and a first proper value w_k corresponding to each tag ID information id_k are sored in a confidential value memory of each tag device k where k∈

{1, . . . , m} and m represents a total number of tag devices, in a manner relating to each other and in which each tag ID information id_n (n ∈

{1, . . . , m}) and a corresponding second confidential value s_{n, 1}and a second proper value w_n are stored in a database memory of a backend apparatus in a manner relating to each other;

comprising;

reading out the first confidential value s_{k, i} from the confidential value memory and applying thereto a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof-to generate tag output information F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information F2(s_{k, i}) from an output section of the tag device;

reading out the first confidential value s_{k, i} and the first proper value w_k from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to a bit combination value of the first confidential value and the first proper value, and saving a result of such calculation F1(s_{k, i}|w_k) as a new confidential value s_{k, i,+1} in the confidential value memory by overwriting in a first calculator of the tag device;

accepting an input of the tag output information F2(s_{k, i}) by an input section of the backend apparatus;

reading out the second confidential value s_{n, 1}and the second proper value w_k from the database memory of the backend apparatus, and applying the second function F2 to I^j(n) where I^j(n)=s_{n, 1}(j=0) and I^j(n)=F1 (I^j-1(n))|id_n)(j≧

1) to calculate F2(I^j(n)) in a third calculator of the backend apparatus;

comparing the tag ID information F2(s_{k, i}) and a result of calculation F2(I^j(n)) in the third calculator in a comparator of the backend apparatus;

in the event the tag output information F2(s_{k, i}) does not match the result of calculation F2(I^j(n)), the processings in the third calculator and the comparator being executed again by changing the value of at least one of n and j;

and in the event the tag output information F2(s_{k, i}) matches the result of calculation F2(I^j(n)), extracting the tag ID information id_n which is related to the second confidential value s_{n, 1} and the second proper value w_n corresponding to the matching result of calculation F2(I^j(n)) from the database memory by a reader.

11. A tag privacy protection method for preventing privacy information of a user from being acquiring from information which is delivered from a tag device, in which a first confidential value s_{k, i} and a first proper value w_k which correspond to each tag ID information id_k are stored in a confidential value memory of each tag device k where k∈

{1, . . . , m}, and m represents a total number of tag devices and in which a tag ID information id_n (n∈

{1, . . . , m}) and a second confidential value S_{n, 1} and a second proper value w_n which correspond thereto are stored in a database memory of a backend apparatus in a manner relating to each other;

comprising;

reading out the first confidential value s_{k, i} and the first proper value w_k from the confidential value memory and applying to a bit combination value thereof a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to generate tag output information F2(s_{k, i}|w_k) in a second calculator of the tag device;

delivering the tag output information F2(s_{k, i}|w_k) from an output section of the tag device;

reading out the first confidential value s_{k, i} from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to the first confidential value s_{k, i} which is read out, and saving a result of such calculation F1(s_{k, i}) as a new first confidential value s_{k, i} in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information F2(s_{k, i}|w_k) as an input at an input section of the backend apparatus;

reading out the second confidential value s_{n, 1} and the second proper value w_n from the database memory, of the backend apparatus, applying j times (j∈

{0, . . . , j_max}) the first function F1 to the second confidential value s_{n, 1} to determine a bit combination value F1^j(s_{n, i}) |w_n of a resulting F1^j(s_{n, i}) and the second proper value w_n, and applying the second function F2 to the bit combination value F1^j(s_{n, i})|w_n in a third calculator of the backend apparatus; and

comparing the tag output information F2(s_{k, i}|w_k) against a result of calculation in the third calculator F2(F1^j(S_{n, i})|w_n) in a comparator of the backend apparatus;

in the event the tag output information F2(s_{k, i}|w_k) does not match the result of calculation F2(F1^j(s_{n, i})|w_n), executing the processings in the third calculator and the comparator again by changing the value of at least one of n and j;

and in the event the tag output information F2(s_{k, i}|w_k) matches the result of calculation F2(F1^j(s_{n, i})|w_n), extracting the tag ID information id_n which is related to the second confidential value s_{n, 1} and the second proper value w_n corresponding to the matching result of calculation F2(F1^j(s_{n, i})|w_n) from the database memory by a reader of the backend apparatus.

12. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which a first proper value w_k corresponding to each tag ID information id_k and a first confidential value s_i which assumes an identical initial value s_i for a plurality of tag ID information are stored in a confidential value memory of each tag device k where k∈

{1, . . . , m} and m represents a total number of tag devices, each tag ID information id_n(n∈

{1, . . . , m}) and a corresponding second proper value w_n are stored in a database memory of a backend apparatus in a manner relating to each other, and a first result of calculation s_j+1 obtained by applying j times (j∈

{0, . . . , j_max}) a first function F1 to the second confidential value s₁ which is used in common by the plurality of tag ID information is stored in a calculated value memory of the backend apparatus;

comprising;

reading out the first confidential value s_i and the first proper value w_k from the confidential value memory and applying to a bit combination value thereof a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to generate tag output information F2(s_i|w_k) in a second calculator of the tag device;

delivering the tag output information F2(s_i|w_k) from an output section of the tag device;

reading out the first confidential value s_i from the confidential value memory, applying the first function F1, an inverse image of which is difficult to obtain, to the first confidential value s_i which is read out, and saves a result of such calculation F1 (s_i) as a new first confidential value s_i+1 in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information F2(s_i|w_k) as an input at an input section of the backend apparatus;

reading out a result of the first calculation s_j+1 and the second proper value w_n from the database memory to obtain a bit combination value s_j+1|w_n thereof, and applying the second function F2 thereto in a third calculator of the backend apparatus; and

comparing the tag output information F2(s_i|w_k) against a result of the calculation by the third calculator F2(s_j+1|w_n) in a comparator of the backend apparatus;

in the event the tag output information F2(s_i|w_k) does not match the result of the calculation F2(s_j+1|w_n), executing the processings in the third calculator and the comparator again by changing the value of at least one of n and j;

and in the event the tag output information F2(s_i|w_k) matches the result of the calculation F2(s_j+1|w_n), extracting the tag ID information id_n which is related to the second proper value w_n corresponding to the matching result of calculation F2(s_j+1|w_n) from the database memory by a reader of the backend apparatus.

13. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which a combination of d (d≧

2) elements e_{u, vu}(u∈

{1, . . . , d}) corresponding to each tag ID information id_k is stored in a confidential value memory of each tag device k k∈

{1, . . . , m} and m represents a total number of tag devices), and in which a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

2) of subgroups α

_u (u∈

{1, . . . , d}) and the tag ID information id_n of each tag device n (n∈

{1, . . . , m}) are stored in a database memory of a backend apparatus in a manner relating to each other;

comprising;

reading out the d elements e_{u, vu} from the confidential value memory to form a bit combination value thereof which represents a confidential value s_{k, i} and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to the confidential value s_{k, i} to generate tag output information a_{k, i}=F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information a_{k, i} from an output section of the tag device;

extracting at least part of elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

, and saving a result of such calculation F1 (e<sub>u′

, vu</sub>′

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information a_{k, i} as an input at an input section of the tag device;

applying the first function F1 w_u times (w_u∈

{1, 2, . . . , max}) to d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n, and applying the second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) to determine a calculated value c in a third calculator of the backend apparatus; and

comparing the tag output information a_{k, i} against the calculated value c in a comparator of the backend apparatus;

in the event the tag output information a_{k, i} does not match the calculated value c, executing the processings in the third calculator and the comparator again by changing the value of at least part of n and w_u;

and in the event the tag output information a_{k, i} matches the calculated value c, extracting tag ID information id_n which is related to the combination of d initial elements f_{u, 0} corresponding to the calculated value c from the database memory by a reader of the backend apparatus.

14. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which a combination of d (d≧

2) elements e_{u, vu} (u∈

{1, . . . , d}) which corresponds to each tag ID information id_k and a proper value γ

_k which is inherent to each tag ID information id_k are stored in a confidential value memory of each tag device k where k∈

{1, . . . , m} and where m represents a total number of tag devices and in which a combination of d (d≧

2) elements e_{u, vu} where u∈

{1, . . . , d}which corresponds to each tag ID information id_k and a proper value γ

_k which is inherent to each tag ID information id_k are stored in a database memory of a backend apparatus in a manner relating to each other;

comprising;

reading out the d elements e_{u, vu} and the proper value γ

_k from the confidential value memory, and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of the d elements and the proper value to generate tag output information a_{k, i}=F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information a_{k, 1} from an output section of the tag device;

extracting at least part of elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

, and saving a result of such calculation F1 (e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information a_{k, i} as an input at an input section of the backend apparatus;

applying the first function F1 w_u times (w_u∈

{1, 2, . . . , max}) to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n and applying the second function F2 to a bit combination value of the function values F1^wu(f_{u, 0}) and the proper value γ

_n to determine a calculated value c in a third calculator of the backend apparatus; and

comparing the tag output information a_{k, i} against the calculated value c in a comparator of the backend apparatus;

in the event the tag output information a_{k, i} does not match the calculated value c, executing the processings in the third calculator and the comparator again by changing the value of at least part of n and w_u;

and in the event the tag output information a_{k, i} matches the calculated value c, extracting tag ID information id_n which is related to the combination the plurality of initial elements f_{u, 0} corresponding to the calculated value c from the database memory by a reader of the backend apparatus.

15. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which d (d≧

1) elements e_{u, vu} (u∈

{1, . . . , d}) are stored in a confidential value memory of each tag device k where k∈

{1, . . . , m} and m represents a total number of tag devices, a manifold value z having t kinds (t≧

2) of values is stored in a first manifold value memory of each tag device k, a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

1) of subgroups α

_u (u∈

{1, . . . , d}) and tag ID information id_n (n∈

{1, . . . , m}) of each tag device are stored in a database memory of a backend apparatus in a manner relating to each other, and the manifold value z is stored in a second manifold value memory of the backend apparatus;

comprising;

reading out each element e_{u, vu} from the confidential value memory and reading out either manifold value z from the first manifold value memory and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of the elements and the manifold value to generate tag output information a_{k, i}=F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information a_{k, i} from an output section of the tag device;

extracting at least part of elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information a_{k, i} t times, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

, and saving a result of such calculation F1(e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information a_{k, i} as an input at an input section of the backend apparatus;

applying the first function F1 w_u times (w_u∈

{1, 2, . . . , max}) to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n and applying the second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) and the manifold value z to determine a calculated value c in a third calculator of the backend apparatus; and

comparing the tag output information a_{k, i} against the calculated value c in a comparator of the backend apparatus;

in the event the tag output information a_{k, i} does not match the calculated value c, executing the processings in the third calculator and the comparator again by changing the value of at least part of n, w_u and z;

and in the event the tag output information a_{k, i} matches the calculated value c, extracting the tag ID information id_n which is related to the combination of the d initial elements f_{u, 0} corresponding to the calculated value c from the database memory by a reader of the backend apparatus.

16. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which d (d≧

2) elements e_{u, vu} (u∈

{1, . . . , d}) are stored in a confidential value memory of each tag device k (k∈

{1, . . . , m}, where m represents a total number of tag devices), a manifold value z_u which assumes t_u kinds (t_u≧

2) of values for each u is stored in a first manifold value memory of each tag device k, a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

2) of subgroups α

_u (u∈

{1, . . . , d}) and tag ID information id_n (n∈

{1, . . . , m}) of each tag device are stored in a database memory of a backend apparatus in a manner relating to each other, and the manifold value z_u is stored in a second manifold value memory of the backend apparatus;

comprising;

reading out each element e_{u, vu} from the confidential value memory and reading out either manifold value z_u for each u from the first manifold value memory and applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of e_{u, vu} and z_u to generate tag output information a_{k, i}=F2(s_{k, i}) in a second calculator of the tag device;

delivering the tag output information a_{k, i} from an output section of the tag device;

extracting at least part of elements e_{u, vu} (u′

∈

{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information a_{k, i} some number of times, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

, and saving a result of such calculation F1(e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting in a first calculator of the tag device;

accepting the tag output information a_{k, i} as an input at an input section of the backend apparatus;

applying w_u times (w_u∈

{1, 2, . . . , max}) the first function F1 to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n, and applying the second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) and the manifold value z_u to determine a calculated value c in a third calculator of the backend apparatus; and

comparing the tag output information a_{k, i} against the calculated value c in a comparator of the backend apparatus;

in the event the tag output information a_{k, i} does not match the calculated value c, executing the processings in the third calculator and the comparator again by changing the value of at least part of n, w_u and z_u;

and in the event the tag output information a_{k, i} matches the calculated value c, extracting tag ID information id_n which is related to the combination of a plurality of initial elements f_{u, 0} corresponding to the calculated value c from the database memory by a reader of the backend apparatus.

17. A tag device for use in an automatic tag identification system comprising:

a confidential value memory in which a confidential value corresponding to tag ID information is stored;

a second calculator connected to the confidential value memory for reading out the confidential value from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to the confidential value which is read out to generate tag output information;

an output section for delivering the tag output information;

and a first calculator for reading out at least part of elements of the confidential value from the confidential value memory and for applying a first function F1, an inverse image of which is difficult to obtain, to the elements which are read out, with a result of such calculation being used to update the confidential value in the confidential value memory by overwriting.

65. A computer readable record medium storing a tag program which enables a computer to function as a tag device according to one of claims 17, 57 and 61.

18. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which each tag ID information and a corresponding confidential value are related to each other;

an input section which accepts tag output information as an input;

a calculator for applying a first function F1 which is used in a tag device some number of times to at least part of elements of the confidential value in the database memory and which then applies a second function which is used in the tag device thereto;

a comparator for sequentially comparing a result of the calculation in the calculator against the tag output information;

and a reader for extracting the tag ID information which is related to the confidential value corresponding to the matching result of calculation when a matching between the result of calculation and the tag output information is found from the database memory, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and mapping thereof.

19. A computer readable record medium storing a tag program which enables a computer to function as a backend apparatus according to claim 18.

20. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a first confidential value s_{k, i} corresponding to tag ID information id_k is stored;

a second calculator connected to the confidential value memory for reading out the first confidential value s_{k, i} from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to the first confidential value s_{k, i} to generate tag output information F2(s_{k, i});

an output section for delivering the tag output information F2(s_{k, i});

and a first calculator connected to the confidential value memory for reading out the first confidential value s_{k, i} from the confidential value memory, for applying a first function F1, an inverse image of which is difficult to obtain, to the first confidential value and for saving a result of such calculation F1 (s_{k, i}) as a new first confidential value s_{k, i+1} in the confidential value memory by overwriting.

21. A tag device according to claim 20, further comprising

a counter for counting a number of times m the first confidential value is updated,

the output section also delivering information which specifies the number of updating times rn.

22. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a first confidential value s_{k, i} and a first proper value w_k which correspond to a tag ID information id_k are stored;

a second calculator connected to the confidential value memory for reading out the first confidential value s_{k, i} from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to the first confidential value to generate tag output information F2(s_{k, i});

an output section for delivering the tag output information F2(s_{k, i});

and a first calculator connected to the confidential value memory for reading out the first confidential value s_{k, i} and the first proper value w_k from the confidential value memory, for applying a first function F1, an inverse image of which is difficult to obtain, to a bit combination value of the first confidential value and the first proper value and for saving a result of such calculation F1(s_{k, i}|w_k) as a new first confidential value s_{k, i+1} in the confidential value memory by overwriting.

23. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which each tag ID information id_n (n∈

{1, . . . , m}, where m represents a total number of tag devices) and a second confidential value s_{n, 1} corresponding thereto are related to each other;

an input section which accepts tag output information F2(s_{k, i}) as an input;

a third calculator connected to the database memory for reading out the second confidential value s_{n, 1} from the database memory, applying j times (j∈

{0, . . . , j_max}) a first function F1 which is used in a tag device to each of the second confidential values s_{n, 1} which are read out, and for subsequently applying a second function F2 which is used in the tag device;

a comparator for comparing the tag output information F2(s_{k, i}) against a result of calculation in the third calculator F2(F1^j(s_{n, 1}));

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least one of n and j in the event the tag output information F2(s_{k, i}) and the result of calculation F2(F1^j(s_{n, 1})) do not match;

and a reader connected to the database memory and operative when the tag output information F2(s_{k, i}) matches the result of the calculation F2(F1^j(s_{n, 1})) to extract the tag ID information id_n which is related to the second confidential value s_{n, 1} corresponding to the matching result of the calculation F2(F1^j(s_{n, 1})) from the database memory, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition and a mapping thereof.

24. A backend apparatus according to claim 23 in which the input section accepts an input of information which specifies a number of times rn the first confidential value is updated in the tag device, the third calculator applies the first function F1 j=rn times to each of the confidential values s_{n, 1} which are read out and then applies the second function F2 thereto, and the controller causes the processings in the third calculator and the comparator to be executed again by changing the value of n when the tag output information F2(s_{k, j}) does not match the result of the calculation F2(F1^j(s_{n, 1})).

25. A backend apparatus according to claim 23 in which the database memory stores the result of the calculation F2(F1^j(s_{n, 1})) in the third calculator in a manner relating it to the second confidential value s_{n, 1}, and the comparator performs a comparing processing by using the result of the calculation F2(F1^j(s_{n, 1})) stored in the database memory.

26. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which each tag ID information id_n (n∈

{1, . . . , m}), a corresponding second confidential value s_{n, 1} and second proper value w_n are stored in a manner relating to each other;

a input section which accepts an input of tag output information F2(s_{k, i});

a third calculator connected to the database memory for reading out the second confidential value s_{n, 1} and the second proper value w_n from the database memory and for applying a second function F2 to I^j(n) where I^j(n)=s_{n, 1} (j=0), and I^j(n)=F1(I<sup>j−

1</sup>(n)|id_n) (j≧

1) to calculate F2(I^j(n)) where F1 represents a first function;

a comparator for comparing the tag output information F2(s_{k, i}) against the result of the calculation in the third calculator F2(I^j(n));

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least one of n and j when the tag output information F2(s_{k, i}) does not match the result of the calculation F2(I^j(n));

and a reader for extracting tag ID information id_n which is related to the second confidential value s_{n, 1} and the second proper value w_n corresponding to the matched result of calculation F2(I^j(n)) from the database memory when a matching between the tag output information F2(s_{k, i}) and the result of the calculation F2(I^j(n)) is found wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and a mapping thereof.

27. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a first confidential value s_{k, i} and a first proper value w_k corresponding to tag ID information id_k are stored;

a second calculator connected to the confidential value memory for reading out the first confidential value s_{k, i} and the first proper value w_k from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a bit combination value of the first confidential value and the first proper value to generate tag output information F2(s_{k, i} w_k);

an output section for delivering the tag output information F2(s_{k, i}|w_k)

and a first calculator connected to the confidential value memory for reading the first confidential value s_{k, i} from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to the first confidential value s_{k, i} which is read out and saving a result of such calculation F1(s_{k, i}) as a new first confidential value s_{k, i+1} in the confidential value memory by overwriting.

28. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which each tag ID information id_n (n∈

{1, . . . , m}) and a corresponding second confidential value s_{n, 1} and second proper value w_n are stored in a manner relating to each other;

an input section which accepts an input of tag output information F2(s_{k, i}|w_k);

a third calculator connected to the database memory for reading out the second confidential value s_{n, 1} and the second proper value w_n from the database memory, applying j times (j∈

{0, . . . , j_max}) a first function F1 which is used in a tag device to the second confidential value s_{n, 1}, determining a bit combination value F1^j(s_{n, i})|w_n of a result of application F1^j(s_{n, i}) and the second proper value w_n, and applying a second function F2 which is used in the tag device to the bit combination value F1(s_{n, i}|w_n);

a comparator for comparing the tag output information F2(s_{k, i}|w_k) against a result of calculation in the third calculator F2(F1^j(s_{n, i})|w_n);

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least one of n and j when the tag output information F2(s_{k, i}|w_k) does not match the result of the calculation F2(F1^j(s_{n, i})|w_n);

and a reader connected to the database memory for extracting the tag ID information id_n which is related to the second confidential value s_{n, 1} and the second proper value w_n corresponding to the matched result of calculation F2(F1^j(s_{n, i})|w_n) when a matching between the tag output information F2(s_{k, i}|w_k) and the result of the calculation F2(F1^j(s_{n, i})|w_n) is found wherein

an inverse image of the first function F1 ia difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and mapping thereof.

29. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a first proper value w_k corresponding to each tag ID information id_k and a first confidential value s_i which assumes an equal initial value s_i for a plurality of tag ID information are stored;

a second calculator connected to the confidential value memory for reading out the first confidential value s_i and the first proper value w_k from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a bit combination value of the first confidential value and the first proper value to generate tag output information F2(s₁ i w_k);

an output section for delivering the tag output information F2(s_i|w_k);

and a first calculator connected to the confidential value memory for reading out the first confidential value s_i from the confidential value memory, applying a first function F1, an inverse image of which is difficult obtain, to the first confidential value s_i which is read out and saving a result of such calculation F1(s_i) as a new first confidential value s_i+1 in the confidential value memory by overwriting.

30. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which each tag ID information id_n (n∈

{1, . . . , m}) and a corresponding second proper value w_n are stored in a manner relating to each other;

a calculated value memory in which first results of calculation s_j+1 are stored which are obtained by applying j times (j∈

{0, . . . , j_max}) a first function which is used in a tag device to a second confidential value s₁ which is used in common for a plurality of tag ID information;

an input section which accepts an input of tag output information F2(s_i|w_k);

a third calculator connected to the database memory for reading out the first result of calculation s_j+1 and the second proper value w_n from the database memory to obtain a bit combination value thereof s_j+1|w_n and for applying a second function F2 which is used in the tag device thereto;

a comparator for comparing the tag output information F2(s_i|w_k) and the result of calculation in the third calculator F2(s_j+1|w_n);

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least one of n and j when the tag output information F2(s_i|w_k) does not match the result of calculation F2(s_j+1|w_n);

and a reader connected to the database memory for extracting the tag ID information id_n which is related to the second proper value w_n corresponding to the matched result of calculation F2(s_j+1|w_n) when a matching between the tag output information F2(s_i|w_k) and the result of calculation F2(s_j+1|w_n) is found wherein

an inverse image of the first function F1 ia difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and mapping thereof.

31. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a combination of d (d≧

2) elements e_{u, vu} (u∈

{1, . . . , d}) which corresponds to each tag ID information id_k is stored;

a second calculator connected to the confidential value memory for reading out the d elements e_{u, vu} from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of the d elements to generate tag output information a_{k, i}=F2(s_{k, i});

an output section for delivering the tag output information a_{k, i};

and a first calculator connected to the confidential value memory for extracting at least part of elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory, for applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

and for saving a result of such calculation F1 (e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

32. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

2) of subgroups α

_u(u∈

{1, . . . , d}), and tag ID information id_n of each tag device n (n∈

{1, . . . , m}, where m represents a total number of tag devices) are stored in a manner relating to each other;

an input section for accepting an input of tag output information a_{k, i};

a third calculator for applying w_u times (w_u∈

{1, 2, . . . , max}) a first function F1 to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) which correspond to the tag ID information id_n and for applying a second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) to determine a calculated value c;

a comparator for comparing the tag output information a_{k, i} against the calculated value c;

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least part of n and w_u when the tag output information a_{k, i} does not match the calculated value c;

and a reader connected to the database memory for extracting tag ID information id_n which is related to the combination of d initial elements f_{u, 0} corresponding to the calculated value c when the tag output information a_{k, i} matches the calculated value c, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and a mapping thereof.

33. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which a combination of d (d≧

2) elements e_{u, vu} (u∈

{1, . . . , d}) which correspond to each tag ID information id_k and a proper value γ

_k which is inherent to each tag ID information id_k are stored;

a second calculator connected to the confidential value memory for reading out the d elements e_{u, vu} and the proper value γ

_k from the confidential value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of the d elements and the proper value to generate tag output information a_{k, i}=F2(s_{k, i});

an output section for delivering the tag output information a_{k, i};

and a first calculator connected to the confidential value memory for extracting at least part of the elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

and for saving a result of such calculation F1 (e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

34. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

2) of subgroups α

_u (u∈

{1, . . . , d}), a proper value γ

_n which is inherent to each tag ID information id_n (n∈

{1, . . . , m}) and each tag ID information id_n are stored in a manner relating to each other;

an input section for accepting an input of tag output information a_{k, i};

a third calculator for applying w_u times (w_u∈

{1, 2, . . . , max}) a first function F1 to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n and for applying a second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) and the proper value γ

_n to determine a calculated value c;

a comparator for comparing the tag output information a_{k, i} against the calculated value c;

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least part of n and w_u when the tag output information a_{k, i} does not match the calculated value c;

and a reader connected to the database memory for extracting tag ID information id_n which is related to the combination of a plurality of initial elements f_{u, 0} corresponding to the calculated value c from the database memory when a matching between the tag output information a_{k, i} and the calculated value c is found, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and a mapping thereof.

35. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which d (d≧

1) elements e_{u, vu} (u∈

{1, . . . , d}) are stored;

a first manifold value memory in which a manifold value z which assumes t kinds (t≧

2) of values is stored;

a second calculator connected to the confidential value memory and the first manifold value memory for reading out the elements e_{u, vu} from the confidential value memory and for reading out either manifold value z from the first manifold value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of the elements and the manifold value to generate tag output information a_{k, i}=F2(s_{k, i});

an output section for delivering the tag output information a_{k, i};

and a first calculator connected to the confidential value memory for extracting at least part of elements e<sub>u′

, vu</sub>′

(u′

∈

{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information a_{k, i} t times, for applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

and for saving a result of such calculation F1 (e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

36. A tag device according to claim 35 in which as long as the first calculator does not update elements in the confidential value memory, the manifold value z used by the second calculator in generating the tag output information a_{k, i} changes each time the tag output information a_{k, i} is generated.

37. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which a combination of d initial elements f_{u, 0} comprising one selected from each of d kinds (d≧

1) of subgroup α

_u (u∈

{1, . . . , d}) and a tag ID information id_n (n∈

{1, . . . , m}) of each tag device are stored in a manner relating to each other;

a second manifold value memory in which a manifold value z which assumes t kinds (t≧

2) of values is stored;

an input section for accepting an input of tag output information a_{k, i};

a third calculator for applying w_u times (w_u∈

{1, 2, . . . , max}) a first function F1 to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) in the database memory which correspond to the tag ID information id_n and for applying a second function F2 to a bit combination value of these values F1^wu(f_{u, 0}) and the manifold value z in the second manifold value memory to determine a calculated value c;

a comparator for comparing the tag output information a_{k, i} against the calculated value c;

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value at least part of n, w_u and z when the tag output information a_{k, i} does not match the calculated value c;

and a reader connected to the database memory for extracting the tag ID information id_n which is related to the combination of d initial elements f_{u, 0} corresponding to the calculated value c from the database memory when a matching between the tag output information a_{k, i} and the calculated value c is found, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and a mapping thereof.

38. A tag device for use in an automatic tag identification system comprising

a confidential value memory in which d (d≧

2) elements e_{u, vu} (u∈

{1, . . . , d}) are stored;

a first manifold value memory in which a manifold value z_u which assumes t_u kinds (t_u≧

2) of values for each u is stored;

a second calculator connected to the confidential value memory and the first manifold value memory for reading out the elements e_{u, vu} from the confidential value memory and for reading out either manifold value z_u for each u from the first manifold value memory and for applying a second function F2 which disturbs a relationship between elements of a definition domain and a mapping thereof to a confidential value s_{k, i} which is a bit combination value of these e_{v, vu} and z_u to generate tag output information a_{k, i}=F2(s_{k, i});

an output section for delivering the tag output information a_{k, i};

and a first calculator connected to the confidential value memory for extracting at least part of the elements e<sub>u′

, vu′</sub>

(u′

∈

{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information a_{k, i} some number of times, for applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements e<sub>u′

, vu′</sub>

, and for saving a result of such calculation F1(e<sub>u′

vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

39. A tag device according to claim 38 in which each time the output section delivers the tag output information a_{k, i}, the first calculator extracts at least part of the elements e_u′

, vu′

from the confidential value memory, applies the first function F1 to the extracted elements e<sub>u′

, vu′</sub>

and saves a result of such calculation F1(e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

40. A tag device according to claim 38 in which each time the output section delivers the tag output information

$a_{k,i}$

∑

u = 1 d ⁢

t u

times, the first calculator extracts at least part of the elements e<sub>u′

, vu′</sub>

from the confidential value memory, applies the first function F1 to the extracted elements e<sub>u′

, vu′</sub>

, and saves a result of such calculation F1(e<sub>u′

, vu′</sub>

) as new elements e<sub>u′

, vu′

+1</sub> in the confidential value memory by overwriting.

41. A tag device according claim 40 in which as long as the first calculator does not update the elements in the confidential value memory, a combination of manifold values z_u (u∈

{1, . . . , d}) which are used by the second calculator in generating the tag output information a_{k, i} changes each time the tag output information a_{k, i} is generated.

42. A backend apparatus for use in an automatic tag identification system comprising

a database memory in which a combination of d initial elements f_{u, 0} which comprises one selected from each of d kinds (d≧

1) of subgroups α

_u (u∈

{1, . . . , d}) and tag ID information id_n (n∈

{1, . . . , m}) of each tag device are stored in a manner relating to each other;

a second manifold value memory in which a manifold value z_u which assumes t_u kinds (t_u≧

2) of values for each u is stored;

an input section for accepting an input of tag output information a_{k, i};

a third calculator for applying w_u times (w_u∈

{1, 2, . . . , max}) a first function F1 which is used in a tag device to the d initial elements f_{u, 0} (u∈

{1, . . . , d}) corresponding to the tag ID information id_n and for applying a second function F2 which is used in the tag device to a bit combination value of these values F1^wu(f_{u, 0}) and the manifold value z_u to determine a calculated value c;

a comparator for comparing the tag output information a_{k, i} against the calculated value c;

a controller for causing the processings in the third calculator and the comparator to be executed again by changing the value of at least part of n, w_u and z;

and a reader connected to the database memory for extracting tag ID information id_n which is related to the combination of the d initial elements f_{u, 0} corresponding to the calculated value c from the database memory when a matching between the tag output information a_{k, i} and the calculated value c is found, wherein

an inverse image of the first function F1 is difficult to obtain, the second function F2 disturbs a relationship between elements of a definition domain and a mapping thereof.

43. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which privileged ID information sid_h which is formed by privileging respective tag ID information id_h is stored in a confidential value memory of each tag device;

comprising

reading out the privileged ID information sid_h stored in the confidential value memory in a read/write section of the tag device;

delivering the privileged ID information sid_h to an updater which is provided externally of each tag device from a first output section of the tag device;

accepting an input of the privileged ID information sid_h at a first input section of the updater;

updating the privileged sid_h to new privileged ID information sid_h′

, both the privileged ID information sid_h and the new privileged ID information sid_h′

corresponding to the tag ID information sid_h, in an updating section of the updater;

delivering the new privileged ID information sid_h′

to the tag device from a second output section of the updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the tag device; and

storing the new privileged ID information sid_h′

in the confidential value memory.

44. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which the privileged ID information sid_h which is a random value r_h related to each tag ID information id_h is stored in a confidential value memory of each tag device h (h∈

{1, . . . , m}, where m represents a total number of tag devices), and each tag ID information id_h and privileged ID information sid_h which is the random value r_h related to the tag ID information id_h are stored in a privileged ID memory of an updater which is provided externally of each tag device h in a manner relating to each other;

comprising;

reading out the privileged ID information sid_h stored in the confidential value memory thereof in a first read/write section of the tag device h;

delivering the privileged ID information sid_h to the updater from a first output section of the tag device h;

accepting an input of the privileged ID information sid_h at a first input section of the updater;

generating a new random value r_h′

in a random value generator of the updater;

selecting tag ID information id_h corresponding to the privileged ID information sid_h which is accepted as the input from the privileged ID memory and storing the new random value r_h′

in the privileged ID memory in a manner relating to new privileged ID information sid_h′

in a second read/write section of the updater;

delivering the new privileged ID information sid_h′

to the tag device h from a second output section of the updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the updater device h; and

storing the new privileged ID information sid_h′

in the confidential value memory.

45. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which privileged ID information sid_h is stored in a confidential value memory of each tag device h (h∈

{1, . . . , m}, where m represents a total number of tag devices), the privileged ID information sid_h including a first encrypted text according to a common key encryption technique which corresponds to each tag ID information id_h and key ID information kid_j of a common key k_j used in the encryption (j∈

{1, . . . , n}, where n represents a total number of tag devices), and each key ID information kid_j are stored and each common key k_j in a key memory of an updater which is provided externally of each tag device h in a manner relating to each other;

comprising;

reading out the privileged ID information sid_h stored in the confidential value memory thereof in a first read/write section of the tag device h;

delivering the privileged ID information sid_h to an updater from a first output section of the tag device h;

accepting an input of the privileged ID information sid_h at a first input section of the;

extracting the common key k_j corresponding to the key ID information kid_j included in the privileged ID information sid_h from the key memory by a second read/write section of the updater;

decrypting the first encrypted text using the common key k_j extracted by the second read/write section to extract tag ID information id_h by an ID extractor of the updater;

generating a second encrypted text, using the tag ID information id_h extracted by the ID extractor and the common key k_j which is used in the extraction in an encryptor of the updater;

delivering new privileged ID information sid_h′

including the second encrypted text and the key ID information kid_j of the common key k_j to the tag device h from a second output section of the updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the tag device h;

storing the new privileged ID information sid_h′

in the confidential value memory.

46. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which privileged ID information sid_h is stored in a confidential value memory of each tag device h (h∈

{1, . . . , m}, where m represents a total number of tag devices), the privileged ID information sid_h including a first encrypted text according to a pubic key encryption technique which corresponds to each tag ID information id_h and key ID information kid_j for a key pair (sk_j, pk_j) (where sk_j represents a secret key and pk_j represents a public key, j∈

{1, . . . , n}, where n represents a total number of tag devices), and each key ID information kid_j and each key pair (sk_j, pk_j) in a key memory of an updater which is provided externally of each tag device h in a manner relating to each other;

comprising;

reading out the privileged ID information sid_h stored in the confidential value memory in a first read/write section of the tag device h;

delivering the privileged ID information sid_h to an updater from a first output section of the tag device h;

accepting an input of the privileged ID information sid_h at a first input section of the updater;

extracting the key pair (sk_j, pk_j) which corresponds to the key ID information kid_j which is included in the privileged ID information sid_h accepted as the input to the first input section by a second read/write section of the updater;

decrypting the first encrypted text using the secret key sk_j extracted by the second read/write section to extract the tag ID information id_h by an ID extractor of the updater;

generating a second encrypted text, using the tag ID information id_h extracted by the ID extractor and the public pk_j which is extracted by the second read/write section by an encryptor of the updater;

delivering new privileged ID information sid_h′

including the second encrypted text and the key ID information kid_j of the key pair (sk_j, pk_j) to the tag device h from a second output section of the updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the tag device h; and

storing the new privileged ID information sid_h′

in the confidential value memory.

47. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which privileged ID information sid_h is stored in a confidential value memory of each tag device h (h∈

{1, . . . , m}, where m represents a total number of tag devices), the privileged ID information sid_h including a first encrypted text according to re-encryptable public key encryption technique which corresponds to each tag ID information id_h and key ID information kid_j of the public key pk_j (j∈

{1, . . . , n}, where n represents a total number of keys), each key ID information kid_j and each public key pk_j are stored in a key memory of an updater which is provided externally of each tag device h in a manner relating to each other;

comprising;

readings out the privileged ID information sid_h stored in the confidential value memory in a first read/write section of the device h;

delivers the privileged ID information sid_h to an updater from a first output section of the device h;

accepting an input of the privileged ID information sid_h at a first input section of the updater;

extracting the public key pk_j which corresponds to the key ID information kid_j included in the privileged ID information sid_h which is accepted as the input to the first input section from the key memory by a second read/write section;

re-encrypting the first encrypted text in the privileged ID information sid_h using the public key pk_j extracted by the second read/write section to generate a second encrypted text, by an encryptor of the updater;

delivering new privileged ID information sid_h′

including the second encrypted text and the key ID information kid_j of the public key pk_j to the tag device h from a second output section of the updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the tag device h; and

storing the new privileged ID information sid_h′

in the confidential value memory.

48. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, in which privileged ID information sid_h which has privileged each tag ID information id_h is stored in a confidential value memory of each tag device h (h∈

{1, . . . , m}, where m represents a total number of tag devices);

comprising;

reading out the privileged ID information sid_h stored in the confidential value memory by a first read/write section of the tag device h;

delivering the privileged ID information sid_h to a first updater which is provided externally of the tag device h from a first output section of the tag device h;

accepting an input of the privileged ID information sid_h at a first input section of the first updater;

determining tag ID information id_h from the privileged ID information sid_h by an ID extractor of the first updater;

delivering the tag ID information id_h to a second updater which is provided externally of the tag device h from a second output section of the first updater;

accepting an input of the tag ID information id_h at a third input section of the second updater;

generating new privileged ID information sid_h′

which has privileged the tag ID information id_h by an encryptor of the second updater;

delivering the new privileged ID information sid_h′

to the tag device h from a third output section of the second updater;

accepting an input of the new privileged ID information sid_h′

at a second input section of the tag device h; and

storing the new privileged ID information sid_h′

in the confidential value memory.

49. An updater for updating privileged ID information in a tag device, the updater being provided externally of the tag device and comprising

a privileged ID memory for storing each tag ID information id_h and privileged ID information sid_h which is a random value r_h which corresponds to the tag ID information id_h in a manner relating to each other;

a first input section which accepts an input of the privileged ID information sid_h which is delivered from the tag device;

a random value generator for generating a new random value r_h′

;

a second read/write section connected to the privileged ID memory for selecting tag ID information id_h which corresponds to the privileged ID information sid_h which is accepted by the first input section as the input from the privileged ID memory and for relating this with the new random value r_h′

as new privileged ID information sid_h′

to be stored in the privileged ID memory;

and a second output section for delivering the new privileged ID information sid_h′

to the tag device h.

54. A computer readable record medium storing an update program which enables a computer to function as an updater according to one of claims 49 to 52.

50. An updater for updating privileged ID information in a tag device, the updater being provided externally of the tag device and comprising

a key memory for storing each key ID information kid_j (j∈

{1, . . . , n}, where n represents a total number of keys) and each common key k_j of a common key encryption technique in a manner relating to each other;

a first input section for accepting an input of privileged ID information sid_h which includes a first encrypted text according to the common key encryption technique which corresponds to the tag ID information id_h and key ID information kid_j of the common key k_j which is used in the encryption;

a second read/write section connected to the key memory for extracting the common key k_j which corresponds to the key ID information kid_j which is included in the privileged ID information sid_h from the key memory;

an ID extractor for decrypting the first encrypted text using the common key k_j which is extracted by the second read/write section to extract tag ID information id_h;

an encryptor for generating a second encrypted text, using the tag ID information id_h extracted by the ID extractor and the common key k_j which is used in the extraction;

and a second output section for delivering new privileged ID information sid_h′

which includes the second encrypted text and the key ID information kid_j for the common key k_j to the tag device h.

53. An updater according to one of claims 50 to 52 in which the key ID information kid_j is information which is shared by a plurality unrelated tag devices.

51. An updater for updating privileged ID information in a tag device, the updater being provided externally of the tag device and comprising

a key memory for storing each key ID information kid_j (j∈

{1, . . . , n}, where n represents a total number of keys) and each key pair (sk_j, pk_j) (sk_j represents a secret key and pk_j a public key) in a manner relating to each other;

a first input section for accepting an input of privileged ID information sid_h which includes a first encrypted text according to a public key encryption technique which corresponds to tag ID information id_h and key ID information kid_j for the public key pk_j which is used in the encryption;

a second read/write section connected to the key memory for extracting the key pair (sk_j, pk_j) which corresponds to the key ID information kid_j which is included in the privileged ID information sid_h accepted by the first input section as the input from the key memory;

an ID extractor for decrypting the first encrypted text using the secret key sk_j extracted by the second read/write section to extract tag ID information id_h;

an encryptor for generating a second encrypted text, using the tag ID information id_h extracted by the ID extractor and the public key pk_j extracted by the second read/write section;

and a second output section for delivering new privileged ID information sid_h′

which includes the second encrypted text and the key ID information kid_j for the key pair (sk_j, pk_j) to the tag device h.

52. An updater for updating privileged ID information in a tag device, the updater being provided externally of the tag device and comprising

a key memory for storing each key ID information kid_j (j∈

{1, . . . , n}, where n represents a total number of keys) and each public key pk_j in a manner relating to each other;

a first input section for accepting an input of privileged ID information sid_h which includes a first encrypted text according to re-encryptable public key encryption technique which corresponds to tag ID information id_h and key ID information kid_j for the public key pk_j;

a second read/write section connected to the key memory for extracting the public key pk_j which corresponds to the key ID information kid_j which is included in the privileged ID information sid_h which is accepted by the first input section as the input from the key memory;

an encryptor for re-encrypting the first encrypted text which is included in the privileged ID information sid_h using the public key pk_j extracted by second read/write section to generate a second encrypted text;

and a second output section for delivering new privileged ID information sid_h′

which includes the second encrypted text and the key ID information kid_j for the public key pk_j to the tag device h.

55. An update solicitor for soliciting an updater to update privileged ID information in a tag device, the update solicitor being provided externally of the tag device and comprising

a privileged ID input section to which a plurality of kinds of privileged ID'"'"'s, which are two or more kinds of re-encryptable encrypted texts corresponding to an identical tag ID information id_h, are input;

a privileged ID memory for storing a plurality of kinds of privileged ID'"'"'s which are input thereto;

a privileged ID extractor connected to the privileged ID memory for extracting one of privileged ID'"'"'s from the privileged ID memory at a given opportunity;

and a privileged ID output section for delivering the extracted privileged ID to the tag device.

56. A computer readable record medium storing an update soliciting program which enables a computer to function as an update solicitor according to claim 55.

57. A tag device for use in an automatic tag identification system comprising

a privileged ID input section to which a plurality of kinds of privileged ID'"'"'s, which are two or more kinds of re-encryptable encrypted texts corresponding to an identical tag ID information id_h, are input;

a privileged ID memory for storing the plurality of kinds of privileged ID'"'"'s which are input thereto;

a privileged ID extractor connected to the privileged ID memory for extracting one of the privileged ID'"'"'s from the privileged ID memory at a given opportunity;

and a privileged ID output section for delivering the extracted privileged ID.

58. A tag privacy protection method for preventing privacy information of a user from being acquired from information which is delivered from a tag device, comprising:

extracting a key ID from a read only region of a privileged ID memory of a tag device and extracting a first privileged ID from a rewritable region of the privileged ID memory of the tag device by a read/write section of the tag device, the first privileged ID being an encrytpted text tag of ID information, the encrypted text encrypted with a key specified by the key ID;

delivering the extracted key ID and the first privileged ID to an updater from a first output section of the tag device, the updater apparatus having a key memory storing a key ID and a key in a manner relating to each other;

accepting the key ID and the first privileged ID as inputs at a first input section of the updater;

extracting a key which corresponds to the key ID which is input to the first input section from the key memory by a first key extractor of the updater;

updating the first privileged ID to a second privileged ID, the second privileged ID being a new encrypted text of the tag ID information corresponding to first privileged ID, the new encrypted text encrypted with the key extracted by the first key extractor, in a privileged ID updating section of the updater;

delivering the second privileged ID from a second output section;

accepting an input of the second privileged ID at a second input section of the tag device; and

storing the second privileged ID in the rewritable region of the privileged ID memory.

59. A tag privacy protection method according to claim 58, further comprising:

generating a verification information for the second privileged ID in a verification information generator of the updater apparatus;

delivering the second privileged ID and the verification information from the second output section of the updater;

accepting the second privileged ID and the verification information as inputs at the second input section of the tag device;

storing the second privileged ID and the verification information in the rewritable region the of privileged ID memory.

60. A tag privacy protection method according to claim 58, further comprising:

extracting the key ID from the read-only region of the privileged ID memory and extracting the first or second privileged ID from the rewritable region, by the read/write section of the tag device;

delivering the extracted key ID and the first or second privileged ID to a decrypt or from the first output section of the tag device;

accepting the key ID and the first or second privileged ID as inputs at a third input section of the decryptor;

extracting a key which corresponds to the key ID which is accepted by the third input section as an input from the key memory by a second key extractor of the decryptor;

decrypting the first or second privileged ID with the key extracted by the second key extractor of the decryptor to calculate the tag ID information in an ID calculator;

and verifying the structure of the calculated tag ID information by an ID structure verifier of the decryptor.

61. A tag device for use in an automatic tag identification system comprising

a privileged ID memory including a read-only region in which a key ID is stored and a rewritable region in which a first privileged ID is stored, the first privileged ID being an encrypted text of tag ID information, the encrypted text encrypted with a key specified by the key ID;

a read/write section for extracting the key ID and the first privileged ID from the privileged ID memory;

a first output section for delivering the key ID and the first privileged ID which are extracted; and

a second input section for accepting an input of a second privileged ID, the second privileged ID being a new encrypted text of the tag ID information corresponding to the first privileged ID, the new encrypted text encrypted with the key specified by the key ID, the first privileged ID differing from the second privileged ID;

wherein the read/write section storing the second privileged ID which is input in the rewritable region of the privileged ID memory.

62. A tag device according to claim 61 in which the second input section additionally accepts an input of verification information for the second privileged ID and the read/write section additionally stores the verification information which is input in the rewritable region of the privileged ID memory.

63. A tag device according to claim 62 in which each of the first and second privileged ID is encrypted text of part of to the tag ID information, the part of the tag ID being inherent to each tag device.

64. A tag device according to claim 62 in which an identical key ID is allocated to unrelated tag devices.