Verification apparatus

The present invention relates to a verification apparatus that verifies the consistency of a ciphertext or the like in a cryptographic system such as a public key cryptographic system.

A cryptographic system is available which employs a finite group such as a group formed of the residue classes of integers under multiplication or a group formed of points on an elliptic curve.

In the cryptographic system employing the finite group, it may be judged whether or not h=e·s (when group operation of the finite group is described additively) or h=s e (when group operation of the finite group is described multiplicatively) based on elements h and s of the finite group and an integer e in order to verify, for example, the consistency of a ciphertext. Patent Document 1: JP 2004-201124 Patent Document 2: WO00/39668 Patent Document 3: U.S. Pat. No. 7,110,538 Non-Patent Document 1: R. P. Gallant, R. J. Lambert, S. A. Vanstone, “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”, Crypto 2001, LNCS 2139, pp. 190 to 200, 2001 Non-Patent Document 2: “18033-2: Information Technology-Security techniques-Encryption algorithms-Part 2: Asymmetric ciphers”, ISO/IEC 18033-2, 2006 Non-Patent Document 3: R. Cramer, V. Shoup, “Design and Analysis of Practical Public-Key Encryption Schemes secure against Adaptive Chosn Ciphertext Attack” Cryptology ePrint Archive, http://eprint.iacr.org, 2001 Non-Patent Document 4: D. Boneh, X. Boyen, “Efficient Selective-ID Secure Identity Based Encryption Without Random Oracle” EUROCRYPT 2004, LNCS 3027, pp. 223 to 238, 2004 Non-Patent Document 5: X. Boyen, “The BB1 Identity-Based Cryptosystem: A Standard for Encryption and Key Encapsulation”, Submissions for IEEE P1363.3, http://grouper.ieee.org/groups/1363/IBC/submissions/index.html, 2006 Non-Patent Document 6: M. Barbosa, L. Chen, Z. Cheng, M. Chimley, A. Dent, P. Farshim, K. Harrison, J. Malone-Lee, N. P. Smart, F. Vercauteren, “SK-KEM: An Identity-Based KEM”, Submissions for IEEE P1363.3, http://grouper.ieee.org/groups/1363/IBC/submissions/index.html Non-Patent Document 7: M. Bellare, C. Namprempre, G. Neven, “Security Proofs for Identity-Based Identification and Signature Schemes”, EUROCRYPT 2004, LNCS 3027, 2004

Problems to be Solved by the Invention

The finite group employed in the cryptographic system has a very large order. It may take a long period of time for a processing device such as a computer to perform one group operation.

The present invention has been made to solve, for example, the above problem, and has as its object to judge at a high speed whether or not h=s·e using a processing device such as a computer.

Means to Solve the Problem

A verification apparatus according to the present invention comprises

a processing device which processes data, an integer partitioning unit, a verification value calculation unit, and a verification judging unit, using the processing device, the integer partitioning unit inputs an order p of a finite group G and an integer e, and calculates an integer e 1 and an integer e 2 that satisfy e 1 ·e≡e 2 (mod p) based on the order p and the integer e which are input, using the processing device, the verification value calculation unit inputs an element s of the finite group G and an element h of the finite group G, and calculates an element a (=e 1 ·h−e 2 ·s) of the finite group G based on the element s and the element h which are input and the integer e 1 and the integer e 2 which are calculated by the integer partitioning unit, and the verification judging unit judges, using the processing device and based on the element a calculated by the verification value calculation unit, that verification is successful when the element a is an identity element of the finite group G.

In the verification apparatus according to the present invention, the integer partitioning unit calculates, using the processing device, the integer e 1 and the integer e 2 that satisfy a condition that an absolute value of the integer e 1 is smaller than a square root of the order p and that the integer e 2 is smaller than a square root of the order p.

The verification apparatus according to the present invention further comprises a storage device which stores data,

the integer partitioning unit has a first remainder storage unit, a second remainder storage unit, an initial value setting unit, a conformity judging unit, a third remainder calculation unit, and a partitioned integer output unit, the first remainder storage unit stores an integer v 1 using the storage device, the second remainder storage unit stores an integer v 2 using the storage device, the initial value setting unit causes, using the processing device, the first remainder storage unit to store the order p as the integer v 1 , and the second remainder storage unit to store the integer e as the integer v 2 , the conformity judging unit judges, using the processing device, that the output condition is satisfied when the integer v 2 stored by the second remainder storage unit is smaller than the square root of the order p, when the conformity judging unit does not judge that the output condition is satisfied, the third remainder calculation unit calculates, using the processing device and based on the integer v 1 stored by the first remainder storage unit and the integer v 2 stored by the second remainder storage unit, a remainder obtained when the integer v 1 is divided by the integer v 2 , and treats the remainder as an integer v 3 , causes the first remainder storage unit to store the integer v 2 stored by the second remainder storage unit as the integer v 1 , and causes the second remainder storage unit to store the integer v 3 calculated as the integer v 2 , and when the conformity judging unit judges that the output condition is satisfied, the partitioned integer output unit outputs, using the processing device, the integer v 2 stored by the second remainder storage unit as the integer e 2 .

In the verification apparatus according to the present invention,

the integer partitioning unit further comprises a first coefficient storage unit, a second coefficient storage unit, a quotient calculation unit, and a third coefficient calculation unit, the first coefficient storage unit stores an integer t 1 using the storage device, the second coefficient storage unit stores an integer t 2 using the storage device, the initial value setting unit, using the processing device, further causes the first coefficient storage unit to store 0 as the integer t 1 , and the second coefficient storage unit to store 1 as the integer t 2 , the quotient calculation unit, using the processing device and based on the integer v 1 stored by the first remainder storage unit and the integer v 2 stored by the second remainder storage unit, calculates a maximum integer that does not exceed a quotient obtained when the integer v 1 is divided by the integer v 2 , and treats the integer calculated as an integer q, when the conformity judging unit does not judge that the output condition is satisfied, the third coefficient calculation unit calculates, using the processing device and based on the integer t 1 stored by the first coefficient storage unit, the integer t 2 stored by the second coefficient storage unit, and the integer q calculated by the quotient calculation unit, an integer obtained by subtracting a product of the integer t 2 and the integer q from the integer t 1 and treats the integer calculated as an integer t 3 , causes the first coefficient storage unit to store the integer t 2 stored by the second coefficient storage unit as the integer t 1 , and causes the second coefficient storage unit to store the integer t 3 calculated as the integer t 2 , and using the processing device, when the conformity judging unit judges that the output condition is satisfied, the partitioned integer output unit further outputs the integer t 2 stored by the second coefficient storage unit as the integer e 1 .

In the verification apparatus according to the present invention,

the verification value calculation unit calculates Σ(n i ·P i ) using the processing device (where n is a predetermined integer not less than 2, i is an integer not less than 0 and not more than k, k is a maximum value of numbers of digits of an absolute value of the integer e 1 and of the integer e 2 , both expressed in base-n notation, P i is an element of the finite group G and satisfies P i =e 1,sgn ·e 1,i ·h−e 2,i ·s, e 1,sgn is one of 1 and −1, and e 1,i and e 2,i are integers each not less than 0 and not more than n−1 and satisfying e 1 =e 1,sgn ·Σ(n i ·e 1,i ) and e 2 =Σ(n i ·e 2,i )), and treats the value calculated as the element a of the finite group G.

A ciphertext decryption apparatus according to the present invention comprises a storage device which stores data, a processing device which processes data, a key storage unit, a ciphertext input unit, a ciphertext verification unit, a verification apparatus according to claim 1 , and a decrypted text generating unit,

the key storage unit stores, using the storage device, a key for decrypting a ciphertext, the ciphertext input unit inputs, using the processing device, the ciphertext, the ciphertext verification unit calculates, using the processing device, an integer e, an element s of the finite group G, and an element h of the finite group G, which are to be input by the verification apparatus, based on the key stored by the key storage unit and the ciphertext input by the ciphertext input unit, the verification apparatus inputs the integer e, the element s of the finite group G, and the element h of the finite group G, which are calculated by the ciphertext verification unit, and judges whether or not verification is successful, and when the verification apparatus judges that the verification is successful, the decrypted text generating unit decrypts, using the processing device, the ciphertext input by the ciphertext input unit using the key stored by the key storage unit, to generate a decrypted text.

The ciphertext decryption apparatus according to the present invention further comprises an encryption parameter storage unit, an identifier storage unit, an identifier element calculation unit, and an identifier element storage unit,

using the storage device, the encryption parameter storage unit stores an order p of the finite group G, a generator g 1 of the finite group G, and an element R of the finite group G, using the storage device, the identifier storage unit stores a bit string ID that identifies the ciphertext decryption apparatus, using the processing device, based on the bit string ID stored by the identifier storage unit, the identifier element calculation unit calculates a hash value which is obtained when the bit string ID is hashed by a predetermined hash function H 1 , and treats the hash value calculated as an integer H 1 (ID), and based on the generator g 1 stored by the encryption parameter storage unit, the element R stored by the encryption parameter storage unit, and the integer H 1 (ID) calculated, the identifier element calculation unit adds the element R to an element which is obtained when the generator g 1 is multiplied by the integer H 1 (ID), and treats a result as an element Q (=R+H 1 (ID)·g 1 ) of the finite group G, using the storage device, the identifier element storage unit stores the element Q calculated by the identifier element calculation unit, using the storage device, the key storage unit stores an element D ID of finite group G 2 , using the processing device, the ciphertext input unit inputs an element U of the finite group G and a bit string V as a ciphertext, the ciphertext verification unit has the pairing value calculation unit, a bit string calculation unit, and an integer calculation unit, using the processing device and based on the element U input by the ciphertext input unit and the element D ID stored by the key storage unit, the pairing value calculation unit calculates a pairing value of the element U and element D ID by a predetermined pairing function e, and treats the pairing value calculated as a pairing value α (=e(U,D ID )), using the processing device, based on the pairing value α calculated by the pairing value calculation unit, the bit string calculation unit calculates a hash value which is obtained when the pairing value α is hashed by a predetermined hash function H 2 , and treats the hash value calculated as a bit string H 2 (α), and based on the bit string V input by the ciphertext input unit and the bit string H 2 (α) calculated, the bit string calculation unit obtains an exclusive OR of the bit string V and the bit string H 2 (α), and treats the exclusive OR obtained as a bit string m (=V XOR H 2 (α)), using the processing device and based on the bit string m calculated by the bit string calculation unit, the integer calculation unit calculates a hash value which is obtained when the bit string m is hashed by a predetermined hash function H 3 , and treats the hash value calculated as an integer r (=H 3 (m)), the verification apparatus inputs an order p stored by the encryption parameter storage unit as the order p, the integer r calculated by the integer calculation unit as the integer e, the element Q stored by the identifier element storage unit as the element s, and the element U input by the ciphertext input unit as the element h, and judges whether or not verification is successful, and when the verification apparatus judges that the verification is successful, the decrypted text generating unit, using the processing device, calculates, based on the bit string m calculated by the bit string calculation unit, a hash value which is obtained when the bit string m is hashed by a predetermined hash function H 4 , and treats the hash value calculated as a common key K (=H 4 (m)), and outputs the common key K calculated as the decrypted text.

In the ciphertext decryption apparatus according to the present invention, the identifier element calculation unit calculates the element Q before the ciphertext input unit inputs the ciphertext.

The ciphertext decryption apparatus according to the present invention further comprises a common key storage unit, an encrypted message input unit, and a message decryption unit,

using the storage device, the common key storage unit stores the common key K output by the decrypted text generating unit, using the processing device, the encrypted message input unit inputs an encrypted message, and using the processing device, the message decryption unit decrypts the encrypted message input by the encrypted message input unit by means of the common key K stored by the common key storage unit.

The ciphertext decryption apparatus according to the present invention further comprises an encryption parameter storage unit,

using the storage device, the encryption parameter storage unit stores the order p of the finite group G, using the storage device, the key storage unit stores an integer w not less than 1 and not more than p−1, an integer x not less than 1 and not more than p−1, an integer y not less than 1 and not more than p−1, and an integer z not less than 1 and not more than p−1, using the processing device, the ciphertext input unit inputs an element u of the finite group G, an element u′ of the finite group G, and an element v of the finite group G, as the ciphertext, the ciphertext verification unit has a hash value calculation unit and an integer calculation unit, using the processing device and based on the element u and element u′ input by the ciphertext input unit, the hash value calculation unit calculates a hash value which is obtained when the element u and the element u′ are hashed by a predetermined hash function H, and treats the hash value calculated as an integer α (=H(u,u′)), using the processing device, and based on the order p stored by the encryption parameter storage unit, the integer x and integer y stored by the key storage unit, and the integer α calculated by the hash value calculation unit, the integer calculation unit calculates a remainder which is obtained when a sum of the integer x and a product of the integer y and integer α is divided by the order p, and treats the remainder calculated as an integer t (=(x+y·α)mod p), the verification apparatus inputs the order p stored by the encryption parameter storage unit as the order p, the integer w stored by the key storage unit as the integer e, the element u input by the ciphertext input unit as the element s, and the element u′ input by the ciphertext input unit as the element h, judges whether or not the verification is successful, and treats a judgment result as a first verification result, and the verification apparatus inputs the order p stored by the encryption parameter storage unit, the integer t stored by the integer calculation unit as the integer e, the element u input by the ciphertext input unit as the element s, and the element v input by the ciphertext input unit as the element h, judges whether or not the verification is successful, and treats a judgment result as a second verification result, and when both the first verification result and the second verification result show that the verification apparatus judges the verification successful, using the processing device, based on the integer z stored by the key storage unit and the element u input by the ciphertext input unit, the decrypted text generating unit adds z times the element u, and treats a result as the element h (=z·u) of the finite group G, and based on the element u input by the ciphertext input unit and an element h ˜ calculated, the decrypted text generating unit generates the common key K (=KDF(u,h ˜ )) from the element u and the element h ˜ by a predetermined key derivation function KDF, and outputs the common key K generated as the decrypted text.

The ciphertext decryption apparatus according to the present invention further comprises a common key storage unit, an encrypted message input unit, and a message decryption unit,

using the storage device, the common key storage unit stores the common key K output by the decrypted text generating unit, using the processing device, the encrypted message input unit inputs an encrypted message, and using the processing device and by means of the common key K stored by the common key storage unit, the message decryption unit decrypts the encrypted message input by the encrypted message input unit.

The ciphertext decryption apparatus according to the present invention further comprises an encryption parameter storage unit,

using the storage device, the encryption parameter storage unit stores an order p of an additive group G 1 , a generator g of the additive group G 1 , and an element v 0 of a multiplicative group G T whose order is the order p, using the storage device, the key storage unit stores an element d 0 of an additive group G 2 whose order is the order p, and an element d 1 of the additive group G 2 , using the processing device, the ciphertext input unit inputs a bit string c, an element c 0 of the additive group G 1 , an element c 1 of the additive group G 1 , and an integer t not less than 1 and not more than p−1, as the ciphertext, the ciphertext verification unit has a pairing value calculation unit and an integer calculation unit, using the processing device, based on the element c 0 input by the ciphertext input unit and the element d 0 stored by the secret key storage unit, the pairing value calculation unit calculates a pairing value of the element c 0 and element d 0 by a predetermined pairing function e, and treats the value calculated as an element k 0 (=e(c 0 , d 0 )) of the multiplicative group G T , based on the element c 1 input by the ciphertext input unit and the element d 1 stored by the secret key storage unit, the pairing value calculation unit calculates a pairing value of the element c 1 and element d 1 by the pairing function e, and treats the value calculated as an element k 1 (=e(c 1 , d 1 )) of the multiplicative group G T , and based on the element k 0 calculated and the element k 1 calculated, the pairing value calculation unit divides the element k 0 by the element k 1 , and treats an element obtained as an element k (=k 0 /k 1 ) of the multiplicative group G T , using the processing device, based on the element k calculated by the pairing value calculation unit, and the bit string c, element c 0 , and element c 1 input by the ciphertext input unit, the integer calculation unit calculates a hash value which is obtained when the element k, bit string c, element c 0 , and element c 1 are hashed by a predetermined hash function H″, and treats a value calculated as an integer H″(k,c,c 0 ,c 1 ), and based on the integer t input by the ciphertext input unit, the integer H″(k,c,c 0 ,c 1 ) calculated, and the order p stored by the encryption parameter storage unit, the integer calculation unit calculates a remainder which is obtained when an integer obtained by subtracting the integer H″(k,c,c 0 ,c 1 ) from the integer t is divided by the order p, and treats the remainder calculated as an integer s (=t−H″(k,c,c 0 ,c 1 )mod p), the verification apparatus treats the additive group G 1 as the finite group G, and inputs the order p stored by the encryption parameter storage unit, as the order p, the integer s calculated by the integer calculation unit, as the integer e, the generator g stored by the encryption parameter storage unit, as the element s, and the element c 0 input by the ciphertext input unit, as the element h, the verification apparatus judges whether or not the verification is successful, and treats a result as a first verification result, the verification apparatus treats the multiplicative group G T as the finite group G, and inputs the order p stored by the encryption parameter storage unit, as the order p, the integer s calculated by the integer calculation unit, as the integer e, the element v 0 stored by the encryption parameter storage unit, as the element s, and the element k calculated by the pairing value calculation unit, as the element h, and the verification apparatus judges whether or not the verification is successful, and treats a result as a second verification result, and when both the first verification result and the second verification result show that the verification apparatus judges the verification successful, using the processing device, based on the element k calculated by the pairing value calculation unit, the decrypted text generating unit calculates a hash value which is obtained when the element k is hashed by a hash function H′, and treats the value calculated as a bit string H′(k), based on the bit string c input by the ciphertext input unit and the bit string H′(k) calculated, the decrypted text generating unit obtains an exclusive OR of the bit string c and the hash value H′(k), and treats a result as a bit string M′ (=c XOR H′(k)), and the decrypted text generating unit outputs the calculated bit string M′ as the decrypted text.

A signature verification apparatus according to the present invention comprises a processing device which processes data, a message input unit, a signature input unit, a signature verification unit, a verification apparatus and a verification result output unit,

using the processing device, the message input unit inputs a message, using the processing device, the signature input unit inputs a signature for the message input by the message input unit, using the processing device and based on the message input by the message input unit and the signature input by the signature input unit, the signature verification unit calculates an integer e, an element s of the finite group G, and an element h of the finite group G, which are to be input to the verification apparatus, the verification apparatus inputs the integer e, the element s of the finite group G, and the element h of the finite group G, which are calculated by the signature verification unit, and judges whether or not verification is successful, and using the processing device and based on a verification result of the verification apparatus, the verification result output unit outputs a verification result indicating whether or not the verification is successful.

The signature verification apparatus according to the present invention further comprises a storage device which stores data, an encryption parameter storage unit, and an identifier storage unit,

using the storage device, the encryption parameter storage unit stores an order p of the finite group G, a generator g of the finite group G, and an element X of the finite group G, using the storage device, the identifier storage unit stores a bit string ID that identifies a signature apparatus, using the processing device, the message input unit inputs a bit string M as the message, using the processing device, the signature input unit inputs an element R of the finite group G, an element S of the finite group G, an element Y of the finite group G, and an integer z not less than 1 and not more than p−1, as the signature, the signature verification unit has an integer calculation unit, a verification element calculation unit, a challenge calculation unit, and a first verification unit, using the processing device and based on the element R input by the signature input unit and the bit string ID stored by the identifier storage unit, the integer calculation unit calculates a hash value which is obtained when the element R and the bit string ID are hashed by a predetermined hash function H, and treats the value calculated as an integer h (=H(R,ID)), using the processing device and based on the element R and element S input by the signature input unit, the verification element calculation unit adds the element S and an inverse element of the element R, and treats a sum as an element R′ (=S−R) of the finite group G, using the processing device and based on the bit string ID stored by the identifier storage unit, the element R, element S, and element Y input by the signature input unit, and the bit string M input by the message input unit, the challenge calculation unit calculates a hash value which is obtained when the bit string ID, the element R, the element S, the element Y, and the bit string M are hashed by a predetermined hash function H′, and treats the value calculated as an integer c (=H′(I,R,S,Y,M)), using the processing device and based on the generator g stored by the encryption parameter storage unit, the element S, element Y, and integer z input by the signature input unit, and the integer c calculated by the challenge calculation unit, the first verification unit judges whether or not an element Y+c·S, obtained by adding the element Y and an element c·S which is obtained when the element S is added a number of times of the integer c, is equal to an element z·g obtained when the generator g is added a number of times of the integer z, and when the element Y+c·S and the element z·g are equal, the first verification unit judges that the verification is successful, and treats a judgment result as a first verification result, the verification apparatus inputs an order p stored by the encryption parameter storage unit, as the order p, the integer h calculated by the integer calculation unit, as the integer e, the element X stored by the encryption parameter storage unit, as the element s, and the element R′ calculated by the verification element calculation unit, as the element h, judges whether or not the verification is successful, and treats a judgment result as a second verification result, and using the processing device and based on the first verification result of the verification by the first verification unit and the second verification result of the verification by the verification apparatus, when both the first verification result and the second verification result show that the verification is judged successful, the verification result output unit outputs a verification result indicating that the verification is successful.

An authentication apparatus according to the present invention comprises a processing device which processes data, a transmission device which transmits data, a reception device which receives data, an authentication request reception unit, a question transmission unit, a response reception unit, a signature verification unit, a verification apparatus, and an authentication result output unit,

using the reception device, the authentication request reception unit receives an authentication request message, using the transmission device, the question transmission unit transmits a question message as a response to the authentication request message received by the authentication request reception unit, using the reception device, the response reception unit receives the response message to the question message transmitted, using the processing device and based on the authentication request message received by the authentication request reception unit and the response message received by the response reception unit, the signature verification unit calculates an integer e, an element s of the finite group G, and an element h of the finite group G which are to be input to the verification apparatus, the verification apparatus inputs the integer e, the element s of the finite group G, and the element h of the finite group G which are calculated by the signature verification unit, and judges whether or not verification is successful, and using the processing device and based on a verification result of the verification apparatus, the authentication result output unit outputs an authentication result indicating whether or not the verification is successful.

The authentication apparatus further comprises a storage device which stores data, an encryption parameter storage unit, an identifier storage unit, and a challenge generating unit,

using the storage device, the encryption parameter storage unit stores an order p of the finite group G, a generator g of the finite group G, and an element X of the finite group G, using the storage device, the identifier storage unit stores a bit string ID which identifies a proving apparatus, using the reception device, the authentication request reception unit receives an element R of the finite group G, an element S of the finite group G, and an element Y of the finite group G from the proving apparatus as the authentication request message, using the processing device, the challenge generating unit randomly generates an integer c not less than 1 and not more than p−1, using the transmission device, the question transmission unit transmits the integer c generated by the challenge generating unit to the proving apparatus as the question message, using the reception device, the response reception unit receives an integer z not less than 1 and not more than p−1 from the proving apparatus as the response message, the signature verification unit has an integer calculation unit, a verification element calculation unit, and a first verification unit, using the processing device and based on the element R received by the authentication request reception unit and the bit string ID stored by the identifier storage unit, the integer calculation unit calculates a hash value which is obtained when the element R and the bit string ID are hashed by a predetermined hash function H, and treats the hash value calculated as an integer h (=H(R,ID)), using the processing device and based on the element R and element S received by the authentication request reception unit, the verification element calculation unit adds the element S and an inverse element of the element R, and treats a sum as an element R′ of the finite group G, using the processing device and based on the generator g stored by the encryption parameter storage unit, the element S and element Y received by the authentication request reception unit, the integer c generated by the challenge generating unit, and the integer z received by the response reception unit, the first verification unit judges whether or not an element Y+c·S, which is obtained by adding the element Y and an element c·S obtained when the element S is added c times, is equal to an element z·g which is obtained when the element g is added z times, and when the element Y+c·S and the element z·g are equal, the first verification unit judges that verification is successful, and treats a judgment result as a first verification result, the verification apparatus inputs an order p stored by the encryption parameter storage unit, as the order p, the integer h calculated by the integer calculation unit, as the integer e, the element X stored by the encryption parameter storage unit, as the element s, and the element R′ calculated by the verification element calculation unit, as the element h, judges whether or not verification is successful, and treats a judgment result as a second verification result, and using the processing device and based on the first verification result of the verification by the first verification unit and the second verification result of the verification by the verification apparatus, when both the first verification result and the second verification result show that the verification is judged successful, the authentication result output unit outputs an authentication result indicating that authentication is successful.

A cryptographic system according to the present invention comprises the verification apparatus.

A computer program according to the present invention causes a computer having a processing device that processes data, to serve as a verification apparatus according to claim 1 .

In a verification method according to the present invention used by a verification apparatus having a processing device that processes data, to verify consistency,

the processing device inputs an order p of a finite group G and an integer e, and calculates an integer e 1 and an integer e 2 that satisfy e 1 ·e≡e 2 (mod p) based on the order p and the integer e which are input, the processing device inputs an element s of the finite group

G and an element h of the finite group G, and calculates an element a (=e 1 ·h−e 2 ·s) of the finite group G based on the element g and the element h which are input and the integer e 1 and the integer e 2 which are calculated, and

the processing device judges, based on the element a calculated, that verification is successful when the element a is an identity element of the finite group G.

Effect of the Invention

According to the present invention, for example, when the element a calculated by the verification value calculation unit based on the integer e 1 and integer e 2 calculated by the integer partitioning unit is the identity element of the finite group G, the verification judging unit judges that the verification is successful. Hence, when h=e·s, it can be judged that the verification is successful. If, in the verification value calculation unit, the time necessary for the process of calculating the element a is shorter than the time necessary for calculating e·s, then the time necessary for the process of judging whether or not h=e·s can be shortened.

The first embodiment will be described with reference to FIGS. 1 to 9 .

In the following description, the finite group employed by the cryptographic system is defined as G.

An operation on the finite group G will be described additively. This is for the sake of descriptive convenience and does not exclude a group whose group operation is described multiplicatively.

Assume that an order p of the finite group G is a prime number. Accordingly, the finite group G is a cyclic group.

FIG. 1 is a block diagram showing a configuration example of the function block of a ciphertext decryption apparatus 200 of this embodiment.

The ciphertext decryption apparatus 200 inputs a ciphertext and decrypts the input ciphertext to generate a decrypted text. The ciphertext decryption apparatus 200 includes a key storage unit 210 , a ciphertext input unit 220 , a ciphertext verification unit 230 , a verification apparatus 100 , and a decrypted text generating unit 260 .

The key storage unit 210 stores a key (secret key) for decrypting the ciphertext.

The ciphertext input unit 220 inputs the ciphertext. The ciphertext verification unit 230 calculates values necessary for verifying the ciphertext input by the ciphertext input unit 220 based on the key stored by the key storage unit 210 and the ciphertext input by the ciphertext input unit 220 . The verification apparatus 100 verifies the ciphertext input by the ciphertext input unit 220 based on the values calculated by the ciphertext verification unit 230 . When the verification by the verification apparatus 100 is successful, the decrypted text generating unit 260 decrypts the ciphertext input by the ciphertext input unit 220 using the key stored by the key storage unit 210 , to generate a text as the decrypted text.

An unauthorized person may try to obtain a clue to decipher a regular ciphertext by inputting an irregular ciphertext to the ciphertext decryption apparatus 200 and analyzing a decrypted text generated by the ciphertext decryption apparatus 200 .

The ciphertext decryption apparatus 200 verifies the consistency of the ciphertext and generates a decrypted text only when the verification is successful, so that a clue to decipher the regular ciphertext will not be given to the unauthorized person.

FIG. 2 shows an example of the appearance of the ciphertext decryption apparatus 200 according to this embodiment.

The ciphertext decryption apparatus 200 includes hardware resources such as a system unit 910 , a display device 901 having a display screen such as a CRT (Cathode Ray Tube) or LCD (Liquid Crystal Display), a keyboard 902 (K/B), a mouse 903 , an FDD 904 (Flexible Disk Drive), a compact disk drive 905 (CDD), a printer 906 , and a scanner 907 , which are connected through cables and signal lines. The system unit 910 , being a computer, is connected to a facsimile machine 932 and a telephone 931 through cables, and to the Internet 940 through a local area network 942 (LAN) and a gateway 941 .

FIG. 3 shows an example of the hardware resources of the ciphertext decryption apparatus 200 of this embodiment.

The ciphertext decryption apparatus 200 includes a CPU 911 (also called a Central Processing Unit, central processing device, processing device, operation device, microprocessor, microcomputer, or processor) which executes programs. The CPU 911 is connected through a bus 912 to a ROM 913 , a RAM 914 , a communication device 915 , the display device 901 , the keyboard 902 , the mouse 903 , the FDD 904 , the CDD 905 , the printer 906 , the scanner 907 , and a magnetic disk drive 920 , and controls these hardware devices. In place of the magnetic disk drive 920 , a storage device such as an optical disk drive and a memory card reader/writer may be used. The RAM 914 is an example of a volatile memory. Storage media such as the ROM 913 , FDD 904 , CDD 905 , and magnetic disk drive 920 are examples of a nonvolatile memory. These are examples of a storage device or a storage unit. The communication device 915 , the keyboard 902 , the scanner 907 , the FDD 904 , and the like are examples of an input unit or an input device. The communication device 915 , the display device 901 , the printer 906 , and the like are examples of an output unit or an output device.

The communication device 915 is connected to the facsimile machine 932 , the telephone 931 , the LAN 942 , and the like. The communication device 915 may be connected not only to the LAN 942 but also to a WAN (Wide Area Network) such as the Internet 940 or ISDN. When connected to the WAN such as the Internet 940 or ISDN, the gateway 941 becomes unnecessary.

In the magnetic disk drive 920 , an operating system 921 (OS), a window system 922 , a program group 923 , and a file group 924 are stored. The programs of the program group 923 are executed by the CPU 911 , the operating system 921 , and the window system 922 .

In the program group 923 , a program for executing functions indicated by the term “unit” described in the embodiments to be stated below is stored. The program is read and executed by the CPU 911 .

In the file group 924 , information, data, signal values, variables, and parameters indicated by the terms “judgment result of”, “calculation result of”, or “processing result of” described in the embodiments to be stated below are stored as items of the “file” or “database”. Such “file” and “database” are stored by a recording medium such as a disk or a memory. The information, data, signal values, variables, and parameters stored by the storage medium such as a disk or memory are read to a main memory or cache memory by the CPU 911 through a read/write circuit, and used for operations of the CPU such as extraction, search, reference, comparison, operation, calculation, processing, output, printing, and display. During the operations of the CPU, namely during extraction, search, reference, comparison, operation, calculation, processing, output, printing, and display, the information, data, signal values, variables, and parameters are temporarily stored by the main memory, the cache memory, or the buffer memory. Arrows in the flowcharts described in the embodiments to be stated below mainly show inputting and outputting of data or signals. Data and signal values are recorded on recording media such as a memory in the RAM 914 , a flexible disk in the FDD 904 , a compact disk in the CDD 905 , a magnetic disk in the magnetic disk drive 920 , an optical disk, a mini disk, and a DVD (Digital Versatile Disk). Data and signals are transmitted on line by the bus 912 , a signal line, a cable, or other transmission medium.

What is described by the term “unit” in the embodiments stated below may be a “circuit”, a “device”, or an “apparatus”, or may be a “step”, a “procedure”, or “processing”. That is, what is described as a “unit” may be realized by the firmware stored by the ROM 913 . Alternatively, it may be implemented only by software, only by hardware such as an element, a device, a substrate, or a wiring, or by a combination of software and hardware, or by a combination of software, hardware, and firmware. Firmware and software are stored as programs in a recording medium such as a magnetic disk, a flexible disk, an optical disk, a compact disk, a mini disk, or a DVD. Such programs are read by the CPU 911 and executed by the CPU 911 . That is, such programs operate a computer, as units described below, or they cause the computer to execute a procedure or a method of the “unit” described below.

FIG. 4 is a block diagram of a configuration example of the internal block of the verification apparatus 100 according to this embodiment.

The verification apparatus 100 inputs an element s and an element h of the finite group G, the order p of the finite group G, and an integer e and judges whether or not h=e·s. Note that the integer e is equal to or larger than 1 and equal to or smaller than p−1.

The verification apparatus 100 has an integer partitioning unit 110 , a verification value calculation unit 130 , and a verification judging unit 150 .

Using the CPU 911 , the integer partitioning unit 110 inputs the order p of the finite group G and the integer e, and calculates two integers e 1 and e 2 . The verification value calculation unit 130 calculates, using the CPU 911 , an element a of the finite group G based on the element s and the element h of the finite group G and the integer e 1 and the integer e 2 calculated by the integer partitioning unit 110 . The verification judging unit 150 judges, using the CPU 911 , whether or not the element a calculated by the verification value calculation unit 130 is the identity element of the finite group G. If the element a is the identity element of the finite group G, the verification judging unit 150 judges that the verification is successful (that is, h=e·s).

FIG. 5 is a flowchart showing an example of the flow of a verification process used by the verification apparatus 100 of this embodiment to judge whether or not h=e·s.

In an integer partitioning process S 701 , the integer partitioning unit 110 calculates, using the CPU 911 , the two integers e 1 and e 2 based on the input order p and integer e. The integer partitioning unit 110 calculates the integer e 1 and integer e 2 that satisfy conditions e 1 ·e≡e 2 (mod p), |e 1 |<√p, and 0<|e 2 |<√p.

