Signature Apparatus, Verifying Apparatus, Proving Apparatus, Encrypting Apparatus, and Decrypting Apparatus

• US 20080301449A1
• Filed: 12/13/2005
• Published: 12/04/2008
• Est. Priority Date: 01/21/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Teranishi, Isamu
• Granted Patent: US 8,028,171 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• 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-40. -40. (canceled)

41. A signature apparatus for generating a signature text by using a commitment, wherein the commitment is a hush 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 is used as a public key, and a discrete logarithm of an order of the pair is used as a secret key, the signature apparatus comprising:

committed vector selecting means which selects a committed vector associated with a first commitment;

first commitment calculating means which calculates the first commitment;

basis vector calculating means which calculates a basis vector;

second commitment calculating means which calculates the power residue and calculates a second commitment;

vector challenge calculating means which calculates a vector challenge;

vector response calculating means which calculates 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 storage unit which stores the committed vector, the first commitment, the basis vector, the second commitment, the vector challenge, and the vector response,

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

42. The signature apparatus according to claim 41,

wherein the committed vector selecting means selects a plurality of the committed vectors, each having the same configuration as the committed vector,

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

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

43. The signature apparatus according to claim 42,

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

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

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

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

44. The signature apparatus according to claim 43,

wherein the committed vector includes two components, the 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,

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

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

45. The signature apparatus according to claim 44,

wherein assuming that security parameters are κ

, N, and ν

, and an order of the cyclic group is q,

the committed vector selecting means selects a residue group X_—

{01}, . . . , X_—

{0N}ε

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

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

{1j},

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

the first commitment calculating means selects at random a bit column r of ν

bits,

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},

the basis vector calculating means sets a hash value of data including the public key and the first commitment C_{ij} to the basis vector V=(u_—

1, . . . , u_N),

the second commitment calculating means calculates an inner product of the basis vector V and the Y_—

0 and calculates a second commitment G=ĝ

{X},

the vector challenge calculating means calculates 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,

the vector response calculating means calculates the vector response ξ

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

=(ξ

_—

1, . . . , ξ

_κ

), and

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

) is output.

46. The signature apparatus according to claim 41,

wherein the committed vector selecting means select a plurality of the committed vectors, each having the same configuration as the committed vector, and

each component of the plurality of committed vectors and a secret key satisfy a relational equation.

47. The signature apparatus according to claim 46,

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.

48. The signature apparatus according to claim 47,

wherein the plurality of committed vectors include a plurality of components,

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

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.

49. The signature apparatus according to claim 47,

wherein assuming that security parameters are κ

, N, and ν

, and an integer set R{κ

+ξ

} satisfies 0≦

R{κ

+ξ

}<

2̂

{κ

+ξ

},

the committed vector selecting means selects a residue group X_—

{01}, . . . , X_—

{0N}ε

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

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

{1j},

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

the first commitment calculating means selects at random a bit column r of ν

bits,

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},

the basis vector calculating means sets a hash value of data including the public key and the first commitment C_{ij} to the basis vector V=(u_—

1, . . . , u_N),

the second commitment calculating means calculates an inner product of the basis vector V and the Y_—

0 and calculates a second commitment G=ĝ

{X},

the vector challenge calculating means calculates 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,

the vector response calculating means calculates the vector response ξ

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

=(ξ

_—

1, . . . , ξ

_κ

), and

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

) is output.

50. The signature apparatus according to claim 49, comprising:

committed vector selecting means which selects a committed vector associated with a first commitment;

first commitment calculating means which calculates a first commitment;

basis vector calculating means which calculates a basis vector;

second commitment calculating means which calculates the power residue and generates a second commitment;

vector challenge calculating means which calculates a vector challenge;

vector response calculating means which calculates 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 storage unit which stores the committed vector, the first commitment, the basis vector, the second commitment, the vector challenge, and the vector response,

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

51. The signature apparatus according to claim 50,

wherein the committed vector selecting means selects a plurality of the committed vectors, each having the same configuration as the committed vector,

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

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

52. The signature apparatus according to claim 51,

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

the first commitment is data including a random number,

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

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

53. The signature apparatus according to claim 52,

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,

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

the basis vector is a value obtained by multiplying a predetermined number t with (1, t̂

1, t̂

2, . . . , t̂

N).

54. The signature apparatus according to claim 53,

wherein assuming that the message is M,

the committed vector selecting means selects at random Y_—

0=(X_—

{01}, . . . , X_—

{0N})ε

Zq̂

{N}, calculates X_—

{1j}=x+X_—

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

1=(X_—

{11}, . . . X_—

{1N}),

the second commitment calculating means calculates X=<

{Y_—

0, V}>

=Σ

_jX_—

{0j}2̂

{j−

1} modq and calculates the commitment G=ĝ

{X},

the first commitment calculating means selects at random r_{ij}ε

{0, 1}̂

