Signature apparatus, verifying apparatus, proving apparatus, encrypting apparatus, and decrypting apparatus

• US 8,028,171 B2
• Filed: 12/13/2005
• Issued: 09/27/2011
• Est. Priority Date: 01/21/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Teranishi, Isamu
• Primary Examiner(s): Patel; Nirav B
• Application Number:
  US11/795,616
• Publication Number:
  US 20080301449A1
• Time in Patent Office: 2,114 Days
• Field of Search: 713/168, 713/176, 713/180, 713/181, 380 28- 30
• US Class Current: 713/180
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Provided are a signature apparatus, a verifying apparatus, a proving apparatus, an encrypting apparatus, and a decrypting apparatus capable of efficiently reducing a signature text counterfeit problem to a discrete logarithm problem. The commitment is a hash value of a set of a value to be committed. Data including a pair of elements of a cyclic group associated with a discrete logarithm problem is used as a public key, and a discrete logarithm of an order of the pair is used as a secret key. Accordingly, it is possible to summarize secret information of an attacker from the commitment without rewinding the attacker and to ensure a higher safety than that of a Schnorr signature scheme. In addition, one-time power residue calculation is performed in each of the signature and verification calculations, so that it is possible to lower an amount of calculation in the signature and verification calculations.

Claims

1. A signature apparatus for generating a signature text by using a commitment, wherein the commitment is a hash value of a set including a value to be committed, data including a pair of elements of a cyclic group associated with a discrete logarithm problem which is used as a public key, and a discrete logarithm of an order of the pair which is used as a secret key, the signature apparatus comprising:

a committed vector selecting unit configured to select a committed vector associated with a first commitment;

a first commitment calculating unit configured to calculate the first commitment;

a basis vector calculating unit configured to calculate a basis vector;

a second commitment calculating unit configured to calculate a power residue and calculates a second commitment;

a vector challenge calculating unit configured to calculate a vector challenge;

a vector response calculating unit configured to calculate a vector response by using the first commitment, a set used for calculating the power residue, the vector challenge, and the basis vector; and

a memory configured to store the committed vector, the first commitment, the basis vector, the second commitment, the vector challenge, and the vector response,

wherein a signature text is generated based in part on the first commitment, the second commitment, and the vector response, and wherein a signature text output means is configured to read the signature text from the memory and output the signature text to a verifying apparatus,

wherein the basis vector and the vector challenge are hash values,

wherein the committed vector selecting unit is further configured to select a plurality of committed vectors, each having the same configuration as the committed vector, and

wherein each component of the plurality of committed vectors and the secret key satisfy a relation equation, and

wherein the first commitment is a hash value of data including components of the vector response, the public key which is data including a pair of elements of the cyclic group associated with the discrete logarithm problem, and the secret key which is a discrete logarithm of an order of the pair.

2. The signature apparatus according to claim 1, wherein each component of the plurality of committed vectors and the secret key satisfy the relation equation with a group order as a modulus, and

wherein the set is data calculated by using a portion of data selected by the committed vector selecting unit, the basis vector, and the vector challenge.

3. The signature apparatus according to claim 2, wherein each component of the committed vectors and the secret key satisfy a linear equation with the group order as a modulus,

wherein an input of the first commitment is data including a random number,

wherein a portion of the data is determined by the vector challenge, and

wherein the set is represented by a linear equation of the portion of the data and the basis vector.

4. The signature apparatus according to claim 3, wherein the committed vector includes two components, one component being a value obtained by adding a secret key to the other component and obtaining a residue with a group order as a modulus,

wherein an input to the first commitment includes data for specifying each component of the committed vector, and

wherein the set is an inner product of the portion of the data and the basis vector.

5. The signature apparatus according to claim 4, wherein assuming that security parameters are κ

, N, and ν

, and an order of the cyclic group is q,

wherein the committed vector selecting unit is configured to select a residue group X_—

{01}, . . . , X_—

{0N}ε

(Z/qZ) at random and set values obtained by adding x to the residue group X_—

{0j} for j =1, . . . N and obtain a residue with the order q as a modulus to X_—

{1j},

wherein the committed vector for i =0, 1 is Y_i =(X_{i1}, . . . , X_{iN}),

wherein the first commitment calculating unit is configured to select at random a bit column r of ν

bits,

wherein a hash value of data including the public key, X_{ij}, i, j, r for i =0, 1 is set to a first commitment C_{ij},