In a verification value calculation process S 702 , the verification value calculation unit 130 calculates, using the CPU 911 , the element a=e·h−e 2 ·s of the finite group G based on the input element s and element h and the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 in the integer partitioning process S 701 .

In a verification judging process S 703 , the verification judging unit 150 judges, using the CPU 911 , whether or not the element a calculated by the verification value calculation unit 130 in the verification value calculation process S 702 is the identity element (to be described as “0” hereinafter) of the finite group G.

If it is judged that the element a is the identity element O, the process advances to a successful judgment process S 704 . If it is judged that the element a is not the identity element O, the process advances to a failure judgment process S 705 .

In the successful judgment process S 704 , using the CPU 911 , the verification judging unit 150 judges that the verification is successful, and ends the verification process.

In the failure judgment process S 705 , using the CPU 911 , the verification judging unit 150 judges that the charter fails, and ends the verification process.

FIG. 6 is a detailed block diagram showing a configuration example of the internal block of the integer partitioning unit 110 according to this embodiment.

The integer partitioning unit 110 calculates the integer e 1 and integer e 2 that satisfy e 1 ·e≡e 2 (mod p) based on the order p of the finite group G and the integer e. More specifically, the integer partitioning unit 110 determines the integer e 1 and integer e 2 such that the remainder obtained when the product of the integer e 1 and integer e is divided by the order p is equal to the integer e 2 . In order to speedup the calculation in the verification value calculation unit 130 , the integer partitioning unit 110 chooses, among integers e 1 and integers e 2 satisfying e 1 ·e≡e 2 (mod p), an integer e 1 whose absolute value is smaller than the square root of the order p and an integer e 2 which is an integer equal to or larger than 1 and smaller than the square root of the order p.

The integer partitioning unit 110 has an order input unit 111 , an integer input unit 112 , an initial value setting unit 113 , a first remainder storage unit 114 , a second remainder storage unit 115 , a conformity judging unit 116 , a third remainder calculation unit 117 , a first coefficient storage unit 124 , a second coefficient storage unit 125 , a quotient calculation unit 126 , a third coefficient calculation unit 127 , and a partitioned integer output unit 129 .

The order input unit 111 inputs, using the CPU 911 , data representing the order p of the finite group G. The order input unit 111 stores, using the RAM 914 , the input data representing the order p.

The integer input unit 112 inputs, using the CPU 911 , data representing the integer e. The integer input unit 112 stores, using the RAM 914 , the input data representing the integer e.

The first remainder storage unit 114 stores, using the RAM 914 , data representing an integer v 1 .

The second remainder storage unit 115 stores, using the RAM 914 , data representing an integer v 2 . The first coefficient storage unit 124 stores, using the RAM 914 , data representing an integer t 1 . The second coefficient storage unit 125 stores, using the RAM 914 , data representing an integer t 2 .

The initial value setting unit 113 sets initial values to the first remainder storage unit 114 , second remainder storage unit 115 , first coefficient storage unit 124 , and second coefficient storage unit 125 .

Using the CPU 911 , the initial value setting unit 113 inputs the data representing the order p and stored by the order input unit 111 and the data representing the integer e and stored by the integer input unit 112 . The initial value setting unit 113 causes, using the CPU 911 , the first remainder storage unit 114 to store the input data representing the order p as the data representing the integer v 1 . The initial value setting unit 113 causes, using the CPU 911 , the second remainder storage unit 115 to store the input data representing the integer e as the data representing the integer v 2 . The initial value setting unit 113 causes, using the CPU 911 , the first coefficient storage unit 124 to store data representing 0 as the data representing the integer t 1 . The initial value setting unit 113 causes, using the CPU 911 , the second coefficient storage unit 125 to store data representing 1 as the data representing the integer t 2 .

Note that v 1 =p, v 2 =e, t 1 =0, and t 2 =1. Hence,

t 1 ·e+k 1 ·p=v 1   [Equation 1]

t 2 ·e+k 2 ·p=v 2   [Equation 2]

v 1 >v 2 ≧0   [Equation 3]

| t 1 |<t 2 |[Equation 4]

v 1 ·|t 2 |+v 2 ·|t 1 |=p   [Equation 5]

where k 1 and k 2 are integers.

The conformity judging unit 116 inputs, using the CPU 911 , the data representing the order p and stored by the order input unit 111 , and the data representing the integer v 2 by the second remainder storage unit 115 . The conformity judging unit 116 judges, using the CPU 911 , whether or not an output condition is satisfied based on the order p and integer v 2 represented by the input data. More specifically, using the CPU 911 , the conformity judging unit 116 compares the integer v 2 and the square root of the order p, and judges that the output condition is satisfied when the integer v 2 is smaller than the square root of the order p.

Alternatively, the conformity judging unit 116 may, using the CPU 911 , calculate in advance the maximum integer that does not exceed the square root of the order p. In place of calculating the square root of the order p, whether or not the output condition is satisfied may be judged by comparing the number of digits of the integer v 2 in binary notation and the number of digits of the order p in binary notation. More specifically, using the CPU 911 , the conformity judging unit 116 obtains the number of bits of the data representing the order p in advance, and divides the obtained number of bits by 2 (rounds it up if it not divisible), thus obtaining a square-root number of bits. A square-root number of bits represents the number of digits of an integer, in binary notation, that does not exceed the square root of the order p. The conformity judging unit 116 stores, using the RAM 914 , the calculated square-root number of bits, and calculates, using the CPU 911 , the number of bits of the data representing the integer v 2 . The conformity judging unit 116 compares, using the CPU 911 , the calculated number of bits with the stored square-root number of bits. If the number of bits of the data representing the integer v 2 is equal to or smaller than the square-root number of bits, the conformity judging unit 116 considers that the integer v 2 is smaller than the square root of the order p, and judges that the output condition is satisfied.

If the conformity judging unit 116 judges that the output condition is not satisfied, the third remainder calculation unit 117 inputs, using the CPU 911 , the data representing the integer v 1 and stored by the first remainder storage unit 114 and the data representing the integer v 2 and stored by the second remainder storage unit 115 . Based on the integer v 1 and integer v 2 represented by the input data, the third remainder calculation unit 117 calculates the remainder obtained when the integer v 1 is divided by the integer v 2 , and treats it as an integer v 3 .

Also, if the conformity judging unit 116 judges that the output condition is not satisfied, the quotient calculation unit 126 inputs, using the CPU 911 , the data representing the integer v 1 and stored by the first remainder storage unit 114 and the data representing the integer v 2 and stored by the second remainder storage unit 115 . Based on the integer v 1 and integer v 2 represented by the input data, the quotient calculation unit 126 calculates the maximum integer that does not exceed the quotient obtained when the integer v 1 is divided by the integer v 2 , and treats it as an integer q. The quotient calculation unit 126 stores, using the RAM 914 , data representing the calculated integer q.

Using the CPU 911 , the third coefficient calculation unit 127 inputs the data representing the integer t 1 and stored by the first coefficient storage unit 124 , the data representing the integer t 2 and stored by the second coefficient storage unit 125 , and the data presenting the integer q and stored by the quotient calculation unit 126 . Based on the integer t 1 , integer t 2 , and integer q represented by the input data, the third coefficient calculation unit 127 calculates, using the CPU 911 , an integer t 3 (=t 1 −q·t 2 ) which is obtained by subtracting the product of the integer q and integer t 2 from the integer t 1 .

Note that

v 3 - t 3 · e = ( v 1 - q · v 2 ) - ( t 1 - q · v 3 ) · e = ( v 1 - t 1 · e ) - q · ( v 2 - t 2 · e ) = ( k 1 - q · k 2 ) · p ⁢

∴ t 3 · e + k 3 · p = v 3 [ Equation ⁢ ⁢ 6 ]

where k 3 is an integer.

Also, since the integer v 3 is the remainder obtained when the integer v 1 is divided by the integer v 2 ,

v 2 >v 3 ≧0   [Equation 7]

Also, if v 1 >v 2 >0, q≧1 is established. Hence, if t 1 ≦0 and t 2 >0,

t 3 =t 1 −q·t 2 <0   [Equation 8]

If t 1 >0 and t 2 <0,

t 3 =t 1 −q˜t 2 >0   [Equation 9]

Therefore, in either case,

| t 3 |=|t 1 |+q·|t 2 |  [Equation 10]

Hence,

The third remainder calculation unit 117 causes, using the CPU 911 , the first remainder storage unit 114 to store the input data representing the integer v 2 as data representing the integer v 1 . Based on the calculated integer v 3 , the third remainder calculation unit 117 causes, using the CPU 911 , the second remainder storage unit 115 to store data representing the integer v 3 as data representing the integer v 2 .

The third coefficient calculation unit 127 causes, using the CPU 911 , the first coefficient storage unit 124 to store the input data representing the integer t 2 as data representing the integer t 1 . Based on the calculated integer t 3 , the third coefficient calculation unit 127 causes, using the CPU 911 , the second coefficient storage unit 125 to store data representing the integer t 3 as data representing the integer t 2 .

From equations 6 to 11, equations 1 to 5 hold among the integer v 1 , integer v 2 , integer t 1 , and integer t 2 represented by the latest data stored by the first remainder storage unit 114 , the second remainder storage unit 115 , the first coefficient storage unit 124 , and the second coefficient storage unit 125 , respectively.

When the conformity judging unit 116 judges that the output condition is satisfied, the partitioned integer output unit 129 inputs, using the CPU 911 , the data representing the integer v 2 and stored by the second remainder storage unit 115 and the data representing the integer t 2 and stored by the second coefficient storage unit 125 . The partitioned integer output unit 129 outputs, using the CPU 911 , the input data representing the integer t 2 as data representing the integer e 1 . The partitioned integer output unit 129 also outputs, using the CPU 911 , the input data representing the integer v 2 as data representing the integer e 2 .

When the third remainder calculation unit 117 and the third coefficient calculation unit 127 repeatedly perform these calculations, v 2 will become the greatest common divisor of the order p and integer e. As the order p is a prime number, the greatest common divisor of the order p and integer e is 1. Hence, 0<v 2 <√p is established eventually, and the partitioned integer output unit 129 outputs data representing the integer e 1 and integer e 2 .

FIG. 7 is a flowchart showing an example of the flow of an integer partitioning process used by the integer partitioning unit 110 according to this embodiment to partition the integer e.

In an initial value setting step S 711 , using the CPU 911 , the initial value setting unit 113 sets the initial values to the first remainder storage unit 114 , the second remainder storage unit 115 , the first coefficient storage unit 124 , and the second coefficient storage unit 125 . The first remainder storage unit 114 stores, using the RAM 914 , the order p input by the order input unit 111 as the integer v 1 . The second remainder storage unit 115 stores, using the RAM 914 , the integer e input by the integer input unit 112 as the integer v 2 . The first coefficient storage unit 124 stores, using the RAM 914 , 0 as the integer t 1 . The second coefficient storage unit 125 stores, using the RAM 914 , 1 as the integer t 2 .

In a conformity judging step S 712 , the conformity judging unit 116 judges, using the CPU 911 , whether or not the integer v 2 stored by the second remainder storage unit 115 is smaller than the square root of the order p input by the order input unit 111 .

If it is judged that the integer v 2 is smaller than the square root of the order p, the process advances to a partitioned integer output step S 718 . If it is judged that the integer v 2 is larger than the square root of the order p, the process advances to a remainder calculation step S 713 .

In the remainder calculation step S 713 , using the CPU 911 , the third remainder calculation unit 117 calculates the remainder obtained when the integer v 1 stored by the first remainder storage unit 114 is divided by the integer v 2 stored by the second remainder storage unit 115 , and treats it as the integer v 3 .

In a quotient calculation step S 714 , using the CPU 911 , the quotient calculation unit 126 calculates the maximum integer that does not exceed the quotient obtained when the integer v 1 stored by the first remainder storage unit 114 is divided by the integer v 2 stored by the second remainder storage unit 115 , and treats it as the integer q.

In a coefficient calculation step S 715 , using the CPU 911 , the third coefficient calculation unit 127 calculates an integer obtained by subtracting the product of the integer t 2 stored by the second coefficient storage unit 125 and the integer q calculated by the quotient calculation unit 126 in the quotient calculation step S 714 from the integer t 1 stored by the first coefficient storage unit 124 , and treats it as the integer t 3 .

In a remainder update step S 716 , using the CPU 911 , the third remainder calculation unit 117 updates the first remainder storage unit 114 and the second remainder storage unit 115 . Using the RAM 914 , the first remainder storage unit 114 stores the integer v 2 , stored by the second remainder storage unit 115 , as the integer v 1 . Using the RAM 914 , the second remainder storage unit 115 stores the integer v 3 , calculated by the third remainder calculation unit 117 in the remainder calculation step S 713 , as the integer v 2 .

In a coefficient update step S 717 , using the CPU 911 , the third coefficient calculation unit 127 updates the first coefficient storage unit 124 and the second coefficient storage unit 125 . Using the RAM 914 , the first coefficient storage unit 124 stores the integer t 2 stored by the second coefficient storage unit 125 as the integer t 1 . Using the RAM 914 , the second coefficient storage unit 125 stores the integer t 3 , calculated by the third coefficient calculation unit 127 in the coefficient calculation step S 715 , as the integer t 2 .

After that, the process returns to the conformity judging step S 712 .

In the partitioned integer output step S 718 , using the CPU 911 , the partitioned integer output unit 129 outputs the integer t 2 stored by the second coefficient storage unit 125 as the integer e 1 . Using the CPU 911 , the partitioned integer output unit 129 outputs the integer v 2 stored by the second remainder storage unit 115 as the integer e 2 .

After that, the integer partitioning process is ended.

From equation 2, the integer e 1 and integer e 2 output by the partitioned integer output unit 129 satisfy:

e 1 ·e+k 2 ·p=e 2 ∴e 1 ·e≡e 2 (mod p)   [Equation 12]

Also, in the conformity judging step S 712 , it is judged that the output condition is satisfied. Hence,

e 2 =v 2 <√{square root over ( p )}  [Equation 13]

Assume that the conformity judging step S 712 has been executed twice or more. In the previous conformity judging step S 712 , it is judged that the output condition is not satisfied. Hence,

v 1 >√{square root over ( p )}  [Equation 14]

At this time, from equation 5,

v 1 ·|t 2 |<p ∴|e 1 |=|t 2 |<√{square root over ( p )}  [Equation 15]

Assume that the conformity judging step S 712 is executed only once. In this case, equation 5 is satisfied since e 1 =1.

As described above, the integer partitioning unit 110 calculates the integer e 1 and integer e 2 that satisfy e 1 ·e≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p using the extended Euclidean algorithm.

FIG. 8 is a detailed block diagram showing a configuration example of the internal block of the verification value calculation unit 130 of this embodiment.

Based on the element s and element h of the finite group G and the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 , the verification value calculation unit 130 calculates the element a (=e 1 ·h−e 2 ·s) of the finite group G.

The verification value calculation unit 130 has a partitioned integer input unit 131 , an element input unit 132 , an index calculation unit 133 , a table generating unit 134 , a table storage unit 135 , a verification initial value setting unit 141 , a multiplication result storage unit 142 , a double-base addition unit 143 , an addition result storage unit 144 , a multiplication unit 145 , and a verification value output unit 149 .

Using the CPU 911 , the partitioned integer input unit 131 inputs the data representing the integer e 1 and integer e 2 output by the integer partitioning unit 110 . Using the RAM 914 , the partitioned integer input unit 131 stores the input data representing the integer e 1 and integer e 2 .

Using the CPU 911 , the element input unit 132 inputs data representing the element s and element h of the finite group G. Using the RAM 914 , the element input unit 132 stores the input data representing the element s and element h.

Using the CPU 911 , the index calculation unit 133 inputs the data representing the integer e 1 and integer e 2 and stored by the partitioned integer input unit 131 . Using the CPU 911 , the index calculation unit 133 judges whether the integer e 1 is a positive integer or a negative integer. Using the RAM 914 , the index calculation unit 133 stores data representing the judgment result. When judging that the integer e 1 is a negative integer, using the CPU 911 , the index calculation unit 133 turns the integer e 1 into a positive integer by inverting the sign.

Using the CPU 911 and based on the calculated absolute value of the integer e 1 , the index calculation unit 133 calculates a set of integers (e 1,i ) respectively representing figures that express in base-n notation the absolute value of the integer e 1 (note that i is an integer equal to or larger than 0 and equal to or smaller than k−1, and that n is a predetermined integer equal to or larger than 2). More specifically, using the CPU 911 , the index calculation unit 133 calculates the set of integers (e 1,i ) that satisfy the following conditions:

For example, when n=2, using the CPU 911 , the index calculation unit 133 decomposes data representing the absolute value of the integer e 1 and data representing the integer e 2 in units of bits into (e 1,i ) and (e 2,i ). When n=4, the index calculation unit 133 decomposes the data representing the absolute value of the integer e 1 and the data representing the integer e 2 in units of two-bit strings into (e 1,i ) and (e 2,i ).

Note that k is a minimum integer with which e 1,i =0 and e 2,i =0 hold for every i that satisfies i≧k.

For example, if n=2, e 1 =23, and e 2 =34, then e 1 =(10111) 2 and e 2 =(100010) 2 . Hence, k=6.

Using the RAM 914 , the index calculation unit 133 stores data representing the calculated set of integers (e 1,i ) and set of integers (e 2,i ).

Using the CPU 911 , the table generating unit 134 inputs the data representing the element s and element h and stored by the element input unit 132 , and the data representing the judgment result of the index calculation unit 133 as to whether the integer e 1 is positive or negative.

Using the CPU 911 and based on the element s and element h and the judgment result represented by the input data, the table generating unit 134 calculates n×n elements p x,y (=e i,sgn ·x·h−y·s where x and y are integers each equal to or larger than 0 and equal to or smaller than n−1, and e 1,sgn is 1 when the integer e 1 is positive and −1 when the integer e 1 is negative) of the finite group G. For example, when n=2, the table generating unit 134 calculates four elements p 0,0 , p 1,0 , p 0,1 , and p 1,1 . Since the element p 0,0 is always an identity element, the table generating unit 134 may calculate only the remaining three elements. Using the RAM 914 , the table storage unit 135 stores data representing the n×n elements p x,y calculated by the table generating unit 134 .

Using the RAM 914 , the multiplication result storage unit 142 stores data representing an element a′, which is a value obtained during the calculation of the element ä of the finite group G, of the finite group G.

Using the RAM 914 , the addition result storage unit 144 stores data representing an element a″, which is a value obtained during the calculation of the element ä of the finite group G, of the finite group G.

Using the CPU 911 , the verification initial value setting unit 141 causes the multiplication result storage unit 142 to store data representing the identity element of the finite group G, as data representing the element a′.

Using the CPU 911 , the double-base addition unit 143 inputs the data representing the sets of integers (e 1,i ) and (e 2,i ) and stored by the index calculation unit 133 one by one sequentially with a decrementing order of i.

Using the CPU 911 and based on the integer e 1,i and integer e 2,i represented by the input data, the double-base addition unit 143 acquires, among the data representing the elements p x,y of the finite group G and stored by the table storage unit 135 , data representing an element p x,y that satisfies x=e 1,i and y=e 2,i as data representing an element P i . Using the CPU 911 , the double-base addition unit 143 inputs the data representing the element a′ of the finite group G and stored by the multiplication result storage unit 142 . Using the CPU 911 and based on the element a′ of the finite group G represented by the input data and the element P i , the double-base addition unit 143 calculates an element a′+P i as the sum of the element a′ and element P i . Using the CPU 911 , the double-base addition unit 143 causes the addition result storage unit 144 to store data representing the calculated element a′+P i , as data representing the element a″.

Using the CPU 911 , the multiplication unit 145 inputs the data representing the element a″ of the finite group G and stored by the addition result storage unit 144 . Using the CPU 911 and based on the element a″ represented by the input data, the multiplication unit 145 calculates an element n·a″ by adding the element a″ n times. For example, when n=2, the multiplication unit 145 calculates an element 2·a″ by adding the element a″ and element a″. When n=4, the multiplication unit 145 calculates an element 2·a″ by adding the element a″ and element a″, and then calculates an element 4·a″ by further adding the element 2·a″ and element 2·a″ which are calculated.

Using the CPU 911 , the multiplication unit 145 causes the multiplication result storage unit 142 to store data representing the calculated element n·a″ as data representing the element a′.

The above operation is repeated. When the double-base addition unit 143 inputs all the integers e 1,i and integers e 2,i stored by the index calculation unit 133 , the verification value output unit 149 inputs, using the CPU 911 , the data representing the element a″ of the finite group G and stored by the addition result storage unit 144 . Using the CPU 911 , the verification value output unit 149 outputs the input data representing the element a″, as data representing the element a .

FIG. 9 is a flowchart showing an example of the flow of a verification value calculation process used by the verification value calculation unit 130 of this embodiment to calculate the element a of the finite group G.

In an index calculation step S 721 , using the CPU 911 , the index calculation unit 133 calculates the integer e 1,sgn based on the integer e 1 input by the partitioned integer input unit 131. Using the CPU 911 , the index calculation unit 133 sets the integer e 1,sgn to 1 when the integer e 1 is positive, and −1 when the integer e 2 is negative.

Using the CPU 911 , the index calculation unit 133 calculates k integers e 1,i (where i is an integer equal to or larger than 0 and equal to or smaller than k−1) based on the integer e 1 input by the partitioned integer input unit 131 . For example, using the CPU 911 , the index calculation unit 133 calculates the remainder of the division, by n, of the maximum integer that does not exceed the quotient obtained when the absolute value of the integer e 1 is divided by n raised to the i-th power, and treats the obtained remainder as e 1,i . Similarly, using the CPU 911 , the index calculation unit 133 calculates k integers e 2,i (where i is an integer equal to or larger than 0 and equal to or smaller than k−1) based on the integer e 2 input by the partitioned integer input unit 131 . For example, using the CPU 911 , the index calculation unit 133 calculates the remainder of the division, by n, of the maximum integer that does not exceed the quotient obtained when the integer e 2 is divided by n raised to the i-th power, and treats the obtained remainder as e 2,i .

In a table generating step S 722 , using the CPU 911 , the table generating unit 134 calculates n 2 elements p x,y (where x and y are integers each equal to or larger than 0 and equal to or smaller than n−1) of the finite group G based on the element s and element h input by the element input unit 132 and the integer e 1,sgn calculated by the index calculation unit 133 in the index calculation step S 721 . Using the CPU 911 , the table generating unit 134 calculates an element obtained by subtracting an element as the sum of addition by y times of the element s from an element as the sum of addition by e 1,sgn ·x times of the element h, and treats the result as the element p x,y .

Using the RAM 914 , the table storage unit 135 stores n 2 elements p x,y calculated by the table generating unit 134 .

In a verification initial value setting step S 723 , using the CPU 911 , the verification initial value setting unit 141 initializes the multiplication result storage unit 142 . Using the RAM 914 , the multiplication result storage unit 142 stores the identity element of the finite group G as the element a′.

In a repetitive initial value setting step S 724 , using the RAM 914 , the double-base addition unit 143 stores, as an integer j, an integer obtained by subtracting 1 from the integer k.

In a double-base addition step S 725 , using the CPU 911 and based on the stored integer j, the double-base addition unit 143 acquires, among the k integers e 1,i and the k integers e 2,i calculated by the index calculation unit 133 in the index calculation step S 721 , an integer e 1,j and an integer e 2,j that satisfy i=j.

Using the CPU 911 and based on the acquired integer e 1,i and integer e 2,i , the double-base addition unit 143 acquires an element p x,y that satisfies x=e 1,j and y=e 2,j among the n 2 elements p x,y of the finite group G stored by the table storage unit 135 , and treats it as the element P i . Using the CPU 911 and based on the element a′ of the finite group G stored by the multiplication result storage unit 142 and the acquired element P i , the double-base addition unit 143 calculates the element a′+P i as the sum of the element a′ and element P i by the operation on the finite group G. Using the RAM 914 , the addition result storage unit 144 stores the element a′+P i calculated by the double-base addition unit 143 as the element a″.

In a repetitive update step S 726 , using the CPU 911 , the double-base addition unit 143 calculates an integer j−1 obtained by subtracting 1 from the stored integer j. Using the RAM 914 , the double-base addition unit 143 stores the calculated integer j−1 as the integer j.

When the calculated integer j is positive or 0, the process advances to a multiplication step S 727 . When the calculated integer j is negative, the process advances to a verification value output step S 728 .

In the multiplication step S 727 , using the CPU 911 and based on the element a″ of the finite group G stored by the addition result storage unit 144 , the multiplication unit 145 calculates an element n·a″, which is obtained by adding n times the element a″ by the operation on the finite group G.

Using the RAM 914 , the multiplication result storage unit 142 stores, as the element a′, the element n·a″ calculated by the multiplication unit 145 . Then, the process returns to the double-base addition step S 725 .

In the verification value output step S 728 , using the CPU 911 , the verification value output unit 149 outputs, as the element a , the element a″ of the finite group G stored by the addition result storage unit 144 .

Then, the verification value calculation process is ended.

As described above, the verification value calculation unit 130 calculates the element a by utilizing the double-base scalar multiplication on the additive group (or double-base exponentiation on the multiplicative group).

In the above process, when j=i, if the element a″ stored by the addition result storage unit 144 in the double-base addition step S 725 is rewritten as a i , this yields:

P i =p e 1,i ,e 2,i =e 1,sgn ·e 1,i ·h−e 2,i ·s   [Equation 19]

a=e 1 ·( h−e·s )   [Equation 21]

If h=e·s, the element a is the identity element of the finite group G. If h≠e·s, since the order p of the finite group G is a prime number, the element a is not the identity element of the finite group G unless e 1 =0. Therefore, by judging whether or not the element a calculated by the verification value calculation unit 130 is an identity element, whether or not h=e·s can be judged.

The time necessary for the verification value calculation unit 130 to calculate the element a of the finite group G will be described.

In the following description, assume that the time necessary for performing group operation of the finite group G once is denoted by T. The time necessary for other calculations or data acquisition is much shorter than T and is accordingly ignored.

In the table generating step S 722 , the table generating unit 134 performs group operation n−2 times to calculate the elements p 0,y (y≠0,1), n−2 times to calculate the elements p x,0 (x≠0,1), and (n−1) 2 times to calculate the elements p x,y (x≠0, y≠0). Therefore, the time necessary for the table generating step S 722 is (n 2 −3)T.

In the double-base countable step S 725 , the double-base addition unit 143 performs group operation once to calculate the element a″. As the double-base countable step S 725 is repeated k times, the total time necessary for the double-base countable step S 725 is kT. When n is exponentiation of 2, in the multiplication step S 727 , the multiplication unit 145 performs group operation log 2 n times to calculate the element a′. As the multiplication step S 727 is repeated k−1 times, the total time necessary for the multiplication step S 727 is log 2 n(k−1)T. Hence, the time necessary for the entire verification value calculation process is [n 2 −3+k+log 2 n(k−1)]T. For example, when n=2, the required time is 2kT; when n=4, (3k+12)T.

For the purpose of comparison, the time necessary when calculating e·s without partitioning the integer e will be described.

Assume that the number of digits of the integer e expressed in base-n notation is k′.

The calculation procedure is the same as that for the verification value calculation process. Since the number of elements employed as the base is one, the table to be calculated in advance stores n elements x·s (where x is an integer equal to or larger than 0 and equal to or smaller than n−1). The time necessary for generation of the table is (n−2)T. The total time necessary for addition is k′T. The total time necessary for multiplication is log 2 n(k′−1)T. Therefore, the time necessary for entirely calculating e·s is [n−2+k′+log 2 n(k′−1)]T. For example, when n=2, the time is (2k′−1)T; when n=4, 3k′T.

Since e is an integer equal to or larger than 1 and equal to or smaller than p−1, k′ is probabilistically almost equal to the number of digits of p expressed in base-n notation.

In contrast to this, the absolute value of e 1 , and e 2 are each an integer equal to or larger than 1 and smaller than √p. Hence, k is probabilistically almost equal to the number of digits of √p expressed in base-n notation, which is almost half k′.

Assuming that k=k′/2, the time necessary for the entire verification value calculation process is k′T when n=2 and (1.5k′+12)T when n=4. If the order p of the finite group G is sufficiently large, the time necessary for the entire verification value calculation process is about half the time necessary for the process of calculating e·s.

Hence, the time necessary for judging whether or not h=e·s becomes almost half.

The verification apparatus 100 according to this embodiment has the processing device (CPU 911 ) which processes data, the integer partitioning unit 110 , the verification value calculation unit 130 , and the verification judging unit 150 .

Using the processing device (CPU 911 ), the integer partitioning unit 110 inputs the order p of the finite group G and the integer e, and calculates the integer e 1 and integer e 2 that satisfy e 1 ·e≡e 2 (mod p) based on the input order p and integer e. Using the processing device (CPU 911 ), the verification value calculation unit 130 inputs the element s of the finite group G and the element h of the finite group G, and calculates the element a (=e 1 ·h−e 2 ·s) of the finite group G based on the input element s and element h and the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 . The verification judging unit 150 judges, using the processing device (CPU 911 ) and based on the element a calculated by the verification value calculation unit 130 , that verification is successful when the element a is the identity element of the finite group G.

With the verification apparatus 100 of this embodiment, when the element a calculated by the verification value calculation unit 130 based on the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 is the identity element of the finite group G, the verification judging unit 150 judges that verification is successful. Therefore, when h=e·s, it can be judged that verification is successful. If, in the verification value calculation unit 130 , the time necessary for the process of calculating the element a is shorter than the time necessary for calculating e·s, then the time necessary for the process of judging whether or not h=e·s can be shortened.

The integer partitioning unit 110 according to this embodiments calculates, using the processing device (CPU 911 ), the integer e 1 and integer e 2 that satisfy a condition that the absolute value of the integer e 1 is smaller than the square root of the order p and that the integer e 2 is smaller than the square root of the order p.

With the verification apparatus 100 according to this embodiment, the integer partitioning unit 110 calculates the integer e 1 and integer e 2 that satisfy the condition that the absolute value of the integer e 1 is smaller than the square root of the order p and that the integer e 2 is smaller than the square root of the order p. Therefore, the time necessary for the process of calculating the element a in the verification value calculation unit 130 can be shortened.

The verification apparatus 100 according to this embodiment further has a storage device (such as the RAM 914 or the magnetic disk drive 920 ) which stores data.

The integer partitioning unit 110 has the first remainder storage unit 114 , the second remainder storage unit 115 , the initial value setting unit 113 , the conformity judging unit 116 , the third remainder calculation unit 117 , and the partitioned integer output unit 129 . The first remainder storage unit 114 stores the integer v 1 using the storage device (RAM 914 ). The second remainder storage unit 115 stores the integer v 2 using the storage device (RAM 914 ). The initial value setting unit 113 causes, using the processing device (CPU 911 ), the first remainder storage unit 114 to store the order p as the integer v 1 , and the second remainder storage unit 115 to store the integer e as the integer v 2 . The conformity judging unit 116 judges, using the processing device (CPU 911 ), that the output condition is satisfied when the integer v 2 stored by the second remainder storage unit 115 is smaller than the square root of the order p. When the conformity judging unit 116 does not judge that the output condition is satisfied, the third remainder calculation unit 117 calculates, using the processing device (CPU 911 ) and based on the integer v 1 stored by the first remainder storage unit 114 and the integer v 2 stored by the second remainder storage unit 115 , the remainder obtained when the integer v 1 is divided by the integer v 2 , and treats it as the integer v 3 , causes the first remainder storage unit 114 to store the integer v 2 stored by the second remainder storage unit 115 as the integer v 1 , and causes the second remainder storage unit 115 to store the calculated integer v 3 as the integer v 2 . When the conformity judging unit 116 judges that the output condition is satisfied, the partitioned integer output unit 129 outputs, using the processing device (CPU 911 ), the integer v 2 stored by the second remainder storage unit 115 as the integer e 2 .

With the verification apparatus 100 according to this embodiment, the integer e 2 that satisfies conditions e 1 ·e≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p can be calculated within a short period of time.

The integer partitioning unit 110 according to this embodiment further has the first coefficient storage unit 124 , the second coefficient storage unit 125 , the quotient calculation unit 126 , and the third coefficient calculation unit 127 .

The first coefficient storage unit 124 stores the integer t 1 using the storage device (RAM 914 ). The second coefficient storage unit 125 stores the integer t 2 using the storage device (RAM 914 ). The initial value setting unit 113 , using the processing device (CPU 911 ), further causes the first coefficient storage unit 124 to store 0 as the integer t 1 , and the second coefficient storage unit 125 to store 1 as the integer t 2 . The quotient calculation unit 126 , using the processing device (CPU 911 ) and based on the integer v 1 stored by the first remainder storage unit 114 and the integer v 2 stored by the second remainder storage unit 115 , calculates the maximum integer that does not exceed the quotient obtained when the integer v 1 is divided by the integer v 2 , and treats the calculated integer as the integer q. When the conformity judging unit 116 does not judge that the output condition is satisfied, the third coefficient calculation unit 127 calculates, using the processing device (CPU 911 ) and based on the integer t 1 stored by the first coefficient storage unit 124 , the integer t 2 stored by the second coefficient storage unit 125 , and the integer q calculated by the quotient calculation unit 126 , an integer obtained by subtracting the product of the integer t 2 and the integer q from the integer t 1 and treats it as the integer t 3 , causes the first coefficient storage unit 124 to store the integer t 2 stored by the second coefficient storage unit 125 as the integer t 1 , and causes the second coefficient storage unit 125 to store the calculated integer t 3 as the integer t 2 . Using the processing device (CPU 911 ), when the conformity judging unit 116 judges that the output condition is satisfied, the partitioned integer output unit 129 further outputs the integer t 2 stored by the second coefficient storage unit 125 as the integer e 1 .

