ANONYMOUS SIGNATURE SYSTEM, SIGNATURE GENERATION APPARATUS, ANONYMOUS SIGNATURE GENERATION APPARATUS, VERIFICATION APPARATUS, ANONYMOUS SIGNATURE METHOD AND PROGRAM

Abstract

An anonymous signature system in which a signature σ is anonymized by an agent specified by a signer, includes computers each including a memory and a processor configured to, from a security parameter, generate a system parameter ρ independent of the agent; from ρ, generate an agent secret key w and an agent public key g.sub.A; from ρ, generate a secret key x and a public key y of the signer; from x, a message m on which σ is to be put, and g.sub.A, generate σ to be put on m; from an identifier i of the signer, w, σ, a ring L representing a group to which the signer belongs, a list y.sub.L of public keys y of signers in L, and m, generate a ring signature σ′ by anonymizing σ; and from L, y.sub.L, m, and σ′, output a verification result b form.

Claims

1. An anonymous signature system in which a signature σ is anonymized by an agent specified by a signer, the system comprising: one or more computers each including a memory and a processor configured to take as input a security parameter, to generate a system parameter ρ that does not depend on the agent; take as input the system parameter ρ, to generate an agent secret key w and an agent public key g.sub.A; take as input the system parameter ρ, to generate a secret key x and a public key y of the signer; take as input the secret key x, a message m on which the signature σ is to be put, and the agent public key g.sub.A of the agent specified by the signer, to generate the signature σ to be put on the message m; take as input an identifier i of the signer, the agent secret key w, the signature σ, a ring L representing a group to which the signer belongs, a list y.sub.L of public keys y of signers belonging to the ring L, and the message m, to generate a ring signature σ′ by anonymizing the signature σ; and take as input the ring L, the list y.sub.L, the message m, and the ring signature σ′, to output a verification result b for the message m.

2. The anonymous signature system according to claim 1, wherein the processor is further configured to generate a generator g of a Trapdoor DDH group by inputting a common reference character string crs generated based on the security parameter into a predetermined hash function, and to generate the system parameter ρ based on the generator g.

3. A signature generation apparatus connected to a system parameter generation apparatus through a network, the system parameter generation apparatus generating a system parameter ρ that does not depend on an agent that anonymizes a signature σ though anonymizable signature, the signature generation apparatus comprising: a memory and a processor configured to take as input the system parameter ρ generated by the system parameter generation apparatus, to generate a secret key x and a public key y of a signer; take as input the secret key x, a message m on which the signature σ is to be put, and an agent public key g.sub.A of an agent specified by the signer, to generate the signature σ to be put on the message m; and transmit the message m and the signature σ to an anonymous signature generation apparatus with which the agent anonymizes the signature σ.

4. An anonymous signature generation apparatus connected to a system parameter generation apparatus through a network, the system parameter generation apparatus generating a system parameter ρ that does not depend on an agent that anonymizes a signature σ through anonymizable signature, the anonymous signature generation apparatus comprising: a memory and a processor configured to take as input the system parameter ρ generated by the system parameter generation apparatus, to generate an agent secret key w and an agent public key g.sub.A; and take as input the signature σ, a message m corresponding to the signature σ, an identifier i of a signer of the signature σ, the agent secret key w, a ring L representing a group to which the signer belongs, and a list y.sub.L of public keys y of signers belonging to the ring L, to generate a ring signature σ′ by anonymizing the signature σ.

5. (canceled)

6. (canceled)

7. A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which when executed, cause a computer including a memory and a processor to execute respective operations in the signature generation apparatus according to claim 3, or respective operations in the anonymous signature generation apparatus according to claim 4.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0010] FIG. 1 shows an example of an overall configuration of an anonymous signature system in an embodiment of the present invention.

[0011] FIG. 2 is a flowchart showing an example of system parameter generation processing in the embodiment of the present invention.

[0012] FIG. 3 is a flowchart showing an example of setup processing in the embodiment of the present invention.

[0013] FIG. 4 is a flowchart showing an example of key generation processing in the embodiment of the present invention.

[0014] FIG. 5 is a flowchart showing an example of signature generation processing in the embodiment of the present invention.

[0015] FIG. 6 is a flowchart showing an example of anonymization processing in the embodiment of the present invention.

[0016] FIG. 7 is a flowchart showing an example of verification processing in the embodiment of the present invention.

[0017] FIG. 8 shows an example of a hardware configuration of a signature generation apparatus, an anonymous signature generation apparatus, a signature verification apparatus, and a system parameter generation apparatus in the embodiment of the present invention.

DESCRIPTION OF EMBODIMENTS

[0018] Hereinafter, an embodiment of the present invention will be described. In the embodiment of the present invention, an anonymous signature system 1 will be described in which regeneration of a key (a public key of a signer) following a change of specified agent is not needed in agent-specified anonymizable signature.

[0019] <Notation>

[0020] In the embodiment of the present invention, the following notations are introduced. [0021] Assigning an element selected uniformly at random from a set X to x is denoted as follows.

[00001]$\begin{array}{cc}x\stackrel{\$}{\leftarrow }X\mathrm{or}X\stackrel{\$}{.fwdarw.}x& \left[\mathrm{Math}.1\right]\end{array}$

This is also denoted as “x←.sup.sX” or “X.fwdarw..sup.sx” hereinafter. [0022] Assigning an output of a probabilistic polynomial time algorithm Alg( ) to x is denoted as follows.

[00002]$\begin{array}{cc}x\stackrel{\$}{\leftarrow }\mathrm{Alg}\left(\right)\mathrm{or}x\stackrel{\$}{.fwdarw.}\mathrm{Alg}\left(\right)& \left[\mathrm{Math}.1\right]\end{array}$

This is also denoted as “x←.sup.sAlg( )” or “Alg( ).fwdarw..sup.sx”. [0023] Defining y by x or substituting x into y is denoted as “y←x” or “x.fwdarw.y”. However, “.fwdarw.” or “←” may represent a mapping (or a function) depending on the context.

[0024] When “.fwdarw.” or “←” represents a mapping, it will be explicitly noted that the symbol represents a mapping (or a function).

[0025] <Anonymizable Signature>