wherein the basis vector calculating unit is configured to select a hash value of data including the public key and the first commitment C_{ij} to the basis vector V =(u_—

1, . . . , u_N),

wherein the second commitment calculating unit is configured to select an inner product of the basis vector V and the Y_—

0 and calculate a second commitment G =g^{X},

wherein the vector challenge calculating unit is configured to select a hash value K =(c_—

1, . . . , c_N) of data including the public key, {C_{ij}}, G, r, and a message received by signature apparatus,

wherein the vector response calculating unit is configured to select the vector response ξ

_{j}=X_{c_jj} for all j=1, . . . , N and Ξ

=(ξ

_—

1, . . . , ξ

_κ

), and

wherein a signature text (r, {C_{ij}}, G, Ξ

) is output.

6. The signature apparatus according to claim 1, wherein the relational equation satisfies a linear equation of each of the plurality of vectors and the secret key, and an input of the first commitment is data including a random number.

7. The signature apparatus according to claim 6, wherein the plurality of committed vectors include a plurality of components,

wherein one component is obtained by adding a secret key to another component, and

wherein an input of the first commitment includes data for specifying each of the components and data specifying which is the ordinal number of the component.

8. The signature apparatus according to claim 7,

wherein assuming that security parameters are κ

, N, and ν

, and an integer set R{κ

+ξ

} satisfies 0≦

R{κ

+ξ

}<

2^{κ

+ξ

},

wherein the committed vector selecting unit is configured to select a residue group X_—

{01}, . . . , X_—

{0N}ε

(Z/qZ) at random and set values obtained by adding x to the residue group X_—

{0j} for j =1, . . . N to X_—

{1j},

wherein the committed vector for i =0, 1 is Y_i =(X_{i1}, . . . , X_{iN}),

wherein the first commitment calculating unit is configured to select at random a bit column r of ν

bits,

wherein a hash value of data including the public key, X_{ij}, i, j, r for i =0, 1 is set to the first commitment C_{ij},

wherein the basis vector calculating unit is configured to set a hash value of data including the public key and the first commitment C_{ij} to the basis vector V =(u_—

1, . . . , u_N),

wherein the second commitment calculating unit is configured to calculate an inner product of the basis vector V and the Y_—

0 and calculates a second commitment G =g^{X},

wherein the vector challenge calculating unit is configured to calculate a hash value K =(c_—

1, . . . , c_N) of data including the public key, {C_{ij}}, G, r, and a message received by signature apparatus,

wherein the vector response calculating unit is configured to calculate the vector response ξ

_{j}=X_{c_jj} for all j =1, . . . , N and Ξ

=(ξ

_—

1, . . . , ξ

_κ

), and

wherein a signature text (r, {C_{ij}}, G, Ξ

) is output.

9. The signature apparatus according to claim 2,

wherein each component of the committed vectors and the secret key satisfy a linear equation with a group order as a modulus,

wherein the first commitment is data including a random number,

wherein the portion of the data is determined by the vector challenge, and

wherein the set is represented by a linear equation of the portion of the data and the basis vector.

10. The signature apparatus according to claim 9,

wherein the one component of the committed vector is a value obtained by adding a secret key to another component and obtaining a residue with a group order as a modulus,

wherein the set is an inner product of the portion of the data and the basis vector, and

wherein the basis vector is a value obtained by multiplying a predetermined number t with (1, t^1, t^2, . . . , t^N).

11. The signature apparatus according to claim 10,

wherein assuming that the message is M,

wherein the committed vector selecting unit is configured to select at random Y_—

0=(X_—

{01}, . . . , X_—

{0N})ε

Zq^{N}, calculate X_—

{1j}=x+X_—

{0j}modq for j =1, . . . , N, and generates the committed vector Y_—

1=(X_—

{11}, . . . X_—

{1N}),

wherein the second commitment calculating unit is configured to calculate X =<

{Y_—

0, V}>

=Σ

_jX_—

{0j}2^{j−

1}modq and calculate the commitment G =g^{X},

wherein the first commitment calculating unit is configured to select at random r_{ij}ε

{0, 1}^{ν

} for each i and j and calculate the first commitment C_{ij}=H_—

{{0, 1}^ν

}(X_{ij}, r_{ij}) of the X_{ij},

wherein the vector challenge calculating unit is configured to calculate K =(c_—

{1}, . . . , c_{N}) =H_—