With the verification apparatus 100 according to this embodiment, the integer e 1 that satisfies the conditions e 1 ·e≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p can be calculated within a short period of time.

The verification value calculation unit 130 according to this embodiment calculates Σ(n i ·P i ) using the processing device (CPU 911 ) (where n is a predetermined integer equal to or larger than 2, i is an integer equal to or larger than 0 and equal to or smaller than k, k is the maximum value of the numbers of digits of the absolute value of the integer e 1 and of the integer e 2 , both expressed in base-n notation, P i is an element of the finite group G and satisfies P i =e 1,sgn ·e 2,i ·s, e 1,sgn is 1 or −1, and e 1,i and e 2,i are integers each equal to or larger than 0 and equal to or smaller than n−1 and satisfying e 1 =e 1,sgn ·Σ(n i ·e 1,i ) and e 2 =Σ(n i ·e 2,i )), and treats the calculated value as the element a of the finite group G.

With the verification apparatus 100 according to this embodiment, the time necessary for the verification value calculation unit 130 to calculate the element a is proportional to the number k of digits of the absolute value of the integer e 1 and of the integer e 2 , both expressed in base-n notation. As a result, the time necessary for calculating the element a can be shortened.

The ciphertext decryption apparatus 200 according to this embodiment includes the storage device (e.g., the RAM 914 and the magnetic disk drive 920 ) which stores data, the processing device (e.g., the CPU 911 ) which processes data, the key storage unit 210 , the ciphertext input unit 220 , the ciphertext verification unit 230 , the verification apparatus 100 , and the decrypted text generating unit 260 .

The key storage unit 210 stores, using the storage device, the key for decrypting the ciphertext. The ciphertext input unit 220 inputs, using the processing device, the ciphertext. The ciphertext verification unit 230 calculates, using the processing device, the integer e, the element s of the finite group G, and the element h of the finite group G, which are to be input by the verification apparatus 100 , based on the key stored by the key storage unit 210 and the ciphertext input by the ciphertext input unit 220 . The verification apparatus 100 inputs the integer e, the element s of the finite group G, and the element h of the finite group G, which are calculated by the ciphertext verification unit 230 , and judges whether or not verification is successful. When the verification apparatus 100 judges that the verification is successful, the decrypted text generating unit 260 decrypts, using the processing device, the ciphertext input by the ciphertext input unit 220 using the key stored by the key storage unit 210 , to generate the decrypted text.

The ciphertext decryption apparatus 200 according to this embodiment verifies the consistency of an input ciphertext, and generates a decrypted text when the verification is successful. This can prevent a clue to decipher the ciphertext from being given to an unauthorized person. Also, the verification apparatus 100 verifies the consistency of the ciphertext by judging whether or not h=e·s. Therefore, the time necessary for verification can be shortened.

The verification apparatus 100 according to this embodiment can be realized when the computer executes a computer program that operates the computer as the verification apparatus 100 .

The computer program according to this embodiment is effective in that it can realize the following the verification apparatus 100 . When the element a calculated by the verification value calculation unit 130 based on the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 is the identity element of the finite group G, the verification judging unit 150 judges that verification is successful. Therefore, when h=e·s, it can be judged that verification is successful. If, in the verification value calculation unit 130 , the time necessary for the process of calculating the element a is shorter than the time necessary for calculating e·s, then the time necessary for the process of judging whether or not h=e·s can be shortened.

The verification method used by the verification apparatus 100 according to this embodiment to verify the consistency has the following steps.

The processing device (CPU 911 ) inputs the order p of the finite group G and the integer e, and calculates the integer e 1 and integer e 2 that satisfy e 1 ·e≡e 2 (mod p) based on the input order p and integer e. The processing device (CPU 911 ) inputs the element s of the finite group G and the element h of the finite group G, and calculates the element a (=e 1 ·h−e 2 ·s) of the finite group G based on the input element s and element h and the calculated integer e 1 and integer e 2 . The processing device (CPU 911 ) judges, based on the calculated element a , that verification is successful when the element a is the identity element of the finite group G.

With the verification method of this embodiment, when the element a calculated by the processing device (CPU 911 ) based on the calculated integer e 1 and integer e 2 is the identity element of the finite group G, it is judged that verification is successful. Therefore, when h=e·s, it can be judged that verification is successful. If the time necessary for the process of calculating the element a is shorter than the time necessary for calculating e·s, then the time necessary for the process of judging whether or not h=e·s can be shortened.

The ciphertext decryption apparatus 200 described so far is a public key cryptography decryption apparatus. The ciphertext decryption apparatus 200 has the ciphertext correctness verification apparatus (verification apparatus 100 ). The ciphertext correctness verification apparatus judges whether or not a ciphertext is correct by verifying whether or not an element s e obtained by multiplying the element s of the multiplicative group e times in accordance with exponentiation on the multiplicative group such as a group formed of the residue classes of integers, or the element e·s obtained by adding the element s of the additive group e times in accordance with the scalar multiplication on the additive group such as a group formed of points on a (hyper) elliptic curve, coincides with the known element h.

The ciphertext correctness verification apparatus (verification apparatus 100 ) has a device (integer partitioning unit 110 ) that partitions an exponential part (integer e), a device (verification value calculation unit 130 ) that, using the partitioned exponents (the integer e 1 and integer e 2 ), calculates a value (h e1 −s e2 ) by the double-base exponentiation on the multiplicative group, or a value (e 1 ·h−e 2 ·s) by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper) elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The integer partitioning unit 110 described so far is a calculation device which inputs the exponent (integer) e and the group order p of the multiplicative group or additive group used in a cipher and calculates the two integers e 1 and e 2 (note that e 1 ·e≡e 2 (mod p)) each having a bit length half that of the group order p.

The verification apparatus 100 verifies s e2 ·h −e1 =1 (multiplicative description) or e 2 ·s−e 1 ·h=0 (additive description).

The integer partitioning unit 110 described so far partitions an exponent part by performing the extended Euclidean algorithm.

The integer partitioning unit 110 described so far has, in repetitive division of two integers,

a calculation device (third remainder calculation unit 117 ) in which the integer v 2 as a divisor and the integer v 1 as the dividend are the remainder v 3 of the division of the preceding step and the integer v 2 as the divisor of the preceding step, respectively, and a calculation device (conformity judging unit 116 ) that judges that the remainder v 2 of the division result of each step is equal to or larger than a predetermined number (√p), or equal to or smaller than a predetermined number (√p).

The integer partitioning unit 110 may calculate the integers e 1 and e 2 in accordance with the following procedure other than the procedure described above.

First, using the CPU 911 , the integer partitioning unit 110 inputs a positive integer p, an integer e that satisfies 1<e<p, and the square root √p of p. Then, using the RAM 914 , the integer partitioning unit 110 stores u 1 ←1, v 1 ←p, u 2 ←0, and v 2 ←e as initial values. Then, using the CPU 911 , the integer partitioning unit 110 checks whether v 2 <√p. If v 2 >√p, using the CPU 911 , the integer partitioning unit 110 calculates q←v 1 /v 2 (the fraction is omitted), v 3 ←v 1 mod v 2 , and u 3 ←u 1 −q·u 2 , and using the RAM 914 , stores them as v 1 ←v 2 , v 2 ←v 3 ←u 1 ←u 2 , u 2 ←u 3 . The integer partitioning unit 110 then returns to the checking of whether v 2 <√p. If v 2 >√p, the same calculation is repeated. When v 2 <√p is established, using the CPU 911 , the integer partitioning unit 110 calculates e 1 ←(v 2 −u 2 ·p)/v 1 , and sets e 2 ←v 2 . Finally, using the CPU 911 , the integer partitioning unit 110 outputs e 1 and e 2 . This procedure also provides e 1 ·e≡e 2 (mod p), and the bit length of each of e 1 and e 2 becomes almost half the bit length of p.

The second embodiment will be described with reference to FIGS. 10 to 15 .

FIG. 10 shows an example of the entire system configuration of an ID-based public key cryptographic system 820 A of this embodiment.

The ID-based public key cryptographic system 820 A is a cryptographic communication system that uses identification data such as a mail address that identifies a ciphertext decryption apparatus 200 A as the public key of the ciphertext decryption apparatus 200 A. Since the correspondence between the ciphertext decryption apparatus 200 A and the public key need not be certified, a public key certificate, a certificate authority, and the like are not needed.

The ID-based public key cryptographic system 820 A has an encryption parameter setting apparatus 810 A, a key generating apparatus 300 A, a ciphertext generating apparatus 400 A, and the ciphertext decryption apparatus 200 A.

The encryption parameter setting apparatus 810 A determines encryption parameters to be used in the ID-based public key cryptographic system 820 A. The encryption parameters determined by the encryption parameter setting apparatus 810 A are open to the user of the ID-based public key cryptographic system 820 A. The encryption parameters determined by the encryption parameter setting apparatus 810 A include, e.g., an order p, an additive group G 1 , an element g 1 of the additive group G 1 , an additive group G 2 , an element g 2 of the additive group G 2 , a multiplicative group G T , a pairing e, a hash function H 1 , a hash function H 2 , a hash function H 3 , and a hash function H 4 .

The order p is a prime number. The order of the additive group G 1 is p. The element g 1 is a generator of the additive group G 1 . The order of the additive group G 2 is p, which is the same as the order of the additive group G 1 . The element g 2 is a generator of the additive group G 2 . The order of the multiplicative group G T is p, which is the same as the order of the additive group G 1 or the additive group G 2 . The pairing e is a map that transforms a set of an element of the additive group G 1 and an element of the additive group G 2 into an element (pairing value) of the multiplicative group G T . The pairing e has bilinearity. More specifically, for all u, v, a , and b, e(a·u,b·v)=e(u,v) ab holds (where u is an element of the additive group G 1 , v is an element of the additive group G 2 , and a and b are integers). The pairing value e (g 1 ,g 2 ) of the element g 1 of the additive group G 1 and the element g 2 of the additive group G 2 is not the identity element of the multiplicative group G T . The hash function H 1 is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from a bit string having an arbitrary length. The hash function H 2 is a hash function that generates a bit string having a predetermined length from elements of the multiplicative group G T . The hash function H 3 is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from a bit string having a predetermined length. The hash function H 4 is a hash function that generates a bit string having a predetermined length from a bit string having a predetermined length.

When these encryption parameters are determined in advance, the encryption parameter setting apparatus 810 A need not determine them.

The encryption parameter setting apparatus 810 A generates a secret random number s and a public element R generated based on the secret random number s. The secret random number s generated by the encryption parameter setting apparatus 810 A is notified to the key generating apparatus 300 A in secret. The public element R generated by the encryption parameter setting apparatus 810 A is open to the user of the ID-based public key cryptographic system 820 A. Although the public element R includes information on the secret random number s, it is practically impossible to obtain the secret random number s from the public element R. Hence, the user of the ID-based public key cryptographic system 820 A can use secret information without noticing it if an operation is done using the public element R.

The key generating apparatus 300 A holds in secret the secret random number s notified from the encryption parameter setting apparatus 810 A. The key generating apparatus 300 A generates a secret key D ID of the ciphertext decryption apparatus 200 A based on the public encryption parameters, public identification data ID of the ciphertext decryption apparatus 200 A, and the secret random number s which is held. The secret key D ID generated by the key generating apparatus 300 A is notified to the ciphertext decryption apparatus 200 A in secret.

The ciphertext generating apparatus 400 A generates a ciphertext c and a common key K based on the public encryption parameters, the public element R, and the identification data ID of the ciphertext decryption apparatus 200 A. The ciphertext generating apparatus 400 A encrypts a message M by the generated common key K, thus generating an encrypted message CM. The ciphertext generating apparatus 400 A transmits the generated ciphertext c and the encrypted message CM to the ciphertext decryption apparatus 200 A.

The ciphertext decryption apparatus 200 A holds in secret the secret key D ID generated by the key generating apparatus 300 A. The ciphertext decryption apparatus 200 A receives the ciphertext c and encrypted message CM transmitted by the ciphertext generating apparatus 400 A. Based on the public encryption parameters, the ciphertext decryption apparatus 200 A decrypts the received ciphertext c by the secret key D ID it holds, thus generating a common key K identical to that of the ciphertext generating apparatus 400 A. The ciphertext decryption apparatus 200 A decrypts the encrypted message CM by the generated common key K, thus generating a message M′ identical to the message M.

The appearances and hardware resources of the encryption parameter setting apparatus 810 A, key generating apparatus 300 A, ciphertext generating apparatus 400 A, and ciphertext decryption apparatus 200 A are similar to those of the ciphertext decryption apparatus 200 A described in the first embodiment.

FIG. 11 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 A of this embodiment.

The encryption parameter setting apparatus 810 A has an encryption parameter storage unit 819 A, a public element generating unit 811 A, a secret random number output unit 814 A, and a public element output unit 815 A.

Using a magnetic disk drive 920 , the encryption parameter storage unit 819 A stores data representing the public encryption parameters.

The public element generating unit 811 A generates the secret random number s and the public element R based on the encryption parameters stored by the encryption parameter storage unit 819 A.

The public element generating unit 811 A has a secret random number generating unit 812 A and a public element calculation unit 813 A.

Using a CPU 911 , the secret random number generating unit 812 A inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 819 A. Using the CPU 911 , the secret random number generating unit 812 A randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1 based on the order p represented by the input data, and treats it as the secret random number s. Using a RAM 914 , the secret random number generating unit 812 A stores data representing the generated secret random number s.

Using the CPU 911 , the public element calculation unit 813 A inputs the data representing the additive group G 1 and element g 1 among the encryption parameters stored by the encryption parameter storage unit 819 A, and the data representing the secret random number s and stored by the secret random number generating unit 812 A. Using the CPU 911 and based on the additive group G 1 , element g 1 , and secret random number s represented by the input data, the public element calculation unit 813 A calculates an element which is obtained when the element g 1 is added s times by the operation on the additive group G 1 , and treats it as the public element R. Using the RAM 914 , the public element calculation unit 813 A stores data representing the calculated public element R.

Using the CPU 911 , the secret random number output unit 814 A inputs the data representing the secret random number s and stored by the secret random number generating unit 812 A. Using the CPU 911 , the secret random number output unit 814 A outputs the input data representing the secret random number s.

The secret random number s output by the secret random number output unit 814 A is notified to the key generating apparatus 300 A in secret.

Using the CPU 911 , the public element output unit 815 A inputs the data representing the public element R and stored by the public element calculation unit 813 A. Using the CPU 911 , the public element output unit 815 A outputs the input data representing the public element R.

The public element R output by the public element output unit 815 A is open to the user of the ID-based public key cryptographic system 820 A.

FIG. 12 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 A according to this embodiment.

The key generating apparatus 300 A has an encryption parameter storage unit 390 A, a secret random number storage unit 330 A, an identifier input unit 340 A, a secret key generating unit 350 A, and a secret key output unit 360 A.

Using the magnetic disk drive 920 , the encryption parameter storage unit 390 A stores data representing the public encryption parameters in advance.

Using a tamper-resistant storage device, the secret random number storage unit 330 A stores, in secret, data representing the secret random number s and notified by the encryption parameter setting apparatus 810 A.

As for the ciphertext decryption apparatus 200 A whose secret key is to be generated, the identifier input unit 340 A inputs, using the CPU 911 , an arbitrary-length bit string ID which is identification data for identifying the ciphertext decryption apparatus 200 A. The bit string ID is, for example, data representing a character string indicating the mail address of the ciphertext decryption apparatus 200 A. Using the RAM 914 , the identifier input unit 340 A stores the input bit string ID.

The secret key generating unit 350 A generates the secret key D ID based on the encryption parameters stored by the encryption parameter storage unit 390 A, the secret random number s stored by the secret random number storage unit 330 A, and the bit string ID input by the identifier input unit 340 A.

The secret key generating unit 350 A has a hash value calculation unit 351 A, an integer addition unit 352 A, an inverse number calculation unit 353 A, and a secret key calculation unit 354 A.

Using the CPU 911 , the hash value calculation unit 351 A inputs the data representing the hash function H 1 among the encryption parameters stored by the encryption parameter storage unit 390 A, and the bit string ID stored by the identifier input unit 340 A. Using the CPU 911 and based on the hash function H 1 represented by the input data and the input bit string ID, the hash value calculation unit 351 A calculates a hash value H 1 (ID), which is obtained when the bit string ID is hashed by the hash function H 1 . The hash value H 1 (ID) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the hash value calculation unit 351 A stores data representing the calculated hash value H 1 (ID).

Using the CPU 911 , the integer addition unit 352 A inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 390 A, the data representing the secret random number s and stored by the secret random number storage unit 330 A, and the data representing the hash value H 1 (ID) and stored by the hash value calculation unit 351 A. Using the CPU 911 and based on the order p, secret random number s, and hash value H 1 (ID) represented by the input data, the integer addition unit 352 A calculates an integer s+H 1 (ID), which is the remainder obtained when the sum of the secret random number s and hash value H 1 (ID) is divided by the order p. The integer addition unit 352 A stores, using the RAM 914 , data representing the calculated integer s+H 1 (ID).

Using the CPU 911 , the inverse number calculation unit 353 A inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 390 A, and the data representing the integer s+H 1 (ID) and stored by the integer addition unit 352 A. Using the CPU 911 and based on the order p and integer s+H 1 (ID) represented by the input data, the inverse number calculation unit 353 A calculates an integer 1/[s+H 1 (ID)] which yields a remainder of 1 when its product with the integer s+H 1 (ID) is divided by the order p. The inverse number calculation unit 353 A stores, using the RAM 914 , data representing the calculated integer 1/[s+H 1 (ID)].

Using the CPU 911 , the secret key calculation unit 354 A inputs the data representing the additive group G 2 and element g 2 among encryption parameters stored by the encryption parameter storage unit 390 A, and the data representing the integer 1/[s+H 1 (ID)] and calculated by the inverse number calculation unit 353 A. Using the CPU 911 and based on the additive group G 2 , element g 2 , and integer 1/[s+H 1 (ID)] represented by the input data, the secret key calculation unit 354 A calculates an element which is obtained when the element g 2 is added 1/[s+H 1 (ID)] times by the operation on the additive group G 2 , and treats it as the secret key D ID . Using the RAM 914 , the secret key calculation unit 354 A stores data representing the calculated secret key D ID .

Using the CPU 911 , the secret key output unit 360 A inputs the data representing the secret key D ID and stored by the secret key calculation unit 354 A. Using the CPU 911 , the secret key output unit 360 A outputs the input data representing the secret key D ID .

The secret key D ID output by the secret key output unit 360 A is notified to the ciphertext decryption apparatus 200 A in secret.

FIG. 13 is a block diagram showing a configuration example of the function block of a ciphertext generating apparatus 400 A according to this embodiment.

The ciphertext generating apparatus 400 A has an encryption parameter storage unit 490 A, an identifier storage unit 410 A, a common key generating unit 420 A, a common key storage unit 430 A, a message input unit 440 A, a message encryption unit 450 A, an encrypted message output unit 460 A, and a ciphertext output unit 470 A.

Using the magnetic disk drive 920 , the encryption parameter storage unit 490 A stores data representing the public encryption parameters (including the public element R) in advance.

Using the magnetic disk drive 920 , the identifier storage unit 410 A stores a bit string ID which is the identification data of the ciphertext decryption apparatus 200 A to which the ciphertext is to be transmitted.

Based on the encryption parameters stored by the encryption parameter storage unit 490 A and the bit string ID stored by the identifier storage unit 410 A, the common key generating unit 420 A generates the common key K and a ciphertext which serves to notify the common key K to the ciphertext decryption apparatus 200 A.

The common key generating unit 420 A has a secret bit string generating unit 421 A, a secret integer calculation unit 422 A, an identifier element calculation unit 423 A, a cipher element calculation unit 424 A, a secret pairing value calculation unit 425 A, a cipher bit string calculation unit 426 A, and a common key calculation unit 427 A.

Using the CPU 911 , the secret bit string generating unit 421 A randomly generates a predetermined-length bit string m. Using the RAM 914 , the secret bit string generating unit 421 A stores the generated bit string m.

Using the CPU 911 , the secret integer calculation unit 422 A inputs the data representing the hash function H 3 among the encryption parameters stored by the encryption parameter storage unit 490 A, and the bit string m stored by the secret bit string generating unit 421 A. Using the CPU 911 and based on the hash function H 3 represented by the input data and the input bit string m, the secret integer calculation unit 422 A calculates a hash value r, which is obtained when the bit string m is hashed by the hash function H 3 . The hash value r is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the secret integer calculation unit 422 A stores data representing the calculated hash value r.

Using the CPU 911 , the identifier element calculation unit 423 A inputs the data representing the hash function H 1 , additive group G 1 , element g 1 , and public element R among the encryption parameters stored by the encryption parameter storage unit 490 A, and the bit string ID stored by the identifier storage unit 410 A. Using the CPU 911 and based on the hash function H 1 represented by the input data and the input bit string ID, the identifier element calculation unit 423 A calculates a hash value H 1 (ID), which is obtained when the bit string ID is hashed by the hash function H 1 . The hash value H 1 (ID) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 and based on the additive group G 1 and element g 1 represented by the input data and the calculated hash value H 1 (ID), the identifier element calculation unit 423 A calculates an element H 1 (ID)·g 1 which is obtained when the element g 1 is added H 1 (ID) times by the operation on the additive group G 1 . Using the CPU 911 and based on the additive group G 1 and public element R represented by the input data and the calculated element H 1 (ID)·g, the identifier element calculation unit 423 A calculates an element which is obtained when the public element R and the element H 1 (ID)·g are added by the operation on the additive group G 1 , and treats it as an element Q. Using the RAM 914 , the identifier element calculation unit 423 A stores data representing the calculated element Q.

Since R=s·g 1 , the element Q calculated by the identifier element calculation unit 423 A is expressed as:

Using the CPU 911 , the cipher element calculation unit 424 A inputs the data representing the additive group G 1 among the encryption parameters stored by the encryption parameter storage unit 490 A, the data representing the hash value r and stored by the secret integer calculation unit 422 A, and the data representing the element Q and stored by the identifier element calculation unit 423 A. Using the CPU 911 and based on the additive group G 1 , hash value r, and element Q represented by the input data, the cipher element calculation unit 424 A calculates an element which is obtained when the element Q is added r times by the operation on the additive group G 1 , and treats it as an element U. Using the RAM 914 , the cipher element calculation unit 424 A stores data representing the calculated element U.

Using the CPU 911 , the secret pairing value calculation unit 425 A inputs the data representing the element g 1 , element g 2 , pairing e, and multiplicative group G T among the encryption parameters stored by the encryption parameter storage unit 490 A, and the data representing the hash value r and stored by the secret integer calculation unit 422 A. Using the CPU 911 and based on the element g 1 , element g 2 , and pairing e represented by the input data, the secret pairing value calculation unit 425 A calculates a pairing value e(g 1 ,g 2 ) of the element g 1 and element g 2 . The pairing value e(g 1 ,g 2 ) is an element of the multiplicative group G T . Alternatively, the secret pairing value calculation unit 425 A may calculate a pairing value e(g 1 ,g 2 ) in advance and, using the magnetic disk drive 920 , store data representing the calculated pairing value e(g 1 ,g 2 ). Using the CPU 911 and based on the hash value r represented by the input data and the calculated pairing value e(g 1 ,g 2 ), the secret pairing value calculation unit 425 A calculates an element which is obtained when the pairing value e(g 1 ,g 2 ) is multiplied r times by the operation on the multiplicative group G T , and treats it as an element α. Using the RAM 914 , the secret pairing value calculation unit 425 A stores data representing the calculated element α.

Using the CPU 911 , the cipher bit string calculation unit 426 A inputs the data representing the hash function H 2 among the encryption parameters stored by the encryption parameter storage unit 490 A, the bit string m stored by the secret bit string generating unit 421 A, and the data representing the element α and stored by the secret pairing value calculation unit 425 A. Using the CPU 911 and based on the hash function H 2 and element α represented by the input data, the cipher bit string calculation unit 426 A calculates a hash value H 2 (α), which is obtained when the element α is hashed by the hash function H 2 . The hash value H 2 (α) is a bit string having a predetermined length. Using the CPU 911 and based on the input bit string m and the calculated hash value H 2 (α), the cipher bit string calculation unit 426 A obtains the bitwise exclusive OR of the bit string m and the hash value H 2 (α), and treats the result as a bit string V. Using the RAM 914 , the cipher bit string calculation unit 426 A stores the calculated bit string V.

Using the CPU 911 , the common key calculation unit 427 A inputs the data representing the hash function H 4 among the encryption parameters stored by the encryption parameter storage unit 490 A, and the bit string m stored by the secret bit string generating unit 421 A. Using the CPU 911 and based on the hash function H 4 represented by the input data and the input bit string m, the common key calculation unit 427 A calculates a hash value which is obtained when the bit string m is hashed by the hash function H 4 , and treats it as a common key K. The common key K is a bit string having a predetermined length. Using the RAM 914 , the common key calculation unit 427 A stores the calculated common key K.

Using the CPU 911 , the common key storage unit 430 A inputs the common key K stored by the common key calculation unit 427 A. Using the RAM 914 , the common key storage unit 430 A stores the input common key K.

Using the CPU 911 , the ciphertext output unit 470 A inputs the data representing the element U and stored by the cipher element calculation unit 424 A, and the bit string V stored by the cipher bit string calculation unit 426 A. Using the CPU 911 , the ciphertext output unit 470 A generates data including the data representing the input element U and the bit string V, and outputs it as the ciphertext c.

Using the CPU 911 , the message input unit 440 A inputs the message M to be transmitted to the ciphertext decryption apparatus 200 A. Using the magnetic disk drive 920 , the message input unit 440 A stores the input message M.

Using the CPU 911 , the message encryption unit 450 A inputs the common key K stored by the common key storage unit 430 A, and the message M stored by the message input unit 440 A. Using the CPU 911 and based on the input message M and common key K, the message encryption unit 450 A encrypts the message M using the common key K and treats it as the encrypted message CM. Using the magnetic disk drive 920 , the message encryption unit 450 A stores the generated encrypted message CM.

Using the CPU 911 , the encrypted message output unit 460 A inputs the encrypted message CM stored by the message encryption unit 450 A. Using the CPU 911 , the encrypted message output unit 460 A outputs the input encrypted message CM.

The ciphertext c output by the ciphertext output unit 470 A and the encrypted message CM output by the encrypted message output unit 460 A are transmitted to the ciphertext decryption apparatus 200 A.

FIG. 14 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 A according to this embodiment.

The ciphertext decryption apparatus 200 A has an encryption parameter storage unit 290 A, an identifier storage unit 241 A, an identifier element calculation unit 242 A, an identifier element storage unit 243 A, a key storage unit 210 A, a ciphertext input unit 220 A, a ciphertext verification unit 230 A, a verification apparatus 100 A, a decrypted text generating unit 260 A, a common key storage unit 270 A, an encrypted message input unit 281 A, a message decryption unit 282 A, and a decrypted message output unit 283 A.

Using the magnetic disk drive 920 , the encryption parameter storage unit 290 A stores data representing the public encryption parameters (including the public element R) in advance.

Using the magnetic disk drive 920 , the identifier storage unit 241 A stores the bit string ID that identifies the ciphertext decryption apparatus 200 A itself.

Using the CPU 911 , the identifier element calculation unit 242 A inputs data representing the hash function H 1 , additive group G 1 , element g 1 , and public element R among the encryption parameters stored by the encryption parameter storage unit 290 A, and the bit string ID stored by the identifier storage unit 241 A. Using the CPU 911 and based on the hash function H 1 represented by the input data and the input bit string ID, the identifier element calculation unit 242 A calculates a hash value H 1 (ID), which is obtained when the bit string ID is hashed by the hash function H 1 . The hash value H 1 (ID) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 and based on the additive group G 1 and element g 1 represented by the input data and the calculated hash value H 1 (ID), the identifier element calculation unit 242 A calculates an element H 1 (ID)·g 1 , which is obtained when the element g 1 is added H 1 (ID) times by the operation on the additive group G 1 . Using the CPU 911 and based on the additive group G 1 and public element R represented by the input data, and the calculated element H 1 (ID)·g 1 , the identifier element calculation unit 242 A calculates an element which is obtained when the public element R and the element H 1 (ID)·g 1 are added by the operation on the additive group G 1 , and treats it as an element Q. Using the RAM 914 , the identifier element calculation unit 242 A stores data representing the calculated element Q.

Using the CPU 911 , the identifier element storage unit 243 A inputs the data representing the element Q and stored by the identifier element calculation unit 242 A. Using the magnetic disk drive 920 , the identifier element storage unit 243 A stores the input data representing the element Q.

To the ciphertext decryption apparatus 200 A, the bit string that identifies the ciphertext decryption apparatus 200 A itself is constant, and accordingly the value of the element Q is also constant. Hence, the ciphertext decryption apparatus 200 A need not calculate the element Q each time it inputs a ciphertext c. If the identifier element calculation unit 242 A calculates an element Q and the identifier element storage unit 243 A stores it before a ciphertext c is input, the amount of calculation after inputting the ciphertext c can be reduced.

Using a tamper-resistant storage device, the key storage unit 210 A stores in secret data representing the secret key D ID generated by the key generating apparatus 300 A in advance.

Using the CPU 911 , the ciphertext input unit 220 A inputs the ciphertext c received from the ciphertext generating apparatus 400 A. Using the CPU 911 , the ciphertext input unit 220 A acquires data representing the element U and bit string V from the input ciphertext c. Using the RAM 914 , the ciphertext input unit 220 A stores the acquired data representing the element U and bit string V.

The ciphertext verification unit 230 A generates data to be input by the verification apparatus 100 A based on the encryption parameters stored by the encryption parameter storage unit 290 A, the secret key D ID stored by the key storage unit 210 , and the element U and bit string V represented by the ciphertext c input by the ciphertext input unit 220 A.

The ciphertext verification unit 230 A has a pairing value calculation unit 231 A, a bit string calculation unit 232 A, and an integer calculation unit 233 A.

Using the CPU 911 , the pairing value calculation unit 231 A inputs the data representing the pairing e among the encryption parameters stored by the encryption parameter storage unit 290 A, the data representing the secret key D ID and stored by the key storage unit 210 A, and the data representing the element U and stored by the ciphertext input unit 220 . Using the CPU 911 and based on the pairing e, element U, and secret key D ID represented by the input data, the pairing value calculation unit 231 A calculates the pairing value of the element U and secret key D ID by the pairing e, and treats it as a pairing value α. The pairing value α is an element of the multiplicative group G T . Using the RAM 914 , the pairing value calculation unit 231 A stores data representing the calculated pairing value α.

From the bilinearity of the pairing e, the pairing value α calculated by the pairing value calculation unit 231 A is expressed as:

More specifically, the pairing value α calculated by the pairing value calculation unit 231 A is equal to the element a of the multiplicative group G T which is calculated by the secret pairing value calculation unit 425 A of the ciphertext generating apparatus 400 A.

Using the CPU 911 , the bit string calculation unit 232 A inputs the data representing the hash function H 2 among the encryption parameters stored by the encryption parameter storage unit 290 A, the bit string V stored by the ciphertext input unit 220 , and the data representing the pairing value α and stored by the pairing value calculation unit 231 A. Using the CPU 911 and based on the hash function H 2 and pairing value α represented by the input data, the bit string calculation unit 232 A calculates a hash value H 2 (α), which is obtained when the pairing value α is hashed by the hash function H 2 . The hash value H 2 (α) is a bit string having a predetermined length. Using the CPU 911 and based on the input bit string V and the calculated hash value H 2 (α), the bit string calculation unit 232 A obtains the bitwise exclusive OR of the bit string V and the hash value H 2 (α), and treats the result as a bit string m. Using the RAM 914 , the bit string calculation unit 232 A stores the calculated bit string m.

As the pairing value α calculated by the pairing value calculation unit 231 A is equal to the element α of the multiplicative group G T which is calculated by the secret pairing value calculation unit 425 A of the ciphertext generating apparatus 400 A, the bit string m calculated by the bit string calculation unit 232 A is equal to the bit string m calculated by the secret bit string generating unit 421 A of the ciphertext generating apparatus 400 A.

Using the CPU 911 , the integer calculation unit 233 A inputs the data representing the hash function H 3 among the encryption parameters stored by the encryption parameter storage unit 290 A, and the bit string m stored by the bit string calculation unit 232 A. Using the CPU 911 and based on the hash function H 3 represented by the input data and the input bit string m, the integer calculation unit 233 A calculates a hash value which is obtained when the bit string m is hashed by the hash function H 3 , and treats it as a hash value r. The hash value r is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the integer calculation unit 233 A stores data representing the calculated hash value r.

As the bit string m calculated by the bit string calculation unit 232 A is equal to the bit string m generated by the secret bit string generating unit 421 A of the ciphertext generating apparatus 400 A, the hash value r calculated by the integer calculation unit 233 A is equal to the hash value r calculated by the secret integer calculation unit 422 A of the ciphertext generating apparatus 400 A.