[0026] First, anonymizable signature, which is a conventional technology, will be described. It is assumed that k∈N (N is a set of all natural numbers) is a safe parameter, and that M={0, 1, . . . } is a set of signers. A subset L⊂M of the set of signers is referred to as a ring. Moreover, it is assumed that an identifier (for example, a signer ID or the like) of a signer is i, and that a private key and a public key of a signer with an identifier i is x.sub.i and y.sub.i, respectively. However, when the identifier i of a signer is not taken into consideration, a private key and a public key are simply denoted as x and y, respectively.

[0027] Further, for simplicity, it is defined, for any sign “a” and a ring L, that a.sub.L=(a.sub.i).sub.i∈L hereinafter. In other words, for example, when L={L0, L1, . . . }, then a.sub.L=(a.sub.L0, a.sub.L1, . . . ).

[0028] At this time, an anonymizable signature scheme Σ is constituted with four probabilistic polynomial time algorithms (KeyGen, Sign, Anonymize, Verify) that satisfy a construction given below. [0029] Key generation algorithm KeyGen(1.sup.k).fwdarw..sup.s(x, y): A probabilistic polynomial time algorithm that takes as input a safe parameter 1.sup.k, and outputs a private key x and a public key y. [0030] Signature algorithm Sign(x, m).fwdarw..sup.sr: A probabilistic polynomial time algorithm that takes as input a private key x and a message m, and outputs a signature r. The message m is an object onto which the signature r is to be put. [0031] Anonymization algorithm Anonymize(i, r, L, y.sub.L, m).fwdarw..sup.sσ or ⊥: A probabilistic polynomial time algorithm that takes as input an identifier i of a signer, a ring L ⊂M, a list y.sub.L of public keys of signers belonging to the ring L, and a message m, and outputs a ring signature σ or reject ⊥. The ring signature σ is also referred to as an anonymous signature σ. As for the public key list y.sub.L, y.sub.L=(y.sub.k).sub.k∈L. [0032] Verification algorithm Verify(L, y.sub.L, m, σ).fwdarw..sup.s0 or 1: A probabilistic polynomial time algorithm that takes as input a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m, and a ring signature σ, and outputs a single bit b∈{0, 1}. For example, “b=0” represents failure in verification, and “b=1” represents success in verification. [0033] Construction: For a message m∈{0, 1}* with any polynomial length, a ring L⊂M with any polynomial length, and an identifier i∈L of any signer, a probability

[00003]$\begin{array}{cc}\mathrm{Pr}[\mathrm{Verify}(L,y_L,m,\mathrm{Anonymize}\left(\mathrm{Sign}\left(x_i,m\right),L,y_L,m\right))=0|{\forall }_j\in L,\left(x_j,y_j\right)\stackrel{\$}{\leftarrow }\mathrm{KeyGen}\left(1^k\right)]& \left[\mathrm{Math}.3\right]\end{array}$

is negligible with respect to k.

[0034] As described above, to ensure anonymity of a signer, a signature r has to be private between the signer and an agent. That is to say, if an attacker obtains the signature r due to leakage, the attacker, similarly to the agent, can find that the signer has put the signature r. Accordingly, agents need to securely manage signatures entrusted by signers as secrets. Generally, in many cases, an agent is entrusted with many signatures by many signers, and a quantity of secrets to be securely managed increases in proportion to the number of signatures entrusted. Here, an agent is, for example, a third party that keeps and manages signatures.

[0035] For a specific configuration of the above-described conventional anonymizable signature, for example, Non-Patent Literature 1 mentioned above can be referenced.

[0036] <Agent-Specified Anonymizable Signature>

[0037] Next, agent-specified anonymizable signature, which is a conventional technology, will be described. An agent-specified anonymizable signature scheme Σ is constituted with five probabilistic polynomial time algorithms (Setup, KeyGen, Sign, Anonymize, Verify) that satisfy a construction given below. [0038] Agent key generation algorithm Setup(1.sup.k).fwdarw..sup.s(w, ρ): A probabilistic polynomial time algorithm that takes as input a safe parameter 1.sup.k, and outputs an agent private key w and a system parameter ρ. The system parameter ρ is common reference information known to participants (signers) who participate in the agent-specified anonymization signature scheme Σ, and is generated and made public by each agent. The agent private key w is private information used by an agent to anonymize a signature r. [0039] Key generation algorithm KeyGen(ρ).fwdarw..sup.s(x, y): A probabilistic polynomial time algorithm that takes as input a system parameter ρ, and outputs a private key x and a public key y. In other words, the key generation algorithm KeyGen(ρ) takes as input a system parameter ρ made public by an agent specified by a signer, among one or more agents, and outputs a private key x and a public key y. [0040] Signature algorithm Sign(x, m).fwdarw..sup.sr: A probabilistic polynomial time algorithm that takes as input a private key x and a message m, and outputs a signature r. [0041] Anonymization algorithm Anonymize(i, w, r, L, y.sub.L, m).fwdarw..sup.sσ or ⊥: A probabilistic polynomial time algorithm that takes as input an identifier i of a signer, a signature r of the signer, a ring L⊂M, a list y.sub.L of public keys of signers belonging to the ring L, a message m corresponding to the signature r, and an agent private key w, and outputs a ring signature σ or reject ⊥. The ring signature σ is also referred to as an anonymous signature. [0042] Verification algorithm Verify(L, y.sub.L, m, σ).fwdarw..sup.s0 or 1: A probabilistic polynomial time algorithm that takes as input a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m, and a ring signature σ, and outputs a single bit b∈{0, 1}. For example, “b=0” indicates that the message m is invalid, and “b=1” indicates that the message m is valid. [0043] Construction: For a message m∈{0, 1}* with any polynomial length, a ring L⊂M with any polynomial length, and an identifier i∈L of any signer, a probability

[00004]$\begin{array}{cc}\mathrm{Pr}\left[\mathrm{Verify}\left(L,y_L,m,\sigma \right)=0|\begin{array}{c}\left(w,\rho \right)\stackrel{\$}{\leftarrow }\mathrm{Setup}\left(1^k\right),\\ \forall j\in L,\left(x_j,y_j\right)\stackrel{\$}{\leftarrow }\mathrm{KeyGen}\left(\rho \right),\\ r\stackrel{\$}{\leftarrow }\mathrm{Sign}\left(x_i,m\right),\\ \sigma \stackrel{\$}{\leftarrow }\mathrm{Anonymize}\left(i,w,r,L,y_L,m\right)\end{array}\right]& \left[\mathrm{Math}.4\right]\end{array}$

