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, where h ∈ {1,..., m}, and m represents a total number of tag devices, which is formed by privileging respective tag ID information id h, is stored in a confidential value memory of each tag device; comprising the steps of reading out the privileged ID information sid h stored in the confidential value memory by a first read/write section of the tag device in response to a read demand; delivering the privileged ID information sid h to a security server 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 security server; delivering new privileged ID information sid h ' to the tag device from a second output section of the security server; 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 by the first read/write section; wherein the tag device outputs the new privileged ID information sid h ' in response to a read demand after the new privileged ID information sid h ' is stored in the confidential value memory; characterized in that: the privileged ID information sid h includes a first encrypted text according to a common key encryption technique, which corresponds to the tag ID information id h and key ID information kid j of a common key k j used in the encryption, where j ∈ {1,..., n}, and n represents a total number of keys, and the key ID information kid j; pieces of key ID information kid j and corresponding common keys k j are stored in a key memory of the security server in a manner relating to each other; and the method further comprises the steps of 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 security server; decrypting the first encrypted text using the common key k j extracted by the second read/write section to extract the tag ID information id h by an ID extractor of the security server; and generating a second encrypted text using the tag ID information id h and the common key k j, in an encryptor of the security server, by means of probabilistic encryption; wherein the new privileged ID information sid h ' includes the second encrypted text and the key ID information kid j of the common key k j. the privileged ID information sid h includes a first encrypted text according to a common key encryption technique, which corresponds to the tag ID information id h and key ID information kid j of a common key k j used in the encryption, where j ∈ {1,..., n}, and n represents a total number of keys, and the key ID information kid j; pieces of key ID information kid j and corresponding common keys k j are stored in a key memory of the security server in a manner relating to each other; and the method further comprises the steps of 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 security server; decrypting the first encrypted text using the common key k j extracted by the second read/write section to extract the tag ID information id h by an ID extractor of the security server; and generating a second encrypted text using the tag ID information id h and the common key k j, in an encryptor of the security server, by means of probabilistic encryption; wherein the new privileged ID information sid h ' includes the second encrypted text and the key ID information kid j of the common key k j.