Hence, if the ciphertext c input by the ciphertext input unit 220 A is a correct ciphertext, U=r·Q is established.

The verification apparatus 100 A checks whether or not U=r·Q. If U=r·Q, the verification apparatus 100 A judges that the verification is successful.

The verification apparatus 100 A is an apparatus corresponding to the verification apparatus 100 described in the first embodiment. Using the CPU 911 , the verification apparatus 100 A inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 A, as data representing the order p described in the first embodiment. Using the CPU 911 , the verification apparatus 100 A inputs the data representing the hash value r and stored by the integer calculation unit 233 A, as data representing the integer e described in the first embodiment. Using the CPU 911 , the verification apparatus 100 A inputs the data representing the element U and stored by the ciphertext input unit 220 , as data representing the element h described in the first embodiment. Using the CPU 911 , the verification apparatus 100 A inputs the data representing the element Q and stored by the identifier element storage unit 243 A, as data representing the element s described in the first embodiment. Using the CPU 911 and based on the order p and hash value r represented by the input data, the verification apparatus 100 A calculates an integer e 1 and integer e 2 that satisfy e 1 ·r≡e 2 (mod p) |e 1 |<√p, and 0<e 2 <√p. Using the CPU 911 and based on the element U and element Q represented by the input data and the calculated integer e 1 and integer e 2 , the verification apparatus 100 A calculates an element a=e 1 ·U−e 2 ·Q of the additive group G 1 by the operation on the additive group G 1 . The verification apparatus 100 A judges, using the CPU 911 and based on the calculated element a , whether or not the element a is an identity element of the additive group G 1 . Using the CPU 911 , if the element a is an identity element of the additive group G 1 , the verification apparatus 100 A judges that “the verification is successful”; if not, “the verification fails”. Using the CPU 911 , the verification apparatus 100 A outputs data representing the verification result.

Using the CPU 911 , the decrypted text generating unit 260 A inputs the data representing the verification result and output by the verification apparatus 100 A. If the verification result represented by the input data expresses that “the verification is successful”, the decrypted text generating unit 260 A generates, using the CPU 911 , a common key K. If the verification result expresses that “the verification fails”, the decrypted text generating unit 260 A does not generate a common key K. Alternatively, if the verification result expresses that “the verification fails”, the decrypted text generating unit 260 A may generate a random common key K that will be of no clue to the unauthorized person.

If the judgment result expresses that “the verification is successful”, using the CPU 911 , the decrypted text generating unit 260 A inputs the data representing the hash function H 4 among the encryption parameters stored by the encryption parameter storage unit 290 A, and the bit string m stored by the bit string calculation unit 232 A. Using the CPU 911 and based on the hash function H 4 represented by the input data and the input bit string m, the decrypted text generating unit 260 A calculates a hash value which is obtained when the bit string m is hashed by the hash function H 4 , and treats it as a common key K. The common key K is a bit string having a predetermined length. Using the RAM 914 , the decrypted text generating unit 260 A stores the calculated common key K.

If the ciphertext c input by the ciphertext input unit 220 A is a correct ciphertext, the bit string m calculated by the bit string calculation unit 232 A is equal to the bit string m generated by the secret bit string generating unit 421 A of the ciphertext generating apparatus 400 A. Hence, the common key K calculated by the decrypted text generating unit 260 A is equal to the common key K calculated by the common key calculation unit 427 A of the ciphertext generating apparatus 400 A.

Therefore, the ciphertext generating apparatus 400 A and ciphertext decryption apparatus 200 A can share the same common key K.

Using the CPU 911 , the common key storage unit 270 A inputs the common key K stored by the decrypted text generating unit 260 A. Using the RAM 914 , the common key storage unit 270 A stores the input common key K.

Using the CPU 911 , the encrypted message input unit 281 A inputs the encrypted message CM received from the ciphertext generating apparatus 400 A. Using the magnetic disk drive 920 , the encrypted message input unit 281 A stores the input encrypted message CM.

Using the CPU 911 , the message decryption unit 282 A inputs the common key K stored by the common key storage unit 270 A, and the encrypted message CM stored by encrypted message input unit 281 A. Using the CPU 911 , the message decryption unit 282 A decrypts the input encrypted message CM by the input common key K, thus generating a message M′. Using the magnetic disk drive 920 , the message decryption unit 282 A stores the generated message M′.

As the ciphertext generating apparatus 400 A and ciphertext decryption apparatus 200 A share the same common key K, the message M′ generated by the message decryption unit 282 A is identical to the message M input by the message input unit 440 A of the ciphertext generating apparatus 400 A.

Using the CPU 911 , the decrypted message output unit 283 A inputs the message M′ stored by the message decryption unit 282 A. Using the CPU 911 , the decrypted message output unit 283 A outputs the input message M′.

FIG. 15 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 A according to this embodiment to decrypt the ciphertext c.

In a pairing value calculation step S 731 A, using the CPU 911 and based on the element U input by the ciphertext input unit 220 A and the secret key D ID stored by the key storage unit 210 A, the pairing value calculation unit 231 A calculates the pairing value of the element U and secret key D ID by the pairing e, and treats it as the pairing value α.

In a bit string calculation step S 732 A, using the CPU 911 and based on the pairing value α calculated by the pairing value calculation unit 231 A in the pairing value calculation step S 731 A, the bit string calculation unit 232 A calculates the hash value H 2 (α), which is obtained when the pairing value α is hashed by the hash function H 2 . Using the CPU 911 and based on the bit string V input by the ciphertext input unit 220 A and the calculated hash value H 2 (α), the bit string calculation unit 232 A obtains the bitwise exclusive OR of the bit string V and the hash value H 2 (α), and treats the result as the bit string m.

In an integer calculation step S 733 A, using the CPU 911 and based on the bit string m calculated by the bit string calculation unit 232 A in the bit string calculation step S 732 A, the integer calculation unit 233 A calculates the hash value which is obtained when the bit string m is hashed by the hash function H 3 , and treats it as the hash value r.

In a ciphertext verification step S 734 A, using the CPU 911 and based on the element Q stored by the identifier element storage unit 243 A, the element U input by the ciphertext input unit 220 A, and the hash value r calculated by the integer calculation unit 233 A in the integer calculation step S 733 A, the verification apparatus 100 A verifies whether U=r·Q.

If U=r·Q, the process advances to a decrypted text generating step S 735 A. If U≠r·Q, the ciphertext decryption process is ended.

In the decrypted text generating step S 735 A, using the CPU 911 and based on the bit string m calculated by the bit string calculation unit 232 A in the bit string calculation step S 732 A, the decrypted text generating unit 260 A calculates the hash value which is obtained when the bit string m is hashed by the hash function H 4 , and treats it as the common key K.

After that, the ciphertext decryption process is ended, and the encrypted message CM is decrypted by the calculated common key K.

In order not to give any clue to decipher a cipher to an unauthorized person who wishes to decipher the cipher illegally, the ciphertext decryption apparatus 200 A must verify whether the ciphertext is consistent.

In the ciphertext decryption apparatus 200 A according to this embodiment, in order to verify the consistency of the ciphertext, the verification apparatus 100 A judges whether or not U=r·Q. As described in the first embodiment, the verification apparatus 100 A can verify whether or not U=r·Q at high speed. Hence, the ciphertext decryption apparatus 200 A can decrypt the ciphertext at high speed.

The ciphertext decryption apparatus 200 A according to this embodiment includes a storage device (e.g., RAM 914 and magnetic disk drive 920 ) which stores data, a processing device (CPU 911 ) which processes data, the key storage unit 210 A, the ciphertext input unit 220 A, the ciphertext verification unit 230 A, the verification apparatus 100 A, and the decrypted text generating unit 260 A.

The key storage unit 210 stores, using the storage device, a key (secret key D ID ) for decrypting the ciphertext. Using the processing device (CPU 911 ), the ciphertext input unit 220 A inputs the ciphertext c. Using the processing device (CPU 911 ) and based on the key (secret key D ID ) stored by the key storage unit 210 A and the ciphertext c input by the ciphertext input unit 220 A, the ciphertext verification unit 230 calculates the integer e (hash value r), the element s (element Q) of the finite group G (additive group G 1 ), and the element h (element U) of the finite group G (additive group G 1 ), which are to be input by the verification apparatus 100 A. The verification apparatus 100 A inputs the integer e (hash value r), the element s (element Q) of the finite group G (additive group G 1 ), and the element h (element U) of the finite group G (additive group G 1 ), which are calculated by the ciphertext verification unit 230 A, and judges whether or not verification is successful. When the verification apparatus 100 A judges that the verification is successful, the decrypted text generating unit 260 A, using the processing device (CPU 911 ), decrypts the ciphertext c input by the ciphertext input unit 220 A by means of the key (secret key D ID ) stored by the key storage unit 210 A, to generate the decrypted text (common key K).

According to the ciphertext decryption apparatus 200 A of this embodiment, when the verification apparatus 100 A verifies the consistency of the ciphertext and judges that the verification is successful, the decrypted text generating unit 260 A generates a decrypted text. This can prevent any clue to decipher a cipher from being given to an unauthorized person who inputs an incorrect ciphertext to the ciphertext decryption apparatus 200 A with the intention of obtaining from the decryption result a clue to decipher the cipher. Also, the time necessary for the verification apparatus 100 A to perform the process of verifying the consistency of the ciphertext can be shortened. Thus, the time necessary for the ciphertext decryption apparatus 200 A to perform the entire process of decrypting the ciphertext can be shortened.

The ciphertext decryption apparatus 200 A according to this embodiment further has the encryption parameter storage unit 290 A, the identifier storage unit 241 A, the identifier element calculation unit 242 A, and the identifier element storage unit 243 A.

Using the storage device (magnetic disk drive 920 ), the encryption parameter storage unit 290 A stores the order p of the finite group G (additive group G 1 ), the generator g 1 of the finite group G (additive group G 1 ), and the element R of the finite group G (additive group G 1 ). Using the storage device (magnetic disk drive 920 ), the identifier storage unit 241 A stores the bit string ID that identifies the ciphertext decryption apparatus 200 A. Using the processing device and based on the bit string ID stored by the identifier storage unit 241 A, the identifier element calculation unit 242 A calculates the hash value which is obtained when the bit string ID is hashed by the predetermined hash function H 1 , and treats it as the integer (hash value) H 1 (ID). Using the processing device and based on the generator g 1 stored by the encryption parameter storage unit 290 A, the element R stored by the encryption parameter storage unit 290 A, and the calculated integer (hash value) H 1 (ID), the identifier element calculation unit 242 A adds the element R to an element which is obtained when the generator g 1 is multiplied by the integer (hash value) H 1 (ID), and treats the result as the element Q (=R+H 1 (ID)·g 1 ) of the finite group G (additive group G 1 ). Using the storage device (magnetic disk drive 920 ), the identifier element storage unit 243 A stores the element Q calculated by the identifier element calculation unit 242 A. Using the storage device, the key storage unit 210 A stores the element D ID of the finite group (additive group G 1 ) G 2 . Using the processing device (CPU 911 ), the ciphertext input unit 220 A inputs the element U of the finite group G (additive group G 1 ) and the bit string V as the ciphertext c. The ciphertext verification unit 230 A has the pairing value calculation unit 231 A, the bit string calculation unit 232 A, and the integer calculation unit 233 A. Using the processing device (CPU 911 ) and based on the element U input by the ciphertext input unit 220 A and the element D ID stored by the key storage unit 210 A, the pairing value calculation unit 231 A calculates the pairing value of the element U and element D ID by a predetermined pairing function e, and treats it as a pairing value α (=e(U,D ID )). Using the processing device (CPU 911 ) and based on the pairing value α calculated by the pairing value calculation unit 231 A, the bit string calculation unit 232 A calculates a hash value which is obtained when the pairing value α is hashed by the predetermined hash function H 2 , and treats it as a bit string (hash value) H 2 (α). Using the processing device (CPU 911 ) and based on the bit string V input by the ciphertext input unit 220 A and the calculated bit string (hash value) H 2 (α), the bit string calculation unit 232 A obtains the exclusive ORs of the bit string V and the bit string (hash value) H 2 (α), and treats the result as the bit string m (=V XOR H 2 (α)). Using the processing device (CPU 911 ) and based on the bit string m calculated by the bit string calculation unit 232 A, the integer calculation unit 233 A calculates a hash value which is obtained when the bit string m is hashed by the predetermined hash function H 3 , and treats it as an integer (hash value) r (=H 3 (m)). The verification apparatus 100 A inputs the order p stored by the encryption parameter storage unit 290 A, the integer (hash value) r calculated by the integer calculation unit 233 A as the integer e, the element Q stored by the identifier element storage unit 243 A as the element s, and the element U input by the ciphertext input unit 220 A as the element h, and judges whether or not the verification is successful. When the verification apparatus 100 A judges that the verification is successful, the decrypted text generating unit 260 A, using the processing device (CPU 911 ), calculates, based on the bit string m calculated by the bit string calculation unit 232 A, a hash value which is obtained when the bit string m is hashed by the predetermined hash function H 4 , and treats it as the common key K (=H 4 (m)). The decrypted text generating unit 260 A outputs the calculated common key K as the decrypted text.

According to the ciphertext decryption apparatus 200 A of this embodiment, when the verification apparatus 100 A verifies whether U=r·Q and judges that the verification is successful, the decrypted text generating unit 260 A generates the decrypted text. This can prevent any clue to decipher a cipher from being given to an unauthorized person. Also, the time necessary for the verification apparatus 100 A to perform the process of verifying whether U=r·Q can be shortened. Thus, the time necessary for the ciphertext decryption apparatus 200 A to perform the entire process of decrypting the ciphertext can be shortened.

The identifier element calculation unit 242 A according to this embodiment calculates the element Q before the ciphertext input unit 220 A inputs the ciphertext c.

According to the ciphertext decryption apparatus 200 A of this embodiment, the process of calculating the element Q is executed before the ciphertext input unit 220 A inputs the ciphertext c. Therefore, the time taken since the ciphertext input unit 220 A inputs the ciphertext c until the decrypted text generating unit 260 A calculates the common key K can be further shortened.

The ciphertext decryption apparatus 200 A according to this embodiment further has the common key storage unit 270 A, the encrypted message input unit 281 A, and the message decryption unit 282 A.

Using the storage device (RAM 914 ), the common key storage unit 270 A stores the common key K output by the decrypted text generating unit 260 A. Using the processing device (CPU 911 ), the encrypted message input unit 281 A inputs the encrypted message CM. Using the processing device (CPU 911 ), the message decryption unit 282 A decrypts the encrypted message CM input by the encrypted message input unit 281 A by means of the common key K stored by the common key storage unit 270 A.

According to the ciphertext decryption apparatus 200 A of this embodiment, the message decryption unit 282 A decrypts the encrypted message CM by the common key K shared with the ciphertext generating apparatus 400 A through the ciphertext c. Hence, common key cryptography that enables high-speed processing can be employed for the generation and decryption of the encrypted message CM.

The cryptographic system (ID-based public key cryptographic system 820 A) of this embodiment has the verification apparatus 100 A.

According to the cryptographic system (ID-based public key cryptographic system 820 A) of this embodiment, since the verification apparatus 100 A verifies the consistency of the ciphertext, any clue to decipher the cipher can be prevented from being given to the unauthorized person. Also, since the time necessary for the verification apparatus 100 A to perform the process of verifying the consistency of the ciphertext can be shortened, the time taken by the entire cryptographic communication can be shortened.

The ciphertext decryption apparatus 200 A (public key cryptography decryption apparatus) described so far is a key decapsulation apparatus in a public key cryptographic system (ID-based public key cryptographic system 820 A), and has a ciphertext correctness verification apparatus (verification apparatus 100 A). The ciphertext correctness verification apparatus judges whether or not a ciphertext is correct by verifying whether or not an element s e obtained when the element s of the multiplicative group is multiplied e times in accordance with exponentiation on a multiplicative group such as a group formed of the residue classes of integers, or the element e·s obtained when the element s of an additive group is added e times in accordance with the scalar multiplication on an additive group such as a group formed of points on a (hyper)elliptic curve, coincides with the known element h.

The ciphertext correctness verification apparatus (verification apparatus 100 A) has a device (integer partitioning unit 110 ) that partitions an exponential part (integer e), a device (verification value calculation unit 130 ) that, using the partitioned exponents (the integer e 1 and integer e 2 ), calculates a value h e1 −s e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·h−e 2 ·s by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ciphertext decryption apparatus 200 A described so far is an ID-based cryptography decryption apparatus.

The ciphertext decryption apparatus 200 A has an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, a value (element Q=R+H 1 (ID)·g 1 ) which is calculated from the public parameters (element g 1 and public element R) and the ID of the recipient (ciphertext decryption apparatus 200 A), and a storage device (identifier element storage unit 243 A) that stores the advance calculated value (element Q).

The ciphertext decryption apparatus 200 A (ID-based cryptography decryption apparatus) described so far has

an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, a value (element Q) which is calculated from the public parameters (element g 1 and public element R) and the ID of the recipient (ciphertext decryption apparatus 200 A), a storage device (identifier element storage unit 243 A) that stores the advance calculated value (element Q), and the verification apparatus 100 A that verifies a value (Q r ) obtained when the advance calculated value (element Q) is subjected to exponentiation on the multiplicative group, or a value (r·Q) obtained when the advance calculated value (element Q) is subjected to scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve. The verification apparatus 100 A has a device (integer partitioning unit 110 ) that partitions an exponential part (hash value r), a device (verification value calculation unit 130 ) that calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value U e1 ·Q −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·U−e 2 ·Q by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ciphertext decryption apparatus 200 A described so far is an SK (Sakai-Kasahara)-ID-based cryptography decryption apparatus.

The ciphertext decryption apparatus 200 A has an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, an element Q=R·g 1 h or Q=R+h·g 1 , which is calculated from the element R and element g 1 , being the public parameters (encryption parameters), of the multiplicative group or additive group, and the hash value h=H 1 (ID) of the bit string ID that identifies the recipient (ciphertext decryption apparatus 200 A), a storage device (identifier element storage unit 243 A) that stores the element Q, and a ciphertext correctness verification apparatus (verification apparatus 100 A) that judges whether a ciphertext is correct by verifying whether or not Q r or r·Q, concerning the integer r as the hash value of the random bit string m, coincides with known U.

The ciphertext decryption apparatus 200 A described so far is a key decapsulation apparatus (SK-ID-based cipher key decapsulation apparatus) in an SK-ID-based cryptographic system (ID-based public key cryptographic system 820 A).

The ciphertext decryption apparatus 200 A has an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, an element Q=R·g 1 h or Q=R+h·g 1 , which is calculated from the element R and element g 1 , being the public parameters (encryption parameters), of the multiplicative group or additive group, and the hash value h=H 1 (ID) of the bit string ID that identifies the recipient (ciphertext decryption apparatus 200 A), a storage device (identifier element storage unit 243 A) that stores the element Q, and a ciphertext correctness verification apparatus (verification apparatus 100 A) that judges whether a ciphertext is correct by verifying whether or not Q r or r·Q, concerning the integer r which is the hash value of the random bit string m, coincides with known U.

The ciphertext decryption apparatus 200 A (SK-ID-based cryptography decryption apparatus) described so far has

an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, an element Q=R·g 1 h or Q=R+h·g 1 , which is calculated from the element R and element g 1 , being public parameters (encryption parameters), of the multiplicative group or additive group, and the hash value h=H 1 (ID) of the bit string ID that identifies the recipient (ciphertext decryption apparatus 200 A), a storage device (identifier element storage unit 243 A) that stores the element Q, a device (integer calculation unit 233 A) that calculates a hash value (integer r) of a random bit string m, a device (integer partitioning unit 110 ) that partitions an exponential part (integer r), a device (verification value calculation unit 130 ) that calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value U e1 ·Q −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·U−e 2 ·Q by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ciphertext decryption apparatus 200 A (SK-ID-based cipher key decapsulation apparatus) described so far has

an advance calculation device (identifier element calculation unit 242 A) that calculates, in advance, an element Q=R·g 1 h or Q=R+h·g 1 , which is calculated from the element R and element g 1 , being the public parameters (encryption parameters), of the multiplicative group or additive group, and the hash value h=H 1 (ID) of the bit string ID that identifies the recipient (ciphertext decryption apparatus 200 A), a storage device (identifier element storage unit 243 A) that stores the element Q, a device (integer calculation unit 233 A) that calculates an integer r which is a hash value of a random bit string m, a device (integer partitioning unit 110 ) that partitions an exponential part (integer r), a device (verification value calculation unit 130 ) that calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value U e1 ·Q −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·U−e 2 ·Q by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ID-based public key cryptographic system 820 A described so far is an SK-IBKEM cryptographic system which is an ID-based cryptography that utilizes a pairing operation on a (hyper)elliptic curve.

The ID-based public key cryptographic system 820 A employs the additive group G 1 , the additive group G 2 , and the multiplicative group G T which have an order p being a prime number, the base point (generator) g 1 in the group G 1 , the base point g 2 in the group G 2 , and the pairing e. First, using the CPU 911 , the encryption parameter setting apparatus 810 A (encryption parameter generating apparatus) randomly selects the integer s which is equal to or larger than 1 and equal to or smaller than p−1. Then, using the CPU 911 , the encryption parameter setting apparatus 810 A calculates the element R=s·g 1 of the group G 1 . Using the CPU 911 , the encryption parameter setting apparatus 810 A outputs the secret key (secret random number) s for the key generating apparatus 300 A (key generation center or PKG: Private Key Generator) and the public key (public element) R for the PKG. Using the CPU 911 , the key generating apparatus 300 A (secret key derivation device) inputs the bit string ID that identifies the ciphertext decryption apparatus 200 A. First, using the CPU 911 , the key generating apparatus 300 A calculates the hash value h=H1 (ID). Using the CPU 911 , the key generating apparatus 300 A then calculates the integer e=1/(s+h)mod p, and calculates an element d ID =e·g 2 , which is the secret key for the ID, of the group G 2 and outputs it. Using the CPU 911 , the ciphertext generating apparatus 400 A (encryption apparatus) first generates the random bit string m. Then, using the CPU 911 , the ciphertext generating apparatus 400 A calculates the hash value r=H 3 (m) and the hash value h=H 1 (ID), and then calculates the element Q=R+h·g 1 of the group G 1 . Using the CPU 911 , the ciphertext generating apparatus 400 A calculates the element U=r·Q of the group G 1 , and calculates the bit string V=XOR(m,H 2 (e(g 1 ,g 2 ) r )) which is the exclusive ORs of the bit string m and the hash value H 2 (e(g 1 ,g 2 ) r ). Using the CPU 911 , the ciphertext generating apparatus 400 A outputs the key (common key) K=H 4 (m) and the ciphertext c=(U,V). The ciphertext decryption apparatus 200 A (decryption apparatus) inputs the bit string ID that identifies the ciphertext decryption apparatus 200 A itself, the secret key d ID generated by the key generating apparatus 300 A, and the ciphertext c=(U,V) output by the ciphertext generating apparatus 400 A. The ciphertext decryption apparatus 200 A calculates the pairing value α=e(U,d ID ), and calculates the bit string m=XOR(V,H 2 (α)) which is the exclusive ORs of the bit string V and the hash value H 2 (α). The ciphertext decryption apparatus 200 A calculates the hash value r=H 3 (m) and the hash value h=H 1 (ID), and calculates the element Q=R+h·g 1 of the group G 1 . Using the CPU 911 , the ciphertext decryption apparatus 200 A checks whether or not r·Q=U is established. If it is not established, the ciphertext decryption apparatus 200 A outputs “reject”. If it is established, using the CPU 911 , the ciphertext decryption apparatus 200 A calculates the common key K=H 4 (m) and outputs it.

The verification apparatus 100 A described so far speeds up the process of checking whether or not r·Q=U is established in the SK-IBKEM cryptographic system.

Using the CPU 911 and based on the element g 1 and the element R which are encryption parameters commonly used in the entire system, and the hash value h=H 1 (ID) of the ID of the recipient (ciphertext decryption apparatus 200 A) itself, the identifier element calculation unit 242 A calculates the element Q=R+h·g 1 of the group G 1 in advance by the double-base scalar multiplication on the group G 1 regardless of the content of the communication with the ciphertext generating apparatus 400 A.

In the verification apparatus 100 A, using the CPU 911 , the integer partitioning unit 110 inputs r and p and calculates the integers e 1 and e 2 that satisfy e 1 ·r≡e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 calculates an element W=e 2 ·Q−e 1 ·U of the group G 1 by the double-base scalar multiplication on the group G 1 . Using the CPU 911 , the verification judging unit 150 checks whether or not the element W is the identity element 0 of the group G 1 . Thus, whether or not r·Q=U is established is checked at high speed.

The third embodiment will be described with reference to FIGS. 16 to 20 .

FIG. 16 shows an example of the entire system configuration of a public key cryptographic system 820 B of this embodiment.

In the public key cryptographic system 820 B, a ciphertext generating apparatus 400 B generates a ciphertext using the public key of a ciphertext decryption apparatus 200 B, and the ciphertext decryption apparatus 200 B decrypts the ciphertext using a secret key corresponding to the public key.

The public key cryptographic system 820 B has an encryption parameter setting apparatus 810 B, a key generating apparatus 300 B, the ciphertext generating apparatus 400 B, and the ciphertext decryption apparatus 200 B.

The encryption parameter setting apparatus 810 B determines encryption parameters to be used in the public key cryptographic system 820 B. The encryption parameters determined by the encryption parameter setting apparatus 810 B are open to the user of the public key cryptographic system 820 B. The encryption parameters determined by the encryption parameter setting apparatus 810 B include, e.g., an order p, an additive group G, an element g of the additive group G, a hash function H, and a key derivation function KDF.

The order p is a prime number. The order of the additive group G is p. The element g is a generator of the additive group G. The hash function H is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from an ordered pair of two elements of the additive group G. The key derivation function KDF is a function that generates a bit string having a predetermined length from an ordered pair of two elements of the additive group G.

When these encryption parameters are predetermined, the encryption parameter setting apparatus 810 A can be omitted.

The key generating apparatus 300 B generates a pair of a secret key and a public key based on the public encryption parameters. In secret, the secret key generated by the key generating apparatus 300 B is notified to the ciphertext decryption apparatus 200 B. The public key generated by the key generating apparatus 300 B is open to the user in the form of, e.g., a public key certificate, as the public key of the ciphertext decryption apparatus 200 B.

The key generating apparatus 300 B generates four elements g′, c, d, and h of the additive group G as the public key. The key generating apparatus 300 B generates four integers w, x, y, and z, each equal to or larger than 1 and equal to or smaller than p−1, as the secret key.

The key generating apparatus 300 B may be part of the ciphertext decryption apparatus 200 B.

The ciphertext generating apparatus 400 B generates a ciphertext c and a common key K based on the public encryption parameters and the public key. The ciphertext generating apparatus 400 B encrypts a message M by the generated common key K, thus generating an encrypted message CM. The ciphertext generating apparatus 400 B transmits the generated ciphertext c and the encrypted message CM to the ciphertext decryption apparatus 200 B.

The ciphertext decryption apparatus 200 B holds, in secret, the secret key generated by the key generating apparatus 300 B. The ciphertext decryption apparatus 200 B receives the ciphertext c and encrypted message CM transmitted by the ciphertext generating apparatus 400 B. Based on the public encryption parameters, the ciphertext decryption apparatus 200 B decrypts the received ciphertext c by the secret key it holds, thus generating a common key K identical to that of the ciphertext generating apparatus 400 B. The ciphertext decryption apparatus 200 B decrypts the encrypted message CM by the generated common key K, thus generating a message M′ identical to the message M.

The appearances and hardware resources of the encryption parameter setting apparatus 810 B, key generating apparatus 300 B, ciphertext generating apparatus 400 B, and ciphertext decryption apparatus 200 B are similar to those of the ciphertext decryption apparatus 200 described in the first embodiment.

FIG. 17 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 B of this embodiment.

The key generating apparatus 300 B has an encryption parameter storage unit 390 B, a secret key generating unit 350 B, a public key generating unit 370 B, a secret key output unit 360 B, and a public key output unit 380 B.

Using a magnetic disk drive 920 , the encryption parameter storage unit 390 B stores data representing the public encryption parameters in advance.

The secret key generating unit 350 B generates the secret key based on the encryption parameters stored by the encryption parameter storage unit 390 B.

The secret key generating unit 350 B has four secret random number generating units 351 B to 354 B.

Using a CPU 911 , each of the four secret random number generating units 351 B to 354 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 390 B. Using the CPU 911 , each of the four secret random number generating units 351 B to 354 B randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1 based on the order p represented by the input data.

The first secret random number generating unit 351 B treats the generated integer as the integer w and, using a RAM 914 , stores data representing the generated integer w. The second secret random number generating unit 352 B treats the generated integer as the integer x and, using the RAM 914 , stores data representing the generated integer x. The third secret random number generating unit 353 B treats the generated integer as the integer y and, using the RAM 914 , stores data representing the generated integer y. The fourth secret random number generating unit 354 B treats the generated integer as the integer z and, using the RAM 914 , stores data representing the generated integer z.

Based on the encryption parameters stored by the encryption parameter storage unit 390 B and the secret key generated by the secret key generating unit 350 B, the public key generating unit 370 B generates the public key.

The public key generating unit 370 B has four public element calculation units 371 B to 374 B.

Using the CPU 911 , each of the four public element calculation units 371 B to 374 B inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 390 B.

Using the CPU 911 , the first public element calculation unit 371 B inputs the data representing the integer w and stored by the first secret random number generating unit 351 B. Using the CPU 911 and based on the additive group G, element g, and integer w represented by the input data, the first public element calculation unit 371 B calculates an element which is obtained when the element g is added w times by the operation on the additive group G, and treats the calculated element as the element g′. Using the RAM 914 , the first public element calculation unit 371 B stores data representing the calculated element g′. Using the CPU 911 , the second public element calculation unit 372 B inputs the data representing the integer x and stored by the second secret random number generating unit 352 B. Using the CPU 911 and based on the additive group G, element g, and integer x represented by the input data, the second public element calculation unit 372 B calculates an element which is obtained when the element g is added x times by the operation on the additive group G, and treats the calculated element as the element c. Using the RAM 914 , the second public element calculation unit 372 B stores data representing the calculated element c. Using the CPU 911 , the third public element calculation unit 373 B inputs the data representing the integer y and stored by the third secret random number generating unit 353 B. Using the CPU 911 and based on the additive group G, element g, and integer y represented by the input data, the third public element calculation unit 373 B calculates an element which is obtained when the element g is added y times by the operation on the additive group G, and treats the calculated element as the element d. Using the RAM 914 , the third public element calculation unit 373 B stores data representing the calculated element d. Using the CPU 911 , the fourth public element calculation unit 374 B inputs the data representing the integer z and stored by the fourth secret random number generating unit 354 B. Using the CPU 911 and based on the additive group G, element g, and integer z represented by the input data, the fourth public element calculation unit 374 B calculates an element which is obtained when the element g is added z times by the operation on the additive group G, and treats the calculated element as the element h. Using the RAM 914 , the fourth public element calculation unit 374 B stores data representing the calculated element h.

Using the CPU 911 , the secret key output unit 360 B inputs the data representing the integer w, integer x, integer y, and integer z stored by the four secret random number generating units 351 B to 354 B. Using the CPU 911 , the secret key output unit 360 B outputs, as the secret key, the data representing the input integer w, integer x, integer y, and integer z.

In secret, the secret key output by the secret key output unit 360 B is notified to the ciphertext decryption apparatus 200 B.

Using the CPU 911 , the public key output unit 380 B inputs the data representing the element g′, element c, element d, and element h stored by the four public element calculation units 371 B to 374 B. Using the CPU 911 , the public key output unit 380 B outputs, as the public key, the input data representing the element g′, element c, element d, and element h.

The public key output by the public key output unit 380 B is open to the user of the public key cryptographic system 820 B as the public key of the ciphertext decryption apparatus 200 .

FIG. 18 is a block diagram showing a configuration example of the function block of the ciphertext generating apparatus 400 B of this embodiment.

The ciphertext generating apparatus 400 B has an encryption parameter storage unit 490 B, a public key storage unit 410 B, a common key generating unit 420 B, a ciphertext output unit 470 B, a common key storage unit 430 B, a message input unit 440 B, a message encryption unit 450 B, and an encrypted message output unit 460 B.

Using the magnetic disk drive 920 , the encryption parameter storage unit 490 B stores data representing the public encryption parameters in advance.

Using the magnetic disk drive 920 , the public key storage unit 410 B stores data representing the public key of the ciphertext decryption apparatus 200 B to which the ciphertext is to be transmitted.

Based on the encryption parameters stored by the encryption parameter storage unit 490 B and the public key stored by the public key storage unit 410 B, the common key generating unit 420 B generates the common key K and the ciphertext which serves to notify the common key K to the ciphertext decryption apparatus 200 B.

The common key generating unit 420 B has a secret random number generating unit 421 B, a first cipher element calculation unit 422 B, a second cipher element calculation unit 423 B, a hash value calculation unit 424 B, an integer calculation unit 425 B, a third cipher element calculation unit 426 B, a secret element calculation unit 427 B, and a common key calculation unit 428 B.