is negligible with respect to k.

[0044] In the above-described agent-specified anonymizable signature, even if a signature r is leaked to an attacker, it is computationally difficult to identify which signature the signature r is, in terms of which private key x.sub.i is used to create the signature, unless an agent private key w is leaked. In other words, in the agent-specified anonymizable signature, since the agent private key w is required to anonymize the signature r, only an agent specified by a signer can perform signature verification and anonymization. Accordingly, in the agent-specified anonymizable signature, anonymity of the signature r can be ensured unless the agent private key w is leaked.

[0045] For a specific configuration of the above-described agent-specified anonymizable signature, for example, Non-Patent Literature 1 mentioned above can be referenced.

[0046] <Agent-Independent Agent-Specified Anonymizable Signature>

[0047] In the embodiment of the present invention, an agent-specified anonymizable signature (also referred to as “agent-independent agent-specified anonymizable signature”) will be described, as an improvement of the above-described agent-specified anonymizable signature, to eliminate regeneration of a key (a public key of a signer) following a change of specified agent.

[0048] Meanwhile, for example, in the specific configuration of the agent-specified anonymizable signature according to Non-Patent Literature 1 mentioned above, a system parameter ρ is configured by using a generator g generated by an agent, and a signer performs generation of a private key x and a public key y and generation of a signature r by using the system parameter ρ. Accordingly, when the specified agent is changed, the signer needs to regenerate a public key y.

[0049] The agent-independent agent-specified anonymizable signature is therefore configured such that a generator g whose discrete logarithm is unknown to anyone is generated by using a hash value of a common reference character string crs that does not depend on an agent, and a system parameter ρ is configured from the generator g. Thus, in the agent-independent agent-specified anonymizable signature, regeneration of a public key y can be eliminated even when the specified agent is changed.

[0050] An agent-independent agent-specified anonymizable signature scheme Σ is constituted with six probabilistic polynomial time algorithms (CrsGen, Setup, KeyGen, Sign, Anonymize, Verify) that satisfy a construction given below. [0051] Common reference information generation algorithm CrsGen(1.sup.k).fwdarw..sup.sρ: A probabilistic polynomial time algorithm that takes as input a safe parameter 1.sup.k, and outputs a system parameter ρ. The system parameter ρ is generated from a generator g that is generated based on a hash value of a common reference character string crs. [0052] Agent key generation algorithm Setup(ρ).fwdarw..sup.s(w, g.sub.A): A probabilistic polynomial time algorithm that takes as input a system parameter ρ, and outputs an agent private key w and an agent public key g.sub.A. [0053] Key generation algorithm KeyGen(ρ).fwdarw..sup.s(x, y): A probabilistic polynomial time algorithm that takes as input a system parameter ρ, and outputs a private key x and a public key y. [0054] Signature algorithm Sign(x, m, g.sub.A).fwdarw..sup.sσ: A probabilistic polynomial time algorithm that takes as input a private key x, a message m, and an agent public key g.sub.A, and outputs a signature σ. [0055] Anonymization algorithm Anonymize (i, w, σ, L, y.sub.L, m).fwdarw..sup.sσ′ or ⊥: A probabilistic polynomial time algorithm that takes as input an identifier i of a signer, an agent private key w, a signature σ of the signer, a ring L⊂M, a list y.sub.L of public keys of signers belonging to the ring L, and a message m corresponding to the signature σ, and outputs a ring signature σ′ or reject ⊥. The ring signature σ is also referred to as an anonymous signature. [0056] Verification algorithm Verify(L, y.sub.L, m, σ′).fwdarw..sup.s0 or 1: A probabilistic polynomial time algorithm that takes as input a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m, and a ring signature σ′, and outputs a single bit b∈{0, 1}. For example, “b=0” indicates that the message m is invalid, and “b=1” indicates that the message m is valid. [0057] Construction: For a message m∈{0, 1}* with any polynomial length, a ring L⊂M with any polynomial length, and an identifier i∈L of any signer, a probability

[00005]$\begin{array}{cc}\mathrm{Pr}\left[\mathrm{Verify}\left(L,y_L,m,{\sigma }^{\prime }\right)=0|\begin{array}{c}\rho \stackrel{\$}{\leftarrow }\mathrm{CrsGen}\left(1^k\right),\\ \left(w,g_A\right)\stackrel{\$}{\leftarrow }\mathrm{Setup}\left(\rho \right),\\ \forall j\in L,\left(x_j,y_j\right)\stackrel{\$}{\leftarrow }\mathrm{KeyGen}\left(\rho \right),\\ \sigma \stackrel{\$}{\leftarrow }\mathrm{Sign}\left(x_i,m,g_A\right),\\ {\sigma }^{\prime }\stackrel{\$}{\leftarrow }\mathrm{Anonymize}\left(i,w,\sigma ,L,y_L,m\right)\end{array}\right]& \left[\mathrm{Math}.5\right]\end{array}$

is negligible with respect to k.

[0058] In the above-described agent-independent agent-specified anonymizable signature, as in the conventional agent-specified anonymizable signature, even if a signature σ is leaked to an attacker, it is computationally difficult to identify which signature the signature σ is, in terms of which private key x.sub.i is used to create the signature, unless an agent private key w is leaked. Accordingly, in the agent-independent agent-specified anonymizable signature, only an agent specified by a signer can perform signature verification and anonymization, and a public key y does not need to be regenerated even when the signer changes the specified agent.

[0059] Here, the above-described agent-independent agent-specified anonymizable signature can be configured specifically by using a Trapdoor DDH group, similarly to the agent-specified anonymizable signature according to Non-Patent Literature 1. Accordingly, to implement such a specific configuration, several notions will be described hereinafter.

[0060] <Trapdoor DDH>

[0061] For example, the following Reference Literature 1 describes a specific configuration of a special Trapdoor DDH group made by extending pairing.

[0062] [Reference Literature 1]

[0063] F. Hoshino, “A Variant of Diffie-Hellman Problem and How to Prove Independency.” SCIS 2014 The 31st Symposium on Cryptography and Information Security Kagoshima, Japan, Jan. 21-24, 2014.