{ν

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

{{0, 1}̂

ν

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

the vector challenge calculating means calculates K=(c_—

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

{{0, 1}̂

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

the vector response calculating means calculates the vector response ξ

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

=(ξ

_—

{1}, . . . , ξ

_{N}), and

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

) is output.

66. A proving apparatus using a method of determining a validity of a proof text in the method according to claim 44.

67. A proving apparatus using a method of determining a validity of a signature text in the method according to claim 48.

68. A proving apparatus using a method of determining a validity of a signature text generated by the method according to claim 53.

69. A proving apparatus for determining a validity of a 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

a signature text generated by the signature apparatus according to claim 44 is used as a proof text or a portion thereof for determining validity.

70. A proving apparatus for determining a validity of a 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

a signature text generated by the signature apparatus according to claim 48 is used as a proof text or a portion thereof for determining validity.

71. A proving apparatus for determining a validity of a public key in a verifying apparatus using a verifier-designated proving scheme,

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

a signature text generated by the signature apparatus according to claim 53 is used as a proof text or a portion thereof for determining validity.

74. An encrypting apparatus using a signature text generated by the method according to claim 44 as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

75. An encrypting apparatus using a signature text generated by the method according to claim 48 as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

76. An encrypting apparatus using a signature text generated by the method according to claim 53 as a proof text or a portion thereof for proving knowledge of a random number used to generate a cipher text.

55. A verifying apparatus for determining a validity of an input data,

wherein the input data includes a message and a signature text associated with the message,

only if the data is valid, the data is accepted, first commitments are used for verification calculation, and a power residue is performed the number of times less than the number of the first commitments,

if the validity of the data is authenticated, the first commitments are hash values of data including components of a vector response which is a portion of the data,

a public key is data including a pair of elements of a cyclic group associated with a discrete logarithm problem, and

a secret key is a discrete logarithm of an order of the pair.

56. The verifying apparatus according to claim 55, comprising:

basis vector calculating means which calculates a basis vector;

vector challenge calculating means which calculates a vector challenge;

first commitment validity verifying means which determines a validity of the first commitment;

second validity verifying means which calculates power residue and determines a validity of the vector response; and

storage means which stores data input to and output from each of the means,

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

only if the first commitment validity verifying means and the second validity verifying means determine that the signature text is valid, the input of the data is accepted.

57. The verifying apparatus according to claim 56,

wherein the first commitment validity verifying means inputs a portion of the input data including the vector response to a hash function in a predetermined method and determines that the first commitment is valid only if the calculated hash value is equal to the first commitment,

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

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

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

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.

58. The verifying apparatus according to claim 57,

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

the data selected at random is input to each hash function calculated by the first commitment validity verifying means,

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

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

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

59. The verifying apparatus according to claim 58,

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.

60. The verifying apparatus according to claim 59,

wherein assuming that the message is M, and the to-be-determined data is (r, {C_{ij}}, G, Ξ

),

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

1, . . . , u_N),

the vector challenge calculating means calculates 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),

the first commitment validity verifying means determines 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,

the hash function is a hash value of data including the public key, ξ

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

the second validity verifying means determines whether or not ĝ

{<

V, Ξ

>

}=ĥ

{<

V, K>

}G is satisfied and determines that the signature text is valid if ĝ

{<

V, Ξ

>

}=ĥ

{<

V, K>

}G is satisfied.

61. The verifying apparatus according to claim 55, comprising:

vector challenge calculating means which calculates the vector challenge;

first commitment validity verifying means which determines a validity of the first commitment; and

second validity verifying means which calculates the power residue and determines a validity of the vector response,

wherein the signature text is accepted only if the validity is authenticated in the first commitment validity verifying means and the second validity verifying means.

62. The verifying apparatus according to claim 61,

wherein, if a hash value obtained by inputting a portion of the input data to a hash function is equal to the first commitment, the first commitment validity verifying means determines that the first commitment is valid, and

the data input to the hash function is used to calculate two power residues, and it is determined 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,

the 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,

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,

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

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

63. The verifying apparatus according to claim 62,

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

the data to be selected at random is input to each of the hash functions calculated by the first commitment validity verifying means,

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

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

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

64. The verifying apparatus according to claim 63,

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.

65. The verifying apparatus according to claim 64,

wherein assuming that the message is M, and the to-be-verified signature text is ({C_{ij}}, {r_{cjj}}, G, Ξ

),

the vector challenge calculating means calculates K=(c_—

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

{{0, 1}̂

{N}}(g, h, {C_{ij}, G, M},

the first commitment validity verifying means determines 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, the second validity verifying means determines whether or not ĝ

{<

V, Ξ

>

}=ĥ

{<

V, K>

}G is satisfied,

if ĝ

{<

V, Ξ

>

}=ĥ

{<

V, K>

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

if ĝ

{<

V, Ξ

>

}=ĥ

{<

V, K>

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

72. A verifying apparatus for verifying a validity of a proof text for a public key of a verifier-designated proving scheme verifying apparatus, wherein the verifying is performed by using the method according to claim 59.

73. A verifying apparatus for verifying a validity of a proof text for a public key of a verifier-designated proving scheme verifying apparatus, wherein the verifying is performed by using the method according to claim 64.

77. A decrypting apparatus including a proof text as a portion of a cipher text and verifying the proof text by the method according to claim 59.

78. A decrypting apparatus including a proof text as a portion of a cipher text and verifying the proof text by the method according to claim 64.