Using the CPU 911 , the secret random number generating unit 421 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 490 B. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 421 B randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as a secret random number r. Using the RAM 914 , the secret random number generating unit 421 B stores data representing the generated secret random number r.

Using the CPU 911 , the first cipher element calculation unit 422 B inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 490 B, and the data representing the secret random number r and stored by the secret random number generating unit 421 B. Using the CPU 911 and based on the additive group G, element g, and secret random number r represented by the input data, the first cipher element calculation unit 422 B calculates an element which is obtained when the element g is added r times by the operation on the additive group G, and treats it as an element u. Using the RAM 914 , the first cipher element calculation unit 422 B stores data representing the calculated element u.

Using the CPU 911 , the second cipher element calculation unit 423 B inputs the data representing the additive group G among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the element g′ of the public key of the ciphertext decryption apparatus 200 B stored by the public key storage unit 410 B, and the data representing the secret random number r and stored by the secret random number generating unit 421 B. Using the CPU 911 and based on the additive group G, element g′, and secret random number r represented by the input data, the second cipher element calculation unit 423 B calculates an element which is obtained when the element g′ is added r times by the operation on the additive group G, and treats it as an element u′. Using the RAM 914 , the second cipher element calculation unit 423 B stores data representing the calculated element u′.

Since g′=w·g and u=r·g, the element u′ calculated by the second cipher element calculation unit 423 B is expressed as:

u′=r·g′=w·u   [Equation 24]

Using the CPU 911 , the hash value calculation unit 424 B inputs the data representing the hash function H among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the element u and stored by the first cipher element calculation unit 422 B, and the data representing the element u′ and stored by the second cipher element calculation unit 423 B. Using the CPU 911 and based on the hash function H, element u, and element u′ represented by the input data, the hash value calculation unit 424 B calculates a hash value which is obtained when an ordered pair of the element u and element u′ is hashed, and treats it as a hash value α. The hash value α is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the hash value calculation unit 424 B stores data representing the calculated hash value α.

Using the CPU 911 , the integer calculation unit 425 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the secret random number r and stored by the secret random number generating unit 421 B, and the data presenting the hash value α calculated by the hash value calculation unit 424 B. Using the CPU 911 and based on the order p, secret random number r, and hash value α represented by the input data, the integer calculation unit 425 B calculates a remainder which is obtained when the product of the hash value α and secret random number r is divided by the order p, and treats it as an integer r′. Using the RAM 914 , the integer calculation unit 425 B stores data representing the calculated integer r′.

Using the CPU 911 , the third cipher element calculation unit 426 B inputs the data representing the additive group G among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the element c and element d of the public key of the ciphertext decryption apparatus 200 B stored by the public key storage unit 410 B, the data representing the secret random number r and stored by the secret random number generating unit 421 B, and the data representing the integer r′ and stored by the integer calculation unit 425 B. Using the CPU 911 and based on the additive group G, element c, element d, secret random number r, and integer r′ represented by the input data, the third cipher element calculation unit 426 B calculates an element which is the sum of an element obtained when the element c is added r times and an element obtained when the element d is added r′ times by the operation on the additive group G, and treats the sum as an element v. Using the RAM 914 , the third cipher element calculation unit 426 B stores data representing the calculated element v.

Since c=x·g, d=y·g, and u=r·g, the element v calculated by the third cipher element calculation unit 426 B is expressed as:

Using the CPU 911 , the secret element calculation unit 427 B inputs the data representing the additive group G among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the element h of the public key, stored by the public key storage unit 410 B, of the ciphertext decryption apparatus 200 B, and the data representing the secret random number r and stored by the secret random number generating unit 421 B. Using the CPU 911 and based on the additive group G, element h, and secret random number r represented by the input data, the secret element calculation unit 427 B calculates an element which is obtained when the element h is added r times by the operation on the additive group G, and treats it as an element h ˜ . Using the CPU 911 , the secret element calculation unit 427 B stores data representing the calculated element h ˜ .

Since h=z·g and u=r·g, the element h ˜ calculated by the secret element calculation unit 427 B is expressed as:

{tilde over (h)}=r·h=z·u   [Equation 26]

Using the CPU 911 , the common key calculation unit 428 B inputs the data representing the key derivation function KDF among the encryption parameters stored by the encryption parameter storage unit 490 B, the data representing the element u and stored by the first cipher element calculation unit 422 B, and the data representing the element h ˜ and stored by the secret element calculation unit 427 B. Based on the key derivation function KDF, element u, and element h ˜ represented by the input data, the common key calculation unit 428 B calculates a bit string from an ordered pair of the element u and element h ˜ by the key derivation function, and treats it as a common key K. Using the RAM 914 , the common key calculation unit 428 B stores the calculated common key K.

Using the CPU 911 , the common key storage unit 430 B inputs the common key K stored by the common key calculation unit 428 B. Using the RAM 914 , the common key storage unit 430 B stores the input common key K.

Using the CPU 911 , the ciphertext output unit 470 B inputs the data representing the element u and stored by the first cipher element calculation unit 422 B, the data representing the element u′ and stored by the second cipher element calculation unit 423 B, and the data representing the element v and stored by the third cipher element calculation unit 426 B. Using the CPU 911 , the ciphertext output unit 470 B outputs data representing the input element u, element u′, and element v as the ciphertext c.

Using the CPU 911 , the message input unit 440 B inputs the message M to be transmitted to the ciphertext decryption apparatus 200 B. Using the magnetic disk drive 920 , the message input unit 440 B stores the input message M.

Using the CPU 911 , the message encryption unit 450 B inputs the common key K stored by the common key storage unit 430 B and the message M stored by the message input unit 440 B. Using the CPU 911 and based on the input message M and common key K, the message encryption unit 450 B encrypts the message M by the common key K into the encrypted message CM. Using the magnetic disk drive 920 , the message encryption unit 450 B stores the encrypted message CM it has generated.

Using the CPU 911 , the encrypted message output unit 460 B inputs the encrypted message CM stored by the message encryption unit 450 B. Using the CPU 911 , the encrypted message output unit 460 B outputs the input encrypted message CM.

The ciphertext c output by the ciphertext output unit 470 B and the encrypted message CM output by the encrypted message output unit 460 B are transmitted to the ciphertext decryption apparatus 200 B.

FIG. 19 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 B of this embodiment.

The ciphertext decryption apparatus 200 B has an encryption parameter storage unit 290 B, a key storage unit 210 B, a ciphertext input unit 220 B, a ciphertext verification unit 230 B, a verification apparatus 100 B, a decrypted text generating unit 260 B, a common key storage unit 270 B, an encrypted message input unit 281 B, a message decryption unit 282 B, and a decrypted message output unit 283 B.

Using the magnetic disk drive 920 , the encryption parameter storage unit 290 B stores data representing the public encryption parameters in advance.

In secret, using a tamper-resistant storage device, the key storage unit 210 B stores data representing the secret key generated by the key generating apparatus 300 B in advance.

Using the CPU 911 , the ciphertext input unit 220 B inputs the ciphertext c received from the ciphertext generating apparatus 400 B. Using the CPU 911 , the ciphertext input unit 220 B acquires the data representing the element u, element u′, and element v from the input ciphertext c. Using the RAM 914 , the ciphertext input unit 220 B stores the acquired data representing the element u, element u′, and element v.

The ciphertext verification unit 230 B has a hash value calculation unit 231 B and an integer calculation unit 232 B.

Using the CPU 911 , the hash value calculation unit 231 B calculates the data representing the hash function H among the encryption parameters stored by the encryption parameter storage unit 290 B, and the data representing the element u and element u′ and stored by the ciphertext input unit 220 B. Using the CPU 911 and based on the hash function H, element u, and element u′ represented by the input data, the hash value calculation unit 231 B calculates a hash value which is obtained when an ordered pair of the element u and element u′ is hashed by the hash function H, and treats it as a hash value α. The hash value α is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the hash value calculation unit 231 B stores data representing the calculated hash value α.

The hash value α calculated by the hash value calculation unit 231 B is equal to the hash value α calculated by the hash value calculation unit 424 B of the ciphertext generating apparatus 400 B.

Using the CPU 911 , the integer calculation unit 232 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 B, the data representing the integer x and integer y of the secret key stored by the key storage unit 210 B, and the hash value α stored by the hash value calculation unit 231 B. Using the CPU 911 and based on the order p, integer x, integer y, and hash value α represented by the input data, the integer calculation unit 232 B calculates a remainder which is obtained when the sum of the integer x and the product of the integer y and hash value α is divided by the order p, and treats it as an integer t. Using the CPU 911 , the integer calculation unit 232 B stores data representing the calculated integer t.

If the ciphertext c input by the ciphertext input unit 220 A is a correct ciphertext, equation 24 and equation 25 are established. Hence, whether the ciphertext c input by the ciphertext input unit 220 A is a correct ciphertext can be judged by verifying whether u′=w·u and v=t·u.

The verification apparatus 100 B checks whether or not u′=w·u and checks whether or not v=t·u. If u′=w·u and v=t·u, the verification apparatus 100 B judges that the verification is successful.

Either checking may come first. In the following explanation, whether or not u′=w·u is checked first, and then whether or not v=t·u is checked.

The verification apparatus 100 B is an apparatus corresponding to the verification apparatus 100 described in the first embodiment.

First, the verification apparatus 100 B checks whether or not u′=w·u.

Using the CPU 911 , the verification apparatus 100 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 B, as data representing the order p described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the integer w of the secret key stored by the key storage unit 210 B, as data representing the integer e described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the element u′ and stored by the ciphertext input unit 220 B, as data representing the element h described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the element u and stored by the ciphertext input unit 220 B, as data representing the element s described in the first embodiment. Using the CPU 911 and based on the order p and integer w represented by the input data, the verification apparatus 100 B calculates an integer e 1 and an integer e 2 that satisfy e 1 ·w≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p. The integer w is part of the secret key of the ciphertext decryption apparatus 200 and is known before the ciphertext input unit 220 B inputs the ciphertext c. Hence, using the CPU 911 , the verification apparatus 100 B may calculate the integer e 1 and the integer e 2 in advance before the ciphertext input unit 220 B inputs the ciphertext c, and store them using the tamper-resistant storage device. Using the CPU 911 and based on the element u and element u′ represented by the input data and the calculated integer e 1 and integer e 2 , the verification apparatus 100 B calculates an element a=e 1 ·u′−e 2 ·u of the additive group G by the operation on the additive group G. Using the CPU 911 and based on the calculated element a , the verification apparatus 100 B judges whether or not the element a is the identity element of the additive group G. Using the CPU 911 , if the element a is the identity element of the additive group G, the verification apparatus 100 B judges that the first verification is successful; if not, “the verification fails”.

When it is judged that the first verification is successful, then the verification apparatus 100 B judges whether or not v=t·u.

Using the CPU 911 , the verification apparatus 100 B inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 B, as data representing the order p described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the integer t and stored by the ciphertext input unit 220 , as data representing the element e described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the element v and stored by the ciphertext input unit 220 , as data representing the element h described in the first embodiment. Using the CPU 911 , the verification apparatus 100 B inputs the data representing the element u and stored by the ciphertext input unit 220 , as data representing the element s described in the first embodiment. Using the CPU 911 and based on the order p and integer t represented by the input data, the verification apparatus 100 B calculates an integer e 1 and an integer e 2 that satisfy e·t≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p. Using the CPU 911 and based on the element v and element u represented by the input data and the calculated integer e 1 and integer e 2 , the verification apparatus 100 B calculates an element a=e 1 ·v−e 2 ·u of the additive group G by the operation on the additive group G. Using the CPU 911 and based on the calculated element a , the verification apparatus 100 B judges whether or not the element a is the identity element of the additive group G. Using the CPU 911 , if the element a is the identity element of the additive group G, the verification apparatus 100 B judges that the second verification is also successful and accordingly “the verification is successful”; if not, “the verification fails”. Using the CPU 911 , the verification apparatus 100 B outputs data representing the verification result.

When the verification apparatus 100 B judges that “the verification is successful”, the decrypted text generating unit 260 B generates a common key K.

The decrypted text generating unit 260 B has a secret element calculation unit 261 B and a common key calculation unit 262 B.

Using the CPU 911 , the secret element calculation unit 261 B inputs the data representing the verification result and output by the verification apparatus 100 B. If the verification result represented by the input data expresses that “the verification is successful”, using the CPU 911 , the secret element calculation unit 261 B inputs the data representing the additive group G among the encryption parameters stored by the encryption parameter storage unit 290 B, the data representing the integer z of the secret key stored by the key storage unit 210 B, and the data representing the element u and stored by the ciphertext input unit 220 B. Using the CPU 911 and based on the additive group G, integer z, and element u represented by the input data, the secret element calculation unit 261 B calculates an element which is obtained when the element u is added z times by the operation on the additive group G, and treats it as an element h ˜ . Using the RAM 914 , the secret element calculation unit 261 B stores data representing the calculated element h ˜ .

If the ciphertext c input by the ciphertext input unit 220 A is a correct ciphertext, from Equation 26, the element h ˜ calculated by the secret element calculation unit 261 B is equal to the element h ˜ calculated by the secret element calculation unit 427 B.

Using the CPU 911 , the common key calculation unit 262 B inputs the data representing the key derivation function KDF among the encryption parameters stored by the encryption parameter storage unit 290 B, the data representing the element u and stored by the ciphertext input unit 220 B, and the data representing the element h ˜ and stored by the secret element calculation unit 261 B. Using the CPU 911 and based on the key derivation function KDF, element u, and element h ˜ represented by the input data, the common key calculation unit 262 B calculates a bit string from an ordered pair of the element u and element h ˜ by the key derivation function KDF, and treats it as the common key K. Using the RAM 914 , the common key calculation unit 262 B stores the calculated common key K.

The element h ˜ calculated by the secret element calculation unit 261 B is equal to the element h ˜ calculated by the secret element calculation unit 427 B of the ciphertext generating apparatus 400 B. Hence, the common key K calculated by the common key calculation unit 262 B is equal to the common key K calculated by the common key calculation unit 428 B of the ciphertext generating apparatus 400 B. Therefore, the ciphertext generating apparatus 400 B and the ciphertext decryption apparatus 200 B can share the same common key K.

Using the CPU 911 , the common key storage unit 270 B inputs the common key K stored by the common key calculation unit 262 B. Using the RAM 914 , the common key storage unit 270 B stores the input common key K.

Using the CPU 911 , the encrypted message input unit 281 B inputs the encrypted message CM received from the ciphertext generating apparatus 400 B. Using the magnetic disk drive 920 , the encrypted message input unit 281 B stores the input encrypted message CM.

Using the CPU 911 , the encrypted message input unit 281 B inputs the common key K stored by the common key storage unit 270 B, and the encrypted message CM stored by the encrypted message input unit 281 B. Using the CPU 911 , the message decryption unit 282 B decrypts the input encrypted message CM by the input common key K, thus generating a message M′. Using the magnetic disk drive 920 , the message decryption unit 282 B stores the generated message M′.

As the ciphertext generating apparatus 400 B and the ciphertext decryption apparatus 200 B share the same common key K, the message M′ generated by the message decryption unit 282 B is identical to the message M input by the message input unit 440 B.

Using the CPU 911 , the decrypted message output unit 283 B inputs the message M′ stored by the message decryption unit 282 B. Using the CPU 911 , the decrypted message output unit 283 B outputs the input message M′.

FIG. 20 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 A according to this embodiment to decrypt the ciphertext c.

In a hash value calculation step S 731 B, using the CPU 911 and based on the element u and element u′ input by the ciphertext input unit 220 B, the hash value calculation unit 231 B calculates a hash value which is obtained when the ordered pair of the element u and element u′ is hashed by the hash function H, and treats it as a hash value α.

In an integer calculation step S 732 B, using the CPU 911 and based on the order p stored by the encryption parameter storage unit 290 B, the integer x and integer y stored by the key storage unit 210 B, and the hash value α calculated by the hash value calculation unit 231 B in the hash value calculation step S 731 B, the integer calculation unit 232 B calculates the remainder which is obtained when the sum of the integer x and the product of the integer y and hash value α is divided by the order p, and treats it as the integer t.

In a first verification step S 733 B, using the CPU 911 and based on the integer w stored by the key storage unit 210 and the element u and element u′ input by the ciphertext input unit 220 A, the verification apparatus 100 B verifies whether u′=w·u.

If u′=w·u, the process advances to a second verification step S 734 B. If u′≠w·u, the ciphertext decryption process is ended.

In the second verification step S 734 B, using the CPU 911 , and based on the element u and element v input by the ciphertext input unit 220 B and the integer t calculated by the integer calculation unit 232 B in the integer calculation step S 732 B, the verification apparatus 100 B verifies whether v=t·u.

If v=t·u, the process advances to a secret element calculation step S 735 B. If v≠t·u, the ciphertext decryption process is ended.

In the secret element calculation step S 735 B, using the CPU 911 and based on the integer z stored by the key storage unit 210 B and the element u input by the ciphertext input unit 220 B, the secret element calculation unit 261 B calculates the element which is obtained when the element u is added z times by the operation on the additive group G, and treats it as the element h ˜ .

In a common key calculation step S 736 , using the CPU 911 and based on the element u input by the ciphertext input unit 220 B and the element h ˜ calculated by the secret element calculation unit 261 B in the secret element calculation step S 735 B, the common key calculation unit 262 B calculates the bit string from the ordered pair of the element u and element h ˜ by the key derivation function KDF, and treats it as the common key K.

After that, the ciphertext decryption process is ended, and the encrypted message CM is decrypted using the calculated common key K.

The ciphertext decryption apparatus 200 B according to this embodiment further has the encryption parameter storage unit 290 B.

Using the storage device (magnetic disk drive 920 ), the encryption parameter storage unit 290 B stores the order p of the finite group (additive group) G. Using the storage device, the key storage unit 210 B stores the integer w equal to or larger than 1 and equal to or smaller than p−1, the integer x equal to or larger than 1 and equal to or smaller than p−1, the integer y equal to or larger than 1 and equal to or smaller than p−1, and the integer z equal to or larger than 1 and equal to or smaller than p−1. Using the processing device (CPU 911 ), the ciphertext input unit 220 B inputs the element u of the finite group (additive group) G, the element u′ of the finite group (additive group) G, and the element v of the finite group (additive group) G, as the ciphertext c. The ciphertext verification unit 230 B has the hash value calculation unit 231 B and the integer calculation unit 232 B. Using the processing device (CPU 911 ) and based on the element u and element u′ input by the ciphertext input unit 220 B, the hash value calculation unit 231 B calculates the hash value which is obtained when the element u and element u′ are hashed by the predetermined hash function H, and treats it as an integer (hash value) α (=H(u,u′)). Using the processing device (CPU 911 ), and based on the order p stored by the encryption parameter storage unit 290 B, the integer x and integer y stored by the key storage unit 210 B, and the integer (hash value) α calculated by the hash value calculation unit 231 B, the integer calculation unit 232 B calculates the remainder which is obtained when the sum of the integer x and the product of the integer y and integer (hash value) α is divided by the order p, and treats it as the integer t (=(x+y·α)mod p). The verification apparatus 100 B inputs the order p stored by the encryption parameter storage unit 290 B, the integer w stored by the key storage unit 210 B as the integer e, the element u input by the ciphertext input unit 220 B as the element s, and the element u′ input by the ciphertext input unit 220 B as the element h, judges whether or not the verification is successful, and treats the judgment result as the first verification result. The verification apparatus 100 B inputs the order p stored by the encryption parameter storage unit 290 B, the integer t stored by the integer calculation unit 232 B as the integer e, the element u input by the ciphertext input unit 220 B as the element s, and the element v input by the ciphertext input unit 220 B as the element h, judges whether or not the verification is successful, and treats the judgment result as the second verification result. When both the first verification result and the second verification result show that the verification apparatus 100 B judges the verification successful, using the processing device (CPU 911 ) and based on the integer z stored by the key storage unit 210 B and the element u input by the ciphertext input unit 220 B, the decrypted text generating unit 260 B calculates the element which is obtained when the element u is added z times, and treats the result as the element h (=z·u) of the finite group G. Using the processing device (CPU 911 ) and based on the element u input by the ciphertext input unit 220 B and the calculated element h ˜ , the decrypted text generating unit 260 B generates the common key K (=KDF (u, h ˜ )) from the element u and the element h ˜ by the predetermined key derivation function KDF, and outputs the generated common key K as the decrypted text.

With the ciphertext decryption apparatus 200 B according to this embodiment, when the verification apparatus 100 B verifies whether u′=w·u and v=t·u and judges that the verification is successful, the decrypted text generating unit 260 B generates a decrypted text. This can prevent any clue to decipher a cipher from being given to an unauthorized person. Also, the time necessary for the verification apparatus 100 B to perform the process of verifying whether u′=w·u and v=t·u can be shortened. Thus, the time necessary for the ciphertext decryption apparatus 200 B to perform the entire process of decrypting the ciphertext can be shortened.

The ciphertext decryption apparatus 200 B according to this embodiment further has the common key storage unit 270 B, the encrypted message input unit 281 B, and the message decryption unit 282 B.

Using the storage device (RAM 914 ), the common key storage unit 270 B stores the common key K output by the decrypted text generating unit 260 B. Using the processing device (CPU 911 ), the encrypted message input unit 281 B inputs the encrypted message CM. Using the processing device (CPU 911 ) and by means of the common key K stored by the common key storage unit 270 B, the message decryption unit 282 B decrypts the encrypted message CM input by the encrypted message input unit 281 B.

With the ciphertext decryption apparatus 200 B according to this embodiment, the message decryption unit 282 B decrypts the encrypted message CM by means of the common key K which is shared with the ciphertext generating apparatus 400 B through the ciphertext c. Thus, the common key cryptographic system that can perform high-speed processing can be employed for generation and decryption of the encrypted message CM.

The ciphertext decryption apparatus 200 B (public key cryptography decryption apparatus) described so far has, in order to verify whether a relationship u′=u w (multiplicative description) or u′=w·u (additive description) is established among the element u and element u′, which are part of the ciphertext, of the multiplicative group or additive group, and the integer w as part of the secret key,

a device (integer partitioning unit 110 ) that partitions an exponential part (integer w), a device (verification value calculation unit 130 ) that calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value u′ e1 u −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·u′−e 2 ·u by the double-base scalar multiplication on the additive group such as a group formed on points on a (hyper) elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the obtained value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ciphertext decryption apparatus 200 B (public key cryptography decryption apparatus) described so far has, in order to verify whether a relationship v=u t (multiplicative description) or t·u=v (additive description) is established among the exponent (integer) t calculated based on the hash value α calculated from part (element u and element u′) of the ciphertext and the element u and element v as part of the ciphertext,

a device (integer partitioning unit 110 ) that partitions an exponential part (integer w), a device (verification value calculation unit 130 ) that calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value v e1 ·u −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·v−e 2 ·u by the double-base scalar multiplication on the additive group such as a group formed on points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) that judges whether or not the obtained value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The public key cryptographic system 820 B described so far is a key encapsulation scheme ACE-KEM cryptographic system that is standardized based on the Cramer-Shoup public key cryptography.

The public key cryptographic system 820 B employs the group (additive group) G having the prime-number order p and the base point (generator) g in the group G. Using the CPU 911 , the key generating apparatus 300 B randomly selects the integer w, integer x, integer y, and integer z each of which is equal to or larger than 0 and equal to or smaller than p−1. Using the CPU 911 , the key generating apparatus 300 B calculates the element g′=w·g of the group G, the element c=x·g of the group G, the element d=y·g of the group G, and the element h=z·g of the group G. Using the CPU 911 , the key generating apparatus 300 B outputs the public key (g′,c,d,h) and the secret key (w,x,y,z). Using the CPU 911 , the ciphertext generating apparatus 400 B (encryption apparatus) inputs the public key (g′,c,d,h). Using the CPU 911 , the ciphertext generating apparatus 400 B generates the random number r equal to or larger than 0 and equal to or smaller than p−1, and calculates the element u=r·g of the group G, the element u′=r·g′ of the group G, and the element h ˜ =r·h of the group G. Using the CPU 911 , the ciphertext generating apparatus 400 B calculates the hash value α=H (u∥u′), which is obtained when a bit string u∥u′ obtained by concatenating a bit string expressing the element u and a bit string expressing the element u′ is hashed, and calculates the integer r′=α·r mod p. Using the CPU 911 , the ciphertext generating apparatus 400 B calculates the element v=r·c+r′·d of the group G. Using the CPU 911 , the ciphertext generating apparatus 400 B calculates the key K=KDF (u∥h ˜ ), which is derived based on a bit string u∥h ˜ obtained when the bit string expressing the element u and a bit string expressing the element h ˜ are concatenated. Using the CPU 911 , the ciphertext generating apparatus 400 B outputs a ciphertext C 0 =(u,u′,v) and the key K. Using the CPU 911 , the ciphertext decryption apparatus 200 B (decryption apparatus) inputs the secret key (w,x,y,z) and the ciphertext C 0 =(u,u′,v). Using the CPU 911 , the ciphertext decryption apparatus 200 B calculates the hash value α=H (u∥u′), which is obtained when the bit string u∥u′ obtained by concatenating the bit string expressing the element u and the bit string expressing the element u′ is hashed. Using the CPU 911 , the ciphertext decryption apparatus 200 B calculates the integer t=x+y·α mod p. Using the CPU 911 , the ciphertext decryption apparatus 200 B checks whether or not w·u=u′ and t·u=v are established. If they are not, the ciphertext decryption apparatus 200 B outputs “reject”. If they are, using the CPU 911 , the ciphertext decryption apparatus 200 B calculates the element h ˜ =z·u, and calculates the key K=KDF (u∥h ˜ ) and outputs it.

The verification apparatus 100 B described above speeds up the process of checking whether or not w·u=u′ and t·u=v are established in this ACE-KEM cryptographic system.

In the verification apparatus 100 B, using the CPU 911 , the integer partitioning unit 110 inputs w and p and calculates the integers e 1 and e 2 that satisfy e 1 ·w≡e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 calculates the element U=e 2 ·u−e 1 ·u′ of the group G by the double-base scalar multiplication on the group G. Using the CPU 911 , the verification judging unit 150 checks at high speed whether w·u=u′ by checking whether the element U is the identity element O of the group G. Also, using the CPU 911 , the integer partitioning unit 110 inputs t and p and calculates the integers e 1 and e 2 that satisfy e 1 ·t≡e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 calculates the element V=e 2 ·u−e 1 ·v of the group G by the double-base scalar multiplication on the group G. Using the CPU 911 , the verification judging unit 150 checks at high speed whether t·u=v is established by checking whether the element V is the identity element O of the group G.

The fourth embodiment will be described with reference to FIGS. 21 to 27 .

FIG. 21 shows an example of the entire system configuration of an ID-based public key cryptographic system 820 C of this embodiment.

The ID-based public key cryptographic system 820 C is a cryptographic communication system that uses identification data that identifies a ciphertext decryption apparatus 200 C as the public key of the ciphertext decryption apparatus 200 C in the same manner as the ID-based public key cryptographic system 820 A described in the second embodiment.

The ID-based public key cryptographic system 820 C has an encryption parameter setting apparatus 810 C, a key generating apparatus 300 C, a ciphertext generating apparatus 400 C, and a ciphertext decryption apparatus 200 C.

The encryption parameter setting apparatus 810 C determines encryption parameters to be used in the ID-based public key cryptographic system 820 C. The encryption parameters determined by the encryption parameter setting apparatus 810 C are open to the user of the ID-based public key cryptographic system 820 C. The encryption parameters determined by the encryption parameter setting apparatus 810 C include, e.g., an order p, an additive group G, an element g of the additive group G, an additive group G′, an element g′ of the additive group G′, a multiplicative group G t , a pairing e, a hash function H, a hash function H′, and a hash function H″.

The order p is a prime number. The order of the additive group G is p. The element g is the generator of the additive group G. The order of the additive group G′ is p, which is the same as the order of the additive group G. The element g′ is a generator of the additive group G′. The order of the multiplicative group G t is p, which is the same as the order of each of the additive group G and additive group G′. The pairing e is a map that maps a set of an element of the additive group G and an element of the additive group G′ to an element (pairing value) of the multiplicative group G t . The pairing e has bilinearity. A pairing value e (g, g′) of the element g of the additive group G and the element g′ of the additive group G′ is not the identity element of the multiplicative group G t . The hash function H is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from a bit string having an arbitrary length. The hash function H′ is a hash function that generates a bit string having a predetermined length from an element of the multiplicative group G t .

The hash function H″ is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from a set of an element of the multiplicative group G t , a bit string having a predetermined length, and an ordered pair of elements of two additive groups G.

The element g′ of the additive group G′ is used by only the key generating apparatus 300 C and accordingly need not be open to other users.

When these encryption parameters are determined in advance, the encryption parameter setting apparatus 810 C need not determine them.

The encryption parameter setting apparatus 810 C generates a master key and public parameters generated based on the master key. The master key generated by the encryption parameter setting apparatus 810 C includes three integers α, β, and γ. The public parameters generated by the encryption parameter setting apparatus 810 C include an element g 1 of the additive group G, an element g 3 of the additive group G, and an element v 0 of the multiplicative group G t . The master key generated by the encryption parameter setting apparatus 810 C is notified to the key generating apparatus 300 C in secret. The public parameters generated by the encryption parameter setting apparatus 810 C are open to the user of the ID-based public key cryptographic system 820 C.

The key generating apparatus 300 C holds in secret the master key notified from the encryption parameter setting apparatus 810 C. Based on the public encryption parameters, the public identification data ID of the ciphertext decryption apparatus 200 C, and the held master key, the key generating apparatus 300 A generates the secret key of the ciphertext decryption apparatus 200 C. The secret key generated by the key generating apparatus 300 C includes an element d 0 of the additive group G′ and an element d 1 of the additive group G′. The secret key generated by the key generating apparatus 300 A is notified to the ciphertext decryption apparatus 200 C in secret.

Based on the public encryption parameters, the public parameters, and the identification data ID of the ciphertext decryption apparatus 200 C, the ciphertext generating apparatus 400 C encrypts a message M, thus generating a ciphertext C. The ciphertext generating apparatus 400 C transmits the generated ciphertext C to the ciphertext decryption apparatus 200 C.

The ciphertext decryption apparatus 200 C holds in secret the secret key generated by the key generating apparatus 300 C. The ciphertext decryption apparatus 200 C receives the ciphertext C transmitted by the ciphertext generating apparatus 400 C. Based on the public encryption parameters and the held secret key, the ciphertext decryption apparatus 200 C decrypts the received ciphertext C, thus generating a message M′ identical to the message M.

The appearances and hardware resources of the encryption parameter setting apparatus 810 C, key generating apparatus 300 C, ciphertext generating apparatus 400 C, and ciphertext decryption apparatus 200 C are similar to those of the ciphertext decryption apparatus 200 described in the first embodiment.

FIG. 22 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 C of this embodiment.

The encryption parameter setting apparatus 810 C has an encryption parameter storage unit 819 C, a master key generating unit 812 C, a public parameter generating unit 813 C, a master key output unit 814 C, and a public parameter output unit 815 C.

Using a magnetic disk drive 920 , the encryption parameter storage unit 819 C stores data representing the public encryption parameters.

The master key generating unit 812 C generates the master key based on the encryption parameters stored by the encryption parameter storage unit 819 C.

The master key generating unit 812 C has three secret random number generating units 816 C to 818 C. Using a CPU 911 , each of the three secret random number generating units 816 C to 818 C inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 819 C. Using the CPU 911 , each of the three secret random number generating units 816 C to 818 C randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1 based on the order p represented by the input data. The first secret random number generating unit 816 C treats the generated integer as the integer α and, using a RAM 914 , stores data representing the generated integer α. The second secret random number generating unit 817 C treats the generated integer as the integer β and, using the RAM 914 , stores data representing the generated integer β. The third secret random number generating unit 818 C treats the generated integer as the integer γ and, using the RAM 914 , stores data representing the generated integer γ.

Based on the encryption parameters stored by the encryption parameter storage unit 819 C and the master key generated by the master key generating unit 812 C, the public parameter generating unit 813 C generates the public parameters.

The public parameter generating unit 813 C has a first public element calculation unit 831 C, a public pairing value calculation unit 832 C, and a second public element calculation unit 833 C.

Using the CPU 911 , the first public element calculation unit 831 C inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 819 C, and the data representing the integer α and stored by the secret random number generating unit 816 C. Using the CPU 911 and based on the additive group G, element g, and integer α represented by the input data, the first public element calculation unit 831 C calculates an element which is obtained when the element g is added α times by the operation on the additive group G, and treats the calculated element as the element g 1 . Using the RAM 914 , the first public element calculation unit 831 C stores data representing the calculated element g 1 .

Using the CPU 911 , the public pairing value calculation unit 832 C inputs the data representing the element g, element g′, and pairing e among the encryption parameters stored by the encryption parameter storage unit 819 C, the data representing the integer α and stored by the secret random number generating unit 816 C, and the data representing the integer β and stored by the secret random number generating unit 817 C. Using the CPU 911 and based on the element g, element g′, and pairing e represented by the input data, the public pairing value calculation unit 832 C calculates the pairing value e (g, g′) of the element g and element g′ by the pairing e. The pairing value e (g,g′) is an element of the multiplicative group G t . Using the CPU 911 and based on the integer a and integer β represented by the input data and the calculated pairing value e (g,g′), the public pairing value calculation unit 832 C calculates an element which is obtained when the pairing value e (g,g′) is multiplied αβ times which is the product of the integer α and integer β and treats the calculated element as the element v 0 . Using the RAM 914 , the public pairing value calculation unit 832 C stores data representing the calculated element v 0 .