[0064] This Trapdoor DDH group is used to give a specific configuration of the above-described agent-independent agent-specified anonymization signature. An outline of the Trapdoor DDH group is as follows. [0065] p is assumed to be a sufficiently large prime number. [0066] E is assumed to be a supersingular elliptic curve over a finite field F.sub.p, and to be divisible by a prime number q whose order is sufficiently large. Note that F.sub.p=Z/pZ (Z is a ring of integers). [0067] α is assumed to be a generator of E(F.sub.p)[q].

[0068] At this time, it is assumed that G:=GL(n, α).Math.α.sup.n.sup.×, and R:=GL (n, F.sub.q).Math.F.sub.q.sup.n×n. Thus, G is an abelian group based on a group operation that is element-wise elliptic addition, and such an abelian group can be regarded as the Trapdoor DDH group. Moreover, R is a noncommutative ring, and can be regarded as the discrete logarithm with respect to G. Further, a natural pairing mapping can be defined over G, which will be described later.

[0069] <Discrete Logarithm>

[0070] It is assumed that a cyclic group is α, and order is q (where q is a prime number). At this time, when

[00006]$\begin{array}{cc}\begin{array}{ccc}{.Math.\alpha .Math.}^{n\times n}& .Math.& F_q^{n\times n}\\ & & \\ \left(\begin{array}{ccc}{\alpha }^{r_{11}}& .Math.& {\alpha }^{r_{1n}}\\ .Math.& \ddots & .Math.\\ {\alpha }^{r_{n1}}& .Math.& {\alpha }^{r_{\mathrm{nn}}}\end{array}\right)& \mapsto & \left(\begin{array}{ccc}{r}_{11}& .Math.& r_{1n}\\ .Math.& \ddots & .Math.\\ r_{n1}& .Math.& r_{n,n}\end{array}\right)\end{array},& \left[\mathrm{Math}.6\right]\end{array}$

then with respect to

h:=(α.sup.r.sup.ij),  [Math. 7]

r:=(r.sub.ij)  [Math. 8]

is referred to as a discrete logarithm. At this time, h is also denoted as α.sup.r. When r is an identity matrix of n×n, α.sup.r is denoted as I.sub.n. Note that as described above, G=GL(n, α) is a subgroup of α.sup.n×n whose discrete logarithm is regular, and is an abelian group whose group operation is element-wise elliptic addition.

[0071] As an example, operations for following g, h∈G when n=2 will be illustrated.

[00007]$\begin{array}{cc}g:=\left(\begin{array}{cc}{g}_{11}& g_{12}\\ g_{21}& g_{21}\end{array}\right)\in G,h:=\left(\begin{array}{cc}{h}_{11}& h_{12}\\ h_{21}& h_{22}\end{array}\right)\in G& \left[\mathrm{Math}.9\right]\end{array}$

[0072] When both the group operation (elliptic addition) of α and addition of G are expressed in a form of addition, an expression is as follows.

[00008]$\begin{array}{cc}g+h=h+g=\left(\begin{array}{cc}{g}_{11}+h_{11}& g_{12}+h_{12}\\ g_{21}+h_{21}& g_{22}+h_{22}\end{array}\right)\in G& \left[\mathrm{Math}.10\right]\end{array}$

[0073] However, the embodiment of the present invention shows an analogy to the notion of ordinary discrete logarithm, both the group operation (elliptic addition) of α and the addition of G are expressed in a form of multiplication, namely, as follows.

[00009]$\begin{array}{cc}\mathrm{gh}=\mathrm{hg}=\left(\begin{array}{cc}{g}_{11}{h}_{11}& g_{12}{h}_{12}\\ g_{21}{h}_{21}& g_{22}{h}_{32}\end{array}\right)\in G& \left[\mathrm{Math}.11\right]\end{array}$

[0074] <Right Exponentiation, Left Exponentiation>

[0075] Assuming that g, g.sub.1, g.sub.2∈G, when matrices composed of exponent portions of respective elements of g, g.sub.1, g.sub.2 are x, x.sub.1, x.sub.2∈R, respectively, it is assumed that a left exponentiation and a right exponentiation are defined such that following relationships are satisfied.

[00010]$\begin{array}{cc}\begin{array}{c}x=x_1{x}_2=x_1{x}_2\in R\\ ↧↧↧\downarrow \\ g={ }^{x_1}{g}_2=g_1^{x_2}\in G\end{array}& \left[\mathrm{Math}.12\right]\end{array}$

[0076] At this time, when R is a noncommutative ring with respect to the right exponentiation and the left exponentiation, there exists a probabilistic polynomial time algorithm for calculating the right exponentiation and the left exponentiation, with respect to [G, R], as follows. [0077] Non-degenerate bi-homomorphism rpow with respect to G, R: G×R.fwdarw.G [0078] Non-degenerate bi-homomorphism lpow with respect to G, R: R×G.fwdarw.G

[0079] Note that rpow is a mapping for calculating the right exponentiation, and lpow is a mapping for calculating the left exponentiation. Both rpow and lpow satisfy the associative law.

[0080] As an example, operations for x, y∈R when n=2 will be illustrated as follows. The operations are considered as matrix multiplication (.sup.x(α.sup.y)=α.sup.xy, (α.sup.y).sup.x=α.sup.yx) over discrete logarithms.

[00011]$$\begin{gathered} \begin{array}{cc}x:=\left(\begin{array}{cc}{x}_{11}& x_{12}\\ x_{21}& x_{22}\end{array}\right)\in R.Math.F_q^{2\times 2} \\ g:=\left(\begin{array}{cc}{g}_{11}& g_{12}\\ g_{21}& g_{22}\end{array}\right)\in G.Math.{.Math.\alpha .Math.}^{2\times 2}& \left[\mathrm{Math}.13\right]\end{array} \end{gathered}$$

[0081] At this time, expressions for .sup.xg, g.sup.x in a form of multiplication are as follows. An expression for .sup.xI.sub.n, I.sub.n.sup.x is also given below.

