Tag privacy protecting method, tag device, backened device, updating device, update requesting device, programs for these devics, and recording medium storing these programs

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 sk, i corresponding to each tag ID information idk is stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices) and in which each tag ID information idn (nε{1, . . . , m} and a corresponding second confidential value sn, 1 are stored in a database memory of a backend apparatus in a manner relating to each other;

• comprising the steps of
• the tag device
• reading out the first confidential value sk, 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(sk, i) in a second calculator;
• delivering the tag output information F2(sk, i) from an output section;
• and reading out the first confidential value sk, 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 (sk, i) as new first confidential value sk, i+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting an input of the tag output information F2(sk, i) at an input section;
• reading out the second confidential value sn, 1 from the database memory, applying to each second confidential value sn, 1 read out j times (jε{0, . . . , jmax}) the first function F1 and subsequently applying the second function F2 thereto in a third calculator;
• comparing the tag output information F2(sk, i) against the result of calculation F2(F1j(sn, 1)) in a comparator;
• in the event the tag output information F2(sk, i) does not match the result of calculation F2(F1j(sn, 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 the tag ID information idn which is related to the second confidential value Sn, 1 corresponding to the matched result of calculation F2(F1j(sn, 1)) from the database memory when the tag output information F2(sk, i) matches the result of calculation F2(F1j(sn, 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, in which a first confidential value sk, i and a first proper value wk corresponding to each tag ID information idk are stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices) in a manner relating to each other and in which each tag ID information idn (nε{1, . . . , m}) and a corresponding second confidential value sn, 1 and a second proper value wn are stored in a database memory of a backend apparatus in a manner relating to each other;

• comprising the steps of
• the tag device
• reading out the first confidential value sk, 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(sk, i) in a second calculator;
• delivering the tag output information F2(sk, i) from an output section;
• reading out the first confidential value sk, i and the first proper value wk 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(sk, i|wk) as a new confidential value sk, i+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting an input of the tag output information F2(sk, i) by an input section;
• reading out the second confidential value sn, 1 and the second proper value wn from the database memory, and applying the second function F2 to Ij(n) where Ij(n)=sn, 1 (j=0) and Ij(n)=F1(Ij−1(n))|idn)(j≧1) to calculate F2(Ij(n)) in a third calculator;
• comparing the tag ID information F2(sk, i) and a result of calculation F2(Ij(n)) in the third calculator in a comparator;
• in the event the tag output information F2(sk, i) does not match the result of calculation F2(Ij(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(sk, i) matches the result of calculation F2(Ij(n)), extracting the tag ID information idn which is related to the second confidential value sn, 1 and the second proper value wn corresponding to the matching result of calculation F2(Ij(n)) from the database memory by a reader.

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 sk, i and a first proper value wk which correspond to each tag ID information idk are stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices) and in which a tag ID information idn (nε{1, . . . , m}) and a second confidential value Sn, 1 and a second proper value wn which correspond thereto are stored in a database memory of a backend apparatus in a manner relating to each other;

• comprising the steps of
• the tag device
• reading out the first confidential value sk, i and the first proper value wk 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(sk, i|wk) in a second calculator;
• delivering the tag output information F2(sk, i|wk) from an output section;
• and reading out the first confidential value sk, 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 sk, i which is read out, and saving a result of such calculation F1(sk, i) as a new first confidential value sk, i in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information F2(sk, i|wk) as an input at an input section at an input section;
• reading out the second confidential value sn, 1 and the second proper value wn from the database memory, applying j times (jε{0, . . . , jmax}) the first function F1 to the second confidential value sn, 1 to determine a bit combination value F1j(sn, i)|wn of a resulting F1j(sn, i) and the second proper value wn, and applying the second function F2 to the bit combination value F1j(sn, i)|wn in a third calculator;
• comparing the tag output information F2(sk, i|wk) against a result of calculation in the third calculator F2(F1j(Sn, i)|wn) in a comparator;
• in the event the tag output information F2(sk, i|wk) does not match the result of calculation F2(F1j(sn, i)|wn), 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(sk, i|wk) matches the result of calculation F2(F1j(sn, i)|wn), extracting the tag ID information idn which is related to the second confidential value sn, 1 and the second proper value wn corresponding to the matching result of calculation F2(F1j(sn, i)|wn) from the database memory by a reader.

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 wk corresponding to each tag ID information idk and a first confidential value si which assumes an identical initial value si for a plurality of tag ID information are stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices), each tag ID information idn(nε{1, . . . , m}) and a corresponding second proper value wn are stored in a database memory of a backend apparatus in a manner relating to each other, and a first result of calculation sj+1 obtained by applying j times (jε{0, . . . , jmax}) a first function F1 to the second confidential value s1 which is used in common by the plurality of tag ID information is stored in a calculated value memory of the backend apparatus;

• comprising the steps of
• the tag device
• reading out the first confidential value si and the first proper value wk 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(si|wk) in a second calculator;
• delivering the tag output information F2(si|wk) from an output section;
• and reading out the first confidential value si from the confidential value memory, applying the first function F1, an inverse image of which is difficult to obtain, to the first confidential value si which is read out, and saves a result of such calculation F1 (si) as a new first confidential value si+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information F2(si|wk) as an input at an input section;
• reading out a result of the first calculation sj+1 and the second proper value wn from the database memory to obtain a bit combination value sj+1|wn thereof, and applying the second function F2 thereto in a third calculator;
• comparing the tag output information F2(si|wk) against a result of the calculation by the third calculator F2(sj+1|wn) in a comparator;
• in the event the tag output information F2(si|wk) does not match the result of the calculation F2(sj+1|wn), 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(si|wk) matches the result of the calculation F2(sj+1|wn), extracting the tag ID information idn which is related to the second proper value wn corresponding to the matching result of calculation F2(sj+1|wn) from the database memory by a reader.

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 eu, vu(uε{1, . . . , d}) corresponding to each tag ID information idk is stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices) and in which a combination of d initial elements fu, 0 comprising one selected from each of d kinds (d≧2) of subgroups αu (uε{1, . . . , d}) and the tag ID information idn 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 the steps of;

• the tag device
• reading out the d elements eu, vu from the confidential value memory to form a bit combination value thereof which represents a confidential value sk, 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 sk, i to generate tag output information ak, i=F2(sk, i) in a second calculator;
• delivering the tag output information ak, i from an output section;
• and extracting at least part of elements eu′, vu′ (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 eu′, vu′, and saving a result of such calculation F1 (eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information ak, i as an input at an input section;
• applying the first function F1 wu times (wuε{1, 2, . . . , max}) to d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn, and applying the second function F2 to a bit combination value of these values F1wu(fu, 0) to determine a calculated value c in a third calculator;
• comparing the tag output information ak, i against the calculated value c in a comparator;
• in the event the tag output information ak, 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 wu;
• and in the event the tag output information ak, i matches the calculated value c, extracting tag ID information idn which is related to the combination of d initial elements fu, 0 corresponding to the calculated value c from the database memory by a reader.

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 eu, vu (uε{1, . . . , d}) which corresponds to each tag ID information idk and a proper value γk which is inherent to each tag ID information idk are stored in a confidential value memory of each tag device k (kε{1, . . . , m}, where m represents a total number of tag devices) and in which a combination of d (d≧2) elements eu, vu (uε{1, . . . , d}) which corresponds to each tag ID information idk and a proper value γk which is inherent to each tag ID information idk are stored in a database memory of a backend apparatus in a manner relating to each other;

• comprising the steps of
• the tag device
• reading out the d elements eu, 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 sk, i which is a bit combination value of the d elements and the proper value to generate tag output information ak, i=F2(sk, i) in a second calculator;
• delivering the tag output information ak, 1 from an output section;
• and extracting at least part of elements eu′, vu′ (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 eu′, vu′, and saving a result of such calculation F1 (eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information ak, i as an input at an input section;
• applying the first function F1 wu times (wuε{1, 2, . . . , max}) to the d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn and applying the second function F2 to a bit combination value of the function values F1wu(fu, 0) and the proper value γn to determine a calculated value c in a third calculator;
• comparing the tag output information ak, i against the calculated value c in a comparator;
• in the event the tag output information ak, i does not match the calculated value c, executing the processings in the third calculator and the comparator again by changing the value of al least part of n and wu;
• and in the event the tag output information ak, i matches the calculated value c, extracting tag ID information idn which is related to the combination the plurality of initial elements fu, 0 corresponding to the calculated value c from the database memory by a reader.

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 eu, 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 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 fu, 0 comprising one selected from each of d kinds (d≧1) of subgroups αu (uε{1, . . . , d}) and tag ID information idn (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 the steps of
• the tag device
• reading out each element eu, 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 sk, i which is a bit combination value of the elements and the manifold value to generate tag output information ak, i=F2(sk, i) in a second calculator;
• delivering the tag output information ak, i from an output section;
• and extracting at least part of elements eu′, vu′ (u′ε{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information ak, i t times, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements eu′, vu′, and saving a result of such calculation F1(eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information ak, i as an input at an input section;
• applying the first function F1 wu times (wuε{1, 2, . . . , max}) to the d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn and applying the second function F2 to a bit combination value of these values F1wu(fu, 0) and the manifold value z to determine a calculated value c in a third calculator;
• comparing the tag output information ak, i against the calculated value c in a comparator;
• in the event the tag output information ak, 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, wu and z;
• and in the event the tag output information ak, i matches the calculated value c, extracting the tag ID information idn which is related to the combination of the d initial elements fu, 0 corresponding to the calculated value c from the database memory by a reader.

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 eu, 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 zu which assumes tu kinds (tu≧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 fu, 0 comprising one selected from each of d kinds (d≧2) of subgroups αu (uε{1, . . . , d}) and tag ID information idn (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 zu is stored in a second manifold value memory of the backend apparatus;

• comprising the steps of
• the tag device
• reading out each element eu, vu from the confidential value memory and reading out either manifold value zu 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 sk, i which is a bit combination value of eu, vu and zu to generate tag output information ak, i=F2(sk, i) in a second calculator;
• delivering the tag output information ak, i from an output section;
• extracting at least part of elements eu, vu (u′ε{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information ak, i some number of times, applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements eu′, vu′, and saving a result of such calculation F1(eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting in a first calculator;
• the backend apparatus
• accepting the tag output information ak, i as an input at an input section;
• applying wu times (wuε{1, 2, . . . , max}) the first function F1 to the d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn, and applying the second function F2 to a bit combination value of these values F1wu(fu, 0) and the manifold value zu to determine a calculated value c in a third calculator;
• comparing the tag output information ak, i against the calculated value c in a comparator;
• in the event the tag output information ak, 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, wu and zu;
• and in the event the tag output information ak, i matches the calculated value c, extracting tag ID information idn which is related to the combination of a plurality of initial elements fu, 0 corresponding to the calculated value c from the database memory by a reader.

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, a mapping 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.

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.

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

• a confidential value memory in which a first confidential value sk, i corresponding to tag ID information idk is stored;
• a second calculator connected to the confidential value memory for reading out the first confidential value sk, 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 sk, i to generate tag output information F2(sk, i);
• an output section for delivering the tag output information F2(sk, i);
• and a first calculator connected to the confidential value memory for reading out the first confidential value sk, 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 (sk, i) as a new first confidential value sk, i+1 in the confidential value memory by overwriting.

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

• a confidential value memory in which a first confidential value sk, i and a first proper value wk which correspond to a tag ID information idk are stored;
• a second calculator connected to the confidential value memory for reading out the first confidential value sk, 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(sk, i);
• an output section for delivering the tag output information F2(sk, i);
• and a first calculator connected to the confidential value memory for reading out the first confidential value sk, i and the first proper value wk 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(sk, i|wk) as a new first confidential value sk, i+1 in the confidential value memory by overwriting.

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

• a database memory in which each tag ID information idn (nε{1, . . . , m}, where m represents a total number of tag devices) and a second confidential value sn, 1 corresponding thereto are related to each other;
• an input section which accepts tag output information F2(sk, i) as an input;
• a third calculator connected to the database memory for reading out the second confidential value sn, 1 from the database memory, applying j times (jε{0, . . . , jmax}) a first function F1 which is used in a tag device to each of the second confidential values sn, 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(sk, i) against a result of calculation in the third calculator F2(F1j(sn, 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(sk, i) and the result of calculation F2(F1j(sn, 1)) do not match;
• and a reader connected to the database memory and operative when the tag output information F2(sk, i) matches the result of the calculation F2(F1j(sn, 1)) to extract the tag ID information idn which is related to the second confidential value sn, 1 corresponding to the matching result of the calculation F2(F1j(sn, 1)) from the database memory.

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

• a database memory in which each tag ID information idn (nε{1, . . . , m}), a corresponding second confidential value sn, 1 and second proper value wn are stored in a manner relating to each other;
• a input section which accepts an input of tag output information F2(sk, i);
• a third calculator connected to the database memory for reading out the second confidential value sn, 1 and the second proper value wn from the database memory and for applying a second function F2 to Ij(n) where Ij(n)=sn, 1(j=0), and Ij(n)=F1(Ij−1(n)|idn) (j≧1) to calculate F2(Ij(n));
• a comparator for comparing the tag output information F2(sk, i) against the result of the calculation in the third calculator F2(Ij(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(sk, i) does not match the result of the calculation F2(Ij(n));
• and a reader for extracting tag ID information idn which is related to the second confidential value sn, 1 and the second proper value wn corresponding to the matched result of calculation F2(Ij(n)) from the database memory when a matching between the tag output information F2(sk, i) and the result of the calculation F2(Ij(n)) is found.

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

• a confidential value memory in which a first confidential value sk, i and a first proper value wk corresponding to tag ID information idk are stored;
• a second calculator connected to the confidential value memory for reading out the first confidential value sk, i and the first proper value wk 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(sk, i wk);
• an output section for delivering the tag output information F2(sk, i|wk)
• and a first calculator connected to the confidential value memory for reading the first confidential value sk, 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 sk, i which is read out and saving a result of such calculation F1(sk, i) as a new first confidential value sk, i+1 in the confidential value memory by overwriting.

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

• a database memory in which each tag ID information idn (nε{1, . . . , m}) and a corresponding second confidential value sn, 1 and second proper value wn are stored in a manner relating to each other;
• an input section which accepts an input of tag output information F2(sk, i|wk);
• a third calculator connected to the database memory for reading out the second confidential value sn, 1 and the second proper value wn from the database memory, applying j times (jε{0, . . . , jmax}) a first function F1 which is used in a tag device to the second confidential value sn, 1, determining a bit combination value F1j(sn, i)|wn of a result of application F1j(sn, i) and the second proper value wn, and applying a second function F2 which is used in the tag device to the bit combination value F1(sn, i|wn);
• a comparator for comparing the tag output information F2(sk, i|wk) against a result of calculation in the third calculator F2(F1j(sn, i)|wn);
• 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(sk, i|wk) does not match the result of the calculation F2(F1j(sn, i)|wn);
• and a reader connected to the database memory for extracting the tag ID information idn which is related to the second confidential value sn, 1 and the second proper value wn corresponding to the matched result of calculation F2(F1j(sn, i)|wn) when a matching between the tag output information F2(sk, i|wk) and the result of the calculation F2(F1j(sn, i)|wn) is found.

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

• a confidential value memory in which a first proper value wk corresponding to each tag ID information idk and a first confidential value si which assumes an equal initial value si 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 si and the first proper value wk 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(s1 i wk);
• an output section for delivering the tag output information F2(si|wk);
• and a first calculator connected to the confidential value memory for reading out the first confidential value si from the confidential value memory, applying a first function F1, an inverse image of which is difficult obtain, to the first confidential value si which is read out and saving a result of such calculation F1(si) as a new first confidential value si+1 in the confidential value memory by overwriting.

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

• a database memory in which each tag ID information idn (nε{1, . . . , m}) and a corresponding second proper value wn are stored in a manner relating to each other;
• a calculated value memory in which first results of calculation sj+1 are stored which are obtained by applying j times (jε{0, . . . , jmax}) a first function which is used in a tag device to a second confidential value s1 which is used in common for a plurality of tag ID information;
• an input section which accepts an input of tag output information F2(si|wk);
• a third calculator connected to the database memory for reading out the first result of calculation sj+1 and the second proper value wn from the database memory to obtain a bit combination value thereof sj+1|wn and for applying a second function F2 which is used in the tag device thereto;
• a comparator for comparing the tag output information F2(si|wk) and the result of calculation in the third calculator F2(sj+1|wn);
• 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(si|wk) does not match the result of calculation F2(sj+1|wn);
• and a reader connected to the database memory for extracting the tag ID information idn which is related to the second proper value wn corresponding to the matched result of calculation F2(sj+1|wn) when a matching between the tag output information F2(si|wk) and the result of calculation F2(sj+1|wn) is found.

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 eu, vu (uε{1, . . . , d}) which corresponds to each tag ID information idk is stored;
• a second calculator connected to the confidential value memory for reading out the d elements eu, 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 sk, i which is a bit combination value of the d elements to generate tag output information ak, i=F2(sk, i);
• an output section for delivering the tag output information ak, i;
• and a first calculator connected to the confidential value memory for extracting at least part of elements eu′, vu′ (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 eu′, vu′ and for saving a result of such calculation F1 (eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting.

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

• a database memory in which a combination of d initial elements fu, 0 comprising one selected from each of d kinds (d≧2) of subgroups αu(uε{1, . . . , d}), and tag ID information idn 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 ak, i;
• a third calculator for applying wu times (wuε{1, 2, . . . , max}) a first function F1 to the d initial elements fu, 0 (uε{1, . . . , d}) which correspond to the tag ID information idn and for applying a second function F2 to a bit combination value of these values F1wu(fu, 0) to determine a calculated value c;
• a comparator for comparing the tag output information ak, 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 wu when the tag output information ak, i does not match the calculated value c;
• and a reader connected to the database memory for extracting tag ID information idn which is related to the combination of d initial elements fu, 0 corresponding to the calculated value c when the tag output information ak, i matches the calculated value c.

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 eu, vu (uε{1, . . . , d}) which correspond to each tag ID information idk and a proper value γk which is inherent to each tag ID information idk are stored;
• a second calculator connected to the confidential value memory for reading out the d elements eu, 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 sk, i which is a bit combination value of the d elements and the proper value to generate tag output information ak, i=F2(sk, i);
• an output section for delivering the tag output information ak, i;
• and a first calculator connected to the confidential value memory for extracting at least part of the elements eu′, vu′ (u′ε{1, . . . , d}) from the confidential value memory, applying a first function F 1, an inverse image of which is difficult to obtain, to the extracted elements eu′, vu′ and for saving a result of such calculation F1 (eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting;

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

• a database memory in which a combination of d initial elements fu, 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 idn (nε{1, . . . , m}) and each tag ID information idn are stored in a manner relating to each other;
• an input section for accepting an input of tag output information ak, i;
• a third calculator for applying wu times (wuε{1, 2, . . . , max}) a first function F1 to the d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn and for applying a second function F2 to a bit combination value of these values F1wu(fu, 0) and the proper value γn to determine a calculated value c;
• a comparator for comparing the tag output information ak, 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 wu when the tag output information ak, i does not match the calculated value c;
• and a reader connected to the database memory for extracting tag ID information idn which is related to the combination of a plurality of initial elements fu, 0 corresponding to the calculated value c from the database memory when a matching between the tag output information ak, i and the calculated value c is found.

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

• a confidential value memory in which d (d≧1) elements eu, 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 eu, 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 sk, i which is a bit combination value of the elements and the manifold value to generate tag output information ak, i=F2(sk, i);
• an output section for delivering the tag output information ak, i;
• and a first calculator connected to the confidential value memory for extracting at least part of elements eu′, vu′(u′ε{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information ak, i t times, for applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements eu′, vu′ and for saving a result of such calculation F1 (eu′, vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting.

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

• a database memory in which a combination of d initial elements fu, 0 comprising one selected from each of d kinds (d≧1) of subgroup αu (uε{1, . . . , d}) and a tag ID information idn (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 ak, i;
• a third calculator for applying wu times (wuε{1, 2, . . . , max}) a first function F1 to the d initial elements fu, 0 (uε{1, . . . , d}) in the database memory which correspond to the tag ID information idn and for applying a second function F2 to a bit combination value of these values F1wu(fu, 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 ak, 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, wu and z when the tag output information ak, i does not match the calculated value c;
• and a reader connected to the database memory for extracting the tag ID information idn which is related to the combination of d initial elements fu, 0 corresponding to the calculated value c from the database memory when a matching between the tag output information ak, i and the calculated value c is found.

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

• a confidential value memory in which d (d≧2) elements eu, vu (uε{1, . . . , d}) are stored;
• a first manifold value memory in which a manifold value zu which assumes tu kinds (tu≧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 eu, vu from the confidential value memory and for reading out either manifold value zu 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 sk, i which is a bit combination value of these ev, vu and zu to generate tag output information ak, i=F2(sk, i);
• an output section for delivering the tag output information ak, i;
• and a first calculator connected to the confidential value memory for extracting at least part of the elements eu′, vu′ (u′ε{1, . . . , d}) from the confidential value memory each time the output section delivers the tag output information ak, i some number of times, for applying a first function F1, an inverse image of which is difficult to obtain, to the extracted elements eu′, vu′, and for saving a result of such calculation F1(eu′vu′) as new elements eu′, vu′+1 in the confidential value memory by overwriting.

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

• a database memory in which a combination of d initial elements fu, 0 which comprises one selected from each of d kinds (d≧1) of subgroups αu (uε{1, . . . , d}) and tag ID information idn (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 zu which assumes tu kinds (tu≧2) of values for each u is stored;
• an input section for accepting an input of tag output information ak, i;
• a third calculator for applying wu times (wuε{1, 2, . . . , max}) a first function F1 which is used in a tag device to the d initial elements fu, 0 (uε{1, . . . , d}) corresponding to the tag ID information idn and for applying a second function F2 which is used in the tag device to a bit combination value of these values F1wu(fu, 0) and the manifold value zu to determine a calculated value c;
• a comparator for comparing the tag output information ak, 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, wu and z;
• and a reader connected to the database memory for extracting tag ID information idn which is related to the combination of the d initial elements fu, 0 corresponding to the calculated value c from the database memory when a matching between the tag output information ak, i and the calculated value c is found.

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 sidh which is formed by privileging respective tag ID information idh is stored in a confidential value memory of each tag device;

• comprising the steps of
• the tag device
• reading out the privileged ID information sidh stored in the confidential value memory in a read/write section;
• and delivering the privileged ID information sidh to an updater which is provided externally of each tag device from a first output section;
• the updater
• accepting an input of the privileged ID information sidh at a first input section;
• generating new privileged ID information sidh′, the association of which with the privileged ID information sidh is difficult to follow in an updating section;
• delivering the new privileged ID information sidh′ to the tag device from a second output section;
• the tag device further
• accepting an input of the new privileged ID information sidh′ at a second input section;
• the read/write section of the tag device storing the new privileged ID information sidh′ in the confidential value memory.

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 sidh which is a random value rh related to each tag ID information idh 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 idh and privileged ID information sidh which is the random value rh related to the tag ID information idh 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 the steps of
• the tag device h
• reading out the privileged ID information sidh stored in the confidential value memory thereof in a first read/write section;
• and delivering the privileged ID information sidh to the updater from a first output section;
• the updater
• accepting an input of the privileged ID information sidh at a first input section;
• generating a new random value rh′ in a random value generator;
• selecting tag ID information idh corresponding to the privileged ID information sidh which is accepted as the input from the privileged ID memory and storing the new random value rh′ in the privileged ID memory in a manner relating to new privileged ID information sidh′ in a second read/write section;
• and delivering the new privileged ID information sidh′ to the tag device h from a second output section;
• the tag device h further
• accepting an input of the new privileged ID information sidh′ at a second input section;
• the read/write section of the tag device storing the new privileged ID information sidh′ in the confidential value memory.

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 sidh 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 sidh including a first encrypted text according to a common key encryption technique which corresponds to each tag ID information idh and key ID information kidj of a common key kj used in the encryption (jε{1, . . . , n}, where n represents a total number of tag devices), and each key ID information kidj are stored and each common key kj in a key memory of an updater which is provided externally of each tag device h in a manner relating to each other;

• comprising the steps of
• the tag device h
• reading out the privileged ID information sidh stored in the confidential value memory thereof in a first read/write section;
• and delivering the privileged ID information sidh to an updater from a first output section;
• the updater
• accepts an input of the privileged ID information sidh at a first input section;
• extracting the common key kj corresponding to the key ID information kidj included in the privileged ID information sidh from the key memory by a second read/write section;
• decrypting the first encrypted text using the common key kj extracted by the second read/write section to extract tag ID information idh by an ID extractor;
• generating a second encrypted text, the association of which with the first encrypted text is difficult to follow, using the tag ID information idh extracted by the ID extractor and the common key kj which is used in the extraction in an encryptor;
• and delivering new privileged ID information sidh′ including the second encrypted text and the key ID information kidj of the common key kj to the tag device h from a second output section;
• the tag device h further
• accepting an input of the new privileged ID information sidh′ at a second input section;
• the first read/write section of the tag device storing the new privileged ID information sidh′ in the confidential value memory.

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 sidh 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 sidh including a first encrypted text according to a pubic key encryption technique which corresponds to each tag ID information idh and key ID information kidj for a key pair (skj, pkj) (where skj represents a secret key and pkj represents a public key, jε{1, . . . , n}, where n represents a total number of tag devices), and each key ID information kidj and each key pair (skj, pkj) in a key memory of an updater which is provided externally of each tag device h in a manner relating to each other;

• comprising the steps of
• the tag device h
• reading out the privileged ID information sidh stored in the confidential value memory in a first read/write section;
• and delivering the privileged ID information sidh to an updater from a first output section;
• the updater
• accepting an input of the privileged ID information sidh at a first input section;
• extracting the key pair (skj, pkj) which corresponds to the key ID information kidj which is included in the privileged ID information sidh accepted as the input to the first input section by a second read/write section;
• decrypting the first encrypted text using the secret key skj extracted by the second read/write section to extract the tag ID information idh by an ID extractor;
• generating a second encrypted text, the association of which with the first encrypted text is difficult to follow, using the tag ID information idh extracted by the ID extractor and the public pkj which is extracted by the second read/write section by an encryptor;
• and delivering new privileged ID information sidh′ including the second encrypted text and the key ID information kidj of the key pair (skj, pkj) to the tag device h from a second output section;
• the tag device h further
• accepting an input of the new privileged ID information sidh′ at a second input section;
• the read/write section storing the new privileged ID information sidh′ in the confidential value memory.

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 sidh 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 sidh including a first encrypted text according to re-encryptable public key encryption technique which corresponds to each tag ID information idh and key ID information kidj of the public key pkj (jε{1, . . . , n}, where n represents a total number of keys), each key ID information kidj and each public key pkj 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 the steps of
• the tag device h
• reads out the privileged ID information sidh stored in the confidential value memory in a first read/write section;
• and delivers the privileged ID information sidh to an updater from a first output section;
• the updater comprising
• accepting an input of the privileged ID information sidh at a first input section;
• extracting the public key pkj which corresponds to the key ID information kidj included in the privileged ID information sidh 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 sidh using the public key pkj extracted by the second read/write section to generate a second encrypted text, the association of which with the first encrypted text is difficult to follow, by an encryptor;
• and for delivering new privileged ID information sidh′ including the second encrypted text and the key ID information kidj of the public key pkj to the tag device h from a second output section;
• the tag device h further
• accept an input of the new privileged ID information sidh′ at a second input section;
• the read/write section storing the new privileged ID information sidh′ in the confidential value memory.

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 sidh which has privileged each tag ID information idh 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 the steps of
• the tag device h
• reading out the privileged ID information sidh stored in the confidential value memory by a first read/write section;
• and delivering the privileged ID information sidh to a first updater which is provided externally of the tag device h from a first output section;
• the first updater
• accepting an input of the privileged ID information sidh at a first input section;
• determining tag ID information idh from the privileged ID information sidh by an ID extractor;
• and delivering the tag ID information idh to a second updater which is provided externally of the tag device h from a second output section;
• the second updater
• accepting an input of the tag ID information idh at a third input section;
• generating new privileged ID information sidh′ which has privileged the tag ID information idh by an encryptor;
• and delivering the new privileged ID information sidh′ to the tag device h from a third output section;
• the tag device h further accepting an input of the new privileged ID information sidh′ at a second input section;
• the read/write section storing the new privileged ID information sidh′ in the confidential value memory.

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 idh and privileged ID information sidh which is a random value rh which corresponds to the tag ID information idh in a manner relating to each other;
• a first input section which accepts an input of the privileged ID information sidh which is delivered from the tag device;
• a random value generator for generating a new random value rh′;
• a second read/write section connected to the privileged ID memory for selecting tag ID information idh which corresponds to the privileged ID information sidh 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 rh′ as new privileged ID information sidh′ to be stored in the privileged ID memory;
• and a second output section for delivering the new privileged ID information sidh′ to the tag device h.

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 kidj (jε{1, . . . , n}, where n represents a total number of keys) and each common key kj 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 sidh which includes a first encrypted text according to the common key encryption technique which corresponds to the tag ID information idh and key ID information kidj of the common key kj which is used in the encryption;
• a second read/write section connected to the key memory for extracting the common key kj which corresponds to the key ID information kidj which is included in the privileged ID information sidh from the key memory;
• an ID extractor for decrypting the first encrypted text using the common key kj which is extracted by the second read/write section to extract tag ID information idh;
• an encryptor for generating a second encrypted text, the association of which with first encrypted text is difficult to follow, using the tag ID information idh extracted by the ID extractor and the common key kj which is used in the extraction;
• and a second output section for delivering new privileged ID information sidh′ which includes the second encrypted text and the key ID information kidj for the common key kj to the tag device h.

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 kidj (jε{1, . . . , n}, where n represents a total number of keys) and each key pair (skj, pkj) (skj represents a secret key and pkj a public key) in a manner relating to each other;
• a first input section for accepting an input of privileged ID information sidh which includes a first encrypted text according to a public key encryption technique which corresponds to tag ID information idh and key ID information kidj for the public key pkj which is used in the encryption;
• a second read/write section connected to the key memory for extracting the key pair (skj, pkj) which corresponds to the key ID information kidj which is included in the privileged ID information sidh 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 skj extracted by the second read/write section to extract tag ID information idh;
• an encryptor for generating a second encrypted text, the association of which with the first encrypted text is difficult to follow, using the tag ID information idh extracted by the ID extractor and the public key pkj extracted by the second read/write section;
• and a second output section for delivering new privileged ID information sidh′ which includes the second encrypted text and the key ID information kidj for the key pair (skj, pkj) to the tag device h.

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 kidj (jε{1, . . . , n}, where n represents a total number of keys) and each public key pkj in a manner relating to each other;
• a first input section for accepting an input of privileged ID information sidh which includes a first encrypted text according to re-encryptable public key encryption technique which corresponds to tag ID information idh and key ID information kidj for the public key pkj;
• a second read/write section connected to the key memory for extracting the public key pkj which corresponds to the key ID information kidj which is included in the privileged ID information sidh 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 sidh using the public key pkj extracted by second read/write section to generate a second encrypted text, the association of which with the first encrypted text is difficult to follow;
• and a second output section for delivering new privileged ID information sidh′ which includes the second encrypted text and the key ID information kidj for the public key pkj to the tag device h.

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 re-encryptable encrypted texts corresponding to an identical tag ID information idh, 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.

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 re-encryptable encrypted texts corresponding to an identical tag ID information idh, 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.

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 key ID and a key are stored in a key memory in a manner relating to each other, the tag device comprises 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;

• comprising the steps of
• the tag device
• extracting the key ID and the first privileged ID from the privileged ID memory by a read/write section;
• and delivering the extracted key ID and first privileged ID to an updater from a first output section;
• the updater
• accepting the key ID and the first privileged ID as inputs at a first input section;
• 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;
• generating a second privileged ID, the association of which with the first privileged ID is difficult to follow, using the key extracted by the first key extractor and the first privileged ID which is input to the first input section in a privileged ID updating section;
• and delivering the second privileged ID from a second output section;
• the tag device further
• accepting an input of the second privileged ID at a second input section;
• the read/write section storing the second privileged ID in the rewritable region of the privileged ID memory.

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;
• 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 association of which with the first privileged ID is difficult to follow;
• the read/write section storing the second privileged ID which is input in the rewritable region of the privileged ID memory.