Using the CPU 911 , the second public element calculation unit 833 C inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 819 C, and the data representing the integer γ and stored by the secret random number generating unit 818 C. Using the CPU 911 and based on the additive group G, element g, and integer γ represented by the input data, the second public element calculation unit 833 C calculates an element which is obtained when the element g is added γ times by the operation on the additive group G, and treats the calculated element as the element g 3 . Using the RAM 914 , the second public element calculation unit 833 C stores data representing the calculated element g 3 .

Using the CPU 911 , the master key output unit 814 C inputs the data representing the integer α, integer β, and integer γ stored by the three secret random number generating units 816 C to 818 C. Using the CPU 911 , the master key output unit 814 C outputs, as the master key, the input data representing the integer α, integer β, and integer γ.

The master key output by the master key output unit 814 C is notified to the key generating apparatus 300 C in secret.

Using the CPU 911 , the public parameter output unit 815 C inputs the data representing the element g 1 and stored by the first public element calculation unit 831 C, the data representing the element v 0 and stored by the public pairing value calculation unit 832 C, and the data representing the element g 3 and stored by the second public element calculation unit 833 C. Using the CPU 911 , the public parameter output unit 815 C outputs, as the public parameters, the input data representing the element g 1 , element g 3 , and element v 0 .

The public parameters output by the public parameter output unit 815 C are open to the user of the ID-based public key cryptographic system 820 C.

FIG. 23 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 C of this embodiment.

The key generating apparatus 300 C has an encryption parameter storage unit 390 C, a master key storage unit 330 C, an identifier input unit 340 C, a secret key generating unit 350 C, and a secret key output unit 360 C.

Using the magnetic disk drive 920 , the encryption parameter storage unit 390 C stores the data representing the public encryption parameters in advance.

Using a tamper-resistant storage device, the master key storage unit 330 C stores, in secret, the master key notified from the encryption parameter setting apparatus 810 C.

As for the ciphertext decryption apparatus 200 C whose secret key is to be generated, the identifier input unit 340 C inputs, using the CPU 911 , an arbitrary-length bit string ID which is identification data for identifying the ciphertext decryption apparatus 200 C. Using the RAM 914 , the identifier input unit 340 C stores the input bit string ID.

The secret key generating unit 350 C generates the secret key of the ciphertext decryption apparatus 200 C based on the encryption parameters stored by the encryption parameter storage unit 390 C, the master key stored by the master key storage unit 330 C, and the bit string ID input by the identifier input unit 340 C.

The secret key generating unit 350 C has a secret random number generating unit 351 C, a first secret element calculation unit 352 C, and a second secret element calculation unit 353 C.

Using the CPU 911 , the secret random number generating unit 351 C inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 390 C. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 351 C randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as a secret random number r. Using the RAM 914 , the secret random number generating unit 351 C stores data representing the generated secret random number r.

Using the CPU 911 , the first secret element calculation unit 352 C inputs the data representing the additive group G′, element g′, and hash function H among the encryption parameters stored by the encryption parameter storage unit 390 C, the data representing the integer α, integer β, and integer γ of the master key stored by the master key storage unit 330 C, the bit string ID stored by the identifier input unit 340 C, and the data representing the secret random number r and stored by the secret random number generating unit 351 C. Using the CPU 911 and based on the hash function H represented by the input data and the input bit string ID, the first secret element calculation unit 352 C calculates a hash value H(ID) which is obtained when the bit string ID is hashed by the hash function H. Using the CPU 911 and based on the integer α, integer β, integer γ, and secret random number r represented by the input data and the calculated hash value H(ID), the first secret element calculation unit 352 C calculates an integer {α·β+[α·H(ID)+γ]·r} which is obtained when the product of the secret random number r and an integer (α·H(ID)+γ), which is the sum of the integer γ and the product of the integer a and hash value H(ID), is added with the product of the integer a and integer p. Using the CPU 911 and based on the additive group G′ and element g′ represented by the input data and the calculated integer {α·β+[α·H(ID)+γ]·r}, the first secret element calculation unit 352 C calculates an element which is obtained when the element g′ is added {α·β+[α·H(ID)+γ]·r} times by the operation on the additive group G′, and treats the obtained element as the secret element d 0 . Using the RAM 914 , the first secret element calculation unit 352 C stores data representing the calculated secret element d 0 .

Using the CPU 911 , the second secret element calculation unit 353 C inputs the data representing the additive group G′ and element g′ among the encryption parameters stored by the encryption parameter storage unit 390 C, and the data representing the secret random number r and stored by the secret random number generating unit 351 C. Using the CPU 911 and based on the additive group G′, element g′, and secret random number r represented by the input data, the second secret element calculation unit 353 C calculates an element which is obtained when the element g′ is added r times by the operation on the additive group G′, and treats the obtained element as the secret element d 1 . Using the RAM 914 , the second secret element calculation unit 353 C stores data representing the calculated secret element d 1 .

Using the CPU 911 , the secret key output unit 360 C inputs the data representing the secret element d 0 and stored by the first secret element calculation unit 352 C and the data representing the secret element d 1 and stored by the second secret element calculation unit 353 C. Using the CPU 911 , the secret key output unit 360 C outputs the input data representing the secret element d 0 and secret element d 1 as the secret key of the ciphertext decryption apparatus 200 C.

The secret key of the ciphertext decryption apparatus 200 C output by the secret key output unit 360 C is notified to the ciphertext decryption apparatus 200 C in secret.

FIG. 24 is a block diagram showing a configuration example of the function block of the ciphertext generating apparatus 400 C of this embodiment.

The ciphertext generating apparatus 400 C has an encryption parameter storage unit 490 C, an identifier storage unit 410 C, a message input unit 440 C, a message encryption unit 450 C, and a ciphertext output unit 470 C.

Using the magnetic disk drive 920 , the encryption parameter storage unit 490 C stores the public encryption parameters (including the public parameters) in advance.

Using the magnetic disk drive 920 , the identifier storage unit 410 C stores the bit string ID which is the identification data of the ciphertext decryption apparatus 200 C to which the ciphertext is to be transmitted.

Using the CPU 911 , the message input unit 440 C inputs a predetermined-length bit string M which is the message to be transmitted to the ciphertext decryption apparatus 200 C. When the message to be transmitted to the ciphertext decryption apparatus 200 C has a length equal to or larger than a predetermined length, the message is divided into a plurality of bit strings M having predetermined lengths, and the message input unit 440 C inputs the plurality of bit strings M. Using the RAM 914 , the message input unit 440 C stores the input bit string M.

Based on the encryption parameters (including the public parameters) stored by the encryption parameter storage unit 490 C and the bit string ID stored by the identifier storage unit 410 C, the message encryption unit 450 C encrypts the bit string M input by the message input unit 440 C, thus generating the ciphertext C.

The message encryption unit 450 C has a secret random number generating unit 451 C, a pairing value calculation unit 452 C, a cipher bit string calculation unit 453 C, a first cipher element calculation unit 454 C, a second cipher element calculation unit 455 C, and a cipher integer calculation unit 456 C.

Using the CPU 911 , the secret random number generating unit 451 C inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 490 C. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 451 C randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1 and treats it as a secret random number s. Using the RAM 914 , the secret random number generating unit 451 C stores data representing the generated secret random number s.

Using the CPU 911 , the pairing value calculation unit 452 C inputs the data representing the multiplicative group G t and element v 0 among the encryption parameters stored by the encryption parameter storage unit 490 C, and the data representing the secret random number s and stored by the secret random number generating unit 451 C. Using the CPU 911 and based on the multiplicative group G t , element v 0 , and secret random number s represented by the input data, the pairing value calculation unit 452 C calculates an element which is obtained when the element v 0 is multiplied s times by the operation on the multiplicative group G t , and treats the obtained element as an element k. Using the RAM 914 , the pairing value calculation unit 452 C stores data representing the calculated element k.

Using the CPU 911 , the cipher bit string calculation unit 453 C inputs the data representing the hash function H′ among the encryption parameters stored by the encryption parameter storage unit 490 C, the bit string M stored by the message input unit 440 C, and the data representing the element k and stored by the pairing value calculation unit 452 C. Using the CPU 911 and based on the hash function H′ and element k represented by the input data, the cipher bit string calculation unit 453 C calculates a hash value H′(k) which is obtained when the element k is hashed by the hash function H′. The hash value H′(k) is a bit string having a predetermined length. Using the CPU 911 and based on the input bit string M and the calculated hash value H′(k), the cipher bit string calculation unit 453 C obtains the bitwise exclusive OR of the bit string M and the hash value H(k), and treats the result as a bit string c. Using the RAM 914 , the cipher bit string calculation unit 453 C stores the calculated bit string c.

Using the CPU 911 , the first cipher element calculation unit 454 C inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 490 C, and the data representing the secret random number s and stored by the secret random number generating unit 451 C. Using the CPU 911 and based on the additive group G, element g, and secret random number s represented by the input data, the first cipher element calculation unit 454 C calculates an element which is obtained when the element g is added s times by the operation on the additive group G, and treats the obtained element as an element c 0 . Using the RAM 914 , the first cipher element calculation unit 454 C stores data representing the calculated element c 0 .

Using the CPU 911 , the second cipher element calculation unit 455 C inputs the data representing the additive group G, hash function H, element g 1 , and element g 3 among the encryption parameters stored by the encryption parameter storage unit 490 C, the bit string ID stored by the identifier storage unit 410 C, and the data representing the secret random number s and stored by the secret random number generating unit 451 C. Using the CPU 911 and based on the hash function H represented by the input data and the input bit string ID, the second cipher element calculation unit 455 C calculates a hash value H(ID) which is obtained when the bit string ID is hashed by the hash function H. The hash value H(ID) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 and based on the additive group G, element g 1 , element g 3 , and secret random number s represented by the input data and the calculated hash value H(ID), the second cipher element calculation unit 455 C calculates an element as the sum of an element which is obtained when the element g 1 is added a number of times H(ID)·s which is the product of the hash value H(ID) and secret random number s, and an element which is obtained when the element g 3 is added s times, and treats the obtained element as an element c 1 . Using the RAM 914 , the second cipher element calculation unit 455 C stores data representing the calculated element c 1 .

Since g 1 =α·g and g 3 =γ·g, the element c 1 calculated by the second cipher element calculation unit 455 C is expressed as:

Using the CPU 911 , the cipher integer calculation unit 456 C inputs the data representing the order p and hash function H″ among the encryption parameters stored by the encryption parameter storage unit 490 C, the data representing the secret random number s and stored by the secret random number generating unit 4510 , the data representing the element k and stored by the pairing value calculation unit 452 C, the bit string c stored by the cipher bit string calculation unit 453 C, the data representing the element c 0 and stored by the first cipher element calculation unit 454 C, and the data representing the element c 1 and stored by the second cipher element calculation unit 455 C. Using the CPU 911 and based on the hash function H″, element k, element c 0 , and element c 1 represented by the input data, and the input bit string c, the cipher integer calculation unit 456 C calculates a hash value H″(k,c,c 0 ,c 1 ) which is obtained when the element k, the bit string c, and the ordered pair of the element c 0 and element c 1 are hashed by the hash function H″. The hash value H″(k,c,c 0 ,c 1 ) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 and based on the order p and secret random number s represented by the input data and the calculated hash value H″(k,c,c 0 ,c 1 ), the cipher integer calculation unit 456 C calculates the remainder which is obtained when the sum of the secret random number s and hash value H″(k,c,c 0 ,c 1 ) is divided by the order p, and treats the obtained remainder as an integer t. Using the CPU 911 , the cipher integer calculation unit 456 C stores data representing the calculated integer t.

Using the CPU 911 , the ciphertext output unit 470 C inputs the bit string c stored by the cipher bit string calculation unit 453 C, the data representing the element c 0 and stored by the first cipher element calculation unit 454 C, the data representing the element c 1 and stored by the second cipher element calculation unit 455 C, and the data representing the integer t and stored by the cipher integer calculation unit 456 C. Using the CPU 911 , the ciphertext output unit 470 C generates the ciphertext C including the input bit string c and the input data representing the element c 0 , element c 1 , and integer t. Using the CPU 911 , the ciphertext output unit 470 C outputs the generated ciphertext C.

The ciphertext C output by the ciphertext output unit 470 C is transmitted to the ciphertext decryption apparatus 200 C.

FIG. 25 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 C of this embodiment.

The ciphertext decryption apparatus 200 C has an encryption parameter storage unit 290 C, a key storage unit 210 C, a ciphertext input unit 220 C, a ciphertext verification unit 230 C, a verification apparatus 100 C, a decrypted text generating unit 260 C, and a decrypted message output unit 283 C.

Using the magnetic disk drive 920 , the encryption parameter storage unit 290 C stores data representing the public encryption parameters in advance.

In secret, using the tamper-resistant storage device, the key storage unit 210 C stores the secret key generated by the key generating apparatus 300 C in advance.

Using the CPU 911 , the ciphertext input unit 220 C inputs the ciphertext C received from the ciphertext generating apparatus 400 C. Using the CPU 911 and based on the input ciphertext C, the ciphertext input unit 220 C acquires the bit string c, and the data representing the element c 0 , element c 1 , and integer t. Using the RAM 914 , the ciphertext input unit 220 C stores the acquired bit string c, and the data representing the element c 0 , element c 1 , and integer t.

Based on the encryption parameters stored by the encryption parameter storage unit 290 C, the secret key stored by the key storage unit 210 C, and the ciphertext C input by the ciphertext input unit 220 C, the ciphertext verification unit 230 C generates data to be input to the verification apparatus 100 C.

The ciphertext verification unit 230 C has a pairing value calculation unit 231 C and an integer calculation unit 232 C.

Using the CPU 911 , the pairing value calculation unit 231 C inputs the data representing the multiplicative group G t and pairing e among the encryption parameters stored by the encryption parameter storage unit 290 C, the data representing the secret element d 0 and secret element d 1 of the secret key stored by the key storage unit 210 C, and the data representing the element c 0 and element c 1 and stored by the ciphertext input unit 220 C. Using the CPU 911 and based on the pairing e, element c 0 , and secret element d 0 represented by the input data, the pairing value calculation unit 231 C calculates the pairing value of the element c 0 and secret element d 0 by the pairing e, and treats the calculated value as a pairing value k 0 . The pairing value k 0 is an element of the multiplicative group G t . Using the CPU 911 and based on the pairing e, element c 1 , and secret element d 1 represented by the input data, the pairing value calculation unit 231 C calculates the pairing value of the element c 1 and secret element d 1 by the pairing e, and treats the calculated value as a pairing value k 1 . The pairing value k 1 is an element of the multiplicative group G t . Using the CPU 911 and based on the multiplicative group G t represented by the input data and the calculated pairing value k 0 and pairing value k 1 , the pairing value calculation unit 231 C calculates an element which is obtained when the pairing value k 0 is multiplied by the inverse element of the pairing value k 1 , and treats the obtained element as an element k. The pairing value calculation unit 231 C stores data representing the calculated element k.

From the bilinearity of the pairing e, the element k calculated by the pairing value calculation unit 231 C is expressed as:

Using the CPU 911 , the integer calculation unit 232 C inputs the data representing the order p and hash function H″ among the encryption parameters stored by the encryption parameter storage unit 290 C, the data representing the bit string c, element c 0 , element c 1 , and integer t stored by the ciphertext input unit 220 C, and the data representing the element k and stored by the pairing value calculation unit 231 C. Using the CPU 911 and based on the hash function H″, bit string c, element c 0 , and element c 1 represented by the input data and the input element k, the integer calculation unit 232 C calculates a hash value H″(k,c,c 0 ,c 1 ) which is obtained when the element k, the bit string c, and the ordered pair of the element c 0 and element c 1 are hashed by the hash function H″. The hash value H″(k,c,c 0 ,c 1 ) is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 and based on the order p and integer t represented by the input data and the calculated hash value H″(k,c,c 0 ,c 1 ), the integer calculation unit 232 C calculates the remainder which is obtained when the integer obtained by subtracting the hash value H″(k,c,c 0 ,c 1 ) from the integer t is divided by the order p, and treats the calculated remainder as an integer s.

If the element k calculated by the pairing value calculation unit 231 C is equal to the element k calculated by the pairing value calculation unit 452 C, then the integer s calculated by the integer calculation unit 232 C is equal to the secret random number s generated by the secret random number generating unit 451 C.

The verification apparatus 100 C checks whether k=v 0 s and c 0 =s·g, and determines that the verification is successful when both k=v 0 s and c 0 =s·g are established.

The verification apparatus 100 C outputs data expressing the verification result.

Using the CPU 911 , the decrypted text generating unit 260 C inputs the data representing the verification result output by the verification apparatus 100 C. When the verification result expressed by the input data indicates that “the verification is successful”, the decrypted text generating unit 260 C, using the CPU 911 , inputs the data representing the hash function H′ among the encryption parameter stored by the encryption parameter storage unit 290 C, the bit string c stored by the ciphertext input unit 220 C, and the data representing the element k and stored by the pairing value calculation unit 231 C. Using the CPU 911 and based on the hash function H′ and element k represented by the input data, the decrypted text generating unit 260 C calculates a hash value H′(k) which is obtained when the element k is hashed by the hash function H′. The hash value H′(k) is a bit string having a predetermined length. Using the CPU 911 and based on the input bit string c and the calculated hash value H′(k), the decrypted text generating unit 260 C obtains the bitwise exclusive OR of the bit string c and the hash value H′(k), and treats the result as a bit string M′. Using the RAM 914 , the decrypted text generating unit 260 C stores the calculated bit string M′.

If the ciphertext c input by the ciphertext input unit 220 C is a correct ciphertext, the element k calculated by the pairing value calculation unit 231 C is equal to the element k calculated by the pairing value calculation unit 452 C of the ciphertext generating apparatus 400 A. Hence, the bit string M′ calculated by the decrypted text generating unit 260 C is equal to the bit string M input by the message input unit 440 C of the ciphertext generating apparatus 400 C.

Using the CPU 911 , the decrypted message output unit 283 C inputs the bit string M′ stored by the decrypted text generating unit 260 C. Using the CPU 911 , the decrypted message output unit 283 C outputs the input bit string M′ as the decrypted message.

FIG. 26 is a detailed block diagram showing a configuration example of the internal block of the verification apparatus 100 C of this embodiment.

The verification apparatus 100 C has an integer partitioning unit 110 C, two verification value calculation units 130 C 1 and 130 C 2 , and a verification judging unit 150 C. The verification apparatus 100 C is an apparatus corresponding to the verification apparatus 100 described in the first embodiment, but has the two verification value calculation units 130 C 1 and 130 C 2 in order to perform the operation on the additive group G and the operation on the multiplicative group G t .

Using the CPU 911 , the integer partitioning unit 110 C inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 C, as data representing the order p described in the first embodiment.

Using the CPU 911 , the integer partitioning unit 110 C inputs the data representing the integer s and stored by the integer calculation unit 232 C, as data representing the integer e described in the first embodiment. Using the CPU 911 and based on the order p and integer s represented by the input data, the integer partitioning unit 110 C calculates an integer e 1 and an integer e 2 that satisfy e 1 ·s≡e 2 (mod p), |e 1 |<√p, and 0<e 2 <√p. Using the RAM 914 , the integer partitioning unit 110 C stores data representing the calculated integer e 1 and integer e 2 .

The verification value calculation unit 130 C 1 calculates an element a=e 1 ·c 0 −e 2 ·g of the additive group G by the operation on the additive group G.

Using the CPU 911 , the verification value calculation unit 130 C 1 inputs the data representing the element g among the encryption parameters stored by the encryption parameter storage unit 290 C, as data representing the element s described in the first embodiment. Using the CPU 911 , the verification value calculation unit 130 C 1 inputs the data representing the element c 0 and stored by the ciphertext input unit 220 C, as data representing the element h described in the first embodiment. Using the CPU 911 , the verification value calculation unit 130 C 1 inputs the data representing the integer e 1 and integer e 2 and stored by the integer partitioning unit 110 C. Using the CPU 911 and based on the element g, element c 0 , integer e 1 , and integer e 2 represented by the input data, the verification value calculation unit 130 C 1 calculates an element obtained by adding an element obtained when the element c 0 is added e 1 times and the inverse element of an element obtained when the element g is added e 2 times, by the operation on the additive group G, and treats the obtained element as the element a . Using the RAM 914 , the verification value calculation unit 130 C 1 stores data representing the calculated element a .

The verification value calculation unit 130 C 2 calculates an element a′=k e1 ·v 0 −e2 of the multiplicative group G t by the operation on the multiplicative group G t . When this operation on the multiplicative group G t is described additively, then a′=e 1 ·k−e 2 ·v 0 . Hence, except for the difference in the practical calculation method of the group operation, the process performed by the verification value calculation unit 130 C 2 is substantially identical to the process performed by the verification value calculation unit 130 C 1 .

Using the CPU 911 , the verification value calculation unit 130 C 2 inputs the data representing the element v 0 among the encryption parameters stored by the encryption parameter storage unit 290 C, as data representing the element s described in the first embodiment.

Using the CPU 911 , the verification value calculation unit 130 C 2 inputs the data representing the element k and stored by the pairing value calculation unit 231 C, as data representing the element h described in the first embodiment. Using the CPU 911 , the verification value calculation unit 130 C 2 inputs the data representing the integer e 1 and integer e 2 and stored by the integer partitioning unit 110 C. Using the CPU 911 and based on the element v 0 , element k, integer e 1 , and integer e 2 represented by the input data, the verification value calculation unit 130 C 2 calculates an element obtained by adding an element obtained when the element k is multiplied e 1 times and the inverse element of an element obtained when the element v 0 is multiplied e 2 times, by the operation on the multiplicative group G t , and treats the obtained element as the element a′. Using the RAM 914 , the verification value calculation unit 130 C 2 stores data representing the calculated element a′.

Using the CPU 911 , the verification judging unit 150 C inputs the data representing the element a and stored by the verification value calculation unit 130 C 1 , and the data representing the element a′ and stored by the verification value calculation unit 130 C 2 . Using the CPU 911 and based on the element a represented by the input data, the verification judging unit 150 C judges whether or not the element a is the identity element of the additive group G. If the element a is the identity element of the additive group G, then c 0 =s·g. Thus, using the CPU 911 , the verification judging unit 150 C judges that the first verification is successful. Using the CPU 911 and based on the element a′ represented by the input data, the verification value calculation unit 130 C 2 judges whether or not the element a′ is the identity element of the multiplicative group G t . If the element a′ is the identity element of the multiplicative group G t , then k=v 0 s . Thus, using the CPU 911 , the verification judging unit 150 C judges that the second verification is successful. When it is judged that the first verification is successful and then the second verification is successful, the verification judging unit 150 C judges that “the verification is successful”. Otherwise, the verification judging unit 150 C judges that “the verification fails”.

Using the CPU 911 , the verification judging unit 150 C outputs data representing the verification result.

FIG. 27 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 C according to this embodiment to decrypt the ciphertext C.

In a pairing value calculation step S 731 C, using the CPU 911 and based on the secret element d 0 stored by the key storage unit 210 C and the element c 0 input by the ciphertext input unit 220 C, the pairing value calculation unit 231 C calculates the pairing value k 0 =e(d 0 ,d 0 ) of the element c 0 and element d 0 by the pairing e. Using the CPU 911 and based on the secret element d 1 stored by the key storage unit 210 C and the element c 1 input by the ciphertext input unit 220 C, the pairing value calculation unit 231 C calculates the pairing value k 1 =e(c 1 ,d 1 ) of the element c 1 and element d 1 by the pairing e. Using the CPU 911 and based on the calculated pairing value k 0 and pairing value k 1 , the pairing value calculation unit 231 C calculates the element k=k 0 /k 1 , which is obtained by multiplying the pairing value k 0 by the inverse element of the pairing value k 1 by the operation on the multiplicative group G t .

In an integer calculation step S 732 C, using the CPU 911 and based on the bit string c, element c 0 , and element c 1 input by the ciphertext input unit 220 C and the element k calculated by the pairing value calculation unit 231 C in the pairing value calculation step S 731 C, the integer calculation unit 232 C calculates the hash value H″(k,c,c 0 ,c 1 ) which is obtained when the element k, the bit string c, and the ordered pair of the element c 0 and element c 1 are hashed by the hash function H″. Using the CPU 911 and based on the order p stored by the encryption parameter storage unit 290 C, the integer t input by the ciphertext input unit 220 , and the calculated hash value H″(k,c,c 0 ,c 1 ), the integer calculation unit 232 C calculates the remainder which is obtained when the integer obtained by subtracting the hash value H″(k,c,c 0 ,c 1 ) from the integer t is divided by the order p, and treats the calculated remainder as the integer s.

In an integer partitioning step S 733 C, using the CPU 911 and based on the order p stored by the encryption parameter storage unit 290 C and the integer s calculated by the integer calculation unit 232 C in the integer calculation step S 732 , the integer partitioning unit 110 C calculates the integer e 1 and the integer e 2 that satisfy e 1 ·s≡e 2 (mod p), |e 1 <√p, and 0<e 2 <√p.

In a first verification step S 734 C, using the CPU 911 and based on the element g stored by the encryption parameter storage unit 290 C, the element c 0 input by the ciphertext input unit 220 C, and the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 C in the integer partitioning step S 733 C, the verification value calculation unit 130 C 1 calculates the element which is the sum of the element obtained when the element c 0 is added e 1 times and the inverse element of the element obtained when the element g is added e 2 times, by the operation on the additive group G, and treats the obtained element as the element a .

Using the CPU 911 and based on the element a calculated by the verification value calculation unit 130 C 1 , the verification judging unit 150 C judges whether or not the element a is the identity element of the additive group G. If the element a is the identity element of the additive group G (i.e. , c 0 =s·g), the flow advances to a second verification step S 735 C. If the element a is not the identity element of the additive group G (i.e. , c 0 ≠s·g), the ciphertext decryption process is ended.

In the second verification step S 735 C, using the CPU 911 and based on the element v 0 stored by the encryption parameter storage unit 290 C, the element k calculated by the pairing value calculation unit 231 C in the pairing calculation step S 731 C, and the integer e 1 and integer e 2 calculated by the integer partitioning unit 110 C in the integer partitioning step S 733 C, the verification value calculation unit 130 C 2 calculates the element obtained by multiplying the element which is obtained when the element k is multiplied e 1 times, and the inverse element of the element which is obtained when the element v 0 is multiplied e 2 times, by the operation on the multiplicative group G t , and treats the obtained element as the element a′.

Using the CPU 911 and based on the element a′ calculated by the verification value calculation unit 130 C 2 , the verification judging unit 150 C judges whether or not the element a′ is the identity element of the multiplicative group G t . If the element a′ is the identity element of the multiplicative group G t (i.e., k=v 0 s ), the flow advances to a decrypted text generating step S 736 C. If the element a′ is not the identity element of the multiplicative group G t (i.e., k≠v 0 s ), the ciphertext decryption process is ended.

In the decrypted text generating step S 736 C, using the CPU 911 and based on the element k calculated by the pairing value calculation unit 231 C in the pairing value calculation step S 731 , the decrypted text generating unit 260 C calculates the hash value H′(k) which is obtained when the element k is hashed by the hash function H′. Using the CPU 911 and based on the input bit string c input by the ciphertext input unit 220 C and the calculated hash value H′(k), the decrypted text generating unit 260 C obtains the bitwise exclusive OR of the bit string c and the hash value H′(k), and treats the result as the bit string M′.

Using the CPU 911 , the decrypted message output unit 283 C outputs the bit string M′ calculated by the decrypted text generating unit 260 C, as the decrypted message. Then, the ciphertext decryption process is ended.

In this example, first, whether c 0 =s·g is verified first, and after that whether k=v 0 s is verified. However, this verification order maybe reversed. Alternatively, the verification value calculation unit 130 C 1 and verification value calculation unit 130 C 2 may calculate the element a and element a′ simultaneously in a parallel manner.

The ciphertext decryption apparatus 200 C of this embodiment further has the encryption parameter storage unit 290 C.

Using the storage device (magnetic disk drive 920 ), the encryption parameter storage unit 290 C stores an order p of the additive group G 1 (additive group G), a generator g of the additive group G 1 (additive group G), and the element v 0 of the multiplicative group G t whose order is the order p. Using the storage device, the key storage unit 210 C stores an element (secret element) d 0 of an additive group G 2 (additive group G′) whose order is the order p, and an element (secret element) d 1 of the additive group G 2 (additive group G′). Using the processing device (CPU 911 ), the ciphertext input unit 220 C inputs the bit string c, an element c 0 of the additive group G 1 , an element c 1 of the additive group G 1 , and an integer t equal to or larger than 1 and equal to or smaller than p−1, as the ciphertext C. The ciphertext verification unit 230 C has the pairing value calculation unit 231 C and the integer calculation unit 232 C. Using the processing device (CPU 911 ) and based on the element c 0 input by the ciphertext input unit 220 and the element (secret element) d 0 stored by the key storage unit 210 C, the pairing value calculation unit 231 C calculates the pairing value of the element c 0 and element (secret element) d 0 by the predetermined pairing function e, and treats the calculated value as the element k 0 (=e(c 0 ,d 0 )) of the multiplicative group G t . Using the processing device (CPU 911 ) and based on the element c 1 input by the ciphertext input unit 220 C and the element d 1 stored by the key storage unit 210 C, the pairing value calculation unit 231 C calculates the pairing value of the element c 1 and element d 1 by the pairing function e, and treats the calculated value as the element k 1 (=e(c 1 ,d 1 )) of the multiplicative group G T . Using the processing device (CPU 911 ) and based on the calculated element k 0 and the calculated element k 1 , the pairing value calculation unit 231 C multiplies the element k 0 by the inverse element of the element k 1 , and treats the obtained element as the element k (=k 0 /k 1 ) of the multiplicative group G t . Using the processing device (CPU 911 ) and based on the element k calculated by the pairing value calculation unit 231 C, and the bit string c, element c 0 , and element c 1 input by the ciphertext input unit 220 C, the integer calculation unit 232 C calculates the hash value which is obtained when the element k, bit string c, element c 0 , and element c 1 are hashed by the predetermined hash function H″, and treats the calculated value as the integer (hash value) H″(k,c,c 0 ,c 1 ). Using the processing device (CPU 911 ) and based on the integer t input by the ciphertext input unit 220 C, the calculated integer H″(k,c,c 0 ,c 1 ), and the order p stored by the encryption parameter storage unit 290 C, the integer calculation unit 232 C calculates the remainder which is obtained when the integer obtained by subtracting the integer H″(k,c,c 0 ,c 1 ) from the integer t is divided by the order p, and treats the calculated remainder as the integer s (=t−H″(k,c,c 0 ,c 1 ) mod p). The verification apparatus 100 C treats the additive group G 1 (additive group G) as the finite group G, and inputs the order p stored by the encryption parameter storage unit 290 C, as the order p, the integer s calculated by the integer calculation unit 232 C, as the integer e, the generator g stored by the encryption parameter storage unit 290 C, as the element s, and the element c 0 input by the ciphertext input unit 220 C, as the element h. The verification apparatus 100 C judges whether or not the verification is successful, and treats the result as the first verification result. The verification apparatus 100 C treats the multiplicative group G t as the finite group G, and inputs the order p stored by the encryption parameter storage unit 290 C, as the order p, the integer s calculated by the integer calculation unit 232 C, as the integer e, the element v 0 stored by the encryption parameter storage unit 290 C, as the element s, and the element k calculated by the pairing value calculation unit 231 C, as the element h. The verification apparatus 1000 judges whether or not the verification is successful, and treats the result as the second verification result. When both the first verification result and the second verification result show that the verification apparatus 100 C judges the verification successful, using the processing device (CPU 911 ) and based on the element k calculated by the pairing value calculation unit 231 C, the decrypted text generating unit 260 C calculates the hash value which is obtained when the element k is hashed by the hash function H′, and treats the calculated value as the bit string H′(k). Using the processing device (CPU 911 ) and based on the bit string c input by the ciphertext input unit 220 C and the calculated bit string H′(k), the decrypted text generating unit 260 C obtains the exclusive OR of the bit string c and the hash value H′(k), and treats the result as the bit string M′(=c XOR H′(k)). The decrypted text generating unit 260 C outputs the calculated bit string M′ as the decrypted text.

According to the ciphertext decryption apparatus 200 C of this embodiment, when the verification apparatus 100 C verifies whether c 0 =s·g and k=v 0 s and judges that the verification is successful, the decrypted text generating unit 260 C generates a decrypted text. This can prevent any clue to decipher the ciphertext from being given to an unauthorized person. Since the time necessary for the verification apparatus 100 C to verify whether c 0 =s·g and k=v 0 s can be shortened, the time necessary for the ciphertext decryption apparatus 200 C to perform the entire process of decrypting the ciphertext can be shortened.

The ciphertext decryption apparatus 200 C described so far is a BB(Boneh-Boyen)1-ID-based cryptography decryption apparatus.