[00012]$\begin{array}{cc}{ }^{x}g:=\left(\begin{array}{cc}{g}_{11}^{x_{11}}{g}_{21}^{x_{12}}& g_{12}^{x_{11}}{g}_{22}^{x_{12}}\\ g_{11}^{x_{21}}{g}_{21}^{x_{22}}& g_{12}^{x_{21}}{g}_{22}^{x_{22}}\end{array}\right)\in G{g}^x:=\left(\begin{array}{cc}{g}_{11}^{x_{11}}{g}_{12}^{x_{21}}& g_{11}^{x_{12}}{g}_{12}^{x_{22}}\\ g_{21}^{x_{11}}{g}_{22}^{x_{21}}& g_{21}^{x_{12}}{g}_{22}^{x_{22}}\end{array}\right)\in G{ }^x{I}_n=I_n^x={\alpha }^x& \left[\mathrm{Math}.14\right]\end{array}$

[0082] <Key Exchange>

[0083] Although not directly related to the agent-independent agent-specified anonymizable signature, key exchange can be also implemented because “.sup.x(g.sup.y)=(.sup.xg).sup.y” holds for x, y∈R, g∈G, as mentioned above. In other words, key exchange can be performed through (1) to (4) described below.

[0084] (1) Alice generates x∈R, and transmits .sup.xg to Bob.

[0085] (2) Bob generates y∈R, and transmits g.sup.y to Alice.

[0086] (3) Bob calculates K.sub.A=.sup.x(g.sup.y).

[0087] (4) Alice calculates K.sub.B=(.sup.xg).sup.y.

[0088] As mentioned above, as “.sup.x(g.sup.y)=(.sup.xg).sup.y” holds for x, y∈R, g∈G, K.sub.A=K.sub.B holds, and accordingly, key exchange can be performed.

[0089] <Pairing>

[0090] A natural pairing mapping can be defined over G as follows.

e:α.sup.n×n×α.sup.n×n.fwdarw.μ.sub.q.sup.n×n

[0091] This pairing mapping is considered as matrix multiplication (e (α.sup.x, α.sup.y)=ξ.sup.xy) over discrete logarithms.

[0092] As an example, when n=2, g, h∈G are assumed to be as follows.

[00013]$\begin{array}{cc}g:=\left(\begin{array}{cc}{g}_{11}& g_{12}\\ g_{21}& g_{22}\end{array}\right)\in G,h:=\left(\begin{array}{cc}{h}_{11}& h_{12}\\ h_{21}& h_{22}\end{array}\right)\in G& \left[\mathrm{Math}.16\right]\end{array}$

[0093] At this time, a pairing mapping e(g, h) can be defined by the following expression.

[00014]$\begin{array}{cc}e\left(g,h\right):=\left(\begin{array}{cc}e\left(g_{11},h_{11}\right)e\left(g_{12},h_{21}\right)& e\left(g_{11},h_{12}\right)e\left(g_{12},h_{22}\right)\\ e\left(g_{21},h_{11}\right)e\left(g_{22},h_{21}\right)& e\left(g_{21},h_{12}\right)e\left(g_{22},h_{22}\right)\end{array}\right)\in {\mu }_q^{2\times 2}& \left[\mathrm{Math}.17\right]\end{array}$

[0094] <Overall Configuration of Anonymous Signature System 1>

[0095] Hereinafter, an anonymous signature system 1 that implements the above-described agent-independent agent-specified anonymizable signature scheme Σ will be described with reference to FIG. 1. FIG. 1 shows an example of an overall configuration of the anonymous signature system 1 in the embodiment of the present invention.

[0096] As shown in FIG. 1, the anonymous signature system 1 in the embodiment of the present invention includes a plurality of signature generation apparatuses 10, one or more anonymous signature generation apparatuses 20, one or more signature verification apparatuses 30, and one or more system parameter generation apparatuses 40. The signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 are communicably connected to one another, for example, through a communication network 50 such as the Internet.

[0097] Each signature generation apparatus 10 is a computer or a computer system used by a signer, and performs generation of a private key x and a public key y and generation (creation) of a signature σ. Each signature generation apparatus 10 includes a key generation unit 110 and a signature generation unit 120.

[0098] The key generation unit 110 executes the key generation algorithm KeyGen(ρ) in the agent-independent agent-specified anonymizable signature scheme Σ. Specifically, the key generation unit 110 takes as input a system parameter ρ that does not depend on an agent (that is, an agent-independent system parameter ρ, in other words, a system parameter ρ commonly used by each agent), and outputs a private key x and a public key y. The outputted private key x is stored, for example, in an auxiliary storage device or the like of the signature generation apparatus 10. On the other hand, the outputted public key y is made public by using any method.

[0099] The signature generation unit 120 executes the signature algorithm Sign(x, m, g.sub.A) in the agent-independent agent-specified anonymizable signature scheme Σ. Specifically, the signature generation unit 120 takes as input a private key x, a message m, and an agent public key g.sub.A, and outputs a signature σ. Here, for the agent public key g.sub.A, an agent public key g.sub.A of an agent specified by a signer is used. The outputted signature σ is transmitted, along with the message m, to an anonymous signature generation apparatus 20 of the agent specified by the signer.

[0100] Note that the key generation unit 110 and the signature generation unit 120 are implemented, for example, through processing that one or more programs installed in the signature generation apparatus 10 cause a processor or the like to perform.

[0101] The anonymous signature generation apparatus 20 is a computer or a computer system used by an agent, and performs generation of an agent private key w and an agent public key g.sub.A and anonymization of a signature σ. The anonymous signature generation apparatus 20 includes a setup unit 210 and an anonymization unit 220.

[0102] The setup unit 210 executes the agent key generation algorithm Setup(ρ). Specifically, the setup unit 210 takes as input a system parameter ρ that does not depend on an agent, and outputs an agent private key w and an agent public key g.sub.A. The outputted agent private key w is stored, for example, in an auxiliary storage device or the like of the anonymous signature generation apparatus 20. On the other hand, the outputted agent public key g.sub.A is made public by using any method.

[0103] The anonymization unit 220 executes the anonymization algorithm Anonymize(i, w, σ, L, y.sub.L, m). Specifically, the anonymization unit 220 takes as input an identifier i of a signer, an agent private key w, a signature σ of the signer, a ring L, a list y.sub.L of public keys of signers belonging to the ring L, and a message m corresponding to the signature σ, and outputs a ring signature σ′ or reject ⊥.

[0104] Note that the setup unit 210 and the anonymization unit 220 are implemented, for example, through processing that one or more programs installed in the anonymous signature generation apparatus 20 cause a processor or the like to perform.

