ID-based signature, encryption system and encryption method

• US 7,711,113 B2
• Filed: 02/03/2005
• Issued: 05/04/2010
• Est. Priority Date: 12/09/2004
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Takahashi, Masashi
• Primary Examiner(s): Lipman; Jacob
• Application Number:
  US11/048,863
• Publication Number:
  US 20060126832A1
• Time in Patent Office: 1,916 Days
• Field of Search: 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

An ID-based encryption and signature technique, according to which more efficient and higher speed processing is possible. In generation of public parameters, an element P of a group G₁ of order q is selected, and then, g=e(P, P) calculated in advance is added to the public parameters. At the time of encryption and verification, a public key ID is associated with an element P_ID of the group G₁, using uεZ_q* and two elements P₁ and P₂ (included in the public parameters) of G₁ and calculating P_ID=P₁+uP₂. The above-mentioned elements P₁ and P₂ are determined by P₁=s₁P and P₂=s₂P using random numbers s₁, s₂εZ_q* as a part of a master key, and a private key of a user is determined by d_ID=(s₁+us₂)⁻¹P.

Claims

1. A private key generation apparatus in an ID-based signature and encryption system that comprises an encryption apparatus and a decryption apparatus and can use any character string as a public key, wherein:

said private key generation apparatus comprises;

a control and arithmetic unit, and a storage unit, wherein

said control and arithmetic unit comprises;

a private key generation and issuing means, which generates public parameters and a master key used in the entire system and stores the generated public parameters and master key into said storage unit, and uses said master key of said storage unit for generating a private key corresponding to a client'"'"'s public key in response to a request of a client'"'"'s computer, to issue the generated private key to said client'"'"'s computer as a requester, where the private key is a most elemental private key initially-formed in the system; and

a parameter publication means, which publishes said public parameters of said storage unit; and

said private key generation and issuing means;

adds g=e(P, P) (e is a bilinear mapping called a pairing) calculated in advance using a selected element P of a group of order q to said public parameters of said storage unit; and

defines two elements P₁ and P₂ of said group as P₁=s₁P and P₂=s₂P, using random numbers s₁ and s₂ as a part of said master key, with s₁ and s₂ being included in a set Z_q* of positive integers less than said order q and relatively prime with q, to calculate (s₁+us₂)<sup>−

1</sup>P as the private key which is the most elemental private key initially-formed in the system.

2. A private key generation apparatus according to claim 1, wherein:

for calculating said q, P, g, P₁, P₂, s₁ and s₂ respectively, said private key generation and issuing means comprises;

a prime number generation means, which randomly generates a k bit prime number q for a positive integer k inputted;

a group generation means, which generates two groups G₁ and G₂ of order q;

an element generation means, which generates an element P of said group G₁;

a random number generation means, which generates random numbers s₁ and s₂ satisfying 0<

s₁, s₂<

q;

a group arithmetic means, which performs calculation of P₁=s₁P and P₂=s₂P;

a pairing selection means, which selects a pairing e;

G₁×

G₁→

G₂;

a paring arithmetic means, which calculates g=e(P, P);

a hash selection means, which selects hash functions H₁;

{0, 1}*→

Z_q* and H₂;

G₂→

{0, 1}*;

a function selection means, which selects a function f;

Z_q*→

Z_q*;

a function arithmetic means, which performs a function operation; and

a basic arithmetic means, which performs a residue operation.

3. A private key generation apparatus according to claim 2, wherein;

said parameter publication means publishes <

q, G₁, G₂, e, g, P₁, P₂, H₁, H₂, f>

as said public parameters; and

said private key generation and issuing means stores <

P, s₁, s₂>

into said storage unit as said master key.

4. A private key generation apparatus according to claim 2, wherein:

when said public key is ID and when d_ID=(s₁+us₂)<sup>−

1</sup>P can not be calculated for u=H₁(ID), then said private key generation and issuing means generates d_ID=(s₁+f(u)s₂)<sup>−

1</sup>P as the private key of said client.

5. An encryption and signature generation apparatus in an ID-based signature and encryption system that comprises a private key generation apparatus according to claim 1 and can use any character string as a public key, wherein:

said encryption and signature generation apparatus comprises an encryption and signature generation means, which performs at least one of a message encryption processing performed using the public parameters published by said private key generation apparatus and a public key of a recipient and a signature generation processing performed using said public parameters and a said client'"'"'s private key issued by said private key generation apparatus;

said encryption and signature generation means associates an element P_ID of a group (which is selected when said public parameters are generated) of order q with the public key, by calculating P_ID=P₁+uP₂ using u included in a set Z_q* of positive integers less than order q and relatively prime with order q, and using two elements P₁ and P₂ included in said group.

6. An encryption and signature generation apparatus according to claim 5, wherein:

said encryption and signature generation means determines said u on said group by u=H₁(ID) (ID is the public key); and

when said P_ID becomes an identity in said group, said encryption and signature generation means associates an element P_ID of said group of order q with the public key, by calculating P_ID=P₁+f(u)P₂ (f is a function from Z_q* to Z_q*).

7. An encryption and signature generation apparatus according to claim 5, wherein

said encryption and signature generation means comprises:

a random number generation means, which generates a random number;

a group arithmetic means, which performs a group operation;

a hash value calculation means, which calculates a hash value;

an exclusive OR calculation means, which performs an exclusive OR operation; and

a function arithmetic means, which performs a functional operation.

8. A decryption and signature verification apparatus in an ID-based signature and encryption system that comprises a private key generation apparatus according to claim 1 and an encryption and signature generation apparatus according to claim 5, with said system can use any character string as a public key, wherein:

said decryption and signature verification apparatus comprises a control and arithmetic unit, which performs at least one of decryption processing that is performed using a public parameters published by said private key generation apparatus and said client'"'"'s private key issued by said private key generation apparatus, for decrypting a message encrypted by said encryption and signature generation apparatus, and signature verification processing that is performed using said public parameters and a public key of a sender, for verifying a message on which signature generation processing has been performed by said encryption and signature verification apparatus; and

said control and arithmetic unit associates an element P_ID of a group (which is selected when said public parameters are generated) of order q with the public key, by calculating P_ID=P₁+uP₂ using u included in a set Z_q* of positive integers less than order q and relatively prime with order q, and using two elements P₁ and P₂ included in said group.

9. A decryption and signature verification apparatus according to claim 8, wherein:

when said P_ID becomes the identity in said group, said control and arithmetic unit associates an element P_ID of said group of order q with the public key by calculating P_ID=P₁+f(u)P₂ (f is a function from Z_q* to Z_q*).