The ciphertext decryption apparatus 200 C inputs the secret key d ID =(d 0 ,d 1 ) and the ciphertext C=(c,c 0 ,c 1 ,t) and has a calculation device (pairing value calculation unit 231 C) which calculates the ratio k=e (c 0 ,d 0 )/e(c 1 ,d 1 ) of the pairing values, a calculation device (integer calculation unit 232 C) which calculates the integer s=t−H″(k,c,c 0 ,c 1 ), a device (integer partitioning unit 110 C) which partitions the exponential part (integer) s, a device (verification value calculation unit 130 c 2 ) which calculates, using the partitioned exponents (integer e 1 and integer e 2 ), the value k e1 ·v 0 −e2 by the double-base exponentiation on the multiplicative group G T , and a device (verification judging unit 150 C) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group G T .

The ciphertext decryption apparatus 200 C described so far is a key decapsulation apparatus in a BB1-ID-based cryptographic system (ID-based public key cryptographic system 820 C).

The ciphertext decryption apparatus 2000 (BB1-ID-based cipher key decapsulation apparatus) inputs the secret key d ID =(d 0 ,d 1 ) and the ciphertext C=(c,c 0 ,c 1 ,t) and has

a calculation device (pairing value calculation unit 231 C) which calculates the ratio k=e (c 0 ,d 0 )/e(c 1 ,d1) of the pairing values, a calculation device (integer calculation unit 232 C) which calculates the integer s=t−H″(k,c,c 0 ,c 1 ), a device (integer partitioning unit 110 C) which partitions the exponential part (integer) s, a device (verification value calculation unit 130 C 2 ) which calculates, using the partitioned exponents (integer e 1 and integer e 2 ), the value k e1 ·v o −e2 by the double-base exponentiation on the multiplicative group G T , and a device (verification judging unit 150 C) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group G T .

The ciphertext decryption apparatus 200 C (BB1-ID-based cryptographic decryption apparatus) described so far inputs the secret key d ID =(d 0 ,d 1 ) and the ciphertext C=(c,c 0 ,c 1 ,t) and has

a calculation device (pairing value calculation unit 231 C) which calculates the ratio k=e (c 0 ,d 0 )/e(c 1 ,d 1 ) of the pairing values, a calculation device (integer calculation unit 232 C) which calculates the integer s=t−H″(k,c,c 0 ,c 1 ), a device (integer partitioning unit 110 C) which partitions the exponential part (integer) s, a device (verification value calculation unit 130 C 2 ) which calculates, using the partitioned exponents (integer e 1 and integer e 2 ), the value k e1 ·v 0 −e2 by the double-base exponentiation on the multiplicative group G T , and a device (verification judging unit 150 C) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group G T .

The ciphertext decryption apparatus 200 C (BB1-ID-based cipher key decapsulation apparatus) described so far inputs the secret key d ID =(d 0 ,d 1 ) and the ciphertext C=(c,c 0 ,c 1 ,t) and has

a calculation device (pairing value calculation unit 231 C) which calculates the ratio k=e(c 0 ,d 0 )/e(c 1 ,d 1 ) of the pairing values, a calculation device (integer calculation unit 232 C) which calculates the integer s=t−H″(k,c,c 0 ,c 1 ), a device (integer partitioning unit 110 C) which partitions the exponential part (integer) s, a device (verification value calculation unit 130 C 1 ) which calculates, using the partitioned exponents (integer e 1 and integer e 2 ), a value (e 1 ·c 0 −e 2 ·g) by the double-base scalar multiplication on the additive group G of, e.g., elements formed of points on a (hyper) elliptic curve, and a device (verification judging unit 150 C) which judges whether or not the calculated value is equal to the identity element 0 of the additive group G.

The ID-based public key cryptographic system 820 C described so far is an BB1-ID-based cryptographic system.

The ID-based public key cryptographic system 820 C employs the additive group G, the additive group G′, and the multiplicative group G t which have an order p being a prime number, the generator g of the additive group G, the generator g′ of the additive group G′, and the pairing e. The encryption parameter setting apparatus 810 C performs a set-up process (Setup). Using the CPU 911 , the encryption parameter setting apparatus 810 C generates the random integer α, integer β, and integer γ each equal to or larger than 1 and equal to or smaller than p−1, and calculates the element g 1 =α·g of the group G, the element g 2 =β·g of the group G, and the element g 3 =γ·g of the group G. Using the CPU 911 , the encryption parameter setting apparatus 810 C calculates the element g′ 1 =α·g′ of the group G′, the element g′ 2 =β·g′ of the group G′, and the element g′ 3 =γ·g′ of the group G′. Using the CPU 911 , the encryption parameter setting apparatus 810 C calculates the element g′ 0 =(α·β)·g′ of the group G′, and the pairing value v 0 =e(g,g′ 0 ) (that is, v 0 =e(g,g′) α·β ) of the multiplicative group G t . The encryption parameter setting apparatus 810 C outputs (g, g 1 , g 3 , v 0 ) as the public key of PKG, and (g′,α,β,γ) as the secret key of PKG. The key generating apparatus 300 C performs a secret key extraction process (Extract). Using the CPU 911 , the key generating apparatus 300 C inputs the bit string ID which identifies the ciphertext decryption apparatus 200 C, and generates the random integer (secret random number) r equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the key generating apparatus 300 C calculates the integer e=α·β+(α·H(ID)+γ)·r, the element d 0 =e·g′ of the group G′, and the element d 1 =r·g′ of the group G′, and outputs (d 0 ,d 1 ) as the secret key d ID for the ID. The ciphertext generating apparatus 400 C performs an encryption process (Encrypt). Using the CPU 911 , the ciphertext generating apparatus 400 C inputs the plaintext M and the recipient ID (the bit string ID which identifies the ciphertext decryption apparatus 200 C). Using the CPU 911 , the ciphertext generating apparatus 400 C generates the random integer (secret random number) s equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the ciphertext generating apparatus 400 C calculates the element k=v 0 s of G t . Using the CPU 911 , the ciphertext generating apparatus 400 C calculates the bit string c=XOR (M,H′(k)), the element c 0 =s·g of the group G, the element c 1 =s·g 3 +(H(ID)·g 1 of the group G, and the integer t=s+H″(k,c,c 0 ,c 1 ) by the hash functions H, H′, and H″. Using the CPU 911 , the ciphertext generating apparatus 400 C outputs the ciphertext C=(c,c 0 ,c 1 ,t). The ciphertext decryption apparatus 200 C performs a decryption process (Decrypt). Using the CPU 911 , the ciphertext decryption apparatus 200 C inputs the secret key d ID =(d 0 ,d 1 ) and the ciphertext C=(c,c 0 ,c 1 ,t). Using the CPU 911 , the ciphertext decryption apparatus 200 C calculates the element k=e(c 0 ,d 0 )/e(c 1 ,d 1 ) of the multiplicative group G t , and the integer s=t−H″(k,c,c 0 ,c 1 ), and checks whether or not k=v 0 s and c 0 =s·g are established. If No, using the CPU 911 , the ciphertext decryption apparatus 200 C outputs “reject”. If Yes, using the CPU 911 , the ciphertext decryption apparatus 200 C calculates bit string M=XOR(c,H″(k)) and outputs it.

The verification apparatus 100 C described above speeds up the process of checking whether or not k=v 0 s and c 0 =s·g are established in this BB1-ID-based cryptographic system.

In the verification apparatus 100 C, the integer partitioning unit 110 C, using the CPU 911 , inputs s and p, and calculates the integer e 1 and integer e 2 that satisfy e 1 ·s≡e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 C 2 calculates v 1 =k e1 ·v 0 −s2 by the double-base exponentiation on the multiplicative group G t . Using the CPU 911 , the verification judging unit 150 C checks whether or not v 1 =1, thereby checking at high speed whether or not k=v 0 s is established.

If v 1 =1 is established, using the CPU 911 , the verification value calculation unit 130 C 1 calculates W=e 1 ·c 0 −e 0 ·g by the double-base scalar multiplication on the additive group G. Using the CPU 911 , the verification judging unit 150 C checks whether or not W=0, thereby checking at high speed whether or not c 0 =s·g is established.

The fifth embodiment will be described with reference to FIGS. 28 to 33 .

FIG. 28 shows an example of the entire system configuration of an ID-based signature system 820 D of this embodiment.

The ID-based signature system 820 D is a digital signature system which uses the identification data that identifies a signature apparatus 400 D, as the public key of the signature apparatus 400 D.

The ID-based signature system 820 D has an encryption parameter setting apparatus 810 D, a key generating apparatus 300 D, the signature apparatus 400 D, and a signature verification apparatus 200 D.

The encryption parameter setting apparatus 810 D determines encryption parameters to be used in the ID-based signature system 820 D. The encryption parameters determined by the encryption parameter setting apparatus 810 D are open to the user of the ID-based signature system 820 D. The encryption parameters determined by the encryption parameter setting apparatus 810 C include, e.g., an order p, an additive group G, an element g of the additive group G, a hash function H, and a hash function H′.

The order p is a prime number. The order of the additive group G is p. The element g is the generator of the additive group G. The hash function H is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from the set of an element of the additive group G and a bit string having an arbitrary length. The hash function H′ is a hash function that generates an integer equal to or larger than 1 and equal to or smaller than p−1 from the set of the ordered pair of two arbitrary-length bit strings and the ordered pair of three elements of the additive group G.

When these encryption parameters are determined in advance, the encryption parameter setting apparatus 810 D need not determine them.

The encryption parameter setting apparatus 810 D generates a master key and public parameters generated based on the master key. The master key generated by the encryption parameter setting apparatus 810 D includes an integer x equal to or larger than 1 and equal to or smaller than p−1. The master key generated by the encryption parameter setting apparatus 810 D is notified to the key generating apparatus 300 D in secret. The public parameters generated by the encryption parameter setting apparatus 810 D include an element X of the additive group G. The public parameters generated by the encryption parameter setting apparatus 810 D are open to the user of the ID-based signature system 820 D.

The key generating apparatus 300 D holds in secret the master key notified from the encryption parameter setting apparatus 810 D. Based on the public encryption parameters, the public identification data ID of the signature apparatus 400 D, and the held master key, the key generating apparatus 300 D generates the signing key of the signature apparatus 400 D. The signing key generated by the key generating apparatus 300 D includes an integer s equal to or larger than 1 and equal to or smaller than p−1, and an element R of the additive group G. The signing key generated by the key generating apparatus 300 D is notified to the signature apparatus 400 D in secret.

The signature apparatus 400 D holds in secret the signing key notified from the key generating apparatus 300 D. Based on the public encryption parameters, the public parameters, and the held signing key, the signature apparatus 400 D generates a signature σ for the message M. The signature σ guarantees that the content of the message M is not altered.

Based on the public encryption parameters, the public parameters, and the identification data ID of the signature apparatus 400 D, the signature verification apparatus 200 D verifies the signature σ attached to the message M, and judges if the message M is not altered. The signature verification apparatus 200 D outputs the verification result.

FIG. 29 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 D of this embodiment.

The encryption parameter setting apparatus 810 D has an encryption parameter storage unit 819 D, a secret random number generating unit 812 D, a public element calculation unit 813 D, a master key output unit 814 D, and a public parameter output unit 815 D.

Using a magnetic disk drive 920 , the encryption parameter storage unit 819 D stores the public encryption parameters.

Using a CPU 911 , the secret random number generating unit 812 D inputs data representing the order p among the encryption parameters stored by the encryption parameter storage unit 819 D. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 812 D randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as the secret random number x. Using a RAM 914 , the secret random number generating unit 812 D stores data representing the generated secret random number x.

Using the CPU 911 , the public element calculation unit 813 D inputs data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 819 D, and the data representing the secret random number x and stored by the secret random number generating unit 812 D. Based on the additive group G, element g, and secret random number x represented by the input data, the public element calculation unit 813 D calculates an element which is obtained when the element g is added x times by the operation on the additive group G, and treats the calculated element as a public element X. Using the RAM 914 , the public element calculation unit 813 D stores data representing the calculated public element X.

Using the CPU 911 , the master key output unit 814 D inputs the data representing the secret random number x and stored by the secret random number generating unit 812 D. Using the CPU 911 , the master key output unit 814 D outputs, as the master key, the input data representing the secret random number x.

The master key output by the master key output unit 814 D is notified to the key generating apparatus 300 D in secret.

Using the CPU 911 , the public parameter output unit 815 D inputs the data representing the public element X and stored by the public element calculation unit 813 D. Using the CPU 911 , the public parameter output unit 815 D outputs, as the public parameters, the input data representing the public element X.

The public parameters output by the public parameter output unit 815 D, together with the encryption parameters, are open to the user of the ID-based signature system 820 D.

FIG. 30 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 D of this embodiment.

The key generating apparatus 300 D has an encryption parameter storage unit 390 D, a master key storage unit 330 D, an identifier input unit 340 D, a signing key generating unit 350 D, and a signing key output unit 360 D.

Using the magnetic disk drive 920 , the encryption parameter storage unit 390 D stores the data representing the public encryption parameters in advance.

Using a tamper-resistant storage device, the master key storage unit 330 D stores the master key notified from the encryption parameter setting apparatus 810 D.

Using the CPU 911 , the identifier input unit 340 D inputs an arbitrary-length bit string ID which is identification data for identifying the ciphertext decryption apparatus 400 D whose signing key is to be generated. Using the RAM 914 , the identifier input unit 340 D stores data representing the input bit string ID.

The signing key generating unit 350 D generates the signing key of the signature apparatus 400 D based on the encryption parameters stored by the encryption parameter storage unit 390 D, the master key stored by the master key storage unit 330 D, and the bit string ID input by the identifier input unit 340 D.

The signing key generating unit 3500 has a secret random number generating unit 351 D, a key element calculation unit 352 D, and a key integer calculation unit 353 D.

Using the CPU 911 , the secret random number generating unit 351 D inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 390 D. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 351 D randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as a secret random number r. Using the RAM 914 , the secret random number generating unit 351 D stores data representing the generated secret random number r.

Using the CPU 911 , the key element calculation unit 352 D inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 390 D, and the data representing the secret random number r and stored by the secret random number generating unit 351 D. Using the CPU 911 and based on the additive group G, element g, and secret random number r represented by the input data, the key element calculation unit 352 D calculates an element r·g which is obtained when the element g is added r times by the operation on the additive group G, and treats it as the element R. Using the RAM 914 , the key element calculation unit 352 D stores data representing the calculated element R.

Using the CPU 911 , the key integer calculation unit 353 D inputs the data representing the order p and hash function H among the encryption parameters stored by the encryption parameter storage unit 390 D, the data representing the secret random number x of the master key stored by the master key storage unit 330 D, the bit string ID stored by the identifier input unit 340 D, the data representing the secret random number r and stored by the secret random number generating unit 351 D, and the data representing the public element R and calculated by the key element calculation unit 352 D. Using the CPU 911 and based on the hash function H and element R represented by the input data and the input bit string ID, the key integer calculation unit 353 D calculates a hash value H (R, ID) which is obtained when the set of the element R and bit string ID is hashed by the hash function H. Using the CPU 911 and based on the order p, secret random number x, and secret random number r represented by the input data, and the calculated hash value H (R, ID), the key integer calculation unit 353 D calculates a remainder which is obtained when the sum of the secret random number r and the product of the hash value H (R, ID) and secret random number x is divided by the order p, and treats the calculated remainder as an integer s. Using the RAM 914 , the key integer calculation unit 353 D stores data representing the calculated integer s.

Using the CPU 911 , the signing key output unit 360 D inputs the data representing the element R and stored by the key element calculation unit 352 D, and the data representing the integer s and stored by the key integer calculation unit 353 D. Using the CPU 911 , the signing key output unit 360 D outputs, as the signing key, the input data representing the integer s and element R.

The signing key output by the signing key output unit 360 D is notified to the signature apparatus 400 D in secret.

FIG. 31 is a block diagram showing a configuration example of the function block of the signature apparatus 400 D of this embodiment.

The signature apparatus 400 D has an encryption parameter storage unit 490 D, an identifier storage unit 410 D, a signing key storage unit 420 D, a message input unit 440 D, a signature generating unit 450 D, and a signature output unit 470 D.

Using the magnetic disk drive 920 , the encryption parameter storage unit 490 D stores in advance data representing the public encryption parameters.

Using the magnetic disk drive 920 , the identifier storage unit 410 D stores the bit string ID that identifies the signature apparatus 400 D itself. Using a tamper-resistant storage device, the signing key storage unit 420 D stores data representing the signing key generated by the key generating apparatus 300 D.

Using the CPU 911 , the message input unit 440 D inputs an arbitrary-length bit string M which is the message to be signed. Using the RAM 914 , the message input unit 440 D stores the input bit string M.

Based on the encryption parameters stored by the encryption parameter storage unit 490 D, the bit string ID stored by the identifier storage unit 410 D, the signing key stored by the signing key storage unit 420 D, and the bit string M input by the message input unit 440 D, the signature generating unit 450 D generates a signature σ.

The signature generating unit 450 D has a first signature element calculation unit 451 D, a secret random number generating unit 452 D, a second signature element calculation unit 453 D, a challenge calculation unit 454 D, and a signature integer calculation unit 455 D.

Using the CPU 911 , the first signature element calculation unit 451 D inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 490 D, and the data representing the integer s of the signing key stored by the signing key storage unit 420 D. Using the CPU 911 and based on the additive group G, element g, and integer s represented by the input data, the first signature element calculation unit 451 D calculates an element which is obtained when the element g is added s times by the operation on the additive group G, and treats the calculated element as an element S. Using the RAM 914 , the first signature element calculation unit 451 D stores data representing the calculated element S.

Since the element S is constant irrespective of the bit string M, the first signature element calculation unit 451 D may calculate the element S in advance before the message input unit 440 D inputs the bit string M and, using the magnetic disk drive 920 , may store the element S.

Using the CPU 911 , the secret random number generating unit 452 D inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 490 D. Using the CPU 911 and based on the order p represented by the input data, the secret random number generating unit 452 D randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as a secret random number y. Using the RAM 914 , the secret random number generating unit 452 D stores data representing the generated secret random number y.

Using the CPU 911 , the second signature element calculation unit 453 D inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 490 D, and the data representing the secret random number y and stored by the secret random number generating unit 452 D. Using the CPU 911 and based on the additive group G, element g, and secret random number y represented by the input data, the second signature element calculation unit 453 D calculates an element which is obtained when the element g is added y times by the operation on the additive group G, and treats the calculated element as an element Y. Using the RAM 914 , the second signature element calculation unit 453 D stores data representing the calculated element Y.

Using the CPU 911 , the challenge calculation unit 454 D inputs the data representing the hash function H′ among the encryption parameters stored by the encryption parameter storage unit 490 D, the bit string ID stored by the identifier storage unit 410 D, the data representing the element R of the signing key stored by the signing key storage unit 420 D, the bit string M stored by the message input unit 440 D, the data representing the element S and stored by the first signature element calculation unit 451 D, and the data representing the element Y and stored by the second signature element calculation unit 453 D. Using the CPU 911 and based on the element R, element S, and element Y represented by the input data, and the input bit string ID and bit string M, the challenge calculation unit 454 D calculates a hash value which is obtained when the set of the ordered pair of the bit string ID and bit string M and the ordered pair of the element R, element S, and element Y is hashed by the hash function H′, and treats the calculated hash value as a hash value c. The hash value cis an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the challenge calculation unit 454 D stores data representing the calculated hash value c.

Using the CPU 911 , the signature integer calculation unit 455 D inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 490 D, the data representing the integer s of the signing key stored by the signing key storage unit 420 D, the data representing the secret random number y and stored by the secret random number generating unit 452 D, and the data representing the hash value c and stored by the challenge calculation unit 454 D. Using the CPU 911 and based on the order p, integer s, secret random number y, and hash value c represented by the input data, the signature integer calculation unit 455 D calculates a remainder which is obtained when the sum of the secret random number y and the product of the hash value c and integer s is divided by the order p, and treats the calculated remainder as an integer z. Using the RAM 914 , the signature integer calculation unit 455 D stores data representing the calculated integer z.

Using the CPU 911 , the signature output unit 470 D inputs the data representing the element R of the signing key stored by the signing key storage unit 420 D, the data representing the element S and stored by the first signature element calculation unit 451 D, the data representing the element Y and stored by the second signature element calculation unit 453 D, and the data representing the integer z and stored by the signature integer calculation unit 455 D. Using the CPU 911 and based on the input data, the signature output unit 470 D generates the signature σ including the input data representing the element R, element S, element Y, and integer z. Using the CPU 911 , the signature output unit 470 D outputs the generated signature σ.

FIG. 32 is a block diagram showing a configuration example of the function block of the signature verification apparatus 200 D of this embodiment.

The signature verification apparatus 200 D has an encryption parameter storage unit 290 D, an identifier storage unit 210 D, a message input unit 225 D, a signature input unit 220 D, a signature verification unit 230 D, a verification apparatus 100 D, and a verification result output unit 260 D.

Using the magnetic disk drive 920 , the encryption parameter storage unit 290 D stores in advance data representing the public encryption parameters (including the public parameters).

Using the magnetic disk drive 920 , the identifier storage unit 210 D stores the bit string ID that identifies the signature apparatus 400 D.

Using the CPU 911 , the message input unit 225 D inputs a bit string M which is a message attached with the signature σ. Using the RAM 914 , the message input unit 225 D stores the input bit string M.

Using the CPU 911 , the signature input unit 220 D inputs the signature σ attached to the bit string M input by the message input unit 225 D. Using the CPU 911 , the signature input unit 220 D acquires data representing the element R, element S, element Y, and integer z from the input signature σ. Using the RAM 914 , the signature input unit 220 D stores the acquired data representing the element R, element S, element Y, and integer z.

The signature verification unit 230 D has a challenge calculation unit 231 D, an integer calculation unit 232 D, a verification element calculation unit 233 D, and a first verification unit 250 D.

Using the CPU 911 , the challenge calculation unit 231 D inputs the data representing the hash function H′ and stored by the encryption parameter storage unit 290 D, the bit string ID which identifies the signature apparatus 400 D and is stored by the identifier storage unit 210 D, the data representing the element R, element S, and element Y and stored by the signature input unit 220 D, and the bit string M stored by the message input unit 225 D. Using the CPU 911 and based on the hash function H′, element R, element S, and element Y represented by the input data, and the input bit string ID and bit string M, the challenge calculation unit 231 D calculates a hash value which is obtained when the set of the ordered pair of the bit string ID and bit string M and the ordered pair of the element R, element S, and element Y is hashed by the hash function H′, and treats the calculated hash value as a hash value c. The hash value c is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the RAM 914 , the challenge calculation unit 231 D stores data representing the calculated hash value c.

If the bit string M is not altered, the hash value c calculated by the challenge calculation unit 231 D is equal to the hash value c calculated by the challenge calculation unit 454 D of the signature apparatus 400 D.

Using the CPU 911 , the integer calculation unit 232 D inputs the data representing the hash function H among the encryption parameters stored by the encryption parameter storage unit 290 D, the bit string ID which identifies the signature apparatus 400 D and is stored by the identifier storage unit 210 D, and the data representing the element R and stored by the signature input unit 220 D. Using the CPU 911 and based on the hash function H and element R represented by the input data and the input bit string ID, the integer calculation unit 232 D calculates a hash value which is obtained when the set of the element R and bit string ID is hashed by the hash function H, and treats the calculated hash value as a hash value h. The hash value h is an integer equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the integer calculation unit 232 D stores data representing the calculated hash value h.

Using the CPU 911 , the verification element calculation unit 233 D inputs the data representing the additive group G among the encryption parameters stored by the encryption parameter storage unit 290 D, and the data representing the element R and element S and stored by the signature input unit 220 D. Using the CPU 911 and based on the additive group G, element R, and element S represented by the input data, the verification element calculation unit 233 D calculates an element which is obtained by adding the element S and the inverse element of the element S by the operation on the additive group G, and treats the calculated element as an element R′. Using the RAM 914 , the verification element calculation unit 233 D stores data representing the calculated element R′.

The first verification unit 250 D verifies if z·g=Y+c·S.

Using the CPU 911 , the first verification unit 250 D inputs the data representing the additive group G and element g among the encryption parameters stored by the encryption parameter storage unit 290 D, the data representing the element S, element Y, and integer z and stored by the signature input unit 220 D, and the data representing the hash value c and stored by the challenge calculation unit 231 D. Using the CPU 911 and based on the additive group G, element g, element S, element Y, integer z, and hash value c represented by the input data, the first verification unit 250 D judges whether or not the element Y+c·S obtained by adding the element Y and an element which is obtained by adding c times the element S is equal to the element z·g which is obtained by adding z times the element g. Using the CPU 911 , the first verification unit 250 D judges that “the verification is successful” when the element z·g and the element Y+c·S are equal, and that “the verification fails” when the element z·g and the element Y+c·S are not equal. Using the CPU 911 , the first verification unit 250 D stores data representing the verification result.

Y=y·g, S=s·g, and z=y+c·s mod p. Thus,

Y+c·S =( y+c·s )· g=z·g   [Equation 29]

Therefore, if the bit string M is not altered, z·g=Y+c·S is established.

The verification apparatus 100 D verifies if R′=h·X.

The verification apparatus 100 D is an apparatus corresponding to the verification apparatus 100 described in the first embodiment. Using the CPU 911 , the verification apparatus 100 D inputs the data representing the order p among the encryption parameters stored by the encryption parameter storage unit 290 D, as data representing the order p described in the first embodiment. Using the CPU 911 , the verification apparatus 100 D inputs the data representing the hash value h and stored by the integer calculation unit 232 D, as data representing the integer e described in the first embodiment. Using the CPU 911 , the verification apparatus 100 D inputs the data representing the element R′ and stored by the verification element calculation unit 233 D, as data representing the element h described in the first embodiment. Using the CPU 911 , the verification apparatus 100 D inputs the data representing the public element X among the encryption parameters stored by the encryption parameter storage unit 290 D, as data representing the element s described in the first embodiment. Using the CPU 911 and based on the order p, hash value h, element R′, and element X represented by the input data, the verification apparatus 100 D verifies if R′=h·X. Using the CPU 911 , the verification apparatus 100 D judges that “the verification is successful” when R′=h·X, and that “the verification fails” when R′≠h·X. Using the CPU 911 , the verification apparatus 100 D outputs data representing the verification result.

R=r·g, S=s·g=r+H(R,ID)·mod p, h=H(R,ID), and X=x·g. Thus,

[Equation 30]

Using the CPU 911 , the verification result output unit 260 D inputs the data representing the verification result and stored by the first verification unit 250 D, and the data representing the verification result and output by the verification result output unit 260 D. Using the CPU 911 and based on the two input verification results, the verification result output unit 260 D judges that “the verification is successful” when both the first verification unit 250 D and verification apparatus 100 D judge that “the verification is successful”, and judges that “the verification fails” otherwise. Using the CPU 911 , the verification result output unit 260 D outputs data representing the verification result.

FIG. 33 is a flowchart showing an example of the flow of the signature verification process used by the signature verification apparatus 200 D of this embodiment to verify the signature σ.

In a challenge calculation step S 731 D, using the CPU 911 and based on the bit string ID stored by the identifier storage unit 210 D, the element R, element S, and element Y input by the signature input unit 220 D, and the bit string M input by the message input unit 225 D, the challenge calculation unit 231 D calculates a hash value H′(ID,R,S,Y,M) which is obtained when the set of the ordered pair of the bit string ID and bit string M and the ordered pair of the element R, element S, and element Y is hashed by the hash function H′, and treats the calculated value as the hash value c.

In a first verification step S 732 D, using the CPU 911 and based on the order p and element g stored by the encryption parameter storage unit 290 D, the element S, element Y, and integer z input by the signature input unit 220 D, and the hash value c calculated by the challenge calculation unit 2310 in the challenge calculation step S 731 D, the first verification unit 250 D verifies if z·g=Y+c·S.

When z·g=Y+c·S, the flow advances to an integer calculation step S 733 D. When z·g=Y+c·S, the flow advances to a failure judgment step S 737 D.

In the integer calculation step S 733 , using the CPU 911 and based on the bit string ID stored by the identifier storage unit 210 D and the element R input by the signature input unit 220 D, the integer calculation unit 232 D calculates a hash value H (R, ID) which is obtained by hashing the set of the element R and bit string ID by the hash function H, and treats the calculated value as the hash value h.

In a verification element calculation step S 734 D, using the CPU 911 and based on the element R and element S input by the signature input unit 220 D, the verification element calculation unit 233 D calculates an element S—R which is obtained when the element S and the inverse element of the element R are added by the operation on the additive group G, and treats the calculated element as the element R′.

In a second verification step S 735 D, using the CPU 911 and based on the order p and element X stored by the encryption parameter storage unit 290 D, the hash value h calculated by the integer calculation unit 232 D in the integer calculation step S 733 D, and the element R′ calculated by the verification element calculation unit 233 D in the verification element calculation step S 734 D, the verification apparatus 100 D verifies if R′=h·X.

When R′=h·X, the flow advances to a success judgment step S 736 D. When R′≠h·X, the flow advances to a failure judgment step S 737 D.

In the success judgment step S 736 D, using the CPU 911 , the verification result output unit 260 D judges that the verification is successful, and outputs the verification result.

After that, the signature verification process is ended.

In the failure judgment step S 737 D, using the CPU 911 , the verification result output unit 260 D judges that the verification fails, and outputs the verification result.

After that, the signature verification process is ended.

In this example, if z·g=Y+c·S is verified first, and then if R′=h·X is verified. However, either verification may come first.

The signature verification apparatus 200 D of this embodiment has a processing device (CPU 911 ) which processes data, the message input unit 225 D, the signature input unit 220 D, the signature verification unit 230 D, the verification apparatus 100 D, and the verification result output unit 260 D.

Using the processing device (CPU 911 ), the message input unit 225 D inputs the message (bit string M). Using the processing device (CPU 911 ), the signature input unit 220 D inputs the signature σ for the message (bit string M) input by the message input unit 225 D. Using the processing device (CPU 911 ) and based on the message (bit string M) input by the message input unit 225 D and the signature σ input by the signature input unit 220 D, the signature verification unit 230 D calculates the integer e (hash value h), the element s (public element X) of the finite group (additive group) G, and the element h (element R′) of the finite group (additive group) G, which are to be input to the verification apparatus 100 D. The verification apparatus 100 D inputs the integer e (hash value h), the element s (public element X) of the finite group (additive group) G, and the element h (element R′) of the finite group (additive group) G, which are calculated by the signature verification unit 230 D, and judges whether or not the verification is successful. Using the processing device (CPU 911 ) and based on the verification result of the verification apparatus 100 D, the verification result output unit 260 D outputs a verification result indicating whether or not the verification is successful. With the signature verification apparatus 200 D of this embodiment, the signature can be verified by means of verification by the verification apparatus 100 D that h=e·s. As the time necessary for the verification apparatus 100 D to perform the process of verifying the consistency of the signature can be shortened, the time necessary for the signature verification apparatus 200 D to perform the entire process of verifying the signature can be shortened.

The signature verification apparatus 200 D of this embodiment further has a storage device (e.g., magnetic disk drive 920 and RAM 914 ) which stores data, the encryption parameter storage unit 290 D, and the identifier storage unit 210 D.

Using the storage device (magnetic disk drive 920 ), the encryption parameter storage unit 290 D stores the order p of the finite group (additive group) G, the generator g of the finite group (additive group) G, and the element (public element) X of the finite group (additive group) G. Using the storage device (magnetic disk drive 920 ), the identifier storage unit 210 D stores the bit string ID that identifies the signature apparatus 400 D. Using the processing device (CPU 911 ), the message input unit 225 D inputs the bit string M as the message. Using the processing device (CPU 911 ), the signature input unit 220 D inputs the element R of the finite group (additive group) G, the element S of the finite group (additive group) G, the element Y of the finite group (additive group) G, and the integer z equal to or larger than 1 and equal to or smaller than p−1, as the signature σ. The signature verification unit 230 D has the integer calculation unit 232 D, the verification element calculation unit 233 D, the challenge calculation unit 231 D, and the first verification unit 250 D. Using the processing device (CPU 911 ) and based on the element R input by the signature input unit 220 D and the bit string ID stored by the identifier storage unit 210 D, the integer calculation unit 232 D calculates a hash value which is obtained when the element R and the bit string I are hashed by the predetermined hash function H, and treats the calculated value as the integer h (=H(R,ID)). Using the processing device (CPU 911 ) and based on the element R and element S input by the signature input unit 220 D, the verification element calculation unit 233 D adds the element S and the inverse element of the element R, and treats the sum as the element R′ (=S−R) of the finite group (additive group) G. Using the processing device (CPU 911 ) and based on the bit string ID stored by the identifier storage unit 210 D, the element R, element S, and element Y input by the signature input unit 220 D, and the bit string M input by the message input unit 225 D, the challenge calculation unit 231 D calculates a hash value which is obtained when the bit string ID, the element R, the element S, the element Y, and the bit string M are hashed by the predetermined hash function H′, and treats the calculated value as the integer (hash value) c (=H′(ID,R,S,Y,M)). Using the processing device (CPU 911 ) and based on the generator g stored by the encryption parameter storage unit 290 D, the element S, element Y, and integer z input by the signature input unit 220 D, and the integer (hash value) c calculated by the challenge calculation unit 231 D, the first verification unit 250 D judges whether or not the element Y+c·S, obtained by adding the element Y and the element c·S which is obtained when the element S is added the number of times of the integer (hash value) c, is equal to the element z·g obtained when the generator g is added the number of times of the integer z. When the element Y+c·S and the element z·g are equal, the first verification unit 250 D judges that the verification is successful, and treats this judgment result as the first verification result. The verification apparatus 100 D inputs the order p stored by the encryption parameter storage unit 290 D, as the order p, the integer h calculated by the integer calculation unit 232 D, as the integer e, the element X stored by the encryption parameter storage unit 290 D, as the element s, and the element R′ calculated by the verification element calculation unit 233 D, as the element h, judges whether or not the verification is successful, and treats the judgment result as the second verification result. Using the processing device (CPU 911 ) and based on the first verification result of the verification by the first verification unit 250 D and the second verification result of the verification by the verification apparatus 100 D, when both the first verification result and the second verification result show that the verification is judged successful, the verification result output unit 260 D outputs a verification result indicating that the verification is successful.

With the signature verification apparatus 200 D of this embodiment, since the verification apparatus 100 D verifies if R′=h·X, the signature o can be verified. Since the time necessary for the verification apparatus 100 D to perform the process of verifying if R′=h·X can be shortened, the time necessary for the signature verification apparatus 200 D to perform the entire process of verifying the signature can be shortened.

The signature verification apparatus 200 D described so far is a digital signature verification apparatus which judges whether or not the signature is correct by verifying if the element s e which is obtained when the element s of the multiplicative group is multiplied e times by the exponentiation on the multiplicative group, or the element e·s which is obtained when the element s of the additive group is added e times by the scalar multiplication on the additive group such as a group formed of points on a (hyper) elliptic curve, coincides with the known element h.

The signature verification apparatus 200 D has a device (integer partitioning unit 110 ) which partitions an exponential part (integer e), a device (verification value calculation unit 130 ) which, using the partitioned exponents (integer e 1 and integer e 2 ), calculates a value h e1 ·e −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·h−e 2 ·s by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper) elliptic curve, and a device (verification judging unit 150 ) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The signature verification apparatus 200 D (digital signature verification apparatus) described so far has