[0105] The signature verification apparatus 30 is a computer or a computer system used by an agent or a third party different from the agent, and performs verification of a ring signature σ′. The signature verification apparatus 30 includes a verification unit 310.

[0106] The verification unit 310 executes the verification algorithm Verify(L, y.sub.L, m, σ′). Specifically, the verification unit 310 takes as input a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m, and a ring signature σ′, and outputs a single bit b∈{0, 1}.

[0107] Note that the verification unit 310 is implemented through processing that one or more programs installed in the signature verification apparatus 30 cause a processor or the like to perform.

[0108] The system parameter generation apparatus 40 is a computer or a computer system used by a manager of a system parameter ρ that does not depend on an agent (for example, a third party different from every agent, an agent that represents all agents, or the like), and performs generation of a system parameter ρ. The system parameter generation apparatus 40 includes a system parameter generation unit 410.

[0109] The system parameter generation unit 410 executes the common reference information generation algorithm CrsGen. Specifically, the system parameter generation unit 410 takes as input a safe parameter 1.sup.k, and outputs a system parameter ρ. The system parameter ρ is information commonly referenced by each signer and each agent, and is made public by using any method.

[0110] Note that the system parameter generation unit 410 is implemented, for example, through processing that one or more programs installed in the system parameter generation apparatus 40 cause a processor or the like to perform.

[0111] With the foregoing, the anonymous signature system 1 in the embodiment of the present invention can implement the agent-independent agent-specified anonymizable signature scheme Σ. The agent-independent agent-specified anonymizable signature scheme Σ is assumed to satisfy the construction represented by Math. 5 mentioned above.

[0112] Note that the configuration of the anonymous signature system 1 shown in FIG. 1 is an example, and other configurations may be adopted. For example, the anonymous signature generation apparatus 20 and the signature verification apparatus 30 may be integrally configured as a single apparatus.

[0113] <Details of Processing by Anonymous Signature System 1>

[0114] It is assumed that G is the above-described Trapdoor DDH group, that R is the discrete logarithm with respect to G, and that G.sub.T=GL(n, e(α, α)). Moreover, it is assumed that e: G×G.fwdarw.G.sub.T is a pairing mapping of the above-described Trapdoor DDH group, and that a mapping H: {0, 1}*.fwdarw.G and a mapping H′: {0, 1}*.fwdarw.R are mutually independent random oracles. Further, a system parameter ρ is assumed to have a form of ρ=(R, G, G.sub.T, e, g, H, H′).

[0115] (System Parameter Generation Processing)

[0116] First, system parameter generation processing performed by the system parameter generation unit 410 will be described with reference to FIG. 2. FIG. 2 is a flowchart showing an example of the system parameter generation processing in the embodiment of the present invention.

[0117] Step S101: First, the system parameter generation unit 410 takes as input a safe parameter 1.sup.k.

[0118] Step S102: Subsequently, the system parameter generation unit 410 generates a system parameter ρ as follow.

[0119] crs←{0, 1}.sup.k

[0120] g←H(crs)

[0121] ρ←(R, G, G.sub.T, e, g, H, H′)

[0122] Step S103: Lastly, the system parameter generation unit 410 outputs the system parameter ρ.

[0123] Thus, the system parameter ρ that does not depend on an agent is generated. As described above, a generator g whose discrete logarithm is unknown to anyone is generated by using a hash value of a common reference character string crs that is generated based on the safe parameter 1.sup.k, and the system parameter ρ is then configured by using the generator g. The system parameter ρ is made public to a signer and an agent.

[0124] (Setup Processing)

[0125] Next, setup processing performed by the setup unit 210 will be described with reference to FIG. 3. FIG. 3 is a flowchart showing an example of the setup processing in the embodiment of the present invention. In the setup processing shown in FIG. 3, a case will be described in which the anonymous signature generation apparatus 20 of an agent, among agents, generates an agent private key w and an agent public key g.sub.A.

[0126] Step S201: First, the setup unit 210 takes as input a system parameter ρ.

[0127] Step S202: Subsequently, the setup unit 210 generates an agent private key w and an agent public key g.sub.A as follows.

[00015]$\begin{array}{cc}w\stackrel{\$}{\leftarrow }R{g}_A\leftarrow I_n^w& \left[\mathrm{Math}.18\right]\end{array}$

[0128] Step S203: Lastly, the setup unit 210 outputs the agent private key w and the agent public key g.sub.A.

[0129] Thus, the agent private key w and the agent public key g.sub.A are generated. The agent private key w is stored, for example, in the auxiliary storage device or the like of the anonymous signature generation apparatus 20. On the other hand, the system parameter ρ is made public to a signer.

[0130] (Key Generation Processing)

[0131] Next, key generation processing performed by the key generation unit 110 will be described with reference to FIG. 4. FIG. 4 is a flowchart showing an example of the key generation processing in the embodiment of the present invention. In the key generation processing shown in FIG. 4, a case will be described in which the signature generation apparatus 10 of a certain signer belonging to a ring L generates a private key x and a public key y.

[0132] Step S301: First, the key generation unit 110 takes as input a system parameter ρ. At this time, the key generation unit 110 takes as input the system parameter ρ that is generated and made public by the system parameter generation apparatus 40.

[0133] Step S302: Subsequently, the key generation unit 110 parses the system parameter ρ such that (R, G, G.sub.T, e, g, H, H′)←ρ. In other words, the key generation unit 110 sets the system parameter ρ as (R, G, G.sub.T, e, g, H, H′).

[0134] Step S303: Subsequently, the key generation unit 110 generates a private key x and a public key y, by setting “x←.sup.sR”, and then, “y←.sup.xg”.

[0135] Step S304: Lastly, the key generation unit 110 outputs the private key x and the public key y.

[0136] Thus, the private key x and the public key y of the certain signer belonging to the ring L are generated. At this time, as described above, the private key x and the public key y are generated by using the system parameter ρ that does not depend on an agent. Accordingly, even when the specified agent is changed, the signer does not need to regenerate a private key x and a public key y. The private key x is stored, for example, in the auxiliary storage device or the like of the signature generation apparatus 10. On the other hand, the public key y is made public to an agent.

[0137] (Signature Processing)

[0138] Next, signature processing performed by the signature generation unit 120 will be described with reference to FIG. 5. FIG. 5 is a flowchart showing an example of the signature generation processing in the embodiment of the present invention. In the signature processing shown in FIG. 5, a case will be described in which the signature generation apparatus 10 of the certain signer belonging to the ring L generates (creates) a signature.