{{0, 1}^{N}(g, h, {C_{ij}}, G, M),

wherein the vector response calculating unit is configured to calculate the vector response ξ

_j =X_{c_jj}modq for each j and calculateΞ

=(ξ

_—

{1}, . . . , ξ

_{N}), and

wherein a signature text ({C_{ij}}, {r_{c_jj}}, G, Ξ

) is output.

12. The signature apparatus of claim 4, wherein an associated proving apparatus is configured to determine a validity of a proof text.

13. The signature apparatus of claim 7, wherein an associated proving apparatus is configured to determine a validity of a signature text.

14. The signature apparatus of claim 10, wherein an associated proving apparatus is configured to determine a validity of a signature text.

15. The signature apparatus of claim 4, wherein an associated proving apparatus is configured to determine a validity of the public key in a verifying apparatus using a verifier-designated proving scheme,

wherein the public key of the verifying apparatus includes two data, the first data and the second data belong to the same cyclic group, and a secret key of a verifier or a portion thereof is obtained by designating the first data to an order and designating the second data to a discrete logarithm, and

wherein the signature text generated by the signature apparatus is used as a proof text or a portion thereof for determining validity.

16. The signature apparatus of claim 7, wherein an associated proving apparatus is configured to determine a validity of the public key in the verifying apparatus using a verifier-designated proving scheme,

wherein the public key of the verifying apparatus includes two data, the first data and the second data belong to the same cyclic group, a secret key of a verifier or a portion thereof is obtained by designating the first data to an order and designating the second data to a discrete logarithm, and

wherein the signature text generated by the signature apparatus is used as a proof text or a portion thereof for determining validity.

17. The signature apparatus of claim 10, wherein an associated proving apparatus is configured to determine a validity of the public key in a verifying apparatus using a verifier-designated proving scheme,

wherein the public key of the verifying apparatus includes two data, the first data and the second data belong to the same cyclic group, a secret key of a verifier or a portion thereof is obtained by designating the first data to an order and designating the second data to a discrete logarithm, and

wherein the signature text generated by the signature apparatus is used as a proof text or a portion thereof for determining validity.

18. The signature apparatus of claim 4, wherein an associated encrypting apparatus is configured to use the signature text as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

19. The signature apparatus of claim 7, wherein an associated encrypting apparatus is configured to use the signature text as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

20. The signature apparatus of claim 10, wherein an associated encrypting apparatus is configured to use the signature text as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

21. A verifying method for determining validity of input data, comprising:

receiving, via a receiving device, input data including a message and signature text associated with the message, wherein the signature text is based in part on a first commitment, a second commitment, and a vector response;

verifying a validity of the signature text via processes conducted by a basis vector calculating unit, a vector challenge calculating unit, a first validity verifying unit, a second validity verifying unit, and an output unit, including;

calculating, by the basis calculating unit, a basis vector and storing the basis vector in a storage unit;

calculating, by the vector challenge calculating unit, a vector challenge and storing the vector challenge in the storage unit;

determining, by the first validity verifying unit, a validity of the first commitment by inputting a portion of the input data including the vector response to a hash function; and

calculating power residue and determining a validity of the vector response,

wherein the basis vector and the vector challenge are hash values, and

wherein, the first commitment is a hash value of data including components of the vector response, a public key which is data including a pair of elements of a cyclic group associated with a discrete logarithm problem, and a secret key which is a discrete logarithm of an order of the pair.

22. The verifying method according to claim 21, further comprising:

determining that the first commitment is valid if the calculated hash value is equal to the first commitment,

calculating, when to-be-determined data includes data called the second commitment and the vector response and the public key includes two elements of the cyclic group associated with a discrete logarithm problem, first and second power residues that are power residues of the elements and determining whether or not the first power residue is equal to a value obtained by multiplying the second power residue with the second commitment,

wherein the first power residue is obtained by designating elements which are a portion of the public key to an order and designating a Schnorr challenge to a set, and

wherein the second power residue is obtained by designating elements which are a portion of the public key to an order and designating a Schnorr response to a set, and

wherein the Schnorr challenge is data calculated by using the vector challenge and the basis vector, and the Schnorr response is data calculated by using the vector response and the basis vector.

23. The verifying method according to claim 22,

wherein, if a valid signature text is not included in data selected at random by a signature apparatus, the data is not accepted,

wherein the data selected at random is input to each hash function,

wherein one component of the vector response is input to each of the hash functions,

wherein the Schnorr challenge is a linear equation of the vector challenge and a linear equation of the basis vector, and

wherein the Schnorr response is a linear equation of the vector response and a linear equation of the basis vector.

24. The verifying method according to claim 23, wherein the Schnorr challenge is an inner product of the vector challenge and the basis vector, and the Schnorr response is an inner product of the vector response and the basis vector.

25. The verifying method according to claim 24, wherein assuming that the message is M, and the to-be-determined data is (r, {C_{ij}}, G, Ξ

), the method further comprises;

calculating a hash value of data including the public key and {C_{ij}}, the hash value being the basis vector V =(u_—

1, . . . , u_N),

calculating a hash value of data including the public key, {C_{ij}}, G, r, and M, and the hash value is the vector challenge K =(c_—

1, . . . , c_N),

determining that C_{c_jj} is valid only if C_{c_jj} for j =1, . . . , N are equal to the hash function and determines that {C_{jj}} is valid only if all the C_{c_jj} are valid, wherein the hash function is a hash value of data including the public key, ξ

_{j}, c_j, j, and r, and

determining whether or not g^{<

V, Ξ

<

}=h^{<

V, K>

}G is satisfied and determining that the signature text is valid if g^{<

V, Ξ

>

}=h^{<

V, K>

}G is satisfied.

26. The verifying method according to claim 21,

wherein the signature text is accepted only if the validity is authenticated.

27. The verifying method according to claim 26, further comprising:

determining, if a hash value obtained by inputting a portion of the input data to a hash function is equal to the first commitment, that the first commitment is valid, and

using the data input to the hash function to calculate two power residues, and determining whether or not the one of the two power residues is equal to a value obtained by multiplying the other power residue with the second commitment,

wherein to-be-determined data includes the second commitment and the vector response, the public key includes elements of a cyclic group associated with a discrete logarithm problem,

wherein each of the power residues is obtained by designating the other element which is a portion of the public key to an order and designating a Schnorr challenge to a set,

wherein the Schnorr challenge is calculated by using the vector challenge and the basis vector, and

wherein the Schnorr response is calculated by using the vector response and the basis vector.

28. The verifying method according to claim 27, further comprising:

rejecting the data if data to be selected at random is not included in a case where the signature apparatus generates a signature text validly;

inputting the data to be selected at random to each of the hash functions calculated; and

inputting one component of the vector response to each of the hash functions,

wherein the Schnorr challenge is a linear equation of the vector challenge and a linear equation of the basis vector, and wherein the Schnorr response is a linear equation of the vector response and a linear equation of the basis vector.

29. The verifying method according to claim 28,

wherein the Schnorr challenge is an inner product of the vector challenge and the basis vector, and the Schnorr response is an inner product of the vector response and the basis vector.

30. The verifying method according to claim 29, wherein assuming that the message is M, and the to-be-verified signature text is ({C_{ij}}, {r_{cjj}}, G, Ξ

, the method further comprises;

calculating K =(c_—

{1}, . . . ,c_{N})=H_{{0, 1}^{N}}(g, h, {C_{ij}, G, M},

determining whether or not C_{c_jj}=H_—

{{0, 1}^ν

}(ξ

_j, r_{c_jj}) for all j =1, . . . , N is satisfied, and if the relation for all j is satisfied, it is determined to be b =1, and if not, it is determined to be b =0,

when b =0, determining whether or not g^{<

V, Ξ

>

}=h^{<

V, K>

}G is satisfied,

if g^{<

V, Ξ

>

}=h^{<

V, K>

}G is not satisfied, b =0 is designated, and data indicating that the signature text is rejected is output, and

if g^{<

V, Ξ

>

}=h^{<

V, K>

}G is satisfied, b =1 is designated, and data indicating that the signature text is accepted is output.

31. The verifying method according to claim 24, wherein a verifying apparatus verifies a validity of a proof text for the public key of a verifier-designated proving scheme verifying apparatus.

32. The verifying method according to claim 29, wherein a verifying apparatus verifies a validity of a proof text for the public key of a verifier-designated proving scheme verifying apparatus.

33. The verifying method of claim 24, further comprising verifying a proof text included as a portion of a cipher text in a decrypting apparatus.

34. The verifying method of claim 29, further comprising verifying a proof text included as a portion of a cipher text in a decrypting apparatus.