a calculation device (integer partitioning unit 110 ) which inputs the exponent (integer) e and the group order p of the multiplicative group or additive group used in a cipher and calculates the two integers e 1 and e 2 (note that e 1 ·e≡e 2 (mod p)) each having a bit length half that of the order p, and a verification apparatus (verification value calculation unit 130 , verification judging unit 150 ) which verifies s e2 ·h −e1 =1 or e 2 ·s−e 1 ·h=0.

The integer partitioning unit 110 described so far partitions the exponential part (integer e) by performing the extended Euclidean algorithm.

The integer partitioning unit 110 described so far has, in repetitive division of two integers,

a calculation device (third remainder calculation unit 117 ) in which an integer v 2 as the divisor and an integer v 1 as the dividend are a remainder v 3 of the division of the preceding step and an integer v 2 as the divisor of the preceding step, respectively, and a calculation device (conformity judging unit 116 ) which judges that the remainder v 3 of the division result of each step is equal to or larger than a predetermined number (√p), or equal to or smaller than a predetermined number (√p).

The signature verification apparatus 200 D described so far is a BNN (Bellare-Namprempre-Neven)-ID-based signature verification apparatus.

The signature verification apparatus 200 D has, in order to verify, based on the element X on the multiplicative group or additive group which is the public key of the secret key generation center (key generating apparatus 300 D), the element R as part of the secret key (signing key) of the signing person (signature apparatus 400 D), the element S as part of the signature a, and the bit string ID that identifies the signing person, if an element R·X H(R,ID) or R+H(R,ID)·X coincides with the element S, a device (integer partitioning unit 110) which partitions the exponential part (hash value h=H(R,ID)), a device (verification value calculation unit 130 ) which, using the partitioned exponents (integer e 1 and integer e 2 ), calculates a value (S/R) e1 ·X −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·(S−R)−e 2 ·X by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ID-based signature system 820 D described so far is a signature system employing the BNN-ID-based signature scheme which is a Fiat-Shamir-transformed BNN-ID-based authentication system.

The ID-based authentication system 820 E employs the multiplicative group G whose order p is a prime number, and the generator g of the additive group G.

The encryption parameter setting apparatus 810 D performs a PKG key generating process. Using the CPU 911 , the encryption parameter setting apparatus 810 D generates a random integer x equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the encryption parameter setting apparatus 810 D calculates the element X=g x of the multiplicative group G. Using the CPU 911 , the encryption parameter setting apparatus 810 D outputs the element X of the group G as the PKG public key, and the integer x as the PKG secret key.

The key generating apparatus 300 D performs a user secret key extraction process. Using the CPU 911 , the key generating apparatus 300 D inputs the PKG secret key x and the bit string ID that identifies the proving apparatus 400 E. First, using the CPU 911 , the key generating apparatus 300 D generates a random integer (secret random number) r equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the key generating apparatus 300 D calculates the element R=g r of the group G and the integer s=r+H(R,ID)·x, and outputs (R,s) as the user secret key. The signature apparatus 400 D performs a signature generating process. Using the CPU 911 , the signature apparatus 400 D inputs the message M and the secret key (R,s). First, using the CPU 911 , the signature apparatus 400 D generates the random integer (secret random number) y equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the signature apparatus 400 D calculates the element S=g s of the group G and the element Y=g y of the group G, and calculates the integer c=H 1 (S,Y,R,M). Using the CPU 911 , the signature apparatus 400 D calculates the integer z=y+c·s mod p, and outputs (c,z,S,Y,R) as the signature. The signature verification apparatus 200 D performs a signature verification process. Using the CPU 911 , the signature verification apparatus 200 D inputs the signature (c,z,S,Y,R) and the bit string ID that identifies the signature apparatus 400 D. The signature verification apparatus 200 D verifies if g z =Y·S c and S=R·X H(R,ID) are established, if the element S and element Y are elements of G, and if the integer z is equal to or larger than 1 and equal to or smaller than p−1. If all of these conditions are established, using the CPU 911 , the signature verification apparatus 200 D judges that the signature verification is accepted; if not, the signature verification is not accepted.

The verification apparatus 100 D described so far speeds up the process of verifying whether or not S=R·X H(R,ID) in the BNN-ID-based signature system.

In the verification apparatus 100 D, the integer partitioning unit 110 , using the CPU 911 , inputs h (=H(R,ID)) and p, and calculates the integer e 1 and integer e 2 that satisfy e 1 ·h≡e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 calculates X 1 =X e1 ·R′ e2 (note that R′=S·R −1 ) by the double-base exponentiation on the multiplicative group G. By checking whether or not X 1 =1, the verification apparatus 100 E checks at high speed if S=R·X H(R,ID) is established.

The sixth embodiment will be described with reference to FIGS. 34 to 37 .

FIG. 34 shows an example of the entire system configuration of an ID-based authentication system 820 E of this embodiment.

The ID-based authentication system 820 E is a system in which an authentication apparatus 200 E authenticates that a proving apparatus 400 E is not a counterfeit. In this authentication, the authentication apparatus 200 E utilizes identification data that identifies the proving apparatus 400 E as the public key of the proving apparatus 400 E.

The ID-based authentication system 820 E has an encryption parameter setting apparatus 810 D, a key generating apparatus 300 D, the proving apparatus 400 E, and the authentication apparatus 200 E.

The encryption parameter setting apparatus 810 D and key generating apparatus 300 D are similar to those described in the fifth embodiment, and their description will be omitted.

The proving apparatus 400 E transmits an authentication request message to the authentication apparatus 200 E. The authentication request message transmitted from the proving apparatus 400 E includes ah element R, element S, and element Y of an additive group G.

Upon reception of the authentication request message, the authentication apparatus 200 E transmits a question message to the proving apparatus 400 E. The question message transmitted from the authentication apparatus 200 E includes an integer c equal to or larger than 1 and equal to or smaller than p−1. Upon reception of the question message, the proving apparatus 400 E transmits a response message to the authentication apparatus 200 E. The response message transmitted from the proving apparatus 400 E includes an integer z equal to or larger than 1 and equal to or smaller than p−1 and calculated based on the integer c. The authentication apparatus 200 E verifies the element R, element S, and element Y included in the received authentication request message and the integer z included in the received response message. If they match, the authentication apparatus 200 E authenticates that the proving apparatus 400 E is not a counterfeit.

FIG. 35 shows a block diagram showing a configuration example of the function block of the proving apparatus 400 E of this embodiment.

Portions of the proving apparatus 400 E which are common to those of the signature apparatus 400 D described in the fifth embodiment are denoted by the same reference numerals, and their description will be omitted.

The proving apparatus 400 E has an encryption parameter storage unit 490 D, a signing key storage unit 420 D, a signature generating unit 450 D, an authentication request transmission unit 470 E, a question reception unit 454 E, and a response transmission unit 475 E.

Using a CPU 911 , the authentication request transmission unit 470 E inputs data representing the element R of the signing key and stored by the signing key storage unit 420 D, data representing the element S and stored by a first signature element calculation unit 451 D, and data representing the element Y and stored by a second signature element calculation unit 453 D. Using the CPU 911 , the authentication request transmission unit 470 E generates the authentication request message including the input data representing the element R, element S, and element Y. Using a communication device 915 , the authentication request transmission unit 470 E transmits the generated authentication request message to the authentication apparatus 200 E.

Using the communication device 915 , the question reception unit 454 E receives the question message transmitted from the authentication apparatus 200 E. Using the CPU 911 , the question reception unit 454 E acquires data representing the integer c included in the received question message. Using a RAM 914 , the question reception unit 454 E stores the acquired data representing the integer c.

Using the CPU 911 , a signature integer calculation unit 455 D inputs data representing an order p among the encryption parameters stored by the encryption parameter storage unit 490 D, data representing an integer s of the signing key stored by the signing key storage unit 420 D, data representing a secret random number y stored by the secret random number generating unit 452 D, and the data representing the integer c and stored by the question reception unit 454 E. Using the CPU 911 and based on the order p, integer s, secret random number y, and integer c represented by the input data, the signature integer calculation unit 455 D calculates a remainder which is obtained when the sum of the secret random number y and the product of the integer c and integer s is divided by the order p, and treats the calculated remainder as an integer z. Using the RAM 914 , the signature integer calculation unit 455 D stores data representing the calculated integer z.

Using the CPU 911 , the response transmission unit 475 E inputs the data representing the integer z and stored by the signature integer calculation unit 455 D. Using the CPU 911 , the response transmission unit 475 E generates the response message including the input data representing the integer z. Using the communication device 915 , the response transmission unit 475 E transmits the generated response message to the authentication apparatus 200 E.

FIG. 36 is a block diagram showing a configuration example of the function block of the authentication apparatus 200 E of this embodiment.

Portions of the authentication apparatus 200 E which are common to those of the signature verification apparatus 200 D described in the fifth embodiment are denoted by the same reference numerals, and their description will be omitted.

The authentication apparatus 200 E has an encryption parameter storage unit 290 D, an identifier storage unit 210 D, an authentication request reception unit 220 E, a challenge generating unit 231 E, a question transmission unit 226 E, a response reception unit 227 E, a signature verification unit 230 D, a verification apparatus 100 D, and an authentication result output unit 260 E.

Using the communication device 915 , the authentication request reception unit 220 E receives the authentication request message transmitted from the proving apparatus 400 E. Using the CPU 911 , the authentication request reception unit 220 E acquires the data representing the element R, element S, and element Y included in the received authentication request message. Using the RAM 914 , the authentication request reception unit 220 E stores the acquired data representing the element R, element S, and element Y.

When the authentication request reception unit 220 E receives the authentication request message, the challenge generating unit 231 E, using the CPU 911 , randomly generates an integer equal to or larger than 1 and equal to or smaller than p−1, and treats it as the integer c. Using the RAM 914 , the challenge generating unit 231 E stores data representing the generated integer c.

Using the CPU 911 , the question transmission unit 226 E inputs the data representing the integer c and stored by the challenge generating unit 231 E. Using the CPU 911 , the question transmission unit 226 E generates the question message including the input data representing the integer c. Using the communication device 915 , the question transmission unit 226 E transmits the generated question message to the proving apparatus 400 E.

Using the communication device 915 , the response reception unit 227 E receives the response message transmitted from the proving apparatus 400 E. Using the CPU 911 , the response reception unit 227 E acquires the data representing the integer z included in the received response message. Using the RAM 914 , the response reception unit 227 E stores the acquired data representing the integer z.

A first verification unit 250 D verifies if z·g=Y+c·S.

Using the CPU 911 , the first verification unit 250 D inputs data representing the additive group G and an element g among the encryption parameters stored by the encryption parameter storage unit 290 D, the data representing the element S and element Y and stored by the authentication request reception unit 220 E, the data representing the integer value c and stored by the challenge generating unit 231 E, and the data representing the integer z and stored by the response reception unit 227 E. Using the CPU 911 and based on the additive group G, element g, element S, element Y, integer z, and hash value c represented by the input data, the first verification unit 250 D judges whether or not an element Y+c·S, which is obtained by adding the element Y and an element c·S obtained when the element S is added c times, is equal to an element z·g which is obtained when the element g is added z times, by the operation on the additive group G. When the element z·g and the element Y+c·S are equal, the first verification unit 250 D, using the CPU 911 , judges that “the verification is successful”; if not, “the verification fails”. Using the CPU 911 , the first verification unit 250 D stores data representing the verification result.

Using the CPU 911 , the authentication result output unit 260 E inputs the data representing the verification result and stored by the first verification unit 250 D, and the data representing the verification result and output by the verification apparatus 100 D. Using the CPU 911 and based on the two input verification results, the authentication result output unit 260 E judges that “the verification is successful” when both the first verification unit 250 D and verification apparatus 100 D judge that “the verification is successful”, and judges that “the verification fails” otherwise. Using the CPU 911 , the authentication result output unit 260 E outputs data representing the verification result.

FIG. 37 is a flowchart showing an example of the authentication process used by the authentication apparatus 200 E of this embodiment to authenticate the proving apparatus 400 E.

Portions of the authentication process which are common to the signature verification process described in the fifth embodiment are denoted by the same reference numerals, and their description will be omitted.

In a secret random number generating step S 741 E, a secret random number generating unit 452 D of the proving apparatus 400 E, using the CPU 911 , randomly generates the secret random number y equal to or larger than 1 and equal to or smaller than p−1.

In a signature element calculation step S 742 E, the second signature element calculation unit 453 D, using the CPU 911 and based on the secret random number y generated by the secret random number generating unit 452 D, calculates the element Y (=y·g) of the additive group G. In an authentication request transmission step S 743 E, the authentication request transmission unit 470 E of the proving apparatus 400 E, using the communication device 915 , transmits the authentication request message including the element R stored by the signing key storage unit 420 D, the element S (=s·g) calculated by the first signature element calculation unit 451 D, and the element Y calculated by the second signature element calculation unit 453 D in the secret random number generating step S 741 E to the authentication apparatus 200 E.

In an authentication request reception step S 751 E, the authentication request reception unit 220 E of the authentication apparatus 200 E, using the communication device 915 , receives the authentication request message transmitted from the proving apparatus 400 E in the authentication request transmission step S 743 E.

In a challenge generating step S 752 E, the challenge generating unit 231 E of the authentication apparatus 200 E, using the CPU 911 , randomly generates the integer c equal to or larger than 1 and equal to or smaller than p−1. In a question transmission step S 753 E, the question transmission unit 226 E of the authentication apparatus 200 E, using the communication device 915 , transmits the question message including the integer c generated by the challenge generating unit 231 E in the challenge generating step S 752 E to the proving apparatus 400 E.

In a question reception step S 744 E, the question reception unit 454 E of the proving apparatus 400 E, using the communication device 915 , receives the question message transmitted from the authentication apparatus 200 E in the question transmission step S 753 E.

In a signature integer calculation step S 745 E, the signature integer calculation unit 455 D of the proving apparatus 400 E, using the CPU 911 and based on the order p stored by the encryption parameter storage unit 490 D, the integer s stored by the signing key storage unit 420 D, the secret random number y generated by the secret random number generating unit 452 D in the secret random number generating step S 741 E, and the integer y included in the question message received by the question reception unit 454 E in the question reception step S 744 E, calculates the integer z (=y+c·s mod p). In a response transmission step S 746 E, the response transmission unit 475 E of the proving apparatus 400 E, using the communication device 915 , transmits the response message including the integer z calculated by the signature integer calculation unit 455 D in the signature integer calculation step S 745 E to the authentication apparatus 200 E.

In a response reception step S 754 E, the response reception unit 227 E of the authentication apparatus 200 E, using the communication device 915 , receives the response message transmitted from the proving apparatus 400 E in the response transmission step S 746 E.

A first verification step S 732 D through a second verification step 57350 are similar to the steps described in the fifth embodiment.

In a success judgment step S 735 E, the authentication result output unit 260 E, using the CPU 911 , judges that the authentication is successful, and outputs the authentication result.

After that, the authentication process is ended.

In a failure judgment step S 737 E, the authentication result output unit 260 E, using the CPU 911 , judges that the authentication fails, and outputs the authentication result.

The authentication apparatus 200 E of this embodiment has a processing device (CPU 911 ) which processes data, a transmission device (communication device 915 ) which transmits data, a reception device (communication device 915 ) which receives data, the authentication request reception unit 220 E, the question transmission unit 226 E, the response reception unit 227 E, the signature verification unit 230 D, the verification apparatus 100 D, and the authentication result output unit 260 E.

Using the reception device (communication device 915 ), the authentication request reception unit 220 E receives the authentication request message. Using the transmission device (communication device 915 ), the question transmission unit 226 E transmits the question message as a response to the authentication request message received by the authentication request reception unit 220 E. Using the reception device (communication device 915 ), the response reception unit 227 E receives the response message to the transmitted question message. Using the processing device (CPU 911 ) and based on the authentication request message received by the authentication request reception unit 220 E and the response message received by the response reception unit 227 E, the signature verification unit 230 D calculates an integer e (hash value h), an element s (element X) of the finite group (additive group) G, and an element h (element R′) of the finite group (additive group) G which are to be input to the verification apparatus 100 D. The verification apparatus 100 D inputs the integer e (hash value h), the element s (element X) of the finite group (additive group) G, and the element h (element R′) of the finite group (additive group) G which are calculated by the signature verification unit 230 D, and judges whether or not the verification is successful. Using the processing device (CPU 911 ) and based on the verification result of the verification apparatus 100 D, the authentication result output unit 260 E outputs an authentication result indicating whether or not the verification is successful.

With the authentication apparatus 200 E of this embodiment, the proving apparatus 400 E can be authenticated by means of judgment by the verification apparatus 100 D if h=e·s. As the time necessary for the verification apparatus 100 D to perform the process of verifying the consistency of the signature can be shortened, the time necessary for the authentication apparatus 200 E to perform the entire process of verifying the proving apparatus 400 E can be shortened.

The authentication apparatus 200 E of this embodiment further has a storage device (e.g., magnetic disk drive 920 and RAM 914 ) which stores data, the encryption parameter storage unit 290 D, the identifier storage unit 210 D, and the challenge generating unit 231 E.

Using the storage device (magnetic disk drive 920 ), the encryption parameter storage unit 290 D stores the order p of the finite group (additive group) G, the generator g of the finite group (additive group) G, and the element X of the finite group (additive group) G. Using the storage device (magnetic disk drive 920 ), the identifier storage unit 210 D stores a bit string ID which identifies the proving apparatus 400 E. Using the reception device (communication device 915 ), the authentication request reception unit 220 E receives the element R of the finite group (additive group) G, the element S of the finite group (additive group) G, and the element Y of the finite group (additive group) G from the proving apparatus 400 E as the authentication request message. Using the processing device (CPU 911 ), the challenge generating unit 231 E randomly generates the integer c equal to or larger than 1 and equal to or smaller than p−1. Using the transmission device (communication device 915 ), the question transmission unit 226 E transmits the integer c generated by the challenge generating unit 231 E to the proving apparatus 400 E as the question message. Using the reception device (communication device 915 ), the response reception unit 227 E receives the integer z equal to or larger than 1 and equal to or smaller than p−1 from the proving apparatus 400 E as the response message. The signature verification unit 230 D has the integer calculation unit 232 D, verification element calculation unit 233 D, and first verification unit 250 D. Using the processing device (CPU 911 ) and based on the element R received by the authentication request reception unit 220 E and the bit string ID stored by the identifier storage unit 210 D, the integer calculation unit 232 D calculates a hash value which is obtained when the element R and bit string ID are hashed by a predetermined hash function H, and treats the calculated hash value as the integer h (=H(R,ID)). Using the processing device (CPU 911 ) and based on the element R and element S received by the authentication request reception unit 220 E, the verification element calculation unit 233 D adds the element S and the inverse element of the element R, and treats the sum as an element R′ (=S−R) of the finite group G. Using the processing device (CPU 911 ) and based on the generator g stored by the encryption parameter storage unit 290 D, the element S and element Y received by the authentication request reception unit 220 E, the integer c generated by the challenge generating unit 231 E, and the integer z received by the response reception unit 227 E, the first verification unit 250 D judges whether or not the element Y+c·S, which is obtained by adding the element Y and the element c·S obtained when the element S is added c times, is equal to the element z·g which is obtained when the element g is added z times. When the element Y+c·S and the element z·g are equal, the first verification unit 250 D judges that the verification is successful, and treats this judgment result as the first verification result. The verification apparatus 100 D inputs the order p stored by the encryption parameter storage unit 290 D, as the order p, the integer h calculated by the integer calculation unit 232 D, as the integer e, the element X stored by the encryption parameter storage unit 290 D, as the element s, and the element R′ calculated by the verification element calculation unit 233 D, as the element h, judges whether or not the verification is successful, and treats the judgment result as the second verification result. Using the processing device (CPU 911 ) and based on the first verification result of the verification by the first verification unit 250 D and the second verification result of the verification by the verification apparatus 100 D, when both the first verification result and the second verification result show that the verification is judged successful, the authentication result output unit 260 E outputs an authentication result indicating that the authentication is successful.

With the authentication apparatus 200 E of this embodiment, since the verification apparatus 100 D verifies if R′=h·X, the proving apparatus 400 E can be authenticated. Since the time necessary for the verification apparatus 100 D to perform the process of verifying if R′=h·X can be shortened, the time necessary for the authentication apparatus 200 E to perform the entire process of authenticating the proving apparatus 400 E can be shortened.

The authentication apparatus 200 E described so far is an authentication scheme verification apparatus which authenticates the proving apparatus 400 E by verifying if the element s e which is obtained when the element s on the multiplicative group is multiplied e times by the exponentiation on the multiplicative group, or the element e·s which is obtained when the element s on the additive group is added e times by the scalar multiplication on the additive group such as a group formed of points on a (hyper) elliptic curve, coincides with the known element h.

The authentication apparatus 200 E has a device (integer partitioning unit 110 ) which partitions an exponential part (integer e), a device (verification value calculation unit 130 ) which, using the partitioned exponents (integer e 1 and integer e 2 ), calculates a value h e1 ·e −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·h−e 2 ·s by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The authentication apparatus 200 E (authentication scheme verification apparatus) described so far has

a calculation device (integer partitioning unit 110 ) which inputs the exponent (integer) e and the group order p of the multiplicative group or additive group used in a cipher and calculates the two integers e 1 and e 2 (note that e 1 ·e≡e 2 (mod p)) each having a bit length half that of the order p, and a verification apparatus (verification value calculation unit 130 , verification judging unit 150 ) which verifies s e2 ·h −e1 =1 or e 2 ·s−e 1 ·h=0.

The integer partitioning unit 110 described so far partitions the exponential part (integer e) by performing the extended Euclidean algorithm.

The integer partitioning unit 110 described so far has, in repetitive division of two integers,

a calculation device (third remainder calculation unit 117 ) in which an integer v 2 as the divisor and an integer v 1 as the dividend are a remainder v 3 of the division of the preceding step and an integer v 2 as the divisor of the preceding step, respectively, and a calculation device (conformity judging unit 116 ) which judges that the remainder v 3 of the division result of each step is equal to or larger than a predetermined number (√p), or equal to or smaller than a predetermined number (√p).

The authentication apparatus 200 E described so far is a BNN-ID-based authentication scheme verification apparatus.

The authentication apparatus 200 E has, in order to verify, based on the element X on the multiplicative group or additive group which is the public key of the secret key generation center (key generating apparatus 300 D), the element R as part of the secret key (signing key) of the authentication target party (proving apparatus 400 E), the commit value (element) S of the authentication target party, and the bit string ID that identifies the authentication target party, if an element R·X {H (R,ID) or R+H(R,ID)·X coincides with the element S, a device (integer partitioning unit 110 ) which partitions the exponential part (hash value h=H(R,ID)), a device (verification value calculation unit 130 ) which, using the partitioned exponents (integer e 1 and integer e 2 ), calculates a value (S/R) e1 ·X −e2 by the double-base exponentiation on the multiplicative group, or a value e 1 ·(S−R)−e 2 ·X by the double-base scalar multiplication on the additive group such as a group formed of points on a (hyper)elliptic curve, and a device (verification judging unit 150 ) which judges whether or not the calculated value is equal to the identity element 1 of the multiplicative group or the identity element 0 of the additive group.

The ID-based authentication system 820 E described so far is an authentication system employing the BNN-ID-based authentication scheme.

The ID-based authentication system 820 E has a proving party (proving apparatus 400 E) and an authentication party (authentication apparatus 200 E). First, the proving party (proving apparatus 400 E) sends a commitment Cmt (authentication request message) to the verification party (authentication apparatus 200 E). The verification party (authentication apparatus 200 E) receives the commitment Cmt, calculates challenge data Ch (question message) from the commitment Cmt and the public information (encryption parameters and public parameters), and sends the challenge data Ch to the proving party (proving apparatus 400 E). The proving party (proving apparatus 400 E) receives the challenge data Ch, and calculates response data Rsp and sends it to the verification party (authentication apparatus 200 E). The verification party (authentication apparatus 200 E) receives the response data Rsp and verifies if it is correct data. The verification party (authentication apparatus 200 E) judges that the authentication is accepted when the response data is correct, and judges that the authentication is not accepted otherwise.

The ID-based authentication system 820 E employs the multiplicative group G whose order p is a prime number, and the generator g of the additive group G.

The encryption parameter setting apparatus 810 D performs a PKG key generating process. Using the CPU 911 , the encryption parameter setting apparatus 810 D generates a random integer x equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the encryption parameter setting apparatus 810 D calculates the element X=g x of the multiplicative group G. Using the CPU 911 , the encryption parameter setting apparatus 810 D outputs the element X of the group G as the PKG public key, and the integer x as the PKG secret key. The key generating apparatus 300 D performs a user secret key extraction process. Using the CPU 911 , the key generating apparatus 300 D inputs the PKG secret key x and the bit string ID that identifies the proving apparatus 400 E. First, using the CPU 911 , the key generating apparatus 300 D generates a random integer (secret random number) r equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the key generating apparatus 300 D calculates the element R=g r of the group G and the integer s=r+H(R,ID)·x, and outputs (R,s) as the user secret key. In the Cmt calculation process, using the CPU 911 , the proving apparatus 400 E generates the random integer (secret random number) y equal to or larger than 1 and equal to or smaller than p−1. Using the CPU 911 , the proving apparatus 400 E calculates the element S=g s of the group G and the element Y=g y of the group G, and treats the element S, element Y, and element R as the commitment Cmt (authentication request data). In the Ch calculation process, using the CPU 911 , the authentication apparatus 200 E generates the random integer c equal to or larger than 1 and equal to or smaller than p−1, and treats the generated integer c as the challenge data Ch (question data). In the Rsp calculation process, using the CPU 911 , the proving apparatus 400 E calculates the integer z=y+c·s mod p, and treats the calculated integer z as the response data Rsp. Using the CPU 911 , the authentication apparatus 200 E receives Rsp, and verifies if g z =Y·S c and S=R·X H(R,ID) are established, if the element S and element Y are elements on the group G, and if the integer z is equal to or larger than 1 and equal to or smaller than p−1. If all of these conditions are established, the authentication apparatus 200 E, using the CPU 911 , judges that the authentication is accepted; if not, the authentication is not accepted.

The verification apparatus 100 E described so far speeds up the process of verifying whether or not S=R·X H(R,ID) in the BNN-ID-based authentication system.

In the verification apparatus 100 E, the integer partitioning unit 110 , using the CPU 911 , inputs h (=H(R,ID)) and p, and calculates the integer e 1 and integer e 2 that satisfy e 1 ·h=e 2 (mod p). Using the CPU 911 , the verification value calculation unit 130 calculates X 1 =X e1 ·R′ e2 (note that R′=S·R −1 ) by the double-base exponentiation on the multiplicative group G. By checking whether or not X 1 =1, the verification apparatus 100 E checks at high speed if S=R·X H(R,ID) is established.

In several cryptographic communication system, signature system, and authentication system described above, the verification apparatus 100 speeds up the verification process. However, this technique is not limited to the examples described above, but can be applied to the cryptographic system in general such as the discrete logarithm type cryptographic communication system, authentication system, and signature system.

For the sake of descriptive convenience, cases have been described in which the group operation is described additively. However, whether the group operation is described additively or multiplicatively is not substantial. In a finite group utilized by the cryptographic system, as far as the group operation can be performed using a processing device such as a computer and one group operation takes much time, the speed of the operation can be increased remarkably by this technique.

FIG. 1 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 according to the first embodiment.

FIG. 2 shows an example of the appearance of the ciphertext decryption apparatus 200 according to the first embodiment.

FIG. 3 shows an example of the hardware resources of the ciphertext decryption apparatus 200 according to the first embodiment.

FIG. 4 is a block diagram showing a configuration example of the internal block of the verification apparatus 100 according to the first embodiment.

FIG. 5 is a flowchart showing an example of the flow of the verification process used by the verification apparatus 100 according to the first embodiment to judge whether or not h=e·s.

FIG. 6 is a detailed block diagram showing a configuration example of the internal block of the integer partitioning unit 110 according to the first embodiment.

FIG. 7 is a flowchart showing an example of the flow of the integer partitioning process used by the integer partitioning unit 110 according to the first embodiment to partition the integer e.

FIG. 8 is a detailed block diagram showing a configuration example of the internal block of the verification value calculation unit 130 according to the first embodiment.

FIG. 9 is a flowchart showing an example of the flow of the verification value calculation process used by the verification value calculation unit 130 according to the first embodiment to calculate the element a of the finite group G.

FIG. 10 shows an example of the entire system configuration of the ID-based public key cryptographic system 820 A according to the second embodiment.

FIG. 11 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 A according to the second embodiment.

FIG. 12 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 A according to the second embodiment.

FIG. 13 is a block diagram showing a configuration example of the function block of a ciphertext generating apparatus 400 A according to the second embodiment.

FIG. 14 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 A according to the second embodiment.

FIG. 15 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 A according to the second embodiment to decrypt the ciphertext c.

FIG. 16 shows an example of the entire system configuration of the public key cryptographic system 820 B according to the third embodiment.

FIG. 17 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 B according to the third embodiment.

FIG. 18 is a block diagram showing a configuration example of the function block of the ciphertext generating apparatus 400 B according to the third embodiment.

FIG. 19 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 B according to the third embodiment.

FIG. 20 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 A according to this embodiment to decrypt the ciphertext c.

FIG. 21 shows an example of the entire system configuration of the ID-based public key cryptographic system 820 C according to the fourth embodiment.

FIG. 22 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 C according to the fourth embodiment.

FIG. 23 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 C according to the fourth embodiment.

FIG. 24 is a block diagram showing a configuration example of the function block of the ciphertext generating apparatus 400 C according to the fourth embodiment.

FIG. 25 is a block diagram showing a configuration example of the function block of the ciphertext decryption apparatus 200 C according to the fourth embodiment.

FIG. 26 is a detailed block diagram showing a configuration example of the internal block of the verification apparatus 100 C according to the fourth embodiment.

FIG. 27 is a flowchart showing an example of the flow of the ciphertext decryption process used by the ciphertext decryption apparatus 200 C according to the fourth embodiment to decrypt the ciphertext C.

FIG. 28 shows an example of the entire system configuration of the ID-based signature system 820 D according to the fifth embodiment.

FIG. 29 is a block diagram showing a configuration example of the function block of part of the encryption parameter setting apparatus 810 D according to the fifth embodiment.

FIG. 30 is a block diagram showing a configuration example of the function block of the key generating apparatus 300 D according to the fifth embodiment.

FIG. 31 is a block diagram showing a configuration example of the function block of the signature apparatus 400 D according to the fifth embodiment.

FIG. 32 is a block diagram showing a configuration example of the function block of the signature verification apparatus 200 D according to the fifth embodiment.

FIG. 33 is a flowchart showing an example of the flow of the signature verification process used by the signature verification apparatus 200 D according to the fifth embodiment to verify the signature σ.

FIG. 34 shows an example of the entire system configuration of the ID-based authentication system 820 E according to the sixth embodiment.

FIG. 35 shows a block diagram showing a configuration example of the function block of the proving apparatus 400 E according to the sixth embodiment.

FIG. 36 is a block diagram showing a configuration example of the function block of the authentication apparatus 200 E according to the sixth embodiment.

FIG. 37 is a flowchart showing an example of the authentication process used by the authentication apparatus 200 E according to the sixth embodiment to authenticate the signature apparatus 400 E.