[0139] Step S401: First, the signature generation unit 120 takes as input the private key x, a message m, and an agent public key g.sub.A. At this time, the signature generation unit 120 takes as input an agent public key g.sub.A that is made public by an agent specified by the signer.

[0140] Step S402: Subsequently, the signature generation unit 120 generates a signature σ such that σ.fwdarw.(.sup.xH (ρ, m), .sup.xg.sub.A). ρ used here is the system parameter ρ that is generated and made public by the system parameter generation apparatus 40.

[0141] Step S403: Lastly, the signature generation unit 120 outputs the signature σ.

[0142] Thus, the signature σ is generated. The signature σ is transmitted, along with the message m, to the anonymous signature generation apparatus 20 of the agent specified by the signer.

[0143] (Anonymization Processing)

[0144] Next, anonymization processing performed by the anonymization unit 220 will be described with reference to FIG. 6. FIG. 6 is a flowchart showing an example of the anonymization processing in the embodiment of the present invention. In the anonymization processing shown in FIG. 6, a case will be described in which a signature σ of a signer with an identifier i is anonymized.

[0145] Step S501: First, the anonymization unit 220 takes as input the identifier i of the signer, the signature σ of the signer, a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m corresponding to the signature σ, and an agent private key w.

[0146] Step S502: Subsequently, the anonymization unit 220 generates output values h of a random oracle H such that h.fwdarw.H(ρ, m). For the system parameter ρ, a system parameter ρ that is generated and made public by the system parameter generation apparatus 40 is used.

[0147] Step S503: Subsequently, the anonymization unit 220 parses the signature σ such that (r, Y)←σ. At this time, the anonymization unit 220 parses, for example, σ that is coded as ordered pairs of elements over G by the signature generation unit 120, into ordered pairs (r, Y) of elements over G.

[0148] Step S504: Subsequently, the anonymization unit 220 executes

X←Y.sup.w.sup.−1.  [Math. 19]

[0149] Step S505: Subsequently, the anonymization unit 220 determines whether or not “e(X, g)≠e(I.sub.n, y.sub.i)” is satisfied.

[0150] Step S506: When it is determined in step S505 that “e(X, g)≠e(I.sub.n, y.sub.i)” is not satisfied, the anonymization unit 220 determines whether or not “e(I.sub.n, r)≠e(X, h)” is satisfied.

[0151] Step S507: When it is determined in step S505 that “e(X, g)≠e(I.sub.n, y.sub.i)” is satisfied, or when it is determined in step S506 that “e(I.sub.n, r)≠e(X, h)” is satisfied, the anonymization unit 220 outputs reject ⊥. In such a case, the signature σ cannot be anonymized.

[0152] Step S508: When it is determined in step S506 that “e(I.sub.n, r)≠e(X, h)” is not satisfied, the anonymization unit 220 generates zero-knowledge proofs for r and X such that (∃j∈R, e(I.sub.n, r)=e(X, h)), through following steps S508-1 to S508-4.

[0153] Step S508-1: The anonymization unit 220 executes

[00016]$$\begin{gathered} \begin{array}{cc}{t}_1,t_2,t_3,\beta \stackrel{\$}{\leftarrow }R \\ V\leftarrow { }^{\beta }e\left(I_n,y_i\right),U\leftarrow { }^{\beta }e\left(I_n,r\right) \\ {T}_{1,i}\leftarrow { }^{t_1}e\left(I_n,y_i\right).& \left[\mathrm{Math}.20\right]\end{array} \end{gathered}$$

[0154] Step S508-2: Subsequently, with respect to any j∈L\{i}, the anonymization unit 220 executes

[00017]$$\begin{gathered} \begin{array}{cc}{c}_{1,j},z_{1,j}\stackrel{\$}{\leftarrow }R \\ {T}_{1,j}\leftarrow e\left(I_n,{ }^{z_{1,j}}{y}_j\right){ }^{c_{1,j}}V.& \left[\mathrm{Math}.21\right]\end{array} \end{gathered}$$

[0155] Step S508-3: The anonymization unit 220 executes

T.sub.2←.sup.t.sup.2e(I.sub.n,g),T.sub.2′←.sup.t.sup.2e(I.sub.n,h)

T.sub.3←.sup.t.sup.3e(I.sub.n,I.sub.n)  [Math. 22]

Thus, c.sub.1,j, z.sub.1,j, T.sub.1,j, T.sub.2, T.sub.2′, and T.sub.3 are obtained.

[0156] Step S508-4: The anonymization unit 220 executes

(c.sub.1,i,c.sub.2,c.sub.3)←H′(ρ,L,m,y.sub.L,U,V,T.sub.1,L,T.sub.2,T.sub.2′,T.sub.3)−Σ.sub.j≠i(c.sub.1,j,0,0)

z.sub.1,i←t.sub.1−c.sub.1,iβ

z.sub.2←.sup.t.sup.2I.sub.n/.sup.c.sup.2.sup.βX

z.sub.3←.sup.t.sup.3I.sub.n/.sup.c.sup.3.sup.βr  [Math. 23]

Thus, c.sub.1,i, c.sub.2, c.sub.3, z.sub.1,i, z.sub.2, and z.sub.3 are obtained.

[0157] Step S509: Subsequently, the anonymization unit 220 generates a ring signature σ′ such that σ′←(U, V, c.sub.1,L, c.sub.2, c.sub.3, z.sub.1,L, z.sub.2, z.sub.3).

[0158] Step S510: Lastly, the anonymization unit 220 outputs the ring signature σ′. Thus, the ring signature σ′ is generated.

[0159] As described above, in the agent-independent agent-specified anonymizable signature scheme Σ, as in the conventional agent-specified anonymizable signature, an agent private key w is used to anonymize a signature σ. Accordingly, only an agent specified by a signer can perform anonymization of a signature σ. Accordingly, also in the agent-independent agent-specified anonymizable signature scheme Σ, even if a signature σ is leaked, anonymity of the signature σ can be ensured unless an agent private key w is leaked.

[0160] (Verification Processing)

[0161] Next, verification processing performed by the verification unit 310 will be described with reference to FIG. 7. FIG. 7 is a flowchart showing an example of the verification processing in the embodiment of the present invention.

[0162] Step S601: First, the verification unit 310 takes as input a ring L, a list y.sub.L of public keys of signers belonging to the ring L, a message m, and a ring signature σ′.

[0163] Step S602: Subsequently, the verification unit 310 parses the ring signature σ′ such that (U, V, c.sub.1,L, c.sub.2, c.sub.3, z.sub.1,L, z.sub.2, z.sub.3)←σ′. In other words, the verification unit 310 analyzes the ring signature σ′ into (U, V, c.sub.1,L, c.sub.2, c.sub.3, z.sub.1,L, z.sub.2, z.sub.3).

[0164] Step S603: Subsequently, the verification unit 310 generates output values h of a random oracle H such that h←H(ρ, m). Note that for the system parameter ρ, a system parameter ρ that is generated and made public by the system parameter generation apparatus 40 is used.

[0165] Step S604: Subsequently, with respect to any j∈L, the verification unit 310 executes

T.sub.1,j←e(I.sub.n,.sup.z.sup.1,jy.sub.j).sup.c.sup.1,jV

T.sub.2.fwdarw.e(z.sub.2,g).sup.c.sup.2V,T.sub.2′←e(z.sub.2,h).sup.c.sup.2U

T.sub.3←e(I.sub.n,z.sub.3).sup.c.sup.3U

c.sub.1=Σ.sub.j∈Lc.sub.1,j  [Math. 24]

to generate T.sub.1,j, T.sub.2, T.sub.2′, T.sub.3, and c.sub.1.

[0166] Step S605: Subsequently, the verification unit 310 determines whether or not “H′(ρ, L, m, y.sub.L, U, V, T.sub.1,L, T.sub.2, T.sub.2′, T.sub.3)=(c.sub.1, c.sub.2, c.sub.3)” is satisfied.

[0167] Step S606: When it is determined in step S605 that “H′(ρ, L, m, y.sub.L, U, V, T.sub.1,L, T.sub.2, T.sub.2′, T.sub.3)=(c.sub.1, c.sub.2, c.sub.3)” is satisfied, the verification unit 310 outputs “1” as a verification result. In such a case, it is indicated that the message m is valid.

[0168] Step S607: When it is determined in step S605 that “H′(ρ, L, m, y.sub.L, U, V, T.sub.1,L, T.sub.2, T.sub.2′, T.sub.3)=(c.sub.1, c.sub.2, c.sub.3)” is not satisfied, the verification unit 310 outputs “0” as a verification result. In such a case, it is indicated that the message m is invalid.

[0169] <Hardware Configuration>

[0170] Finally, a hardware configuration of the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 in the embodiment of the present invention will be described with reference to FIG. 8. FIG. 8 shows an example of the hardware configuration of the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 in the embodiment of the present invention. Note that since the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 can be implemented by using almost the same hardware configuration, the hardware configuration of the signature generation apparatuses 10 will be mainly described hereinafter.

[0171] As shown in FIG. 8, each signature generation apparatus 10 in the embodiment of the present invention includes an input device 501, a display device 502, a RAM (Random Access Memory) 503, a ROM (Read Only Memory) 504, a processor 505, an external I/F 506, a communication I/F 507, and an auxiliary storage device 508. Each of the hardware pieces are communicably connected to one another through a bus 509.

[0172] The input device 501 is, for example, a keyboard, a mouse, a touch panel, or the like, and is used for a user to input various operations. The display device 502 is, for example, a display or the like, and is used to display a processing result or the like to the user. Note that the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 may omit including at least one of the input device 501 and the display device 502.

[0173] The RAM 503 is a volatile semiconductor memory that temporarily stores a program and data. The ROM 504 is a non-volatile semiconductor memory that can retain a program and data even when a power supply is turned off. The processor 505 is, for example, a CPU (Central Processing Unit) or the like, and is a computational device that reads a program and data from the ROM 504, the auxiliary storage device 408, or the like onto the RAM 503 and performs processing.

[0174] The external I/F 506 is an interface with an external device. External devices include a recording medium 506a and the like, Examples of the recording medium 506a include a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), a USB (Universal Serial Bus) memory card, and the like.

[0175] The communication I/F 507 is an interface for connecting the signature generation apparatus 10 to the communication network 50. The signature generation apparatus 10 can perform data communication with another device via the communication I/F 507. The same applies to the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40.

[0176] The auxiliary storage device 508 is, for example, a non-volatile storage device such as an HDD (Hard Disk Drive) or an SSD (Solid State Drive). The auxiliary storage device 508 stores various data, programs (for example, one or more programs implementing the key generation unit 110 and the signature generation unit 120), and the like. Note that the auxiliary storage device 508 of the anonymous signature generation apparatus 20 stores, for example, one or more programs implementing the setup unit 210 and the anonymization unit 220, and the like. Similarly, the auxiliary storage device 508 of the signature verification apparatus 30 stores, for example, one or more programs implementing the verification unit 310, and the like. Similarly, the auxiliary storage device 508 of the system parameter generation apparatus 40 stores, for example, one or more programs implementing the system parameter generation unit 410, and the like.

[0177] The signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 in the embodiment of the present invention can implement the above-described various processing by having the hardware configuration shown in FIG. 8. Note that in FIG. 8 although the case is described in which each of the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 is implemented by using a single apparatus (computer), not limited to such a configuration, at least one of the signature generation apparatuses 10, the anonymous signature generation apparatus 20, the signature verification apparatus 30, and the system parameter generation apparatus 40 may be implemented by using a plurality of apparatuses (computers). One apparatus (computer) may include a plurality of processors 505 or a plurality of memories (for example, RAMs 503, ROMs 504, auxiliary storage devices 508, or the like).

[0178] The present invention is not limited to the above-described embodiments specifically disclosed, and various modifications, changes, combinations, and the like can be made without departing from the scope of claims.

REFERENCE SIGNS LIST

[0179] 1 Anonymous signature system [0180] 10 Signature generation apparatus [0181] 20 Anonymous signature generation apparatus [0182] 30 Signature verification apparatus [0183] 40 System parameter generation apparatus [0184] 110 Key generation unit [0185] 120 Signature generation unit [0186] 210 Setup unit [0187] 220 Anonymization unit [0188] 310 Verification unit [0189] 410 System parameter generation unit