US20040174997A1

Movatterモバイル変換

Info

Publication number: US20040174997A1
Application number: US10/725,208
Authority: US
Inventors: Masato Yamamichi; Masami Yamamichi; Yuichi Futa; Motoji Ohomori; Makoto Tatebayashi
Original assignee: Individual
Current assignee: Panasonic Holdings Corp
Priority date: 2002-12-03
Filing date: 2003-12-02
Publication date: 2004-09-09
Also published as: KR101027199B1; EP1475920A4; WO2004051920A1; EP1569378A4; KR20050087815A; WO2004051921A1; AU2003302544A1; KR20050083566A; AU2003302545A1; US20040165726A1; US7471792B2; EP1475920A1; EP1569378A1

Abstract

Provided is a content distribution system that prevents different keys to be derived between an encryption apparatus and a decryption apparatus. A random-number generating unit112, in an encryption apparatus110, generates a random number s. A first function unit113generates a functional value G(s) of the random number s, and generates a random-number value u and a shared key K from the functional value G(s). An encryption unit114generates a first cipher text c1of the random number s, using a public-key polynomial h and the random-number value u. A decryption unit123, in a decryption apparatus120, decrypts the first cipher text c1using a secret-key polynomial f, to generate a decryption random number s′ A second function unit126generates a functional value G(s′) of the decryption random number s′, and generates a random-number value u′ and a shared key K′from the functional value G(s′ ). A comparison unit127generates a first re-cipher text c1′, using the random-number value u′ and the shared key K′, and outputs the shared key K′ if the first cipher text c1is equal to the first re-cipher text c1′.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention[0001]

The present invention relates to a cryptographic technology used as an information security technology. The present invention particularly relates to a technology of distributing a key under a condition that any third party cannot know the content of the key.[0002]

2. Description of Related Art[0003]

Conventionally, the public-key cryptosystem has been used for transmitting information from a transmission apparatus to a reception apparatus in secrecy.[0004]

In the public-key cryptosystem, a transmission apparatus encrypts a communication content using the public key of a reception apparatus, and sends the encrypted communication content to the reception apparatus. The reception apparatus receives the encrypted communication content, and decrypts the encrypted communication content using a secret key, thereby obtaining the original communication content (e.g. refer to the non-patent reference 1).[0005]

In the year of 1996, the NTRU cryptosystem was proposed, as a public-key cryptosystem for high-speed processing (e.g. refer to the non-patent reference 2). The NTRU cryptosystem performs encryption/decryption using a polynomial operation that enables high-speed computation. The NTRU cryptosystem enables higher-speed processing using software, compared to the conventional public-key cryptosystems such as the RSA cryptosystem and the elliptic curve cryptosystem, the RSA cryptosystem performing exponentiation, and the elliptic curve cryptosystem performing scalar multiplication on a point of an elliptic curve.[0006]

In this NTRU cryptosystem, a decrypted text is generated by the processes in which the plaintext is encrypted using the public key to generate a cipher text, and then this cipher text is decrypted using the secret key. However, the mentioned processes have a possibility of yielding decrypted text that is different from the original plaintext. This phenomenon is called “decryption error”. Here, the[0007]patent reference 1, for example, discloses a method of avoiding such decryption errors. In this method, a plaintext is added additional information before being encrypted, and the cipher text is transmitted together with the hash value of the plaintext.

Meanwhile, a mechanism called “key encapsulation mechanism” has recently been proposed as a new notion of the public-key cryptosystem (e.g. refer to the non-patent reference 3). This key encapsulation mechanism is an algorithm that enables distribution of a shared key between a transmission apparatus and a reception apparatus, using the public-key cryptosystem. In this mechanism, the transmission apparatus inputs a public key pk of a receiver into an encryption algorithm E, to generate a cipher text C and a shared key K, and transmits this cipher text C to the reception apparatus. Next, the reception apparatus inputs a secret key sk and the cipher text C into a decryption algorithm D, thereby obtaining the same shared key K as that the transmission apparatus owns.[0008]

After both of the transmission apparatus and the reception apparatus have established therein the shared key K using the key encapsulation mechanism, as described above, the transmission apparatus encrypts the plaintext to be transmitted to the reception apparatus, according to the symmetric key cryptography and using the shared key K, to generate a cipher text, and transmits the generated cipher text to the reception apparatus. The reception apparatus, in turn, receives the cipher text, and decrypts the received cipher text according to the same symmetric key cryptography and using the shared key K, to generate decrypted text.[0009]

With the key encapsulation mechanism, a transmitter cannot take a whole liberty with creation of a shared key, therefore is prevented from committing fraud even though information is only allowed to be distributed from the transmitter to the receiver. This is the distinctive feature that the conventional arts do not have.[0010]

As one example of the mentioned key encapsulation mechanism, an algorithm called RSA-KEM is disclosed (e.g. the non-patent references 3). The following describes the RSA-KEM algorithm disclosed in the non-patent reference 3.[0011]

(1) System Parameter of RSA-KEM[0012]

The RSA-KEM has the following system parameter:[0013]

hash function: G[0014]

Note here that the hash function is detailed in the[0015]non-patent reference 1, and so will not be described here.

(2) Public Key and Secret Key of RSA-KEM[0016]

Prime numbers p and q are selected, to generate n=p*q.[0017]

The least common multiple between (p−1) and (q−1) is calculated, and the result thereof is set as L.[0018]

e that is coprime to L is randomly selected. Note that e is an element of ZL. d=1/e mod L is calculated. Here, ZL is a set comprised of {0, 1, 2 . . . , L−1}.[0019]

A public key pk is set as (e, n), and a secret key sk as (d, n).[0020]

(3) Encryption of RSA-KEM[0021]

In encryption, the public key pk is inputted into an encryption algorithm KemE detailed below, to output a shared key K and a cipher text C. The encryption algorithm KemE is specifically as follows.[0022]

Randomly generates, which is an element of Zn, where Zn is a set comprised of {0, 1, 2, . . . n−1}.[0023]

Generate K=G(s).[0024]

Generate C=s[0025]^emod n.

Output the shared key K and the cipher text C.[0026]

(4) Decryption of RSA-KEM[0027]

In decryption, the cipher text C and the secret key sk are inputted into a decryption algorithm KemD detailed below, to output a shared key K. The decryption algorithm KemD is specifically as follows.[0028]

Generate s=C[0029]^dmod n.

Generate G(s), and set K=G(s).[0030]

Output the shared key K.[0031]

When this RSA-KEM algorithm is applied to the cryptosystem where cryptographic communication is performed between its transmission apparatus and reception apparatus, first of all, the transmission apparatus acquires a public key pk of the reception apparatus that is the communication destination, derives a shared key K and a cipher text C by inputting the acquired public key pk into the aforementioned encryption algorithm KemE, and transmits the cipher text C to the reception apparatus.[0032]

Next, the reception apparatus receives the cipher text C from the transmission apparatus, and derives a shared key K by inputting, into the aforementioned decryption algorithm KemD, the cipher text C that is received and a secret key sk that is owned by the reception apparatus. Here, the shared key K that the reception apparatus has derived is the same as that obtained by the transmission apparatus.[0033]

The above-described RSA-KEM algorithm is summarized as follows. In the encryption algorithm KemE, a randomly generated element s is encrypted using a public key pk, to generate a cipher text C. Next, in the decryption algorithm KemD, the cipher text C is decrypted using a secret key sk, to obtain the random element s which is the same as that generated by the encryption algorithm KemE. In both of the encryption algorithm KemE and the decryption algorithm KemD, the same value for s can be inputted in the hash function G. Therefore, each algorithm can derive the same shared key K.[0034]

As a result, the reception apparatus owning the secret key sk can derive a shared key K which is the same as that derived by the transmission apparatus.[0035]

On the contrary, other reception apparatuses that do not know about the secret key sk cannot obtain the element s from the cipher text C, even if they have acquired the public key pk and received the cipher text C. This means that these reception apparatuses cannot derive the same shared key K as that derived by the transmission apparatus.[0036]

As described above, the transmission apparatus and the reception apparatus are enabled to secretly share a shared key K. On this premise, the transmission apparatus encrypts communication content data to be transmitted to the reception apparatus, according to the symmetric key cryptography and using the shared key K, thereby transmitting the generated cipher text. After this, the reception apparatus receives the cipher text, and decrypts this cipher text according to the same symmetric key cryptography and using the same shared key K, to obtain the original communication content data.[0037]

(Patent Reference 1)[0038]

Japanese Laid-Open Patent application 2002-252611[0039]

(Non-Patent Reference 1)[0040]

Tatsuaki Okamoto, Hirosuke Yamamoto “Modern cryptography”, Series/Mathematics in Information Science, Sangyotosho, 1997 (ISBN4-7828-5353-X C3355)[0041]

(Non-Patent Reference 2)[0042]

Jeffery Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem,” Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998.[0043]

(Non-Patent Reference 3)[0044]

Victor Shoup, “A proposal for an ISO standard for public key encryption (version 2.1)”, online, Dec. 20, 2001 (retrieved on Sep. 29, 2002 on the Internet<URL: http://shoup.net/papers/iso-2[0045]_—1.pdf>)

PROBLEM TO BE SOLVED BY THE INVENTION

As described above, in the RSA-KEM algorithm, an element s is inputted in the hash function G to derive the shared key K, where the element s being hard to be derived from the cipher text C unless the secret key is known. Accordingly, the shared key K will not be derived unless the secret key is known.[0046]

However, suppose that a decryption error occurs in the NTRU cryptography, in an attempt to destribute the shared key with use of the NTRU cryptography to which the RSA-KEM algorithm (i.e. key encapsulation mechanism) is applied. If such a decryption error occurs, then the correct element s will not be derived even with use of the secret key, and so the correct shared key K will not be derived. This is a case where different shared keys are derived between the transmission apparatus and the reception apparatus, which leads to a problem that cryptographic communication, from the transmission apparatus to the reception apparatus, is not performed with reliability.[0047]

SUMMARY OF THE INVENTION

The object of the present invention, in view of the above-described problems, is to provide a key agreement system, a shared-key generation apparatus, a shared-key recovery apparatus, a shared-key generating method, a shared-key recovery method, a shared-key generating program, and a shared-key recovery program, which prevents derivation of different keys between the shared-key generation apparatus and the shared-key recovery apparatus.[0048]

So as to achieve the above object, the present invention provides a key agreement system having a shared-key generation apparatus and a shared-key recovery apparatus, each apparatus establishing therein a same shared key in secrecy, where the shared-key generation apparatus includes: a seed-value generating unit operable to generate a seed value; a first shared-key generating unit operable to generate a blind value and a shared key, from the seed value; an encryption unit operable to encrypt the seed value based on the blind value, to generate encryption information; and a transmitting unit operable to transmit the encryption information, and the shared-key recovery apparatus includes: a receiving unit operable to receive the encryption information; a decryption unit operable to decrypt the encryption information, to generate a decryption seed value; a second shared-key generating unit operable to generate a decryption blind value and a decryption shared key, using the decryption seed value and according to a same method as used in the first shared-key generating unit; a re-encryption unit operable to encrypt the decryption seed value based on the decryption blind value, to generate re-encryption information; a judging unit operable to judge, based on the encryption information and the re-encryption information, whether the decryption shared key should be outputted; and an outputting unit operable, when the judging unit has judged affirmatively, to output the decryption shared key.[0049]

According to this construction, the shared-key generation apparatus encrypts the generated seed value to generate encryption information, and transmits the generated encryption information, and the shared-key recovery apparatus generates a decryption seed value from the received encryption information, re-encrypts the decryption seed value to generate re-encryption information, and judges, based on the received encryption information and the re-encryption information newly generated, whether to output the decryption shared key. Therefore, a decryption shared key will be outputted if a shared key generated in the shared-key generation apparatus is identical to a decryption shared key generated in the shared-key recovery apparatus. In other words, the construction has an effect of preventing a decryption shared key from being outputted, if a shared key generated in the shared-key generation apparatus is not identical to a decryption shared key generated in the shared-key recovery apparatus.[0050]

This is realized as follows. In this construction, the shared-key recovery apparatus generates a decryption blind value from the generated decryption seed value, in the same method used in the shared-key generation apparatus. Accordingly, if a correct decryption seed value is generated by the decryption unit of the shared-key recovery apparatus, then re-encryption information generated by the shared-key recovery apparatus is expected to be identical to encryption information generated by the shared-key generation apparatus.[0051]

In addition, the shared-key generation apparatus generates a shared key and a blind value from the seed value, and encrypts the generated seed value based on the generated blind value. Therefore this construction has an effect of scrambling the seed value.[0052]

Here, the shared-key generation apparatus may further include: an obtaining unit operable to obtain a content; and an encryption unit operable to encrypt the obtained content using the shared key, to generate an encrypted content, the transmitting unit may further transmit the encrypted content, the receiving unit may further receive the encrypted content, and the shared-key recovery apparatus may further include: a decryption unit operable to decrypt the received encrypted content using the decryption shared key, to generate a decrypted content; and an outputting unit operable to output the decrypted content.[0053]

According to this construction, the shared-key generation apparatus encrypts the obtained content using the generated shared key, to generate an encrypted content, and the shared-key recovery apparatus decrypts the received encrypted content, using the outputted decryption shared key, to generate a decrypted content. Therefore, the construction has an effect of transmitting a content from the shared-key generation apparatus to the shared-key recovery apparatus, in secrecy.[0054]

In addition, the present invention is a shared-key generation apparatus that notifies a destination apparatus about a shared key in secrecy, the shared-key generation apparatus including: a seed-value generating unit operable to generate a seed value; a shared-key generating unit operable to generate a blind value and a shared key, from the seed value; an encryption unit operable to encrypt the seed value based on the blind value, to generate encryption information; and a transmitting unit operable to transmit the encryption information.[0055]

According to this construction, the shared-key generation apparatus generates a blind value from the seed value, and encrypts the generated seed value, based on the generated blind value. Therefore there is an effect of scrambling the seed value.[0056]

Here, the shared-key generating unit may perform a one-way function on the seed value, to generate a functional value, and generate the blind value and the shared key from the functional value, the encryption unit may include: a public-key obtaining subunit operable to obtain a public key; and a public-key encryption subunit operable to perform a public-key encryption algorithm on the seed value, using the public key and the blind value, to generate an encryption seed value as the encryption information.[0057]

According to this construction, the shared-key generation apparatus performs a one-way function on the seed value to generate a functional value, and generates the blind value and the shared key from the generated functional value. Therefore, it can be expected that the destination apparatus that receives the encryption information generates a blind value and a shared key respectively being the same as the blind value and the shared key, from the seed value that the destination apparatus has decrypted using the same method.[0058]

In addition, the shared-key generation apparatus obtains a public key, and performs a public-key encryption algorithm on the seed value, using the obtained public key, to generate the encryption information. Therefore, the construction enables adoption of more secured public-key cryptosystem.[0059]

Here, the public-key encryption algorithm may conform to an NTRU cryptosystem, the public-key obtaining subunit may obtain a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, the public-key encryption subunit may generate a seed-value polynomial from the seed value, generate a blind-value polynomial from the blind value, and encrypt the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the encryption seed value, and the transmitting unit may transmit the encryption seed-value polynomial as the encryption seed value.[0060]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm.[0061]

Here, the encryption unit may include: a public-key obtaining subunit operable to obtain a public key; a public-key encryption subunit operable to generate a blind value, perform the public-key encryption algorithm on the seed value using the public key and the blind value, to generate a public-key cipher text; and a function subunit operable to perform a second one-way function on at least one of the seed value, the blind value, and the shared key, to generate a second functional value, and the encryption unit may generate the encryption information that includes the public-key cipher text and the second functional value.[0062]

According to this construction, the shared-key generation apparatus performs a second one-way function on the generated seed value, to generate a second functional value, and transmits the encryption information that includes the second functional value. Therefore, the destination apparatus can perform judgment, using the second functional value, on whether to output a decryption shared key, without performing re-encryption.[0063]

Here, the shared-key generating unit may perform a one-way function on the seed value, to generate a functional value, and generate the blind value and the shared key from the functional value.[0064]

According to this construction, the shared key is generated from the first functional value obtained by performing a first one-way function on the seed value. Therefore even when the seed value is revealed, it is still difficult to estimate the shared key.[0065]

Here, the shared-key generating unit may perform a first one-way function on the seed value, to generate a first functional value, and generate the shared key from the first functional value, instead of generating the blind value and the shared key.[0066]

According to this construction, the shared key is generated from the first functional value obtained by performing a first one-way function on the seed value. Therefore even when the seed value is revealed, it is still difficult to estimate the shared key.[0067]

Here, the public-key encryption algorithm may conform to an NTRU cryptosystem, the public-key obtaining subunit may obtain a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, the public-key encryption subunit may generate a seed-value polynomial from the seed value, generate a blind-value polynomial from the blind value, encrypt the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the public-key cipher text, and the encryption unit may generate the encryption information that includes the encryption seed-value polynomial as the public-key cipher text and the second functional value.[0068]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm.[0069]

Here, the shared-key generating unit may perform a one-way function on the seed value, to generate a functional value, and generate a verification value, the blind value, and the shared key, from the functional value, the encryption unit may include: a public-key obtaining subunit operable to obtain a public key; a first encryption subunit operable to perform a public-key encryption algorithm on the verification value, using the public key and the blind value, to generate a first cipher text; and a second encryption subunit operable to perform, on the seed value, a computation algorithm different from the public-key encryption algorithm, to generate a second cipher text, and the encryption unit may generate the encryption information that includes the first cipher text and the second cipher text.[0070]

According to this construction, the shared-key generation apparatus performs a public-key encryption algorithm on the generated verification value, using the obtained public key and the generated blind value, to generate a first cipher text, performs a different computation algorithm on the generated seed value, based on the generated verification value, to generate a second cipher text, and transmits the encryption information that includes the first cipher text and the second cipher text. Since the construction uses a two-phase algorithm as such, chances of the first and second cipher texts being attacked and decrypted will be lowered.[0071]

Here, the public-key encryption algorithm may conform to an NTRU cryptosystem, the public-key obtaining subunit may obtain a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, the first encryption subunit may generate a verification-value polynomial from the verification value, generate a blind-value polynomial from the blind value, and encrypt the verification-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the verification-value polynomial, to generate an encryption verification-value polynomial as the first cipher text, and the encryption unit may generate the encryption information that includes the encryption verification-value polynomial as the first cipher text and the second cipher text.[0072]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm.[0073]

Here, the different computation algorithm may be a symmetric key encryption algorithm, and the second encryption subunit may perform the symmetric key encryption algorithm on the seed value using the verification value as a key, to generate the second cipher text.[0074]

Alternatively, the different computation algorithm may be bitwise exclusive-or, and the second encryption subunit may perform the bitwise exclusive-or on the verification value and the seed value, to generate the second cipher text.[0075]

Still alternatively, the different computation algorithm may be addition, and the second encryption subunit may perform the addition on the verification value and the seed value, to generate the second cipher text.[0076]

Still alternatively, the different computation algorithm may be multiplication, and the second encryption subunit may perform the multiplication on the verification value and the seed value, to generate the second cipher text.[0077]

According to these constructions, symmetric key encryption algorithm, bitwise exclusive-or, addition, and multiplication may be adopted as the different computation algorithm.[0078]

Here, the seed-value generating unit may generate a random number, as the seed value.[0079]

According to this construction, the shared-key generation apparatus generates a random number, and sets the generated random number as the seed value. This realizes generation of a seed value which is different from another seed value that has been generated first during a series of processes as follows: generating a seed value, generating a blind value and a shared key, generating encryption information, and transmitting the encryption information. Accordingly, the encryption information will be different each time of transmission from the shared-key generation apparatus. Therefore, even if an unauthorized third party illegally intercepts and records the encryption information, it is quite difficult for him to guess an original seed value, from the recorded encryption information.[0080]

Here, the shared-key generating unit may perform a one-way function on the seed value, to generate a functional value, and generate the blind value and the shared key from the functional value.[0081]

According to this construction, the shared-key generation apparatus performs a one-way function on the seed value to generate a functional value, and generates the blind value and the shared key from the generated functional value. Therefore it can be expected that the destination apparatus that receives the encryption information generates a blind value and a shared key respectively being the same as the blind value and the shared key, from the seed value that the destination apparatus has decrypted using the same method.[0082]

Here, the one-way function may be a hash function, and the shared-key generating unit may perform the hash function on the seed value.[0083]

According to this construction, the shared-key generation apparatus performs a hash function on the seed value. Therefore a functional value is a ssuredly obtained.[0084]

Here, the shared-key generating unit may generate the blind value by setting a part of the functional value as the blind value, and generate the shared key by setting another part of the functional value as the shared key.[0085]

According to this construction, the shared-key generation apparatus sets a part of the generated functional value as the blind value, and sets another part thereof as the shared key. Therefore the blind value and the shared key will be obtained assuredly from a functional value.[0086]

Here, the shared-key generation apparatus may further include: an obtaining unit operable to obtain a content; and an encryption unit operable to encrypt the obtained content using the shared key, to generate an encrypted content, where the transmitting unit further transmits the encrypted content.[0087]

According to this construction, the shared-key generation apparatus encrypts the obtained content using the generated shared key to generate an encrypted content, and transmits the encrypted content. Accordingly, there is an effect of transmitting a content decryptable by the destination apparatus, in secrecy.[0088]

In addition, the present invention is a shared-key recovery apparatus that receives a shared key from a shared-key generation apparatus in secrecy, the shared-key generation apparatus generating a seed value, generating a blind value and a shared key from the seed value, encrypting the seed value based on the blind value to generate encryption information, and transmitting the encryption information, the shared-key recovery apparatus including: a receiving unit operable to receive the encryption information; a decryption unit operable to decrypt the encryption information, to generate a decryption seed value; a shared-key generating unit operable to generate a decryption blind value and a decryption shared key, using the decryption seed value and according to a same shared-key generating method used in the shared-key generation apparatus; a re-encryption unit operable to encrypt the decryption seed value based on the decryption blind value, to generate re-encryption information; a judging unit operable-to judge, based on the encryption information and the re-encryption information, whether the decryption shared key should be outputted; and an outputting unit operable, when the judging unit has judged affirmatively, to output the decryption shared key.[0089]

According to this construction, the shared-key recovery apparatus generates a decryption seed value from the received encryption information, re-encrypts the generated decryption seed value, to generate re-encryption information, and judges, based on the received encryption information and the re-encryption information newly generated, whether to output the decryption shared key. Therefore, a decryption shared key will be outputted if a shared key generated in the shared-key generation apparatus is identical to a decryption shared key generated in the shared-key recovery apparatus. In other words, the construction has an effect of preventing a decryption shared key from being outputted, if a shared key generated in the shared-key generation apparatus is not identical to a decryption shared key generated in the shared-key recovery apparatus.[0090]

Here, the shared-key generation apparatus may perform a one-way function on the seed value to generate a functional value, generate the blind value and the shared key from the functional value, obtain a public key, perform a public-key encryption algorithm on the seed value using the public key and the blind value, to generate an encryption seed value as the encryption information, and transmit the encryption seed value, the receiving unit may receive the encryption seed value as the encryption information, the decryption unit may include: a secret-key obtaining subunit operable to obtain a secret key that corresponds to the public key; and a public-key decryption subunit operable to perform, on the received encryption seed value, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, using the obtained secret key, to generate the decryption seed value, the shared-key generating unit may perform the one-way function on the decryption seed value to generate a decryption functional value, and generate the decryption blind value and the decryption shared key from the decryption functional value, the re-encryption unit may include: a public-key obtaining subunit operable to obtain the public key; and a re-encryption subunit operable to perform the public-key encryption algorithm on the decryption seed value using the public key and the decryption blind value, to generate a re-encryption seed value as the re-encryption information, and the judging unit may judge whether the encryption seed value is identical to the re-encryption seed value, and when judging affirmatively, determine that the decryption shared key should be outputted.[0091]

According to this construction, the shared-key recovery apparatus judges whether the encryption seed value is identical to the re-encryption seed value. Since judgment as to whether to output a decryption shared key results in affirmative when these values are identical, there is an effect of assuredly performing the outputting judgment.[0092]

Here, the public-key encryption algorithm and the public-key decryption algorithm may conform to an NTRU cryptosystem, the shared-key generation apparatus may obtain a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, generate a seed-value polynomial from the seed value, generate a blind-value polynomial from the blind value, encrypt the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the encryption seed value, and transmit the encryption seed-value polynomial as the encryption seed value, the receiving unit may receive the encryption seed-value polynomial as the encryption seed value, the secret-key obtaining subunit may obtain a secret-key polynomial generated according to the key-generation algorithm of the NTRU cryptosystem, as the secret key, the public-key decryption subunit may decrypt the received encryption seed-value polynomial according to a decryption algorithm of the NTRU cryptosystem and using the obtained secret-key polynomial as a key, to generate a decryption seed-value polynomial, and generates the decryption seed value from the decryption seed-value polynomial, the public-key obtaining subunit may obtain the public-key polynomial as the public key, the re-encryption subunit may generate a seed-value polynomial from the decryption seed value, generate a blind-value polynomial from the decryption blind value, and encrypt the seed-value polynomial according to the encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate a re-encryption seed-value polynomial, and the judging unit may judge whether the encryption seed-value polynomial is identical to the re-encryption seed-value polynomial.[0093]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm and the public-key decryption algorithm.[0094]

Here, the shared-key generation apparatus may obtain a public key, generate a blind value, perform a public-key encryption algorithm on the seed value using the public key and the blind value to generate a public-key cipher text, perform a second one-way function on at least one of the seed value, the blind value, and the shared key to generate a second functional value, generate the encryption information that includes the public-key cipher text and the second functional value, and transmit the encryption information, the receiving unit may receive the encryption information that includes the public-key cipher text and the second functional value, the decryption unit may include: a secret-key obtaining subunit operable to obtain a secret key that corresponds to the public key; a public-key decryption subunit operable to perform, on the public-key cipher text included in the received encryption information, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, to generate a decryption seed value; and a function subunit operable to perform the second one-way function on at least one of the decryption seed value, the decryption blind value, and the decryption shared key, to generate a decryption second functional value, and the judging unit may judge whether the second functional value included in the received encryption information is identical to the decryption second functional value instead of performing judging based on the encryption information and the re-encryption information, and when judging affirmatively, determine that the decryption shared key should be outputted.[0095]

According to this construction, instead of basing the encryption information and the re-encryption information, the judgment is performed as to whether the second functional value included in the received encryption information is identical to the generated decryption second functional value, then decides to output the decryption shared key when the mentioned values are judged to be identical. Therefore, there is an effect of assuredly performing the outputting judgment.[0096]

Here, the shared-key generation apparatus may perform a one-way function on the seed value to generate a functional value, and generate the blind value and the shared key from the functional value, and the shared-key generating unit may perform the first one-way function on the decryption seed value to generate a decryption functional value, and generate the decryption blind value and the decryption shared key from the decryption functional value.[0097]

According to this construction, the decryption shared key is generated from the decryption functional value obtained by performing the first one-way function on the decryption seed value. Therefore even when the decryption seed value is revealed, it is still difficult to estimate the decryption shared key.[0098]

Here, the shared-key generation apparatus may perform a first one-way function on the seed value to generate a first functional value, and generate the shared key from the first functional value, instead of generating the blind value and the shared key, and the shared-key generating unit may perform the first one-way function on the decryption seed value to generate a decryption functional value, and generate the decryption shared key from the decryption functional value, instead of generating the decryption blind value and the decryption shared key.[0099]

According to this construction, the decryption shared key is generated from the decryption functional value obtained by performing the first one-way function on the decryption seed value. Therefore even when the decryption seed value is revealed, it is still difficult to estimate the decryption shared key.[0100]

Here, the public-key encryption algorithm and the public-key decryption algorithm may conform to an NTRU cryptosystem, the shared-key generation apparatus may obtain a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, generate a seed-value polynomial from the seed value, generate a blind-value polynomial from the blind value, encrypt the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem using the public-key polynomial as a key and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the public-key cipher text, and generate the encryption information that includes the encryption seed-value polynomial as the public-key cipher text and the second functional value, the secret-key obtaining subunit may obtain a secret-key polynomial generated according to the key-generation algorithm of the NTRU cryptosystem, as the secret key, and the public-key decryption subunit may generate a public-key cipher-text polynomial from the public-key ciphertext, decrypts the public-key cipher-text polynomial according to a decryption algorithm of the NTRU cryptosystem using the secret-key polynomial as a key to generate a decryption seed-value polynomial, and generate the decryption seed value from the decryption seed-value polynomial.[0101]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm and the public-key decryption algorithm.[0102]

According to this construction, a decryption verification value is generated by performing, on the first cipher text, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, and based on thus generated decryption verification value, the computation algorithm is performed on the second cipher text, to generate a decryption seed value. Since the construction uses a two-phase algorithm as such, chances of the first and second cipher texts being attacked and decrypted will be lowered.[0104]

According to this construction, an NTRU encryption algorithm may be adopted as the public-key encryption algorithm and the public-key decryption algorithm.[0106]

Here, the different computation algorithm may be a symmetric key encryption algorithm, and the computation algorithm for performing the inverse computation may be a corresponding symmetric key decryption algorithm, and the computation decryption subunit may perform the symmetric key decryption algorithm on the second cipher text, using the decryption verification value as a key, to generate the decryption seed value.[0107]

Alternatively, the different computation algorithm and the computation algorithm for performing the inverse computation may be bitwise exclusive-or, and the computation decryption subunit may perform the bitwise exclusive-or on the decryption verification value and the second cipher text, to generate the decryption seed value.[0108]

Still alternatively, the different computation algorithm may be addition and the computation algorithm for performing the inverse computation be subtraction, and the computation decryption subunit may perform the subtraction on the decryption verification value and the second cipher text, to generate the decryption seed value.[0109]

Still alternatively, the different calculation algorithm may be multiplication and the computation algorithm for performing the inverse computation be division, and the computation decryption subunit may perform the division on the decryption verification value and the second cipher text, to generate the decryption seed value.[0110]

According to these constructions, symmetric key decryption algorithm, bitwise exclusive-or, subtraction, and division may be adopted as the computation algorithm for performing the inverse computation.[0111]

Here, the shared-key generating unit may perform a one-way function on the decryption seed value to generate a functional value, and generate the decryption blind value and the decryption shared key from the functional value.[0112]

According to this construction, a one-way function is performed on a seed value to generate a functional value, and a decryption blind value and a decryption shared key are generated from the generated functional value. Therefore, the same method as used in the shared-key generation apparatus is used.[0113]

Here, the one-way function may be a hash function, and the shared-key generating unit may perform the hash function on the decryption seed value.[0114]

According to this construction, a hash function is performed on the decryption seed value. Therefore, a functional value will be assuredly obtained.[0115]

Here, the shared-key generating unit may generate the decryption blind value by setting a part of the functional value as the decryption blind value, and generate the decryption shared key by setting another part of the functional value as the decryption shared key.[0116]

According to this construction, a part of the generated functional value is set as the decryption blind value, and another part thereof as the decryption shared key. Therefore, the decryption blind value and the decryption shared key will be assuredly obtained from the functional value.[0117]

Here, the shared- key generation apparatus may further obtain a content, encrypt the obtained content using the shared key to generate an encrypted content, and transmit the encrypted content, and the shared-key recovery apparatus may further include: a content receiving unit operable to receive the encrypted content; a decryption unit operable to decrypt the received encrypted content using the outputted decryption shared key, to generate a decrypted content; and a playback unit operable to playback the decrypted content.[0118]

According to this construction, the shared-key recovery apparatus decrypts the received encrypted content, using the outputted decryption shared key, to generate a decrypted content. Therefore, there is an effect that a content is received from the shared-key generation apparatus, in secrecy.[0119]

BRIEF DESCRIPTION OF THE DRAWINGS

These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings which illustrate a specific embodiment of the invention. In the drawings:[0120]

FIG. 1 is a conceptual diagram showing the structure of a[0121]

content distribution system

10, and how its components are connected to each other;

FIG. 2 is a block diagram showing the structure of an[0122]

encryption apparatus

110;

FIG. 3 is a block diagram showing the structure of a[0123]

decryption apparatus

120;

FIG. 4 is a process-block diagram showing the operations of the[0124]

encryption apparatus

110 and thedecryption apparatus120;

FIG. 5 is a flowchart showing the operations of the[0125]

encryption apparatus

110 and thedecryption apparatus120;

FIG. 6 is a block diagram showing the structure of an[0126]

encryption apparatus

110b;

FIG. 7 is a block diagram showing the structure of a[0127]

decryption apparatus

120b;

FIG. 8 is a process-block diagram showing the operations of the[0128]

encryption apparatus

110band thedecryption apparatus120b;

FIG. 9 is a block diagram showing the structure of an[0129]

encryption apparatus

110c;

FIG. 10 is a block diagram showing the structure of a[0130]

decryption apparatus

120c;

FIG. 11 is a process-block diagram showing the operations of the[0131]

encryption apparatus

110cand thedecryption apparatus120c;

FIG. 12 is a process-block diagram showing the operations of a modification example for the[0132]

encryption apparatus

110cand thedecryption apparatus120c;

FIG. 13 is a block diagram showing the structure of an[0133]

encryption apparatus

110d;

FIG. 14 is a block diagram showing the structure of a[0134]

decryption apparatus

120d;

FIG. 15 is a flowchart showing the operations of the[0135]

encryption apparatus

110dand thedecryption apparatus120d;

FIG. 16 is a process-block diagram showing the operations of the[0136]

encryption apparatus

110dand thedecryption apparatus120d;

FIG. 17 is a block diagram showing the structure of an[0137]

encryption apparatus

110e;

FIG. 18 is a block diagram showing the structure of a[0138]

decryption apparatus

120e;

FIG. 19 is a process-block diagram showing the operations of the[0139]

encryption apparatus

110eand thedecryption apparatus120e; and

FIG. 20 is a process-block diagram showing the operations of a modification example for the[0140]

encryption apparatus

110eand thedecryption apparatus120e.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

1. First Embodiment[0141]

The following describes a[0142]

content distribution system

10, as one embodiment relating to the present invention. Thecontent distribution system10 is a cryptographic communication system that performs cryptographic communication using the NTRU cryptosystem and performing key distribution according to the key encapsulation mechanism.

1.1 NTRU Cryptosystem[0143]

As follows, the NTRU cryptosystem used in the[0144]

content distribution system

10 is briefly described. The NTRU cryptosystem is a public-key cryptosystem that performs encryption/decryption using polynomial operation.

Note that the NTRU cryptosystem and the method that the NTRU cryptosystem adopts for generating public key and secret key are detailed in the non-patent reference 2.[0145]

(1) System Parameter of NTRU Cryptosystem[0146]

In the NTRU cryptosystem, system parameters N, p, q (that are integers) exist, and the encryption apparatus and the decryption apparatus, which are detailed later, have these system parameters.[0147]

In the mentioned reference, three examples of system parameters are listed, namely, (N, p, q)=(107, 3, 64), (N, p, q)=(167, 3, 128), and (N, p, q)=(503, 3, 256).[0148]

Hereinafter in this embodiment, the system parameter N=167 is used for description.[0149]

(2) Polynomial Operation in NTRU Cryptosystem[0150]

As aforementioned, the NTRU cryptosystem is a public-key cryptosystem that performs encryption/decryption using polynomial operation.[0151]

The polynomial used in the NTRU cryptosystem is N−1 degrees for the system parameter N. When, for example, N=5, the polynomial is X[0152]⁴+X³+1, and the like. Here, X^ameans the ath power of X.

Furthermore, a public key h, a secret key f, a plaintext m, a random number r, and a cipher text c, which are used in encryption or decryption, are expressed as polynomial that is N−1 degree or below. (hereinafter, each are referred to as “public-key polynomial h”, “secret-key polynomial f”, “plaintext polynomial m”, “random-number polynomial r”, and “cipher text polynomial c”.)[0153]

The polynomial operation is arranged to yield a result being a polynomial at N−1 degree or below, by using the relational expression X[0154]^N=1, for the system parameter N.

For example, when N=5, the product of X[0155]⁴+X²+1 and X³+X is calculated as follows, using the relational expression X⁵=1, where the product between polynomials is represented as *, and the product between an integer and a polynomial as •.

As in the above, the polynomial operation is arranged always to yield a polynomial at N−1 degrees or below.[0156]

(3) Encryption in NTRU Cryptosystem[0157]

The encryption apparatus, which will be described later, performs encryption according to the NTRU cryptosystem, as described as follows.[0158]

In encryption, the encryption algorithm E, which is a polynomial computation, is performed on the plaintext polynomial m, using a random-number polynomial r and a public-key polynomial h (which are detailed later), to generate a cipher text polynomial c=E(m, r, h).[0159]

This E(m, r, h) is a result of the polynomial operation, which is obtained by inputting, in the NTRU cryptographic encryption algorithm E, the plaintext polynomial m, the random-number polynomial r, and the public-key polynomial h. The encryption algorithm E is detailed in the non-patent reference 2, therefore is not described here.[0160]

Note that in the NTRU cryptosystem, a parameter d for generating the random polynomial r is determined in advance. The random polynomial r is selected so that, among the terms constituting the random-number polynomial r, the coefficient for d terms is 1, the coefficient for other d terms is −1, and the coefficient for the rest of the terms is 0.[0161]

To summarize, the random-number polynomial r is a polynomial being N−1 degrees or below, and N coefficients exit for N terms from the degree 0 (constant term) to the degree N−1. The random-number polynomial r is selected so that, out of these N coefficients, d coefficients are 1, other d coefficients are −1, and (N−2d) coefficients are 0.[0162]

In the non-patent reference[0163]2, when the parameter N=167, d=18. That is, the random polynomial r is selected so that 18 coefficients are 1, 18 coefficients are −1, and 131 coefficients (i.e. 167-36) are 0.

(4) Decryption in NTRU Cryptosystem[0164]

The decryption apparatus, which will be described later, performs decryption according to the NTRU cryptosystem, as described as follows.[0165]

In decryption, the decryption algorithm D, which is a polynomial calculation, is performed on the cipher text polynomial c, using a secret-key polynomial f, to generate a decrypted text polynomial m′=D(c, f).[0166]

This D (c, f)is a result of the polynomial operation, which is obtained by inputting, in the NTRU cryptographic decryption algorithm D, the cipher text polynomial c and the secret-key polynomial f. The decryption algorithm D is detailed in the non-patent reference 2, therefore is not described here.[0167]

(5) Decryption Error in NTRU Cryptosystem[0168]

In this NTRU cryptosystem, it sometimes happens that the generated decrypted text polynomial m′ is different from the plaintext polynomial m. In such a case, the correct plaintext m will not be obtained in decryption. This occurrence is called “decryption error”.[0169]

1.2 Structure of[0170]

Content Distribution System

10

The[0171]

content distribution system

10, as shown in FIG. 1, is comprised of acontent server apparatus140, anencryption apparatus110, adecryption apparatus120, aplayback apparatus150, and amonitor155. Thecontent server apparatus140 and theencryption apparatus110 are connected to each other, via adedicated circuit20. Theencryption apparatus110 and thedecryption apparatus120 are connected to each other, via theInternet130. Theplayback apparatus150 is connected to thedecryption apparatus120 and to themonitor155 that contains therein a speaker. Theencryption apparatus110 is equipped with amemory card160, and thedecryption apparatus120 is equipped with amemory card170.

The[0172]

content server apparatus

140 transmits a content comprised of image and audio, such as a movie, to theencryption apparatus110 via thededicated circuit20.

The[0173]

encryption apparatus

110 and thedecryption apparatus120 respectively generate a shared key K and a shared key K′ that are identical to each other. Next, theencryption apparatus110 encrypts a received content using the shared key K to generate an encrypted content, and transmits the encrypted content. Thedecryption apparatus120 receives the encrypted content, and decrypts the received encrypted content to generate a playback content. Theplayback apparatus150 generates an image signal and an audio signal, from the playback content, and themonitor155 displays the images and outputs the audio.

1.3 Structure of[0174]

Content Server Apparatus

140

The[0175]

content server apparatus

140 is a computer system (unshown in any drawing), that is comprised of a microprocessor, a ROM, a RAM, a hard disk unit, a display unit, a communication unit, a key board, a mouse, and the like. The RAM and the hard disk unit record thereon a computer program. Thecontent server apparatus140 performs part of its function, by operation of the microprocessor according to the computer program.

The[0176]

content server apparatus

140 prestores the content, where the content is made up of a plurality of partial contents mi(1=<i=<n). Thecontent server apparatus140 reads the partial contents mi, in accordance with the request by theencryption apparatus110, and transmits the read partial contents mi to theencryption apparatus110 via thededicated circuit20.

1.4 Structure of[0177]

Memory Card

160 andMemory Card170

The[0178]

memory card

160 is a card-type storage apparatus that adopts a flash memory as a recording medium. Thememory card160 prestores therein a public-key polynomial h.

Meanwhile, the[0179]

memory card

170 is a storage apparatus that is a card-type just like thememory card160, and prestores therein a secret-key polynomial f and the public-key polynomial h.

Here, the secret-key polynomial f and the public-key polynomial h are generated according to the NTRU cryptosystem, and correspond to each other.[0180]

1.5 Structure of[0181]

Encryption Apparatus

110

The[0182]

encryption apparatus

110 is, as shown in FIG. 2, comprised of a public-key input unit111, a random-number generating unit112, afirst function unit113, anencryption unit114, afirst transmitting unit117, a shared-key encryption unit118, and asecond transmitting unit119.

The[0183]

encryption apparatus

110 is specifically a computer system comprised of a microprocessor, a ROM, a RAM, and a communication unit, and so on. The RAM stores therein a computer program. Theencryption apparatus110 pursues its function, by operation of the microprocessor according to the computer program.

111

111 reads, from thememory card160, the public-key polynomial h for thedecryption apparatus120, and outputs the read public-key polynomial h to theencryption unit114.

(2) Random-[0186]

Number Generating Unit

112

The random-[0187]

number generating unit

112 generates a random number s, as a seed value on which the generation of the shared key bases, and outputs the generated random number s to thefirst function unit113 and theencryption unit114.

113

113 receives a random number s from the random-number generating unit112, and generates the functional value G(s). Here, the function G is a hash function having output length of 2 k bits. Note that the hash function is one of the one-way functions. Next, thefirst function unit113 sets the k highest-order bits of the functional value G(s) as a random-number value u, and the k lowest-order bits of the G(s) as a shared key K, to generate the shared key K and the random-number value u from the generated functional value G(s). Then, thefirst function unit113 outputs the generated random-number value u to theencryption unit114, and outputs the shared key K to the shared-key encryption unit118.

114

114 receives the public-key polynomial h from the public-key input unit111, receives the random number s from the random-number generating unit112, and receives the random-number value u from thefirst function unit113. Next, as described below, theencryption unit114 generates a first cipher text c1 of the random number s, using the public-key polynomial h and the random-number value u. Here, the random-number value u is a blind value, and is used for making the random number s unclear, the random number s being a target of encryption.

The[0192]

encryption unit

114 generates a random-number polynomial r having the following characteristic, so that it is uniquely defined by the random-number value u. The characteristic of the random-number polynomial r is such that, with respect to the parameter d of NTRU cryptosystem, the coefficient of d terms is 1, the coefficient of d terms is −1, and the coefficient of the rest of the terms is 0.

For example, the[0193]

encryption unit

114 sets the random-number value u as a default value of pseudo-random number system (random-number seed), and thereby generates 2d pseudo-random numbers, from among {0, 1, . . . , N−1}, that do not overlap with each other. Then, theencryption unit114 sets the coefficient of d terms of degree shown by each of the first d pseudo-random numbers as 1. Theencryption unit114 sets the coefficient of d terms of degree shown by each of the rest of d pseudo-random numbers as −1, and the coefficient of the other terms of degree as 0.

Next, the[0194]

encryption unit

114 constructs the random-number polynomial sp, so that the element for each bit of an N-bit bit sequence in which the random number s is represented in binary form, corresponds to the coefficient of a different one of the terms of the random-number polynomial sp. This is for applying the random number s to the encryption algorithm E of the NTRU cryptosystem. For example, the value of the b-th lowest bit of the random number s will be set as the coefficient of the term X^b. Concretely, when s=10010 (representation in bit form), the random-number polynomial sp=X⁵+X²is generated.

Next, the[0195]

encryption unit

114 performs the encryption algorithm E on the random-number polynomial sp, using the public-key polynomial h and the random-number polynomial r, to generate the following:

The first cipher text c[0196]1=the cipher text polynomial E(sp, r, h).

Next, the[0197]

encryption unit

114 outputs the generated first cipher text c1 to thefirst transmitting unit117.

Note that in FIG. 2, each block representing a respective constituting part of the[0198]

encryption apparatus

110 is connected to the other blocks via a connection line. Here, each connection line signifies a path via which signals and information are conveyed. Further, among the plurality of connection lines that are connected to the block for theencryption unit114, one that has a key mark on the connection line signifies a path via which information as a key is conveyed to theencryption unit114. The same thing applies to the block for the shared-key encryption unit118. This also applies to the other diagrams.

(5)[0199]

First Transmitting Unit

117

The[0200]

first transmitting unit

117 receives the first cipher text c1 from theencryption unit114, and transmits the first cipher text c1 to thedecryption apparatus120 via theInternet130.

118

118 has a symmetric key cryptographic algorithm Sym, such as the DES cryptosystem.

Generally, in the symmetric key cryptography, an apparatus at the encryption side performs a symmetric key cryptographic algorithm Sym on a plaintext m, using an encryption key K, to generate a cipher text=Sym(m, K), while an apparatus at the decryption side performs a symmetric key cryptographic algorithm Sym on the cipher text c, using an encryption key K, to generate a decrypted text m′=Sym(c, K) Here, if the encryption key K used in generation of the cipher text is identical to the encryption key K used in generation of the decrypted text, then m′=m holds. Note that the symmetric key cryptography and the DES cryptosystem are detailed in the[0203]non-patent reference 1, therefore detailed description thereof is omitted here.

Next, the shared-[0204]

key encryption unit

118 outputs the shared-key cipher text Ci(1=<i=<n) to thesecond transmitting unit119.

(7)[0205]

Second Transmitting Unit

119

The[0206]

second transmitting unit

119 receives the shared-key cipher text Ci(1=<i=<n), and transmits the received shared-key cipher text Ci(1=<i=<n) to thedecryption apparatus120 via theInternet130.

1.6 Structure of[0207]

Decryption Apparatus

120

The[0208]

decryption apparatus

120 is, as shown in FIG. 3, comprised of a secret-key input unit121, afirst receiving unit122, adecryption unit123, asecond function unit126, acomparison unit127, a shared-key decryption unit128, and asecond receiving unit129.

The[0209]

decryption apparatus

120 is specifically a computer system just like theencryption apparatus110. Thedecryption apparatus120 pursues its function, by operation of its microprocessor according to the computer program.

121

121 reads, from thememory card170, the secret-key polynomial f and the public-key polynomial h, which are for thedecryption apparatus120, and outputs the read secret-key polynomial f to thedecryption unit123, and the read public-key polynomial h to thecomparison unit127.

122

122 receives the first cipher text c1 from theencryption apparatus110 via theInternet130, and outputs the received first cipher text c1 to thedecryption unit123.

123

123 receives the secret-key polynomial f from the secret-key input unit121, and receives the first cipher text c1 from thefirst receiving unit122. Then, as shown as follows, thedecryption unit123 decrypts the first cipher text c1 according to the NTRU cryptography and using the secret-key polynomial f, to generate the decryption random number s′.

The[0216]

decryption unit

123 performs the decryption algorithm D on the first cipher text c1 using the secret-key polynomial f, to generate the decryption random-number polynomial sp′=D(c1, f). Next, since the decryption random-number polynomial sp′ is an NTRU cryptographic decrypted text, and is represented in polynomial form, thedecryption unit123 generates a decryption random number s′ so that the coefficient for each term of the decryption random-number polynomial sp′ corresponds to each element of the N-bit bit sequence in which the decryption random number s′ is represented in binary form. For example, the coefficient of the term X^bwhich is b-th degree of the decryption random-number polynomial sp′ will be the element of the b-th lowest-order bit of the decryption random number s′.

Concretely, when the decryption random-number polynomial sp′=X[0217]⁵+X², the decryption random number s′=10010(representation in bit form) is generated.

Next, the[0218]

decryption unit

123 outputs the received first cipher text c1 and the generated random number s′ to thecomparison unit127. Thedecryption unit123 also outputs the generated random number s′ to thesecond function unit126.

126

126 has an algorithm for a function G that is the same as the function owned by thefirst function unit113.

The[0221]

second function unit

126 receives the decryption random number s′ from thedecryption unit123, and generates the functional value G (s′) for the decryption random number s′, in the same manner as in thefirst function unit113. Next, thesecond function unit126 generates a random-number value u′ and a shared key K′, from the functional value G(s′), and outputs the random-number value u′ and the shared key K′ that have been generated, to thecomparison unit127.

127

127 is, as shown in FIG. 3, comprised of anencryption unit127xand acomparison computation unit127y.

The[0224]

encryption unit

127xreceives the public-key polynomial h from the secret-key input unit121, receives the decryption random number s′ from thedecryption unit123, and receives the random-number value u′ from thesecond function unit126. Next, theencryption unit127x, just as theencryption unit114, encrypts the decryption random number s′ using the public-key polynomial h and the random-number value u′, to generate a first re-cipher text c1′, and outputs the first re-cipher text c1′ to thecomparison computation unit127y.

The[0225]

comparison computation unit

127yreceives the first cipher text c1 from thedecryption unit123, receives the shared key K′ from thesecond function unit126, and receives the first re-cipher text c1′ from theencryption unit127x. Then, thecomparison computation unit127ycompares the first cipher text c1 and the first re-cipher text c1′, and judges whether they are identical. When they are judged to be identical, thecomparison computation unit127youtputs the received shared key K′ to the shared-key decryption unit128. When they are judged not to be identical, thecomparison computation unit127ydoes not output the shared key K′.

(6)[0226]

Second Receiving Unit

129

The[0227]

second receiving unit

129 receives the shared-key cipher text Ci (1=<i=<n), and outputs the received shared-key cipher text Ci (1=<i=<n) to the shared-key decryption unit128 via theInternet130.

128

128 prestores a symmetric key cryptographic algorithm Sym that is the same as the symmetric key cryptographic algorithm Sym owned by the shared-key encryption unit118.

The shared-[0230]

key decryption unit

128 receives the shared key K′ from thecomparison unit127, and receives the shared-key cipher text Ci (1=<i=<n) from thesecond receiving unit129. Then the shared-key decryption unit128 performs the symmetric key cryptographic algorithm Sym on the shared-key cipher text Ci (1=<i=<n), using the received shared key K′, to generate the decrypted text mi′=Sym(Ci, K) (1=<i=<n).

Next, the shared-[0231]

key decryption unit

128 outputs the generated decrypted text mi′((1=<i=<n) to theplayback apparatus150.

1.7[0232]

Playback Apparatus

150 andMonitor155

The[0233]

playback apparatus

150 receives the decrypted text mi′ (1=<i=<n) from thedecryption apparatus120, generates image/audio signals from the received decrypted text mi′ (1=<i=<n), and outputs the generated image/audio signals to themonitor155.

The[0234]

monitor

155 receives the image/audio signals from theplayback apparatus150, and displays an image and outputs an audio, according to the received image/audio signals.

1.8 Operation Performed by[0235]

Encryption Apparatus

110 and byDecryption Apparatus120

The operations performed by the[0236]

encryption apparatus

110 and by thedecryption apparatus120 are described, using the process-block diagram of FIG. 4, and the flowchart of FIG. 5.

The public-[0237]

key input unit

111 of theencryption apparatus110 reads, from thememory card160, the public-key polynomial h of thedecryption apparatus120, and outputs the read public-key polynomial h to the encryption unit114 (Step S101).

Then, the random-[0238]

number generating unit

112 generates a random number s, and outputs the generated random number s to thefirst function unit113 and to the encryption unit114 (Step S102).

The[0239]

first function unit

113 receives the random number s from the random-number generating unit112, and generates a functional value G(s) of the random number s (Step S103). Next, thefirst function unit113 generates a random-number value u and a shared key K from the functional value G(s), outputs the random-number value u to theencryption unit114, and outputs the shared key K to the shared-key encryption unit118 (Step S104).

Next, the[0240]

encryption unit

114 receives the public-key polynomial h from the public-key input unit111, receives the random number s from the random-number generating unit112, and receives the random-number value u from thefirst function unit113. Then, theencryption unit114 generates the first cipher text c1, using the public-key polynomial hand the random-number value u, and outputs the first cipher text c1 to the first transmitting unit117 (Step S105).

The[0241]

first transmitting unit

117 receives the first cipher text c1 from theencryption unit114, and transmits the first cipher text c1 to thedecryption apparatus120 via the Internet130 (Step S106).

Next, the secret-[0242]

key input unit

121 of thedecryption apparatus120 reads, from thememory card170, the secret-key polynomial f and the public-key polynomial h that are for thedecryption apparatus120, and outputs the read secret-key polynomial f to thedecryption unit123, and outputs the read public-key polynomial h to the comparison unit127 (Step S151).

The[0243]

first receiving unit

122 receives the first cipher text c1 from theencryption apparatus110 via theInternet130, and outputs the first cipher text c1 to the decryption unit123 (Step S106).

Next, the[0244]

decryption unit

123 receives the secret-key polynomial f from the secret-key input unit121, and receives the first cipher text c1 from thefirst receiving unit122. Thedecryption unit123 then decrypts the first cipher text c1 using the secret-key polynomial f, to generate a decryption random number s′, and outputs the first cipher text c1 and the decryption random number s′ to thecomparison unit127, and outputs the decryption random number s′ to the second function unit126 (Step S152).

The[0245]

second function unit

126 receives the decryption random number s′ from thedecryption unit123, and generates a functional value G(s′) of the decryption random number s′ (Step S153). Thesecond function unit126 then generates a random-number value u′ and a shared key K′ from the functional value G(s′), and outputs the random-number value u′ and the shared key K′ to the comparison unit127 (Step S154).

Next, the[0246]

comparison unit

127 receives the first cipher text c1 from thedecryption unit123, receives the random-number value u′ and the shared key K′ from thesecond function unit126, and generates a first re-cipher text c1′ (Step S155). Then thecomparison unit127 checks whether the first cipher text c1 is the cipher text of the decryption random number s′ that is obtained by using the random-number value u′. If the first cipher text c1 is not the cipher text of the decryption random number s′ (Step S156), thedecryption apparatus120 ends its operation.

The shared-[0247]

key encryption unit

118 receives a plurality of plaintexts mi (1=<i=<n) from an external device, receives the shared key K from thefirst function unit113, and performs the symmetric key cryptographic algorithm Sym on the plaintext mi (1=<i=<n) using the shared key K to generate a shared-key cipher text Ci=Sym(mi, K) (1=<i=<n), and outputs the shared-key cipher text Ci (1=<i=<n) to the second transmitting unit119 (Step S107).

Next, the[0248]

second transmitting unit

119 receives the shared-key cipher text Ci (1=<i=<n) from the shared-key encryption unit118, transmits the shared-key cipher text Ci (1=<i=<n) to thedecryption apparatus120 via the Internet130 (Step S108), and ends the operations.

If the first cipher text c[0249]1 is the cipher text of the decryption random number s′ (Step S156), thecomparison unit127 outputs the shared key K′ to the shared-key decryption unit128 (Step S157). Next, thesecond receiving unit129 receives the cipher text Ci (1=<i=<n) from theencryption apparatus110 via theInternet130, and outputs it to the shared-key decryption unit128 (Step S108).

The shared-[0250]

key decryption unit

128 receives the shared key K′ from thecomparison unit127, receives the shared-key cipher text Ci (1=<i=<n) from thesecond receiving unit129, and performs the symmetric key cryptographic algorithm Sym on the shared-key cipher text Ci (1=<i=<n) using the shared key K′, to generate the decrypted text mi′=Sym(Ci, K) (1=<i=<n), and outputs the decrypted text mi′ (1=<i=<n) to the playback apparatus150 (Step S158), and ends the operations.

1.9 Operation Verification of[0251]

Content Distribution System

10

As follows, the entire operation performed by the[0252]

content distribution system

10 of the first embodiment is described.

First, the[0253]

encryption apparatus

110 generates a random numbers, using the public-key polynomial hof thedecryption apparatus120 as an input, and derives a random-number value u and a shared key K, from the functional value G(s). Next, theencryption apparatus110 encrypts the random number s using the public-key polynomial h and the random-number value u and according to the NTRU cryptosystem, to generate a first cipher text c1, and transmits the first cipher text c1 to thedecryption apparatus120 via theInternet130.

Specifically, this[0254]

encryption apparatus

110 performs the following operations, so as to transmit the first cipher text c1 to thedecryption apparatus120.

Generate a random number s.[0255]

Generate G(s), and generate u and K, from the G(s).[0256]

Generate a first cipher text c[0257]1 of the random number s, using the public-key polynomial h and the random-number value u.

Output the shared key K and the first cipher text c[0258]1.

Next, the[0259]

encryption apparatus

110 encrypts the plaintext mi (1=<i=<n) having been inputted from an external device, using the derived shared key K and according to the symmetric key cryptography, to generate a cipher text Ci (1=<i=<n), and transmits the cipher text Ci (1=<i=<n) to thedecryption apparatus120 via theInternet130.

On the other hand, the[0260]

decryption apparatus

120 receives the first cipher text c1 from theencryption apparatus110 via theInternet130 by using, as input, the secret-key polynomial f and the public-key polynomial h of thedecryption apparatus120, and decrypts the first cipher text c1, using the secret-key polynomial f, to generate a decryption random number s′. Then, thedecryption apparatus120 derives a random-number value u′ and a shared key K′, from the functional value G(s′) of the decryption random number s′, and encrypts the decryption random number s′ to generate a first re-cipher text c1′, and if c1′=c1, outputs the shared key K′.

Specifically, this[0261]

decryption apparatus

120 performs the following operations, so as to derive the shared key K′.

Decrypt the first cipher text c[0262]1 using the secret-key polynomial f, to generate s′.

Generate G (s′), and generate u′ and K′ from the G (s′).[0263]

Generate a first re-cipher text c[0264]1′ of s′ using the public-key polynomial h and the random-number value u′.

Check to see if c[0265]1′=c1 holds. If it holds, output the shared key K′.

Here, if the[0266]

decryption apparatus

120 has used the correct secret-key polynomial f that corresponds to the public-key polynomial h that theencryption apparatus110 has used, the first cipher text c1 will be correctly decrypted, to generate the decryption random number s′=s, therefore the random-number value u′ derived from the G(s′) is equal to u, and as a result the shared key K′=K holds. Since s′=s and u′=u hold, c1′=c1 also holds, therefore thedecryption apparatus120 can derive the same shared key K as that derived by theencryption apparatus110.

Next, the[0267]

decryption apparatus

120 decrypts the shared-key cipher text Ci (1=<i=<n) having been received from theencryption apparatus110 via theInternet130, using the derived shared key K′ (=K) and according to the symmetric key cryptography, to generate a decrypted text mi′ (1=<i=<n), and outputs the decrypted text mi′ to an external device. Since the encryption key K (used for generation of the shared-key cipher text) is identical to the encryption key K′ (used for generation of decrypted text), thedecryption apparatus120 can obtain the correct mi′=mi (1=<i=<n).

Note that if a decryption error has occurred, the decryption random number s′ and the random number s are not identical. The random-number value u′ and the shared key K′ that are derived from the G(s′) will be respectively different from u and k, too. In this case however, s′ and u′ will be respectively different from s and u, too. Therefore, the first re-cipher text c[0268]1′ will be different from the first cipher text c1, and so thedecryption apparatus120 will not output the shared key K′.

1.10 Effect of First Embodiment[0269]

In the conventional RSA-KEM algorithm, an element s will be inputted into the hash function G to derive a shared key K, the element s being unable to be derived from the cipher text C unless the secret key is known. However, there is a possibility of decryption error if a shared key is attempted to be distributed, using the NTRU cryptosystem and applying the RSA-KEM algorithm that is a key encapsulation mechanism. This means that occasionally the elements cannot be derived even using the secret key, thereby deriving an incorrect shared key K′.[0270]

However the content distribution system, the encryption/decryption apparatuses that relate to the first embodiment are able to prevent derivation of different keys between the encryption apparatus and the decryption apparatus even when a decryption error occurs. This is realized by the processes of the first embodiment. In this process, in addition to a shared key, a random-number value u is generated from the hash functional value G(s) of the random number s, and the decryption apparatus re-encrypts the decryption random number s′ using the random-number value u and the public-key polynomial h, to generate a first re-cipher text c[0271]1′, and unless the first re-cipher text c1′ is identical to the first cipher text c1, the decryption apparatus will not output a shared key K′.

In addition, according to the system of the present invention, the security can be logically verified using the same method as the verification method described in the non-patent reference 3.[0272]

1.11 Modification Example[0273]

The first embodiment described above is one example of carrying out the present invention. Needless to say, the present invention is not limited to this particular embodiment, and can be carried with various modifications as long as they are within the scope of the present invention. In light of this, the following cases are included in the present invention.[0274]

(1) The Parameter N to be Used in NTRU Cryptosystem May Take Other Value than[0275]167.

(2) The conversion method between the element of each bit in the bit sequence and the coefficient of each term in the polynomial, which is performed in the[0276]

encryption unit

114 and thedecryption unit123, is not limited to the aforementioned method, and may be other methods.

For example, the conversion of the random number s to the random-number polynomial sp may be performed using a function that corresponds the element of each bit in the bit sequence to the coefficient of each term in the polynomial, in one-to-one relation. Alternatively, the mentioned conversion may be performed using a functional-value table that stores the element of each bit in the bit sequence and the coefficient of each term in the polynomial in one-to-one relation.[0277]

Moreover, the conversion from the random-number value u to the random-number polynomial r may be performed in other methods, as long as the following conditions are held: r is uniquely obtained from u, and among r, the coefficient of d terms of degree is 1, the coefficient of d terms of degree is −1, and the coefficient of other terms of degree is 0. For example, the conversion may be performed using a function or a functional-value table, which correspond a random-number value u to a polynomial.[0278]

(3) The public-key cryptosystem, used in the[0279]

encryption unit

114 and thedecryption unit123, is not limited to the one described, as long as itsencryption unit114 is operable to encrypt a random number s using a public key and a random-number value u to generate a first cipher text c1, and itsdecryption unit123 is operable to decrypt the first cipher text c1 using a secret key to generate a decryption random number s′ that is equal to the random-number value s.

Accordingly, the public-key cryptosystem used in the[0280]

encryption unit

114 and in thedecryption unit123 may be other cryptosystems different from the NTRU cryptosystem.

For example, if the E[0281]1Gama1 cryptosystem is to be used, h and f may be respectively set as a public key and a secret key of the E1Gama1 cryptosystem. Then, in theencryption unit114, the random number s is encrypted using h and u, to generate c1, and indecryption unit123, c1 is decrypted using f, to generate s′.

Note that the E[0282]1Gama1 cryptosystem is described in greater detail in thenon-patent reference 1, therefore is not detailed here.

(4) In the first embodiment, the[0283]

first function unit

113 sets the k highest-order bits of the functional value G(s) as a random-number value u, and the k lowest-order bits thereof are set as a shared key K. However, other methods may be alternatively used, as long as the random-number value u and the shared key K are derived from the functional value G(s).

For example, the k/2 highest-order bits of the functional value G(s) may be set as a random-number value u, and the k*3/2 lowest-order bits may be set as a shared key K. Alternatively, as a random-number value u, k bits may be selected so that every other bit in the 2 k bits of the functional value G(s) is selected, and the other k bits may be set as a shared key K.[0284]

(5) In the first embodiment, the random-number value u is generated in the[0285]

first function unit

113 and in thesecond function unit126. However, other generation methods may be used, as long as the same value is generated in theencryption apparatus110 and in thedecryption apparatus120.

For example, u=Func(s) may be used with respect to an arbitrary function Func, so that the[0286]

encryption apparatus

110 obtains the same value as that thedecryption apparatus120 obtains. More specifically, theencryption apparatus110 and thedecryption apparatus120 may:

generate G(s), and generate K from the G(s), and[0287]

generate Func(s), and sets u=Func(s).[0288]

(6) Further, the random-number value u is generated in the[0289]

first function unit

113 and in thesecond function unit126, in the first embodiment. However, the condition to be satisfied here is that theencryption apparatus110 and thedecryption apparatus120 obtain the same value. Therefore, theencryption apparatus110 may transmit the random-number value u directly to thedecryption apparatus120.

To be more specific, the first cipher text c[0290]1 and the random-number value u may be transmitted to thedecryption apparatus120, as described below. At this time, the random-number value u may be encrypted before being transmitted.

The encryption apparatus[0291]110:

generates G(s), and generates K from the G(s), and[0292]

transmits the random-number value u separately, from the[0293]

encryption apparatus

110 to thedecryption apparatus120.

The decryption apparatus[0294]120:

receives the random-number value u, and[0295]

generates a first re-cipher text c[0296]1′ using the received random-number value u in place of the random-number value u′.

At this time, it may be arranged that the[0297]

encryption apparatus

110 encrypt the random-number value u before transmitting it, and that thedecryption apparatus120 decrypts the encrypted random-number value u.

(7) As for the random-number value u, the condition is that the[0298]

encryption apparatus

110 and thedecryption apparatus120 obtain the same value. Therefore, it may be arranged to generate part of the information for the random-number value u in thefirst function unit113 and in thesecond function unit126, and to directly transmit the rest of the information for the random-number value u from theencryption apparatus110 to thedecryption apparatus120.

For instance, the[0299]

encryption apparatus

110 may transmit the first cipher text c1 and the random-number value u2 to thedecryption apparatus120, as follows.

The encryption apparatus[0300]110:

(a) generates G (s), and generates K, u1 from the G (s),[0301]

(b) generates the random-number value u2, and separately transmit the random-number value u2 to the[0302]

decryption apparatus

120,

(c) generates a random-number value u from u=u1 xor u2, and[0303]

(d) generates a first cipher text c[0304]1 using the random-number value u.

The decryption apparatus[0305]120:

(e) receives the random-number value u2,[0306]

(f) generates G(s′), and generates K′, and u[0307]1′ from the G(s′),

(g) generates a random-number value u′ from u′=u1′ xor u2, and[0308]

(h) generates a first re-cipher text c[0309]1′ using the generated random-number value u′.

At this time, the[0310]

encryption apparatus

110 may encrypt the random-number value u2 before transmitting it, and thedecryption apparatus120 may decrypt the encrypted random-number value u2.

In (c) and (g), other computation may be performed in place of bitwise exclusive-or. For example, in (c) and (g), addition and subtraction may be used respectively. Alternatively, multiplication and division may be used.[0311]

(8) In the first embodiment, the shared key K′ is outputted when the first re-cipher text c[0312]1′ is identical to the first cipher text c1, so as to prevent derivation of different shared keys for theencryption apparatus110 and thedecryption apparatus120, due to decryption error. However, instead of the above arrangement, the following arrangement may be performed. That is, theencryption apparatus110 generates a hash functional value for at least one of the random number s, the random-number value u, and the shared key K, and transmits this hash functional value to thedecryption apparatus120. Thedecryption apparatus120 then verifies this hash functional value, thereby determining whether to output the shared key K′. For example, as this hash functional value, a hash functional value H(s) of the random number s may be generated for an arbitrary hash function H. Alternatively, a combination of random number s, random-number value u, and shared key K maybe generated, such as a hash functional value H(s||u||k) and a hash functional value H(u||k).

In this case, the[0313]

first function unit

113 in theencryption apparatus110 may derive only a shared key K from G(s), instead of deriving a random-number value u and a shared key K from the functional value G(s).

A concrete example therefor is described as follows.[0314]

The[0315]

content distribution system

10, instead of including theencryption apparatus110 and thedecryption apparatus120, includes anencryption apparatus110band adecryption apparatus120b. Theencryption apparatus110b, as shown in FIG. 6, includes a public-key input unit111, a random-number generating unit112, afirst function unit113b, anencryption unit114b, afirst transmitting unit117b, a shared-key encryption unit118, and asecond transmitting unit119. Thedecryption apparatus120, as shown in FIG. 7, includes a secret-key input unit121b, afirst receiving unit122b, adecryption unit123b, asecond function unit126b, acomparison unit127b, a shared-key decryption unit128, and asecond receiving unit129. Thecomparison unit127bincludes athird function unit127uand acomparison computation unit127v.

The[0316]

encryption apparatus

110bgenerates a hash functional value of the random number s, and thedecryption apparatus120bverifies this hash functional value. During this verification, in theencryption apparatus110b, thefirst function unit113bgenerates G(s) as shown in the process-block diagram of FIG. 8 (Step S103), and generates K from G(s) (Step S104).

Next, the[0317]

encryption unit

114bgenerates a random-number value u, generates a random-number polynomial r from the generated random-number value u, and generates a first cipher text c1 of the random number s using a random-number polynomial r and a public-key polynomial h (Step S105), and finally generates a hash functional value H(s) (Step S111).

The[0318]

first transmitting unit

117btransmits the first cipher text c1 (Step S106), and transmits the hash functional value H(s) (Step S112).

Next, in the[0319]

decryption apparatus

120b, thefirst receiving unit122breceives the first cipher text c1 (Step S106), and receives the hash functional value H(s) (Step S112).

The[0320]

decryption unit

123bdecrypts the first cipher text c1 using the secret-key polynomial f, to generate s′ (Step S152).

Then, the[0321]

second function unit

126 generates G(s′) (Step S153), and generates K′ from G(s′) (Step S154).

In the[0322]

comparison unit

127, thethird function unit127ugenerates H(s′) (Step S154), and thecomparison computation unit127vchecks whether H(s′)=H(s) holds (Step S162), and if it holds, the shared key K′ is outputted (Step S157).

In this case, for further heightening security, the method disclosed in the[0323]patent reference 1 may be used where encryption is performed on a random number s added additional information, so as to generate a first cipher text c1. Specifically, the following arrangement may be performed. That is, in FIG. 6, theencryption unit114bgenerates additional information Ra, and encrypts the value of bit connecting between sand Ra (i.e. s||Ra) to generate a first ciphertext c1. In FIG. 7, thedecryption unit123bdecrypts the first cipher text c1 to generate s′||Ra′, and removes therefrom Ra′ to generate a decryption random number s′.

In addition, as shown in the[0324]patent reference 1, the value of an invertible conversion of s and Ra, namely F(s, Ra), may be used instead of the value of s||Ra.

2. Second Embodiment[0325]

The following describes a content distribution system[0326]10c(unshown in any drawing), as another embodiment relating to the present invention.

The content distribution system[0327]10cis a system based on thecontent distribution system10 with some modifications. The differences with thecontent distribution system10 are that: a verification value a is generated from G(s), in addition to the random-number value u and the shared key K; and the encryption apparatus, instead of generating the first cipher text by encrypting the random number s and transmitting it, generates a first cipher text c1 resulting from encrypting the verification value a, and a second cipher text c2 resulting from encrypting the random number s based on the verification value a, and transmits the first cipher text c1 and the second cipher text c2.

The following description focuses on the differences mentioned above.[0328]

2.1 Structure of Content Distribution System[0329]10c

The content distribution system[0330]10chas the similar structure as thecontent distribution system10, except that theencryption apparatus110 and thedecryption apparatus120 are replaced by anencryption apparatus110cand adecryption apparatus120c, respectively. The other components are the same as those included in thecontent distribution system10, therefore whose explanation is omitted here.

2.2 Structure of[0331]

Encryption Apparatus

110c

The[0332]

encryption apparatus

110c, as shown in FIG. 9, has the similar structure as theencryption apparatus110, and includes a random-number generating unit112c, afirst function unit113c, anencryption unit114c, a random-number mask unit116c, and afirst transmitting unit117c, instead of the random-number generating unit112, thefirst function unit113, theencryption unit114, and thefirst transmitting unit117.

The following describes the random-[0333]

number generating unit

112c, thefirst function unit113c, theencryption unit114c, the random-number mask unit116c, and thefirst transmitting unit117c.

(1) Random-[0334]

Number Generating Unit

112c

The random-[0335]

number generating unit

112cgenerates a random number s, as a seed value on which generation of the shared key K bases, and outputs the generated random number s to thefirst function unit113band to the random-number mask unit116c.

113c

113creceives the random number s from the random-number generating unit112c, and generates a functional value G(s) of the random number s, then generates a verification value a, a shared key K, and a random-number value u, from the generated functional value G(s).

Here, the function G is a hash function having output length of 3 k bits. The[0338]

first function unit

113csets the k highest-order bits of the functional value G(s) as a verification value a, the middle k bits of the functional value G(s) as a shared key K, and the k lowest-order bits of the functional value G(s) as a random-number value u.

Next, the[0339]

first function unit

113coutputs the verification value a and the random-number value u to theencryption unit114c, outputs the shared key K to the shared-key encryption unit118, and outputs the verification value a to the random-number mask unit116c.

114c

114creceives the public-key polynomial h from the public-key input unit111, receives the verification value a and the random-number value u from thefirst function unit113c, and generates a first cipher text c1 of the verification value a, using the public-key polynomial hand the random-number value u, as shown below. Here, the first cipher text c1 is a cipher text generated according to the NTRU cryptography.

The[0342]

encryption unit

114cgenerates a random-number polynomial r having the following characteristic so that it is uniquely defined by the random-number value u. The characteristic of the random-number polynomial r is such that, with respect to the parameter d of the NTRU cryptosystem, each coefficient of d terms is 1, each coefficient of other d terms is −1, and each coefficient of the rest of the terms is 0. Specifically, theencryption unit114csets the random-number value u as a default value of the pseudo-random number system (random-number seed), and selects 2d pseudo-random numbers, from among {0, 1, . . . , N−1}, that do not overlap with each other. Then, theencryption unit114csets the coefficients of terms of degree shown by the first d pseudo-random numbers as 1. The encryption unit sets the coefficients of terms of degree shown by the other d pseudo-random numbers as −1, and the coefficients of the rest of the terms of degree as 0. As a result, theencryption unit114cgenerates the random-number polynomial r.

Next, the[0343]

encryption unit

114 converts the verification value a into a verification-value polynomial ap, by constructing the verification-value polynomial ap so that the element for each bit of an N-bit bit sequence in which the verification value a is represented in binary form, corresponds to the coefficient of a different one of the terms of the verification-value polynomial ap. This is for applying the received verification value a to the encryption algorithm E for the NTRU cryptosystem. For example, the element of the b-th lowest bit of the verification value a will be set as the value of the coefficient of the term X^b. Concretely, when the verification value a=10010 (representation in bit form), the verification-value polynomial ap=X⁵+X²is generated.

Next, the[0344]

encryption unit

114cperforms the encryption algorithm E on the verification-value polynomial ap, using the public-key polynomial h as a key and also using the random-number polynomial r, to generate the first cipher text c1 (which is the cipher text polynomial)=E(ap, r, h)

Next, the[0345]

encryption unit

114coutputs the generated first cipher text c1 to thefirst transmitting unit117c.

116c

116creceives the random number s from the random-number generating unit112c, and receives the verification value a from thefirst function unit113c. Then, the random-number mask unit116cgenerates a second cipher text c2=s xor a, and outputs the generated second cipher text c2 to thefirst transmitting unit117c.

Here, xor is an operator representing bitwise exclusive-or.[0348]

Note that the random-[0349]

number mask unit

116cmay use a symmetric key encryption algorithm, addition, and multiplication, instead of this xor (bitwise exclusive-or).

(5)[0350]

First Transmitting Unit

117c

The[0351]

first transmitting unit

117creceives the first cipher text c1 from theencryption unit114c, receives the second cipher text c2 from the random-number mask unit116c, and transmits the first cipher text c1 and the second cipher text c2, to thedecryption apparatus120cvia theInternet130.

2.2 Structure of[0352]

Decryption Apparatus

120c

The[0353]

decryption apparatus

120chas the same structure as thedecryption apparatus120, as shown in FIG. 10, and includes afirst receiving unit122c, adecryption unit123c, a random-numbermask removal unit125c, asecond function unit126c, and acomparison unit127c, in place of thefirst receiving unit122, thedecryption unit123, thesecond function unit126, and thecomparison unit127.

Here, the[0354]

first receiving unit

122c, thedecryption unit123c, the random-numbermask removal unit125c, thesecond function unit126c, and thecomparison unit127cwill be described.

122c

122creceives the first cipher text c1 and the second cipher text c2, from theencryption apparatus110cvia theInternet130. Thefirst receiving unit122cthen outputs the first cipher text c1 to thedecryption unit123c, and outputs the second cipher text c2 to the random-numbermask removal unit125c.

123c

123creceives the secret-key polynomial f from the secret-key input unit121, and receives the first cipher text c1 from thefirst receiving unit122c, then as shown in the following, decrypts the first cipher text c1 using the secret-key polynomial f, to generate a decryption verification value a′. Here, the decryption verification value a′ is a decrypted text generated according to the NTRU cryptosystem.

123coutputs the generated decryption verification value a′ to the random-numbermask removal unit125c, and outputs the received first cipher text c1 to thecomparison unit127c.

(3) Random-Number[0361]

Mask Removal Unit

125c

The random-number[0362]

mask removal unit

125creceives the second cipher text c2 from thefirst receiving unit122c, receives the decryption verification value a′ from thedecryption unit123c, and then generates a decryption random number s′=c2 xor a′, and outputs the generated decryption random number s′ to thesecond function unit126c.

Note that when the random-[0363]

number mask unit

116c, instead of the bitwise exclusive-or, uses the symmetric key cryptographic encryption algorithm, the addition, or the multiplication, the random-numbermask removal unit125cmay use the symmetric key cryptographic decryption algorithm corresponding to the symmetric key cryptographic encryption algorithm, or the subtraction, or the division.

126c

126chas an algorithm for a function G that is the same as the function owned by thefirst function unit113c.

The[0366]

second function unit

126creceives the decryption random number s′ from the random-numbermask removal unit125c, and generates a functional value G(s′) of the received decryption random number s′. Next, as in the same manner as in thefirst function unit113c, thesecond function unit126cgenerates, from the functional value G(s′), a verification value a″, a shared key K′, and a random-number value u′, and outputs the verification value a″, the shared key K′, and the random-number value u′ to thecomparison unit127c.

127c

127c, as shown in FIG. 10, includes acomparison computation unit127sand anencryption unit127t.

The[0369]

encryption unit

127treceives the public-key polynomial h from the secret-key input unit121, and receives the verification value a″ and the random-number value u′ from thesecond function unit126c. Then, theencryption unit127t, in the same manner as in theencryption unit114c, encrypts the verification value a″, to generate the first re-cipher text c1′, and outputs the generated first re-cipher text c1′ to thecomparison computation unit127s.

Furthermore, the[0370]

comparison computation unit

127sreceives the shared key K′ form thesecond function unit126c, receives the first cipher text c1 from thedecryption unit123c, and receives the first re-cipher text c1′ from theencryption unit127t. Then, thecomparison computation unit127scompares the first cipher text c1 and the first re-cipher text c1′, and if the first cipher text c1=the first re-cipher text c1′, outputs the received shared key K′ to the shared-key decryption unit128.

2.3 Operation Performed by Content Distribution System[0371]10c

As follows, the whole operation performed by the content distribution system[0372]10cis described, using the process-block diagram of FIG. 11.

The[0373]

encryption apparatus

110creceives the public-key polynomial h of thedecryption apparatus120c(Step S101), generates a random number s (Step S102), obtains a functional value G(s), and derives a verification value a, a shared key K, and a random-number value u, from the functional value G(s) (Step S121). Next, theencryption apparatus110cencrypts the verification value a using the public-key polynomial h and the random-number value u and according to the NTRU cryptosystem, to generate a first cipher text c1 (Step S105), and encrypts the random number s based on the verification value a, to generate the second cipher text c2=s xor a (Step S122). Next, theencryption apparatus110ctransmits the first cipher text c1 and the second cipher text c2 to thedecryption apparatus120cvia the Internet130 (Step S106).

Specifically, this[0374]

encryption apparatus

110cperforms the following operations, so as to transmit the cipher text C=(c1, c2) to thedecryption apparatus120c.

(a) Generate a random number s.[0375]

(b) Generate G(s), and generate a, K, and u from the G(s).[0376]

(c) Generate a first cipher text c[0377]1 of a verification value a, using a public-key polynomial h and a random-number value u.

(d) Generate c[0378]2=s xor a.

Next, the[0379]

encryption apparatus

110cencrypts the plaintext mi (1=<i=<n) received from thecontent server apparatus140, using the derived shared key K and according to the symmetric key cryptography, to generate a cipher text Ci (1=<i=<n) (Step S107), and transmits the cipher text Ci (1=<i=<n) to thedecryption apparatus120cvia the Internet130 (Step S108).

On the other hand, the[0380]

decryption apparatus

120creceives the secret-key polynomial f and the public-key polynomial h for thedecryption apparatus120c(Step S151), receives the first cipher text c1 and the second cipher text c2, form theencryption apparatus110cvia the Internet130 (Step S106), and decrypts the first cipher text c1 using the secret-key polynomial f, to generate a decryption verification value a′ (Step S152). Then, thedecryption apparatus120cdecrypts the second cipher text c2 based on the decryption verification value a′, to generate a decryption random number s′=c2 xor a′ (Step S171). Next, thedecryption apparatus120cderives a verification value a″, a shared key K′, and a random-number value u′, from the functional value G(s′) of the decryption random number S′ (Step S172). Further, thedecryption apparatus120cencrypts the verification value a″, to generate a first re-cipher text c1′ (Step S155), and if c1′=c1 (Step S156), outputs the shared key K′ (Step S157).

Specifically, this[0381]

decryption apparatus

120cperforms the following operations, so as to derive the shared key K′.

(a) Decrypt a first cipher text c[0382]1 using a secret-key polynomial f, to generate a′.

(b) Generate s′=c[0383]2 xor a′.

(c) Generate G(s′), and generate a″, K′, u′ from the G(s′)[0384]

(d) Generate a first re-cipher text c[0385]1′ of a″ using a public-key polynomial h and a random-number value u′.

(e) Check to see if c[0386]1′=c1 holds. If it holds, output the shared key K′.

Here, if the[0387]

decryption apparatus

120chas used the regular secret-key polynomial f that corresponds to the public-key polynomial h used in theencryption apparatus110c, the first cipher text c1 will be correctly decrypted, thereby yielding a decryption verification value a′=a, and a decryption random number s′=s (the decryption random number s′ having been generated from the second cipher text c2 and a′). Therefore, a verification value a″=a (the verification value a″ having been derived from G(s″)), and so a shared key K′=K, and a random-number value u′=u will hold. As a result, a″=a′, and u′=u hold, therefore c1′=c1 will hold too. This means that thedecryption apparatus120chas derived the shared key K that is the same one derived by theencryption apparatus110c.

Next, the[0388]

decryption apparatus

120creceives the shared-key cipher text Ci (1=<i=<n) from theencryption apparatus110cvia the Internet130 (Step S108), and decrypts the shared-key cipher text Ci (1=<i=<n) using the derived shared key K′(=K) and according to the symmetric key cryptography to generate a decrypted text mi′ (1=<i=<n) (Step S158), and outputs the decrypted text mi′ (1=<i=<n) to theplayback apparatus150.

Here, since the encryption key K (used for generation of shared-key cipher text) is identical to the encryption key K′ (used for generation of decrypted text), the[0389]

decryption apparatus

120ccan obtain the correct decrypted text mi′=mi (1=<i=<n).

Note that if a decryption error has occurred, the decryption verification value a′ and the verification value a are not identical. The decryption random number s' obtained from the second cipher text c[0390]2 is different from s, too. Therefore, the random-number value u′ and the shared key K′, which are derived from the G(s′), are respectively different from u and K. In this case however, since a′ and u′ are respectively different from a and u, the first re-cipher text c1′ is different from the first cipher text c1. Therefore, thedecryption apparatus120cwill not output the shared key K′.

2.4 Effect of Second Embodiment[0391]

In the conventional RSA-KEM algorithm, an element s will be inputted into the hash function G to derive a shared key K, the element s being unable to be derived from the cipher text C unless the secret key is known. However, there is a possibility of decryption error if a shared key is attempted to be distributed, using the NTRU cryptosystem and applying the RSA-KEM algorithm that is a key encapsulation mechanism. This means that occasionally the element s cannot be derived even using the secret key, thereby deriving an incorrect shared key K′.[0392]

However the content distribution system, the encryption/decryption apparatuses that relate to the second embodiment are able to prevent derivation of different key between the encryption apparatus and the decryption apparatus even when a decryption error occurs. This is realized by the process of the second embodiment, as follows. In this process, in addition to a shared key, a verification value a and a random-number value u are generated from the hash functional value G(s) of the random number s, and the decryption apparatus re-encrypts the decryption verification value a′ using the random-number value u and the public-key polynomial h, to generate a first re-cipher text c[0393]1′, and unless the first re-cipher text c1′ is identical to the first cipher text c1, the decryption apparatus will not output the shared key K′.

In addition, according to the method of the present invention, the security can be logically verified using the same method as the verification method described in the non-patent reference 3.[0394]

2.5 Modification Example[0395]

The second embodiment described above is one example of carrying out the present invention. However, the present invention is not limited to this particular embodiment, and can be carried with various modifications as long as they are within the scope of the present invention. Needless to say, the same modifications as those in the first embodiment can be applied hereto, but the following cases are also included in the present invention.[0396]

(1) The conversion from the verification value a to the verification-value polynomial ap may be other methods. For example, the conversion may be performed using a function that corresponds the element of each bit in the bit sequence to the coefficient of each term in the polynomial, in one-to-one relation. Alternatively, the mentioned conversion may be performed using a functional-value table that stores the element of each bit in the bit sequence and the coefficient of each term in the polynomial in one-to-one relation.[0397]

In addition, the conversion from the random-number value u to the random-number polynomial r may be performed in other methods, as long as the following conditions are held: r is uniquely obtained from r, and the coefficient of d terms of degree is 1, the coefficient of d terms of degree is −1, and the coefficient of other terms of degree is 0. For example, the conversion may be performed using a function or a functional-value table, which correspond a random-number value u to a polynomial.[0398]

(2) The public-key cryptosystem, used in the[0399]

encryption unit

114cand thedecryption unit123c, is not limited to the one described above, as long as itsencryption unit114cis operable to encrypt a verification value a using a public key and a random-number value u to generate a first cipher text c1, and itsdecryption unit123cis operable to decrypt the first cipher text c1 using a secret key to generate a decryption verification value a′ which is identical to the verification value a. Accordingly, the public-key cryptosystem used in theencryption unit114cand in thedecryption unit123cmay be other cryptosystems different from the NTRU cryptosystem, as long as a random number is used therein.

For example, if the E[0400]1Gama1 cryptosystem is to be used, h and f may be respectively set as a public key and a secret key of the E1Gama1 cryptosystem. Then, in theencryption unit114c, a is encrypted using h and the random-number value u, to generate c1, and indecryption unit123c, c1 is decrypted using f, to generate a′.

(3) In the second embodiment, the random-number value u is generated in the[0401]

first function unit

113cand in thesecond function unit126c. However, other generation methods may be used therefor, as long as the same value is generated in theencryption apparatus110cand in thedecryption apparatus120c.

For example, u=Func(s) may be used with respect to an arbitrary function Func, so that the[0402]

encryption apparatus

110cobtains the same value as that thedecryption apparatus120cobtains. More specifically, the following processes may be used.

Generate G(s), and generate a and K from the G(s).[0403]

Generate Func(s), and sets u=Func(s).[0404]

(4) Moreover, the random-number value u is generated in the[0405]

first function unit

113cand in thesecond function unit126c. However, the condition to be satisfied is to obtain the same value therefor, between theencryption apparatus110cand thedecryption apparatus120c. Accordingly, theencryption apparatus110cmay directly transmit the random-number value u to thedecryption apparatus120c.

More specifically, the[0406]

encryption apparatus

110cmay transmit the cipher text C and the random-number value u to thedecryption apparatus120b, as follows. Here, the random-number value u may be encrypted before being transmitted.

Generate G(s), and generate a, and K from the G(s).[0407]

The[0408]

encryption apparatus

110ctransmits the random-number value u separately, to120b.

(5) As for the random-number value u, the condition is that the[0409]

encryption apparatus

110cand thedecryption apparatus120cobtain the same value. Therefore, it may be arranged to generate part of the information for the random-number value u in thefirst function unit113cand in thesecond function unit126c, and to directly transmit the rest of the information for the random-number value u from theencryption apparatus110cto thedecryption apparatus120c.

For instance, the[0410]

encryption apparatus

110cmay transmit the cipher text C and the random-number value u2 to thedecryption apparatus120c, as in the following. In addition, the encryption apparatus may encrypt the random-number value u2 before transmission.

Generate G(s), and generate a, K, u1, from the G(s).[0411]

The[0412]

encryption apparatus

110ctransmits the random-number value u2 separately to thedecryption apparatus120c.

The[0413]

encryption apparatus

110cgenerates the random-number value u=u1 xor u2.

(6) The[0414]

decryption apparatus

120cchecks whether the first cipher text c1 is a cipher text of the verification value a″, obtained in thesecond function unit126c, and if c1=cipher text of a″, decrypts the shared-key cipher text C1 using the shared key K′. Alternatively, however, it is possible to check whether the first cipher text c1 is a cipher text of the decryption verification value a′.

(7) The[0415]

decryption apparatus

120cchecks whether the first cipher text c1 is a cipher text of the verification value a″, obtained in thesecond function unit126c, and if c1-cipher text of a″, decrypts the shared-key cipher text C1 using the shared key K′. Alternatively, however, thecomparison unit127cmay be arranged to check whether the value of a′ resulting from decryption of thedecryption unit123cis equal to the value of a″ generated by thesecond function unit126c, as shown in Step S156 of the process-block diagram of FIG. 12.

(8) In the second embodiment, the shared key K′ is outputted when the first re-cipher text c[0416]1′ is identical to the first cipher text c1, so as to prevent derivation of different shared keys for theencryption apparatus110cand thedecryption apparatus120c. However, instead of the above arrangement, the following arrangement may be performed. That is, theencryption apparatus110cgenerates a hash functional value for at least one of the random numbers, the verification value a, the random-number value u, and the shared key K, and transmits the generated hash functional value to thedecryption apparatus120c. Thedecryption apparatus120cthen verifies the hash functional value, thereby determining whether to output the shared key K′. Alternatively, the method disclosed in thepatent reference1 may be used therefor. In other words, the modification example (8) relating to the first embodiment may be used instead.

3. Summary of First and Second Embodiments[0417]

As described so far, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into random-number data and the shared-key data, based on a predetermined process; and a first encryption unit operable to encrypt the secret-number data based on the public-key data and the random-number data, to generate encryption shared-key data.[0418]

In addition, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into verification-value data, random-number data, and the shared-key data; a first encryption unit operable to encrypt the verification-value data based on the public-key data and the random-number data, to generate first encryption preliminary data; and a second encryption unit operable to encrypt the secret-number data based on the verification-value data, to generate second encryption preliminary data, where the encryption shared-key data is made up of the first encryption preliminary data and the second encryption preliminary data.[0419]

Here, the second encryption unit may perform bitwise exclusive-or on the secret-number data and the verification-value data, to generate the second encryption preliminary data.[0420]

Here, the second encryption unit may encrypt the secret-number data using the verification-value data as a cryptographic key and according to the symmetric key cryptography, to generate the second encryption preliminary data.[0421]

Here, the second encryption unit may add the verification-value data to the secret-number data, to generate the second encryption preliminary data.[0422]

Here, the second encryption unit may multiply the secret-number data by the verification-value data, to generate the second encryption preliminary data.[0423]

Here, the encryption shared-key data may be bit connecting data between the first encryption preliminary data and the second encryption preliminary data.[0424]

Here, the first encryption unit may perform NTRU cryptographic encryption, to generate the encryption shared-key data.[0425]

Here, the first encryption unit may perform NTRU cryptographic encryption, to generate the first encryption preliminary data.[0426]

Here, the secret-number data may be a random number having been randomly generated.[0427]

Here, the shared-key derivation unit may use a one-way hash function, as the predetermined process.[0428]

Furthermore, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on secret-key data and public-key data that are predetermined, to generate shared-key data, and outputs the generated shared-key data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the encryption shared-key data based on the secret-key data, to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into random-number data and the shared-key data, based on a predetermined process; and a third encryption unit operable to encrypt the secret-number data based on the public-key data and the random-number data, to generate re-encryption shared-key data, where the shared-key recovery apparatus outputs the shared-key data when the encryption shared-key data is equal to the re-encryption shared-key data.[0429]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on secret-key data and public-key data that are predetermined, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a second decryption unit operable to decrypt the second encryption preliminary data based on the verification-value data, to generate secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data, random-number data, and the shared-key data; and a third encryption unit operable to encrypt the verification-value verification data based on the public-key data and the random-number data, to generate third encryption preliminary data, where the shared-key recovery apparatus outputs the shared-key data when the first encryption preliminary data is equal to the third encryption preliminary data.[0430]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on secret-key data and public-key data that are predetermined, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a second decryption unit operable to decrypt the second encryption preliminary data based on the verification-value data, to generate secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data, random-number data, and the shared-key data; and a third encryption unit operable to encrypt the verification-value data based on the public-key data and the random-number data, to generate third encryption preliminary data, where the shared-key recovery apparatus outputs the shared-key data when the first encryption preliminary data is equal to the third encryption preliminary data.[0431]

Here, the second decryption unit may perform bitwise exclusive-or on the second encryption preliminary data and on the verification-value data, to generate the secret-number data.[0432]

Here, the second decryption unit may decrypt the second encryption preliminary data using the verification-value data as a cryptographic key and according to the symmetric key cryptography, to generate the secret-number data.[0433]

Here, the second decryption unit may subtract the verification-value data from the second encryption preliminary data, to generate the secret-number data.[0434]

Here, the second decryption unit may divide the second encryption preliminary data by the verification -value data, to generate the secret-number data.[0435]

Here, the first decryption unit may perform NTRU cryptographic decryption, to generate the shared-key data.[0436]

Here, the first decryption unit may perform NTRU cryptographic decryption, to generate the verification-value data.[0437]

Here, the shared-key derivation unit may use a one-way hash function, as the predetermined process.[0438]

Furthermore, the present invention is an encryption apparatus that encrypts plaintext data based on predetermined public-key data, to generate cipher-text data. The encryption apparatus includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into random-number data and shared-key data; a first encryption unit operable to encrypt the secret-number data based on the public-key data and the random-number data, to generate first encryption preliminary data; a second encryption unit operable to encrypt the plaintext data based on the shared-key data, to generate second encryption preliminary data, where the cipher-text data is made up of the first encryption preliminary data and the second encryption preliminary data.[0439]

Further, the present invention is a decryption apparatus that decrypts cipher-text data made up of first encryption preliminary data and second encryption preliminary data, based on secret-key data and public-key data that are predetermined, to generate decrypted-text data, and outputs the decrypted-text data. The decryption apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into random-number data and shared-key data; a third encryption unit operable to encrypt the secret-number data based on the public-key data and the random-number data, to generate third encryption preliminary data; and a decryption unit operable, when the first encryption preliminary data is equal to the third encryption preliminary data, to decrypt the second encryption preliminary data based on the shared-key data, to generate the decrypted-text data.[0440]

As described above, the present invention has been conceived in view of the problems that the conventional system has, and constructs in a cryptosystem a new encapsulation mechanism to which NTRU cryptosystem can be applied to, thereby preventing derivation of different keys between its encryption apparatus and decryption apparatus, and realizing assured cryptographic communication from the transmission apparatus to the reception apparatus, with use of a key derived from the key encapsulation mechanism.[0442]

As clear from the above, the present invention provides a cryptosystem that the conventional technologies were not able to provide, therefore is very valuable.[0443]

4. Third Embodiment[0444]

The following describes a content distribution system[0445]10d(unshown in any drawing), as another embodiment relating to the present invention.

The content distribution system[0446]10dis a system resulting by modifying thecontent distribution system10. The following describes the content distribution system10d, focusing on the differences with thecontent distribution system10.

4.1 Structure of content distribution system[0447]10d

The content distribution system[0448]10dhas the similar structure as thecontent distribution system10, except that theencryption apparatus110 and thedecryption apparatus120 are replaced by anencryption apparatus110dand adecryption apparatus120d, respectively. The other components are the same as those included in thecontent distribution system10, therefore whose explanation is omitted here.

The content distribution system[0449]10dis a cryptographic communication system that performs cryptographic communication that uses NTRU cryptography and performs key distribution according to the key encapsulation mechanism. In the content distribution system10d, theencryption apparatus110dand thedecryption apparatus120dare connected to each other, via theInternet130.

4.2 Structure of[0450]

Encryption Apparatus

110d

The[0451]

encryption apparatus

110d, as shown in FIG. 13, includes a public-key input unit111d, a random-number generating unit112d, afirst function unit113d, anencryption unit114d, asecond function unit115d, a random-number mask unit116d, afirst transmitting unit117d, a shared-key encryption unit118, and asecond transmitting unit119.

The[0452]

encryption apparatus

110dis a computer system similar to theencryption apparatus110, and performs its function, by operation of the microprocessor according to the computer program.

111d

111dreads, from thememory card160, the public-key polynomial h for thedecryption apparatus120, and outputs the read public-key polynomial h to theencryption unit114d.

(2) Random-[0455]

Number Generating Unit

112d

The random-[0456]

number generating unit

112dgenerates a random number s, as a seed value on which the generation of the shared key K bases, and outputs the generated random numbers to thefirst function unit113dand the random-number mask unit116d.

113d

113dreceives the random number s from the random-number generating unit112d, and generates a functional value G(s) of the random numbers, then generates a verification value a, and a shared key K, from the generated functional value G(s). Here, the function G is a hash function having output length of 2 k bits. Note that the hash function is one of the one-way functions. Thefirst function unit113dsets the k highest-order bits of the G(s) as a verification value a, and the k lowest-order bits of the G(s) as a shared key K.

Next, the[0459]

first function unit

113doutputs the generated verification value a to theencryption unit114dand to thesecond function unit115d, and outputs the generated shared key K to the shared-key encryption unit118.

114d

114dreceives the public-key polynomial h from the public-key input unit111d, and receives the verification value a from thefirst function unit113d. Then, as described below, theencryption unit114dgenerates a first cipher text c1 of the verification value a using the received public-key polynomial h. Here, the generated first cipher text c1 is a cipher text generated according to NTRU cryptosystem.

The[0462]

encryption unit

114drandomly generates a random-number polynomial r, so that with respect to the parameter d of NTRU cryptosystem, each coefficient of d terms is 1, each coefficient of other d terms is −1, and each coefficient of the rest of the terms is 0. Next, theencryption unit114dgenerates the verification-value polynomial ap, so that the element for each bit of an N-bit bit sequence in which the verification value a is represented in binary form, corresponds to the coefficient of a different one of the terms of the verification-value polynomial ap. This is for applying the verification value a to the encryption algorithm E of the NTRU cryptosystem. For example, the element of the b-th lowest bit of the verification value a will be set as the coefficient of the term Xb of the verification-value polynomial ap, thereby converting the verification value a into the verification-value polynomial ap. Concretely, when s=10010 (representation in bit form), conversion is performed so that the verification-value polynomial ap=X⁵+X². Next, theencryption unit114dperforms the encryption algorithm E on the verification-value polynomial ap, using the public-key polynomial hand the random-number polynomial r, to generate the following:

The first cipher text c[0463]1=the cipher text polynomial E(ap, r, h).

Next, the[0464]

encryption unit

114doutputs the generated first cipher text c1 to thesecond function unit115dand to thefirst transmitting unit117d.

115d

115dreceives the verification value a from thefirst function unit113d, and receives the first cipher text c1 from theencryption unit114d. Then, as described below, thesecond function unit115dgenerates a functional value for the verification value a and the first cipher text c1, namely the functional value H(a, c1).

Here, the function H is a hash function, and is one of the one-way functions.[0467]

The first cipher text c[0468]1 is an NTRU cryptographic cipher text and is represented in polynomial form. Therefore thesecond function unit115dgenerates a first cipher text bit sequence c1′, so that the coefficient of each term of the first cipher text c1 corresponds to the element of each bit of the N-bit first cipher-text bit sequence c1′, which is represented in binary form. For example, the coefficient of the term X^bwhich is the term of b-th degree of the first cipher text c1 is set as the element of the b-th lowest bit of the first cipher-text bit sequence c1′, thereby converting the first cipher text c1 into the first cipher-text bit sequence c1′. Concretely, if the first cipher text c1=X⁵+X², the conversion is performed so that the first cipher-text bit sequence c1′=10010 (representation in bit form).

Next, the[0469]

second function unit

115dinputs, into the hash function H, a||c1′ (which is the bit connecting between the verification value a and the first cipher-text bit sequence c1′), to generate the functional value H(a, c1)=H (a||c1′). Here, “||” is an operand representing bit connecting.

Next, the[0470]

second function unit

115doutputs the generated functional value H(a, c1) to the random-number mask unit116d.

116d

116dreceives the random number s from the random-number generating unit112d, and receives the functional value H(a, c1) from thesecond function unit115d. Next, the random-number mask unit116dgenerates the second cipher text c2=s xor H(a, c1), and outputs the generated second cipher text c2 to thefirst transmitting unit117d.

Note that the random-[0473]

number mask unit

116dmay use the symmetric key cryptographic encryption algorithm, addition, and multiplication, instead of xor (bitwise exclusive-or).

(7)[0474]

First Transmitting Unit

117d

The[0475]

first transmitting unit

117dreceives the first cipher text c1 from theencryption unit114d, and receives the second cipher text c2 from the random-number mask unit116d. Then thefirst transmitting unit117dtransmits the first cipher text c1 and the second cipher text c2, to thedecryption apparatus120dvia theInternet130.

(8) Shared-[0476]

Key Encryption Unit

118 andSecond Transmitting Unit119

The shared-[0477]

key encryption unit

118 and thesecond transmitting unit119 are the same as the shared-key encryption unit118 and thesecond transmitting unit119 that are included in theencryption apparatus110, except the following points.

The shared-[0478]

key encryption unit

118 receives the shared key K from thefirst function unit113d.

4.3 Structure of[0479]

Decryption Apparatus

120d

The[0480]

decryption apparatus

120d, as shown in FIG. 14, is comprised of a secret-key input unit121d, afirst receiving Unit122d, adecryption Unit123d, athird function unit124d, a random-numbermask removal unit125d, afourth function unit126d, acomparison unit127d, a shared-key decryption unit128, and asecond receiving unit129.

The[0481]

decryption apparatus

120dis a computer system similar to thedecryption apparatus120, and performs its function by operation of the microprocessor according to the computer program.

Note that the shared-[0482]

key decryption unit

128 and thesecond receiving unit129 are respectively the same as the shared-key decryption unit128 and thesecond receiving unit129 that are included in thedecryption apparatus120, and therefore will not be described in the following.

121d

121dreads, from thememory card170, the secret-key polynomial f for thedecryption apparatus120d, and outputs the read secret-key polynomial f to thedecryption unit123d.

122d

122dreceives the first cipher text c1 and the second cipher text c2, from theencryption apparatus110dvia theInternet130, and outputs the received first cipher text c1 to thedecryption unit123dand to thethird function unit124d, and outputs the received second cipher text c2 to the random-numbermask removal unit125d.

Note that when the random-[0487]

number mask unit

116d, instead of the bitwise exclusive-or, uses the symmetric key cryptographic encryption algorithm, the addition, or the multiplication, the random-numbermask removal unit125dmay use the symmetric key cryptographic decryption algorithm corresponding to the symmetric key cryptogrpahic encryption algorithm, the subtraction, or the division.

123d

123dreceives the secret-key polynomial f from the secret-key input unit121d, and receives the first cipher text c1 from thefirst receiving unit122d, and decrypts the first cipher text c1 using the secret-key polynomial f to generate a decryption verification value a′. Here, the decryption verification value a′ is an NTRU cryptographic decrypted text.

123doutputs the decryption verification value a′ to thethird function unit124dand to thecomparison unit127d.

124d

124dhas an algorithm for a function H that is the same function owned by thesecond function unit115d.

The[0494]

third function unit

124dreceives the first cipher text c1 from thefirst receiving unit122d, and receives the decryption verification value a′ from thedecryption unit123d. Next, thethird function unit124d, in the same manner as in thesecond function unit115d, generates a functional value of the verification value a′ and the first cipher text c1, namely H(a′, c1), and outputs the generated H(a′, c1) to the random-numbermask removal unit125d.

(5) Random-Number[0495]

Mask Removal Unit

125d

The random-number[0496]

mask removal unit

125dreceives the second cipher text c2 from thefirst receiving unit122d, and receives the hash functional value H(a′, c1) from thethird function unit124d. Then it generates a decryption random number s′=c2 xor H(a′, c1), and outputs the generated decryption random number s to thefourth function unit126d.

126d

126dhas an algorithm for a function G that is the same as the function owned by thefirst function unit113d.

The[0499]

fourth function unit

126dreceives the decryption random number s′ from the random-numbermask removal unit125d, and generates a hash functional value G(s′) of the decryption random number s′. Next, in the same manner as thefirst function unit113d, thefourth function unit126dgenerates a verification value a″ and a shared key K′ from the functional value G(s′), and outputs the verification value a″ and the shared key K′ to thecomparison unit127d.

127d

127dreceives the decryption verification value a′ from thedecryption unit123d, receives the verification value a″ and the shared key K′ from thefourth function unit126d, and checks whether the decryption verification value a′ is equal to the verification value a″. If they are equal, thecomparison unit127doutputs the shared key K′ to the shared-key decryption unit128.

(8) Shared-[0502]

Key Decryption Unit

128 andSecond Receiving Unit129

The shared-[0503]

key decryption unit

128 receives the shared key K′ from thecomparison unit127d.

For other points, the shared-[0504]

key decryption unit

128 is the same as the shared-key decryption unit128 included in thedecryption apparatus120, and so description thereof is omitted here.

In addition, the[0505]

second receiving unit

129 is the same as thesecond receiving unit129 included in thedecryption apparatus120, and description thereof is omitted here.

4.4 Operation of Content Distribution System[0506]10d

The operations performed by the content distribution system[0507]10dare described, using the process-block diagrams of FIG. 15 and FIG. 16.

The public-[0508]

key input unit

111dreceives, from thememory card160, the public-key polynomial h for thedecryption apparatus120d, and outputs the public-key polynomial h to theencryption unit114d(Step S201).

Next, the random-[0509]

number generating unit

112dgenerates a random number s, and outputs the random number s to thefirst function unit113dand to the random-number mask unit116d(Step S202).

The[0510]

first function unit

113dreceives the random number s from the random-number generating unit112d, and generates a functional value G(s) for the random numbers (Step S203). Then thefirst function unit113dgenerates a verification value a and a shared key K from the functional value G (s), outputs the verification value a to theencryption unit114dand to thesecond function unit115d, and outputs the shared key K to the shared-key encryption unit118 (Step S204).

Next, the[0511]

encryption unit

114dreceives the public-key polynomial h from the public-key input unit111d, and receives the verification value a from thefirst function unit113d. Then, theencryption unit114dgenerates a first cipher text c1 of the verification value a using the public-key polynomial h, and outputs the first cipher text cl to thesecond function unit115dand to thefirst transmitting unit117d(Step S205).

Next, the[0512]

second function unit

115dreceives the verification value a from thefirst function unit113d, receives the first cipher text c1 from theencryption unit114d, and generates a functional value of the verification value a and the first cipher text c1, namely the functional value H(a, c1), and outputs the functional value H(a, c1) to the random-number mask unit116 (Step S206).

The random-[0513]

number mask unit

116dreceives the random number s from the random-number generating unit112d, and receives the functional value H(a, c1) from thesecond function unit115d. The random-number mask unit116dgenerates a second cipher text c2=s xor H(a, c1) and outputs the second cipher text c2 to thefirst transmitting unit117d(Step S207).

Next, the[0514]

first transmitting unit

117dreceives the first cipher text c1 from theencryption unit114d, receives the second cipher text c2 from the random-number mask unit116d, and transmits the first cipher text c1 and the second cipher text c2 to thedecryption apparatus120dvia the Internet130 (Step S208).

Next, the shared-[0515]

key encryption unit

118 receives a plurality of plaintexts mi (1=<i=<n) from acontent server apparatus140, receives the shared key K from thefirst function unit113d, and performs the symmetric key cryptographic algorithm Sym on the plaintext mi (1=<i=<n) to generate a shared-key cipher text Ci=Sym(mi, K) (1=<i=<n), and outputs the shared-key cipher text Ci (1=<i=<n) to the second transmitting unit119 (Step S209).

The[0516]

second transmitting unit

119 receives the shared-key cipher text Ci (1=<i=<n) from the shared-key encryption unit118, transmits the shared-key cipher text Ci (1=<i=<n) to thedecryption apparatus120 via the Internet130 (Step S210), and ends the operations.

On the other hand, the secret-[0517]

key input unit

121dreceives, from thememory card170, the secret-key polynomial f for thedecryption apparatus120d, and outputs the secret-key polynomial f to the decryption apparatus123 (Step S251).

The[0518]

first receiving unit

122dreceives the first cipher text c1 and the second cipher text c2 from theencryption apparatus110dvia theInternet130, outputs the first cipher text c1 to thedecryption unit123dand to thethird function unit124d, and outputs the second cipher text c2 to the random-numbermask removal unit125d(Step S208).

Next, the[0519]

decryption unit

123dreceives the secret-key polynomial f from the secret-key input unit121, and receives the first cipher text c1 from thefirst receiving unit122d. Then thedecryption unit123ddecrypts the first cipher text c1 using the secret-key polynomial f, to generate a decryption verification value a′, and outputs the decryption verification value a′ to thethird function unit124dand to thecomparison unit127d(Step S252).

Next, the[0520]

third function unit

124dreceives the first cipher text c1 from thefirst receiving unit122d, and receives the decryption verification value a′ from thedecryption unit123d. Then as in the same manner as thesecond function unit115d, thethird function unit124dgenerates a functional value H(a′, c1) of the verification value a′ and the first cipher text c1, and outputs the functional value H(a′, c1) to the random-numbermask removal unit125d(Step S253).

The random-number[0521]

mask removal unit

125dreceives the second cipher text c2 from thefirst receiving unit122d, receives the hash functional value (a′, c1) from thethird function unit124d, generates a decryption random number s′=c2 xor H(a′, c1), and outputs the decryption random number s to thefourth function unit126d(Step S254).

The[0522]

fourth function unit

126dreceives the decryption random number s′ from the random-number mask removal unit125, and generates a hash functional value G(s′) of the decryption random number s′ (S255). In the same manner as thefirst function unit113d, thefourth function unit126dgenerates a verification value a″ and a shared key K′ from the functional value G(s′), and outputs the verification value a′ and the shared key K′ to thecomparison unit127d(Step S256).

Next, the[0523]

comparison unit

127dreceives the decryption verification value a′ from thedecryption unit123, receives the verification value a″ and the shared key K′ from thefourth function unit126d, checks whether the decryption verification value a′ is equal to the verification value a″, and if they are not equal (Step S257), ends the operations.

If the decryption verification value a′ and the verification value a″ are equal (Step S[0524]257), thecomparison unit127doutputs the shared key K′ to the shared-key decryption unit128 (Step S258).

Next, the[0525]

second receiving unit

129 receives the cipher text Ci (1=<i=<n) from the encryption apparatus1110dvia theInternet130, and outputs it to the shared-key decryption unit128 (Step S210).

The shared-[0526]

key decryption unit

128 receives the shared key K′ from thecomparison unit127d, receives the shared-key cipher text Ci (1=<i=<n) from thesecond receiving unit129, performs the symmetric key cryptographic algorithm Sym on the shared-key cipher text Ci (1=<i=<n) using the shared key K′ to generate the decrypted text mi′=Sym(Ci, K) (1=<i=<n), and outputs the decrypted text mi′ (1=<i=<n) to an external device (Step S259), and ends the operations.

4.5 Operation Verification of Content Distribution System[0527]10d

As follows, the entire operation performed by the content distribution system[0528]10dis described. First, theencryption apparatus110dgenerates a random numbers, using the public-key polynomial h of thedecryption apparatus120das an input, and derives a verification value a and a shared key K, from the functional value G(s). Next, theencryption apparatus110dencrypts the verification value a using the public-key polynomial h and according to the NTRU cryptosystem,to generate a first cipher text c1. Then theencryption apparatus110dgenerates a functional value H(a, c1) from the verification value a and the first cipher text c1, and generates a second cipher text c2=s xor H(a, c1) from the random number s and the functional value H(a, c1). Next, theencryption apparatus110dtransmits the first cipher text c1 and the second cipher text c2 to thedecryption apparatus120dvia theInternet130.

Specifically, this[0529]

encryption apparatus

110dperforms the following operations, so as to transmit the cipher text C=(c1, c2) to thedecryption apparatus120d.

Generate a random number s.[0530]

Generate G(s), and generate a and K, from the G(s).[0531]

Generate a first cipher text c[0532]1 of the verification value a, using a public-key polynomial h.

Generate c[0533]2=s xor H(a, c1).

Output the shared key K and the cipher text C=(c[0534]1, c2).

Next, the[0535]

encryption apparatus

110dencrypts the plaintext mi (1=<i=<n) having been inputted from acontent server apparatus140, using the derived shared key K and according to the symmetric key cryptography, to generate a cipher text Ci (1=<i=<n), and transmits the cipher text Ci (1=<i=<n) to thedecryption apparatus120dvia theInternet130.

On the other hand, the[0536]

decryption apparatus

120d, using the secret-key polynomial f of thedecryption apparatus120das an input, receives the first cipher text c1 and the second cipher text c2 from theencryption apparatus110dvia theInternet130, and decrypts the first cipher text c1, using the secret-key polynomial f, to generate a decryption verification value a′. Then, thedecryption apparatus120dgenerates a functional value H(a′, c1) from the decryption verification value a′ and the first cipher text c1, and generates a decryption random number s′=c2 xor H(a′, c1), from the second cipher text c2 and the functional value H(a′, c1). Thedecryption apparatus120dderives a verification value a″ and a shared key K′, from the functional value G (s′) of the decryption random number s′, and if the verification value a″=a′, outputs the shared key K′.

Specifically, this[0537]

decryption apparatus

120dperforms the following operations, so as to derive the shared key K′.

Decrypts the first cipher text c[0538]1 using the secret-key polynomial f, to generate a′.

Generate s′=c[0539]2 xor H(a′, c1).

Generate G(s′), and generate a″ and K′ from the G(s′).[0540]

Check to see if a″=a′ holds. If it holds, output the shared key K′.[0541]

Here, if the[0542]

decryption apparatus

120dhas used the correct secret-key polynomial f that corresponds to the public-key polynomial h that theencryption apparatus110dhas used, the first ciphertext c1 will be correctly decrypted, to generate the decryption verification value a′=a, therefore the decryption random number s′=s (the decryption random number s′ having been generated from the second cipher text c2 and the H(a′, c1)). Therefore, the verification value a″=a (the verification value a″ having been derived from the G(s′)). As a result, K′=K holds. Since a″=a′ holds, thedecryption apparatus120dcan derive the same shared key K as that derived by theencryption apparatus110d.

Next, the[0543]

decryption apparatus

120ddecrypts the shared-key cipher text Ci (1=<i=<n) having been received from theencryption apparatus110dvia theInternet130, using the derived shared key K′ (=K) and according to the symmetric key cryptography, to generate a decrypted text mi′ (1=<i=<n), and outputs the decrypted text mi′ to theplayback apparatus150.

Since the encryption key K (used for generation of the shared-key cipher text) is identical to the encryption key K′ (used for generation of decrypted text), the decryption apparatus can obtain the correct mi′=mi (1=<i=<n).[0544]

4.6 Effect of Third Embodiment[0545]

The conventional RSA-KEM algorithm uses a*P and a*W as input of a hash function H, and uses the Diffie-Hellman problem in the final stage of deriving the shared key K, with which the derivation of the shared key K is difficult unless the secret key is known. Therefore, other public-key cryptosystems that do not use the Diffie-Hellman problem, such as the NTRU cryptography, cannot take advantage of the PSEC-KEM algorithm, since these cryptosystems do not have inputs that correspond to a*P, and a*W of the Diffie-Hellman problem.[0546]

However in the present invention, the content distribution system, the encryption apparatus, and the decryption apparatus have a verification value a and its cipher text c[0547]1, as input of a hash function H. Therefore, PSEC-KEM algorithm can be applied, so as to use the NTRU cryptosystem and the other public-key cryptosystems.

Note that in the NTRU cryptosystem, there is a possibility that the resulting decrypted text is different from an original plaintext, even if a public key is used to encrypt a plaintext to generate a cipher text, and the cipher text is decrypted using the secret key (e.g. refer to the non-patent reference 2). If such a decryption error has occurred, an incorrect decryption verification value a′ will be obtained. However, the decryption apparatus of the present invention will not output the shared key K′, since a′ will not be equal to the verification value a″ obtained from G(s′). Therefore, the present invention has an effect of preventing different keys to be established between the encryption apparatus and the decryption apparatus, even if a decryption error has occurred.[0548]

In addition, the decryption apparatus will not perform operation for generating a re-cipher text. Therefore, the computation amount will be reduced, compared to the conventional technology.[0549]

According to this, key encapsulation mechanism can be constructed using the NTRU cryptography, and so the key distribution is realized between the encryption apparatus and decryption apparatus using the NTRU cryptography.[0550]

In addition, according to the system of the present invention, the security can be logically verified using the same method as the verification method described in the non-patent reference 3.[0551]

4.7 Modification Example[0552]

The third embodiment described above is one example of carrying out the present invention. Needless to say, the present invention is not limited to this particular embodiment, and can be carried with various modifications as long as they are within the scope of the present invention. In light of this, the following cases are included in the present invention.[0553]

(1) The parameter N to be used in NTRU cryptosystem may Take Other Value Than 167.[0554]

(2) The conversion from a bit sequence to polynomial, performed in the[0555]

encryption unit

114d, thesecond function unit115d, thedecryption unit123d, and thethird function unit124d, is not limited to as described and may be other methods.

For example, the conversion may be performed using a function or a functional-value table, which correspond bit sequence and polynomial in one-to-one relation.[0556]

Alternatively, the conversion method stated in the modification example (1) for the second embodiment may also be used.[0557]

(3) The public-key cryptosystem, used in the[0558]

encryption unit

114dand in thedecryption unit123d, is not limited to the one described, as long as itsencryption unit114dis operable to encrypt a verification value a using a public key to generate a first cipher text c1, and itsdecryption unit123dis operable to decrypt the first cipher text c1 using a secret key, to generate a decryption verification value a′ that is equal to the verification value a.

Accordingly, the public-key cryptosystem used in the[0559]

encryption unit

114dand in thedecryption unit123dmay be other cryptosystems different from the NTRU cryptosystem.

For example, if the RSA cryptosystem is to be used, h and f may be respectively set as a public key and a secret key of the RSA cryptosystem. Then, in the[0560]

encryption unit

114d, a is encrypted using h, to generate c1, and indecryption unit123d, c1 is decrypted using f, to generate a′.

In addition, if the E[0561]1Gama1 cryptosystem is to be used, h and f may be respectively set as a public key and a secret key of the E1Gama1 cryptosystem. Then, in theencryption unit114d, the random number r is generated, and a is encrypted using h and r, to generate c1, and indecryption unit123d, c1 is decrypted using f, to generate a′.

Note that the RSA cryptosystem and the E[0562]1Gama1 cryptosystem are described in greater detail in thenon-patent reference 1, therefore are not detailed here.

(4) In the third embodiment, the[0563]

first function unit

113dsets the K highest-order bits of the functional value G(s) as a verification value a, and the k lowest-order bits thereof are set as a shared key K. However, other methods maybe alternatively used, as long as the verification value a and the shared key K are derived from the functional value G(s).

(5) The[0564]

second function unit

115dmay use other methods, as long as a functional value H(a, c1) is derived from the verification value a and the first cipher text c1.

For example, with respect to a two term operation #, a#c[0565]1 may be inputted in the function H, thereby deriving the functional value. Note that the first cipher text c1 is a polynomial in the NTRU cryptosystem, and so it is possible to obtain the functional value by converting the first cipher text c1 to the first cipher text bit sequence c1′, and then inputting the a#c1′ in the function H.

(6) Furthermore, the Method Used in the[0566]

Second Function unit

115dmay be other methods, as long as a functional value is derived using a verification value a.

For example, the[0567]

second function unit

115dmay alternatively output H(a), or output the verification value a as it is. Specifically, in theencryption apparatus110d, the second cipher text c2 may be derived by:

making c[0568]2=s xor H(a), or

making c[0569]2=s xor a.

In such cases, the[0570]

third function unit

124dof thedecryption apparatus120dmay respectively output:

H(a′), or[0571]

a′.[0572]

(7) In the third embodiment, the random-[0573]

number mask unit

116dand the random-numbermask removal unit125dmay use other methods, as long as the random-number mask unit116dcan derive a second cipher text c2 from the random number s and the functional value H(a, c1), and the random-numbermask removal unit125dcan derive a random number s from the second cipher text c2 and the functional value H(a, c1).

For example, the random-[0574]

number mask unit

116dmay derive a second cipher text c2, by

making c[0575]2=s+H(a, c1), or

making s*H(a, c[0576]1).

5. Fourth Embodiment[0577]

The following describes a content distribution system[0578]10e(unshown in any drawing), as another embodiment relating to the present invention.

The content distribution system[0579]10eis a system based on the content distribution system10dof the third embodiment, with some modifications. The differences with the content distribution system10dare that: the encryption apparatus generates a random-number value u from the functional value (G), in addition to the verification value a and the shared key K, and generates the first cipher text cl by encrypting the verification value a using the random-number value u; and the method used in the decryption apparatus for performing judging relating to outputting of the shared key K.

The following description focuses on the differences mentioned above.[0580]

5.1 Structure of Content Distribution System[0581]10e

The content distribution system[0582]10ehas the similar structure as the content distribution system10d, except that theencryption apparatus110dand thedecryption apparatus120dare replaced by anencryption apparatus110eand adecryption apparatus120e, respectively. The other components are the same as those included in the content distribution system10d, therefore whose explanation is omitted here.

The content distribution system[0583]10eis a system that performs key distribution using the NTRU cryptosystem, where theencryption apparatus110eand thedecryption apparatus120eare connected to each other, via theInternet130.

5.2 Structure of[0584]

Encryption Apparatus

110e

The[0585]

encryption apparatus

110e, as shown in FIG. 17, includes a public-key input unit111d, a random-number generating unit112d, afirst function unit113e, anencryption unit114e, asecond function unit115d, a random-number mask unit116d, afirst transmitting unit117d, a shared-key encryption unit118, and asecond transmitting unit119.

Among the mentioned components, the public-[0586]

key input unit

111d, the random-number generating unit112d, thesecond function unit115d, the random-number mask unit116d, thefirst transmitting unit117d, the shared-key encryption unit118, and thesecond transmitting unit119 are the same as the components constituting theencryption apparatus110d, therefore will not be described here. Here, thefirst function unit113eand theencryption unit114eare focused, which are different from the counterparts of theencryption apparatus110d, and their structure and operation are described.

113e

113ereceives a random number s from the random-number generating unit112d, and generates a functional value G(s) of the random number s, then as shown below, generates a verification value a, a shared key K, and a random-number value u, from the generated functional value G(s).

Here, the function G is a hash function having output length of 3 k bits. The[0589]

first function unit

113esets the k highest-order bits of the functional value G(s), as a verification value a, the middle k bits of the functional value G(s) as a shared key K, and the k lowest-order bits of the functional value G(s) as a random-number value u.

Next, the[0590]

first function unit

113eoutputs the verification value a to theencryption unit114eand to thesecond function unit115d, outputs the shared key K to the shared-key encryption unit118, and outputs the random-number value u to theencryption unit114e.

114e

114ereceives a public-key polynomial h from the public-key input unit111d, and receives the verification value a and the random-number value u from thefirst function unit113e, and generates a first cipher text c1 of the verification value a, using the public-key polynomial h and the random-number value u, as shown below. Here, the first cipher text c1 is an NTRU cryptographic cipher text, and the random-number value u is a blind value used to making unclear the verification value a to be encrypted.

The[0593]

encryption unit

114egenerates a random-number polynomial r having the following characteristic so that it is uniquely defined by the random-number value u. The characteristic of the random-number polynomial r is such that, with respect to the parameter d of the NTRU cryptosystem, each coefficient of d terms is 1, each coefficient of other d terms is −1, and each coefficient of the rest of the terms is 0.

Specifically, the[0594]

encryption unit

114esets the random-number value u as a default value of the pseudo-random number system (random-number seed), and selects 2d pseudo-random numbers, from among {0, 1, . . . , N−1}, that do not overlap with each other. Then, theencryption unit114esets the coefficients of d terms of degree shown by the next d pseudo-random numbers as 1. Theencryption unit114esets the coefficients of d terms of degree shown by the rest of d pseudo-random numbers as −1, and the coefficients of the other terms of degree as 0. As a result, theencryption unit114egenerates the random-number polynomial r.

Next, in the same manner as the[0595]

encryption unit

114d, theencryption unit114egenerates a first cipher text c1=E(ap, r, h) using the random-number polynomial r.

Next, the[0596]

encryption unit

114eoutputs the generated first cipher text c1 to thesecond function unit115dand to thefirst transmitting unit117d.

5.3 Structure of[0597]

Decryption Apparatus

120e

The[0598]

decryption apparatus

120e, as shown in FIG. 18, includes a secret-key input unit121e, adecryption unit123e, athird function unit124d, a random-numbermask removal unit125d, afourth function unit126e, acomparison unit127e, a shared-key decryption unit128, and asecond receiving unit129.

Here, among the mentioned components, the[0599]

third function unit

124d, the random-numbermask removal unit125d, the shared-key decryption unit128, and thesecond receiving unit129 are the same as their counterparts included in thedecryption apparatus120d, therefore will not be described here. Here, the secret-key input unit121e, thedecryption unit123e, thefourth function unit126e, and thecomparison unit127eare focused, which are different from the counterparts of thedecryption apparatus120d, and their structure and operation are described.

121e

121ereceives, from thememory card170, the secret-key polynomial f and the public-key polynomial h of thedecryption apparatus120e, outputs the secret-key polynomial f to thedecryption unit123e, and outputs the public-key polynomial h to thecomparison unit127e.

123e

123ereceives the secret-key polynomial f from the secret-key input unit121e, and receives the first cipher text c1 from thefirst receiving unit122d. Next, thedecryption unit123edecrypts the first cipher text c1 using the secret-key polynomial f to generate a decryption verification value a′, outputs the decryption verification value a′ to thethird function unit124d, and outputs the first cipher text c1 to thecomparison unit127e.

126e

126ehas an algorithm for a function G that is the same as the function owned by thefirst function unit113e.

The[0606]

fourth function unit

126ereceives a decryption random number s′ from the random-numbermask removal unit125d, and generates a hash functional value G(s′) for the received decryption random number s′. Then, in the same manner as thefirst function unit113e, thefourth function unit126egenerates a verification value a″ a shared key K′, and a random-number value u′ from the functional value G(s′), and outputs the verification value a″, the shared key K′, and the random-number value u′, to thecomparison unit127e.

127e

127eis, as shown in FIG. 18, is comprised of acomparison computation unit127pand anencryption unit127q.

The[0609]

encryption unit

127qreceives the public-key polynomial h from the secret-key input unit121e, and receives the verification value a″ and the random-number value u′ from thefourth function unit126e. Then, theencryption unit127qencrypts the verification value a″ using the public-key polynomial h and the random-number value u′ and in the same way as in theencryption unit114d, to generate a first re-cipher text c1′, and outputs the first re-cipher text c1′ to thecomparison computation unit127p.

The[0610]

comparison computation unit

127preceives the first cipher text c1 from thedecryption unit123b, and receives the first re-cipher text c1′ from theencryption unit127q. Next, thecomparison computation unit127pcompares the first cipher text c1 and the first re-cipher text c1′, to judge whether c1′=c1 holds. If c1′=c1 holds, thecomparison computation unit127poutputs the shared key K′ to the shared-key decryption unit128, and if c1′=c1 does not hold, does not output the shared key K′.

5.4 Operation Verification of Content Distribution System[0611]10e

As follows, the entire operation performed by the content distribution system[0612]10eis described using the process-block diagram of FIG. 19.

The[0613]

encryption apparatus

110ereceives the public-key polynomial h for thedecryption apparatus120e(Step S201), generates a random number s (Step S202), generates a functional value G(s) (Step S203), and derives a verification value a, a shared key K, and a random-number value u from the functional value G(s) (Step S204e). Next, theencryption apparatus110eencrypts the verification value a using the public-key polynomial h and the random-number value u and according to the NTRU cryptosystem, to generate a first cipher text c1 (Step S205), generates a functional value H(a, c1) from the verification value a and the first cipher text c1 (Step S206), and generates a second cipher text c2=s x or H(a, c1), from the random number s and the functional value H(a, c1) (Step S207). Then theencryption apparatus110btransmits the first cipher text cl and the second cipher text c2 to thedecryption apparatus120evia the Internet130 (Step S208).

Specifically, this[0614]

encryption apparatus

110eperforms the following operations (a)-(d), so as to transmit the cipher text C(c1, c2) to thedecryption apparatus120e.

(a) Generate a random number s.[0615]

(b) Generate G(s), and generate a, K, and u, from the G(s).[0616]

(c) Generate a first cipher text c[0617]1 of the verification value a, using a public-key polynomial hand a random-number value u.

(d)Generate c[0618]2=s xor H(a, c1).

Next, the[0619]

encryption apparatus

110eencrypts the plaintext mi (1=<i=<n) having been inputted from thecontent server apparatus140, using the derived shared key K and according to the symmetric key cryptography, to generate a cipher text Ci (1=<i=<n) (Step S209), and transmits the cipher text Ci (1=<i=<n) to thedecryption apparatus120evia the Internet130 (Step S210).

On the other hand, the[0620]

decryption apparatus

120ereceives the secret-key polynomial f and the public-key polynomial h of thedecryption apparatus120e(Step S251, Step S251e), and receives the first cipher text c1 and the second cipher text c2 from theencryption apparatus110evia the Internet130 (Step S208), then decrypts the first cipher text c1, using the secret-key polynomial f, to generate a decryption verification value a′ (Step S252). Then, thedecryption apparatus120egenerates a functional value H(a′, c1) from the decryption verification value a′ and the first cipher text c1 (Step S253), and generates a decryption random number s′=c2 xor H(a′, c1), from the second cipher text c2 and the functional value H(a′, c1) (Step S254). Thedecryption apparatus120egenerates a functional value G(s′) of the decryption random number s′ (Step S255), derives a verification value a″, a shared key K′, a random-number value u′, from the generated functional value G(s′) (Step S256e), generates a first re-cipher text c1′ by encrypting the verification value a″ (Step S261) and if c1′=c1 holds (Step S257e), outputs the shared key K′(Step S258).

Specifically, the[0621]

decryption apparatus

120eperforms the following processes (a)-(e), to derive the shared key K′.

(a) Decrypt the first cipher text c[0622]1 using the secret-key polynomial f, to generate a′.

(b) Generate s′=c[0623]2 xor H(a′, c1).

(c) Generate G(s′), and generate a″, K′, and u′ from the G(s′).[0624]

(d) Generate a first re-cipher text c[0625]1′ of a″ using the public-key polynomial h and the random-number value u′.

(e) Check to see if c[0626]1′=c1 holds, if it holds, output the shared key K′.

Here, if the[0627]

decryption apparatus

120ehas used the correct secret-key polynomial f that corresponds to the public-key polynomial h that theencryption apparatus110ehas used, the first cipher text c1 will be correctly decrypted, to generate the decryption verification value a′=a, therefore the decryption random number s′=s (the decryption random number s′ having been generated from the second cipher text c2 and the H(a′, c1)). Therefore, the verification value a″=a (the verification value a″ having been derived from the G(s′)). As a result, the shared key K′=K holds, and the random-number value u′=u holds. Since a″=a, and u′=u hold, c1′=c1 also holds, thedecryption apparatus120ecan derive the same shared key as that derived by theencryption apparatus110e.

Next, the[0628]

decryption apparatus

120eusing the derived shared key K′ (=K), receives the shared-key cipher text Ci (1=<i=<n) from theencryption apparatus110evia the Internet130 (Step S210), decrypts the shared-key cipher text Ci (1=<i=<n) using the derived shared key K′ (=K) and according to the symmetric key cryptography, to generate a decrypted text mi′ (1=<i=<n) (Step S259), and outputs the decrypted text mi′ (1=<i=<n) to theplayback apparatus150.

Since the encryption key K (used for generation of the shared-key cipher text) is identical to the encryption key K′ (used for generation of decrypted text), the decryption apparatus can obtain the correct mi′=mi (1=<i=<n).[0629]

5.5 Effect of Content Distribution System[0630]10e

The conventional RSA-KEM algorithm uses a*P and a*W as input of a hash function H, and uses the Diffie-Hellman problem in the final stage of deriving the shared key K, with which the derivation of the shared key K is difficult unless the secret key is known. Therefore, other public-key cryptosystems that do not use the Diffie-Hellman problem, such as the NTRU cryptography, cannot take advantage of the PSEC-KEM algorithm, since these cryptosystems do not have inputs that correspond to a*P, and a*W of the Diffie-Hellman problem.[0631]

However in the present invention, the content distribution system, the encryption apparatus, and the decryption apparatus have a verification value a and its cipher text c[0632]1, as input of a hash function H. Therefore, the NTRU cryptosystem and the other public-key cryptosystems can be applied thereto, just as to the third embodiment.

If a decryption error has occurred, an incorrect decryption verification value a′ will be obtained. However, the decryption apparatus of the present invention will not output the shared key K′, since c[0633]1′ will not be equal to c1. Therefore, the present invention has an effect of preventing different keys to be established between the encryption apparatus and the decryption apparatus, even if a decryption error has occurred.

According to this, key encapsulation mechanism can be constructed using the NTRU cryptosystem, and so the key distribution is realized between the encryption apparatus and decryption apparatus using the NTRU cryptosystem.[0634]

In addition, according to the system of the present invention, the security can be logically verified using the same method as the verification method described in the non-patent reference 3.[0635]

5.6 Modification Example[0636]

The fourth embodiment described above is one example of carrying out the present invention. The present invention is not limited to this particular embodiment, and can be carried with various modifications as long as they are within the scope of the present invention. Needless to say, the same modification examples for the third embodiment can be provided for the fourth embodiment. However, the following cases are also included in the present invention.[0637]

(1) The method of converting the random-number value u to the random-number polynomial r, performed in the[0638]

encryption unit

114e, is not limited to the described method, as long as r is uniquely obtained from u. For example, a function or a functional-value table may be alternatively used, which correspond the random-number value u to the polynomial.

Alternatively, the conversion method stated in the modification example (1) for the second embodiment may also be used.[0639]

(2) The public-key cryptosystem, used in the[0640]

encryption unit

114eand in thedecryption unit123e, is not limited to the one described, as long as itsencryption unit114eis operable to encrypt a verification value a using a public key and a random-number value u to generate a first cipher text c1, and itsdecryption unit123eis operable to decrypt the first cipher text c1 using a secret key, to generate a decryption verification value a′ that is equal to the verification value a. Accordingly, the public-key cryptosystem used in theencryption unit114eand in thedecryption unit123emay be other cryptosystems different from the NTRU cryptosystem, as long as they use random number.

If the E[0641]1Gama1 cryptosystem is to be used, h and f may be respectively set as a public key and a secret key of the E1Gama1 cryptosystem. Then, in theencryption unit114e, a is encrypted using h and a random-number value u, to generate c1, and indecryption unit123e, c1 is decrypted using f, to generate a′.

(3) In the fourth embodiment, the random-number value u is generated in the[0642]

first function unit

113eand in thesecond function unit126e. However, other generation methods may be used, as long as the same value is generated in theencryption apparatus110eand in thedecryption apparatus120e.

For example, u=Func(s) may be used with respect to an arbitrary function Func, so that the[0643]

encryption apparatus

110eobtains the same value as that thedecryption apparatus120eobtains. Specifically,

generate G(s), and generate a, and K from the G(s), and[0644]

generate Func(s), and sets u=Func(s).[0645]

(4) Further, the random-number value u is generated in the[0646]

first function unit

113eand in thefourth function unit126e. However, the condition to be satisfied here is that theencryption apparatus110eand thedecryption apparatus120eobtain the same value. Therefore, theencryption apparatus110emay transmit the random-number value u directly to thedecryption apparatus120e.

Specifically, the cipher text C and the random-number value u may be transmitted to the[0647]

decryption apparatus

120eas stated below.

Generate G(s), and generate a and K from the G(s).[0648]

The[0649]

encryption apparatus

110etransmits the random-number value u separately, to thedecryption apparatus120e.

At this time, it may be arranged that the[0650]

encryption apparatus

110 encrypt the random-number value u before transmitting it.

(5) Furthermore, as for the random-number value u, the condition is that the[0651]

encryption apparatus

110eand thedecryption apparatus120eobtain the same value. Therefore, it may be arranged to generate part of the information for the random-number value u in thefirst function unit113eand in thefourth function unit126e, and to directly transmit the rest of the information for the random-number value u from theencryption apparatus110eto thedecryption apparatus120e.

For instance, the cipher text C and the random-number value u2 may be transmitted to the[0652]

decryption apparatus

120e, as follows:

Generate G(s), and generate a, K, and u1, from the G(s)[0653]

The[0654]

encryption apparatus

110etransmits the random-number value u2 separately to thedecryption apparatus120e.

Generate a random-number value u, from u=u1 xor u2.[0655]

At this time, the[0656]

encryption apparatus

110emay encrypt the random-number value u2 before transmitting it.

(6) The[0657]

decryption apparatus

120echecks to see if the first cipher text c1 is a cipher text of the verification value a″ that thefourth function unit126eobtains, and uses the shared key K′ in decrypting the shared-key cipher text Ci, only if c1 is turned out to be a cipher text of a″. However, the same checking method as used by thedecryption apparatus120dof the third embodiment may be used.

Specifically, as the process-block diagram of FIG. 20 shows, the check may be performed using the[0658]

decryption unit

123dcorresponding to thedecryption apparatus120d, and thecomparison unit127d, in the following manner.

(a) Decrypt the first cipher text c[0659]1 using the secret-key polynomial f, to generate a′ (Step S252).

(b) Generate s′=c[0660]2 xor H(a′, c1) (Step S254).

(c) Generate G(s′) (Step S[0661]255), and generate a″, K′, and u′, from the G(s′) (Step S256e).

(d) Check to see if a″=a′ holds (Step S[0662]257). If it holds, output the shared key K′ (Step S258).

In addition, in this process, it may check whether the first cipher text c[0663]1 is a cipher text of the decryption verification value a′.

7. Summary of Third and Fourth Embodiments[0664]

As described so far, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into verification-value data and the shared-key data, based on a predetermined process; and a first encryption unit operable to encrypt the verification-value data based on the public-key data, to generate first encryption preliminary data; a verification-value conversion unit operable to convert the verification-value data into conversion verification-value data, based on a predetermined process; and a second encryption unit operable to encrypt the secret-number data based on the conversion verification-value data, to generate second encryption preliminary data, where the encryption shared-key data is made up of the first encryption preliminary data and the second encryption preliminary data.[0665]

In addition, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data and first encryption preliminary data into verification-value data and the shared-key data, based on a predetermined process; and a first encryption unit operable to encrypt the verification-value data based on the public-key data, to generate the first encryption preliminary data; a verification-value conversion unit operable to convert the verification-value data into conversion verification-value data, based on a predetermined process; and a second encryption unit operable to encrypt the secret-number data based on the conversion verification-value data, to generate second encryption preliminary data, where the encryption shared-key data is made up of the first encryption preliminary data and the second encryption preliminary data.[0666]

In addition, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into verification-value data, random-number data, and the shared-key data, based on a predetermined process; a first encryption unit operable to encrypt the verification-value data based on the public-key data and the random-number data, to generate first encryption preliminary data; a verification-value conversion unit operable to convert the verification-value data into conversion verification-value data, based on a predetermined process; and a second encryption unit operable to encrypt the secret-number data based on the conversion verification-value data, to generate second encryption preliminary data, where the encryption shared-key data is made up of the first encryption preliminary data and the second encryption preliminary data.[0667]

In addition, the present invention is a shared-key generation apparatus, which outputs shared-key data, and encryption shared-key data resulting from encrypting the shared-key data based on predetermined public-key data. The shared-key generation apparatus specifically includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert the secret-number data into verification-value data, random-number data, and the shared-key data, based on a predetermined process; a first encryption unit operable to encrypt the verification-value data based on the public-key data and the random-number data, to generate first encryption preliminary data; a verification-value conversion unit operable to convert the verification-value data and the first encryption preliminary data into conversion verification-value data, based on a predetermined process; and a second encryption unit operable to encrypt the secret-number data based on the conversion verification-value data, to generate second encryption preliminary data, where the encryption shared-key data is made up of the first encryption preliminary data and the second encryption preliminary data.[0668]

Here, the secret-number data may be a random number having been randomly generated.[0669]

Here, the shared-key derivation unit may use a one-way hash function, as the predetermined process.[0670]

Here, the first encryption unit may perform an NTRU cryptographic encryption, to generate the first encryption preliminary data.[0671]

Here, the verification-value conversion unit may use a one-way hash function, as the predetermined process.[0672]

Here, the predetermined process preformed by the verification-value conversion unit may be to set the verification-value data as it is, as the conversion verification-value data.[0673]

Here, the second encryption unit may perform bitwise exclusive-or on the secret-number data and the conversion verification-value data, to generate the second encryption preliminary data.[0674]

Here, the second encryption unit may encrypt the secret-number data using the conversion verification-value data as a cryptographic key and according to the symmetric key cryptography, to generate the second encryption preliminary data.[0675]

Here, the second encryption unit may add the conversion verification-value data to the secret-number data, to generate the second encryption preliminary data.[0676]

Here, the second encryption unit may multiply the secret-number data by the conversion verification-value data, to generate the second encryption preliminary data.[0677]

Here, the encryption shared-key data may be bit connecting data between the first encryption preliminary data and the second encryption preliminary data.[0678]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on predetermined secret-key data, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data and the first encryption preliminary data into conversion verification-value data; a second decryption unit operable to decrypt the second encryption preliminary data based on the conversion verification-value data, to generate secret-number data; and a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data and the shared-key data, where the shared-key recovery apparatus outputs the shared-key data when the verification-value data is equal to the verification-value verification data.[0680]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on predetermined secret-key data, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data and the first encryption preliminary data into conversion verification-value data; a second decryption unit operable to decrypt, based on the conversion verification-value data, the second encryption preliminary data into secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data, random-number data, and the shared-key data, where the shared-key recovery apparatus outputs the shared-key data when the verification-value data is equal to the verification-value verification data.[0682]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on secret-key data and public key data that are predetermined, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data into conversion verification-value data; a second decryption unit operable to decrypt, based on the conversion verification-value data, the second encryption preliminary data into secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data, random-number data, and the shared-key data; and a third encryption unit operable to encrypt the verification-value verification data based on the public-key data and the random-number data, to generate third encryption preliminary data, where the shared-key recovery apparatus outputs the shared-key data when the first encryption preliminary data is equal to the third encryption preliminary data.[0683]

In addition, the present invention is a shared-key recovery apparatus, which decrypts encryption shared-key data based on secret-key data and public key data that are predetermined, to generate shared-key data, and outputs the generated shared-key data, the encryption shared-key data being made up of first encryption preliminary data and second encryption preliminary data. The shared-key recovery apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data into conversion verification-value data; a second decryption unit operable to decrypt, based on the conversion verification-value data, the second encryption preliminary data into secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data, random-number data, and the shared-key data; and a third encryption unit operable to encrypt the verification-value data based on the public-key data and the random-number data, to generate third encryption preliminary data, where the shared-key recovery apparatus outputs the shared-key data when the first encryption preliminary data is equal to the third encryption preliminary data.[0684]

Here, the shared-key derivation unit may use a one-way hash function, as the predetermined process.[0687]

Here, the first decryption unit may perform NTRU cryptographic decryption, to generate the verification-value data.[0688]

Here, the verification-value conversion unit may use a one-way hash function, as the predetermined process.[0689]

Here, the predetermined process preformed by the verification-value conversion unit may be to set the verification-value data as it is, as the conversion verification-value data.[0690]

Here, the second decryption unit may perform bitwise exclusive-or on the second encryption preliminary data and the conversion verification-value data, to generate the secret-number data.[0691]

Here, the second decryption unit may decrypt the second encryption preliminary data using the conversion verification-value data as a cryptographic key and according to the symmetric key cryptography, to generate the secret-number data.[0692]

Here, the second decryption unit may subtract the conversion verification-value data from the second encryption preliminary data, to generate the secret-number data.[0693]

Here, the second decryption unit may divide the second encryption preliminary data by the conversion verification-value data, to generate the secret-number data.[0694]

In addition, the present invention is an encryption apparatus that encrypts data based on predetermined public-key data, to generate cipher-text data. The encryption apparatus includes: a secret-number data generating unit operable to generate secret-number data; a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value data and shared-key data; a first encryption unit operable to encrypt the verification-value data based on the public-key data, to generate first encryption preliminary data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data into conversion verification-value data; a second encryption unit operable to encrypt the secret-number data based on the conversion verification-value data, to generate second encryption preliminary data; and a third encryption unit operable to encrypt the plaintext data based on the shared-key data, to generate third encryption preliminary data, where the cipher-text data is made up of the first encryption preliminary data, the second encryption preliminary data, and the third encryption preliminary data.[0695]

Further, the present invention is a decryption apparatus that decrypts, based on predetermined secret-key data, cipher-text data made up of first encryption preliminary data, second encryption preliminary data, and third encryption preliminary data, to generate decrypted-text data, and outputs the decrypted-text data. The decryption apparatus includes: a first decryption unit operable to decrypt the first encryption preliminary data based on the secret-key data, to generate verification-value data; a verification-value conversion unit operable to convert, based on a predetermined process, the verification-value data into conversion verification-value data; a second decryption unit operable to decrypt the second encryption preliminary data based on the conversion verification-value data, to generate secret-number data; and a shared-key derivation unit operable to convert, based on a predetermined process, the secret-number data into verification-value verification data and shared-key data; and a decryption unit operable, when the verification-value data is identical to the verification-value verification data, to decrypt the third encryption preliminary data based on the shared-key, to generate the decrypted-text data.[0696]

As described above, the present invention has been conceived in view of the problems that the conventional system has, and constructs in a cryptosystem an encapsulation mechanism to which NTRU cryptosystem can be applied, thereby realizing key distribution between its encryption apparatus and decryption apparatus using NTRU cryptography.[0698]

As clear from the above, the present invention provides a cryptosystem that the conventional technologies were not able to provide, therefore is very valuable.[0699]

8. Other Modification Examples[0700]

So far, the present invention has been described by way of the aforementioned embodiments. However, needless to say, the present invention is not limited to the aforementioned embodiments, and includes the following cases.[0701]

(1) Instead of transmitting each of cipher texts to the decryption apparatus via the Internet, the encryption apparatus may alternatively write each cipher text in a recording medium such as a DVD, and the decryption apparatus may accordingly read each cipher text from the recording medium.[0702]

(2) The NTRU cryptosystem used in the present invention may be, instead of in the type described in the non-patent reference 3, in an EESS (efficient embedded security standard) type. The detail of the EESS-type NTRU cryptosystem is described in “EESS: Consortium for efficient embedded security, efficient embedded security standards #1: Implementation aspects of NTRU encrypt and NTRU sign, Version 2.0,” available at http://www.ceesstandards.org, May 2003. Therefore, the following only briefly discusses the EESS-type NTRU cryptosystem.[0703]

In the EESS-type NTRU cryptosystem, a random-number polynomial r is either a polynomial expression that has d coefficients of 1, and (N-d) coefficients of 0, or a polynomial expression obtained using a plurality of such polynomial expressions. Therefore, if the random polynomial r in the above-described embodiments is generated to yield such polynomial expressions, the EESS-type NTRU cryptosystem may be alternatively used, instead of the NTRU cryptosystem, with a similar effect.[0704]

(3) The content distribution system may be structured as follows.[0705]

That is, the content distribution system may be comprised of a content server apparatus, an encryption apparatus, a broadcast apparatus, a reception apparatus, a decryption apparatus, a playback apparatus, and a monitor.[0706]

Here, the encryption apparatus and the decryption apparatus respectively correspond to the[0707]

encryption apparatus

110 and thedecryption apparatus120 of thecontent distribution system10.

The content server apparatus and the encryption apparatus are connected to each other via a dedicated circuit, and the content server apparatus transmits contents such as movie, made up of image and audio, to the encryption apparatus via this dedicated circuit. The encryption apparatus and the broadcast apparatus are connected with each other via a dedicated circuit. The encryption apparatus transmits each of cipher texts to the broadcast apparatus, and the broadcast apparatus performs multiplexing on the cipher texts, and broadcasts them over a digital broadcast wave.[0708]

The reception apparatus and the decryption apparatus are connected to each other, and likewise, the decryption apparatus and the playback apparatus are connected to each other too. The reception apparatus receives a digital broadcast wave, extracts each of cipher texts from the received digital broadcast wave, and transmits extracted cipher texts to the decryption apparatus. The decryption apparatus receives the cipher texts, generates a playback content using the received cipher texts, and outputs the generated playback content to the playback apparatus. The playback apparatus is connected to the decryption apparatus and to the monitor that includes therein a speaker. The playback apparatus receives the playback content, and generates an image signal and an audio signal, from the received playback content, and the monitor displays an image and outputs an audio.[0709]

(4) The content server apparatus and the encryption apparatus may be integrated into one apparatus. The decryption apparatus and the playback apparatus may be also integrated into one apparatus.[0710]

(5) In each of the aforementioned embodiments, the[0711]

memory card

160 prestores a public-key polynomial h, and thememory card170 prestores a secret-key polynomial f and a public-key polynomial h. Theencryption apparatus110 and thedecryption apparatus120 obtain, from thememory card160 and thememory card170, a public-key polynomial and a secret-key polynomial respectively. However, the present invention is not limited to such.

Alternatively, the[0712]

encryption apparatus

110 may prestore a public-key polynomial, and thedecryption apparatus120 may prestore a public-key polynomial and a secret-key polynomial.

In addition, the key management apparatus may generate a secret-key polynomial and a public-key polynomial, and transmit the secret-key polynomial and the public-key polynomial secretly and securely, to the[0713]

decryption apparatus

120, and transmit the public-key polynomial secretly and securely to theencryption apparatus110.

(6) The contents to be distributed in the content distribution system is not limited to contents such as movie, comprised of image and audio. Alternatively, the contents may include a database generated by moving images, still images, audio, music, document, novel, DB software, and the like. Further, electric spreadsheet-data and computer program generated using spreadsheet software, and other kinds of data for computer may be included therein.[0714]

Furthermore, the contents may, instead of being the mentioned work, may alternatively be key information used for such as encryption, decryption, digital signature, and signature verification.[0715]

For example, the following arrangement is possible. As described in each of the above embodiments, the encryption apparatus and the decryption apparatus share a same shared-key. On this premise, the encryption apparatus encrypts a content key using the shared key to generate an encrypted content key, encrypts a content using the content key to generate an encrypted content, and transmits the encrypted content key and the encrypted content to the decryption apparatus. Then the decryption apparatus receives the encrypted content key and the encrypted content, decrypts the encrypted content key using the shared key to generate the content key, and decrypts the encrypted content using thus obtained content key, to finally obtain the content.[0716]

(7) The present invention may be methods of the above description. Moreover, the present invention may be a computer program that realizes these methods using a computer, or may be a digital signal comprised of the computer program.[0717]

In addition, the present invention may be a computer-readable recording medium storing the mentioned computer program or the mentioned digital signal. The computer-readable recording medium includes: a flexible disc, a hard disc, a CD-ROM, an MO, a DVD, a DVD-ROM, a DVD-RAM, a BD(blu-ray disc), and a semiconductor memory.[0718]

In addition, the present invention may be the computer program and the digital signal, in a form recorded in these recording mediums.[0719]

In addition, the present invention may be to transmit the computer program or the digital signal, such as via a network and a data broadcast and the like, the network being represented by an electric communication circuit, a radio circuit, a cable communication circuit, and the Internet.[0720]

In addition, the present invention may be a computer system equipped with a microprocessor and a memory, where the memory stores the computer program, and the microprocessor operates according to the computer program.[0721]

In addition, another computer system that is independent may execute the present invention, by transmitting the computer program or the digital signal in a form stored in the recording medium, or by transmitting the computer program or the digital signal via the described network, and the like.[0722]

(8) The present invention may be a combination of some of the described embodiments and the modification examples.[0723]

Although the present invention has been fully described by way of examples with reference to accompanying drawings, it is to be noted that various changes and modifications will be apparent to those skilled in the art. Therefore, unless such changes and modifications depart from the scope of the present invention, they should be construed as being included therein.[0724]

([0725]
PCT
)

Industrial Applicability

The content distribution system described above is used managerially, repeatedly, and continuously, in an industry where a content supplier provides users with digital work such as music, movie, and novel. Furthermore, the encryption apparatus and the decryption apparatus that constitute the content distribution system are produced and sold, in the electric-appliance industry selling electric appliances.[0726]
In particular, the present invention is preferable in industries that supply digital work in recorded form in a recording medium, either by distribution in the market, via the network, or by the broadcast.[0727]
Although the present invention has been fully described by way of examples with reference to accompanying drawings, it is to be noted that various changes and modifications will be apparent to those skilled in the art. Therefore, unless such changes and modifications depart from the scope of the present invention, they should be construed as being included therein.[0728]

Claims

What is claimed is:

1. A key agreement system comprising a shared-key generation apparatus and a shared-key recovery apparatus, each apparatus establishing therein a same shared key in secrecy, wherein

the shared-key generation apparatus includes:

a seed-value generating unit operable to generate a seed value;

a first shared-key generating unit operable to generate a blind value and a shared key, from the seed value;

an encryption unit operable to encrypt the seed value based on the blind value, to generate encryption information; and

a transmitting unit operable to transmit the encryption information, and

the shared-key recovery apparatus includes:

a receiving unit operable to receive the encryption information;

a decryption unit operable to decrypt the encryption information, to generate a decryption seed value;

a second shared-key generating unit operable to generate a decryption blind value and a decryption shared key, using the decryption seed value and according to a same method as used in the first shared-key generating unit;

a re-encryption unit operable to encrypt the decryption seed value based on the decryption blind value, to generate re-encryption information;

a judging unit operable to judge, based on the encryption information and the re-encryption information, whether the decryption shared key should be outputted; and

an outputting unit operable, when the judging unit has judged affirmatively, to output the decryption shared key.

2. The key agreement system ofclaim 1, wherein

the shared-key generation apparatus further includes:

an obtaining unit operable to obtain a content; and

an encryption unit operable to encrypt the obtained content using the shared key, to generate an encrypted content,

the transmitting unit further transmits the encrypted content,

the receiving unit further receives the encrypted content, and the shared-key recovery apparatus further includes:

a decryption unit operable to decrypt the received encrypted content using the decryption shared key, to generate a decrypted content; and

an outputting unit operable to output the decrypted content.

3. A shared-key generation apparatus that notifies a destination apparatus about a shared key in secrecy, the shared-key generation apparatus comprising:

a seed-value generating unit operable to generate a seed value;

a shared-key generating unit operable to generate a blind value and a shared key, from the seed value;

a transmitting unit operable to transmit the encryption information.

4. The shared-key generation apparatus ofclaim 3, wherein

the shared-key generating unit performs a one-way function on the seed value, to generate a functional value, and generates the blind value and the shared key from the functional value,

the encryption unit includes:

a public-key obtaining subunit operable to obtain a public key; and

a public-key encryption subunit operable to perform a public-key encryption algorithm on the seed value, using the public key and the blind value, to generate an encryption seed value as the encryption information.

5. The shared-key generation apparatus ofclaim 4, wherein

the public-key encryption algorithm conforms to an NTRU cryptosystem,

the public-key obtaining subunit obtains a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key,

the public-key encryption subunit generates a seed-value polynomial from the seed value, generates a blind-value polynomial from the blind value, and encrypts the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the encryption seed value, and

the transmitting unit transmits the encryption seed-value polynomial as the encryption seed value.

6. The shared-key generation apparatus ofclaim 3, wherein

the encryption unit includes:

a public-key obtaining subunit operable to obtain a public key;

a public-key encryption subunit operable to generate a blind value, perform the public-key encryption algorithm on the seed value using the public key and the blind value, to generate a public-key cipher text; and

a function subunit operable to perform a second one-way function on at least one of the seed value, the blind value, and the shared key, to generate a second functional value, and

the encryption unit generates the encryption information that includes the public-key cipher text and the second functional value.

7. The shared-key generation apparatus ofclaim 6, wherein

the shared-key generating unit performs a one-way function on the seed value, to generate a functional value, and generates the blind value and the shared key from the functional value.

8. The shared-key generation apparatus ofclaim 6, wherein

the shared-key generating unit performs a first one-way function on the seed value, to generate a first functional value, and generates the shared key from the first functional value, instead of generating the blind value and the shared key.

9. The shared-key generation apparatus ofclaim 6, wherein

the public-key encryption algorithm conforms to an NTRU cryptosystem,

the public-key encryption subunit generates a seed-value polynomial from the seed value, generates a blind-value polynomial from the blind value, encrypts the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the public-key cipher text, and

the encryption unit generates the encryption information that includes the encryption seed-value polynomial as the public-key cipher text and the second functional value.

10. The shared-key generation apparatus ofclaim 3, wherein

the shared-key generating unit performs a one-way function on the seed value, to generate a functional value, and generates a verification value, the blind value, and the shared key, from the functional value,

the encryption unit includes:

a public-key obtaining subunit operable to obtain a public key;

a first encryption subunit operable to perform a public-key encryption algorithm on the verification value, using the public key and the blind value, to generate a first cipher text; and

a second encryption subunit operable to perform, on the seed value, a computation algorithm different from the public-key encryption algorithm, to generate a second cipher text, and

the encryption unit generates the encryption information that includes the first cipher text and the second cipher text.

11. The shared-key generation apparatus ofclaim 10, wherein

the public-key encryption algorithm conforms to an NTRU cryptosystem,

the first encryption subunit generates a verification-value polynomial from the verification value, generates a blind-value polynomial from the blind value, and encrypts the verification-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the verification-value polynomial, to generate an encryption verification-value polynomial as the first cipher text, and

the encryption unit generates the encryption information that includes the encryption verification-value polynomial as the first cipher text and the second cipher text.

12. The shared-key generation apparatus ofclaim 11, wherein

the different computation algorithm is a symmetric key encryption algorithm, and

the second encryption subunit performs the symmetric key encryption algorithm on the seed value using the verification value as a key, to generate the second cipher text.

13. The shared-key generation apparatus ofclaim 11, wherein

the different computation algorithm is bitwise exclusive-or, and

the second encryption subunit performs the bitwise exclusive-or on the verification value and the seed value, to generate the second cipher text.

14. The shared-key generation apparatus ofclaim 11, wherein

the different computation algorithm is addition, and

the second encryption subunit performs the addition on the verification value and the seed value, to generate the second cipher text.

15. The shared-key generation apparatus ofclaim 11, wherein

the different computation algorithm is multiplication, and

the second encryption subunit performs the multiplication on the verification value and the seed value, to generate the second cipher text.

16. The shared-key generation apparatus ofclaim 3, wherein

the seed-value generating unit generates a random number, as the seed value.

17. The shared-key generation apparatus ofclaim 3, wherein

18. The shared-key generation apparatus ofclaim 17, wherein

the one-way function is a hash function, and

the shared-key generating unit performs the hash function on the seed value.

19. The shared-key generation apparatus ofclaim 17, wherein

the shared-key generating unit generates the blind value by setting a part of the functional value as the blind value, and generates the shared key by setting another part of the functional value as the shared key.

20. The shared-key generation apparatus ofclaim 3, further comprising:

obtaining unit operable to obtain a content; and

an encryption unit operable to encrypt the obtained content using the shared key, to generate an encrypted content, wherein

the transmitting unit further transmits the encrypted content.

21. A shared-key recovery apparatus that receives a shared key from a shared-key generation apparatus in secrecy, the shared-key generation apparatus generating a seed value, generating a blind value and a shared key from the seed value, encrypting the seed value based on the blind value to generate encryption information, and transmitting the encryption information, the shared-key recovery apparatus comprising:

a receiving unit operable to receive the encryption information;

a shared-key generating unit operable to generate a decryption blind value and a decryption shared key, using the decryption seed value and according to a same shared-key generating method used in the shared-key generation apparatus;

22. The shared-key recovery apparatus ofclaim 21, wherein

the shared-key generation apparatus performs a one-way function on the seed value to generate a functional value, generates the blind value and the shared key from the functional value, obtains a public key, performs a public-key encryption algorithm on the seed value using the public key and the blind value, to generate an encryption seed value as the encryption information, and transmits the encryption seed value,

the receiving unit receives the encryption seed value as the encryption information,

the decryption unit includes:

a secret-key obtaining subunit operable to obtain a secret key that corresponds to the public key; and

a public-key decryption subunit operable to perform, on the received encryption seed value, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, using the obtained secret key, to generate the decryption seed value,

the shared-key generating unit performs the one-way function on the decryption seed value to generate a decryption functional value, and generates the decryption blind value and the decryption shared key from the decryption functional value,

the re-encryption unit includes:

a public-key obtaining subunit operable to obtain the public key; and

a re-encryption subunit operable to perform the public-key encryption algorithm on the decryption seed value using the public key and the decryption blind value, to generate a re-encryption seed value as the re-encryption information, and

the judging unit judges whether the encryption seed value is identical to the re-encryption seed value, and when judging affirmatively, determines that the decryption shared key should be outputted.

23. The shared-key recovery apparatus ofclaim 22, wherein

the public-key encryption algorithm and the public-key decryption algorithm conform to an NTRU cryptosystem,

the shared-key generation apparatus obtains a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, generates a seed-value polynomial from the seed value, generates a blind-value polynomial from the blind value, encrypts the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the encryption seed value, and transmits the encryption seed-value polynomial as the encryption seed value,

the receiving unit receives the encryption seed-value polynomial as the encryption seed value,

the secret-key obtaining subunit obtains a secret-key polynomial generated according to the key-generation algorithm of the NTRU cryptosystem, as the secret key,

the public-key decryption subunit decrypts the received encryption seed-value polynomial according to a decryption algorithm of the NTRU cryptosystem and using the obtained secret-key polynomial as a key, to generate a decryption seed-value polynomial, and generates the decryption seed value from the decryption seed-value polynomial,

the public-key obtaining subunit obtains the public-key polynomial as the public key,

the re-encryption subunit generates a seed-value polynomial from the decryption seed value, generates a blind-value polynomial from the decryption blind value, and encrypts the seed-value polynomial according to the encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the seed-value polynomial, to generate a re-encryption seed-value polynomial, and

the judging unit judges whether the encryption seed-value polynomial is identical to the re-encryption seed-value polynomial.

24. The shared-key recovery apparatus ofclaim 21, wherein

the shared-key generation apparatus obtains a public key, generates a blind value, performs a public-key encryption algorithm on the seed value using the public key and the blind value to generate a public-key cipher text, performs a second one-way function on at least one of the seed value, the blind value, and the shared key to generate a second functional value, generates the encryption information that includes the public-key cipher text and the second functional value, and transmits the encryption information,

the receiving unit receives the encryption information that includes the public-key cipher text and the second functional value,

the decryption unit includes:

a secret-key obtaining subunit operable to obtain a secret key that corresponds to the public key;

a public-key decryption subunit operable to perform, on the public-key cipher text included in the received encryption information, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, to generate a decryption seed value; and

a function subunit operable to perform the second one-way function on at least one of the decryption seed value, the decryption blind value, and the decryption shared key, to generate a decryption second functional value, and

the judging unit judges whether the second functional value included in the received encryption information is identical to the decryption second functional value instead of performing judging based on the encryption information and the re-encryption information and when judging affirmatively, determines that the decryption shared key should be outputted.

25. The shared-key recovery apparatus ofclaim 24, wherein

the shared-key generation apparatus performs a one-way function on the seed value to generate a functional value, and generates the blind value and the shared key from the functional value, and

the shared-key generating unit performs the first one-way function on the decryption seed value to generate a decryption functional value, and generates the decryption blind value and the decryption shared key from the decryption functional value.

26. The shared-key recovery apparatus ofclaim 24, wherein

the shared-key generation apparatus performs a first one-way function on the seed value to generate a first functional value, and generates the shared key from the first functional value, instead of generating the blind value and the shared key, and

the shared-key generating unit performs the first one-way function on the decryption seed value to generate a decryption functional value, and generates the decryption shared key from the decryption functional value, instead of generating the decryption blind value and the decryption shared key.

27. The shared-key recovery apparatus ofclaim 24, wherein the public-key encryption algorithm and the public-key decryption algorithm conform to an NTRU cryptosystem,

the shared-key generation apparatus obtains a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, generates a seed-value polynomial from the seed value, generates a blind-value polynomial from the blind value, encrypts the seed-value polynomial according to an encryption algorithm of the NTRU cryptosystem using the public-key polynomial as a key and using the blind-value polynomial to randomize the seed-value polynomial, to generate an encryption seed-value polynomial as the public-key cipher text, and generates the encryption information that includes the encryption seed-value polynomial as the public-key cipher text and the second functional value,

the secret-key obtaining subunit obtains a secret-key polynomial generated according to the key-generation algorithm of the NTRU cryptosystem, as the secret key, and

the public-key decryption subunit generates a public-key cipher-text polynomial from the public-key cipher text, decrypts the public-key cipher-text polynomial according to a decryption algorithm of the NTRU cryptosystem using the secret-key polynomial as a key to generate a decryption seed-value polynomial, and generates the decryption seed value from the decryption seed-value polynomial.

28. The shared-key recovery apparatus ofclaim 21, wherein

the shared-key generation apparatus performs a one-way function on the seed value to generate a functional value, generates a verification value, the blind value, and the shared key from the functional value, obtains a public key, performs a public-key encryption algorithm on the verification value using the public key and the blind value to generate a first cipher text, performs, based on the verification value, a computation algorithm different from the public-key encryption algorithm on the seed value, to generate a second cipher text, generates the encryption information that includes the first cipher text and the second cipher text, and transmits the encryption information,

the receiving unit receives the encryption information that includes the first cipher text and the second cipher text,

the decryption unit includes:

a public-key decryption subunit operable to perform, on the first cipher text included in the received encryption information, a public-key decryption algorithm that corresponds to the public-key encryption algorithm, to generate a decryption verification value; and

a computation decryption subunit operable to perform, on the second cipher text included in the received encryption information, a computation algorithm for performing an inverse computation of the different computation algorithm, to generate a decryption seed value,

the shared-key generating unit performs the one-way function on the decryption seed value to generate a decryption functional value, and generates a decryption verification value, the decryption blind value, and the decryption shared key, from the decryption functional value,

the re-encryption unit includes:

a public-key obtaining subunit operable to obtain the public key; and

a re-encryption subunit operable to perform, on the decryption verification value, the public-key encryption algorithm using the public key and the decryption blind value, to generate the re-encryption information, and

the judging unit judges whether the first cipher text included in the encryption information is identical to the re-encryption information, and when judging affirmatively, determines that the decryption shared key should be outputted.

29. The shared-key recovery apparatus ofclaim 28, wherein

the shared-key generation apparatus obtains a public-key polynomial generated according to a key-generation algorithm of the NTRU cryptosystem, as the public key, generates a verification-value polynomial from the verification value, generates a blind-value polynomial from the blind value, encrypts the verification-value polynomial according to an encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the verification-value polynomial, to generate an encryption verification-value polynomial as the first cipher text, generates the encryption information that includes the encryption verification-value polynomial as the first cipher text and the second cipher text, and transmits the encryption information,

the receiving unit receives the encryption information that includes the encryption verification-value polynomial and the second cipher text,

the public-key decryption subunit generates a first cipher-text polynomial from the first cipher text, decrypts the first cipher-text polynomial according to a decryption algorithm of the NTRU cryptosystem using the secret-key polynomial as a key, to generate a decryption verification polynomial, and generates the decryption verification value from the decryption verification-value polynomial,

the public-key obtaining subunit obtains the public-key polynomial,

the re-encryption subunit generates a decryption verification-value polynomial from the decryption verification value, generates a blind-value polynomial from the decryption blind value, and encrypts the decryption verification-value polynomial according to the encryption algorithm of the NTRU cryptosystem, using the public-key polynomial as a key, and using the blind-value polynomial to randomize the decryption verification-value polynomial, to generate a re-encryption verification-value polynomial as the re-encryption information, and

the judging unit judges whether the encryption verification-value polynomial as the first cipher text is identical to the re-encryption verification-value polynomial as the re-encryption information.

30. The shared-key recovery apparatus ofclaim 29, wherein

the different computation algorithm is a symmetric key encryption algorithm, and the computation algorithm for performing the inverse computation is a corresponding symmetric key decryption algorithm, and

the computation decryption subunit performs the symmetric key decryption algorithm on the second cipher text, using the decryption verification value as a key, to generate the decryption seed value.

31. The shared-key recovery apparatus ofclaim 29, wherein

the different computation algorithm and the computation algorithm for performing the inverse computation are bitwise exclusive-or, and

the computation decryption subunit performs the bitwise exclusive-or on the decryption verification value and the second cipher text, to generate the decryption seed value.

32. The shared-key recovery apparatus ofclaim 29, wherein

the different computation algorithm is addition and the computation algorithm for performing the inverse computation is subtraction, and

the computation decryption subunit performs the subtraction on the decryption verification value and the second cipher text, to generate the decryption seed value.

33. The shared-key recovery apparatus ofclaim 29, wherein

the different calculation algorithm is multiplication and the computation algorithm for performing the inverse computation is division, and

the computation decryption subunit performs the division on the decryption verification value and the second cipher text, to generate the decryption seed value.

34. The shared-key recovery apparatus ofclaim 21, wherein

the shared-key generating unit performs a one-way function on the decryption seed value to generate a functional value, and generates the decryption blind value and the decryption shared key from the functional value.

35. The shared-key recovery apparatus ofclaim 34, wherein

the one-way function is a hash function, and the shared-key generating unit performs the hash function on the decryption seed value.

36. The shared-key recovery apparatus ofclaim 34, wherein

the shared-key generating unit generates the decryption blind value by setting a part of the functional value as the decryption blind value, and generates the decryption shared key by setting another part of the functional value as the decryption shared key.

37. The shared-key recovery apparatus ofclaim 21, wherein

the shared-key generation apparatus further obtains a content, encrypts the obtained content using the shared key to generate an encrypted content, and transmits the encrypted content, and

the shared-key recovery apparatus further includes:

a content receiving unit operable to receive the encrypted content;

a decryption unit operable to decrypt the received encrypted content using the outputted decryption shared key, to generate a decrypted content; and

a playback unit operable to playback the decrypted content.

38. A shared-key generating method used in a shared-key generation apparatus that notifies a destination apparatus about a shared key in secrecy, the shared-key generating method comprising:

a seed-value generating step of generating a seed value;

a shared-key generating step of generating a blind value and a shared key, from the seed value;

an encryption step of encrypting the seed value based on the blind value, to generate encryption information; and

a transmitting step of transmitting the encryption information.

39. A shared-key generating program used in a shared-key generation apparatus that notifies a destination apparatus about a shared key in secrecy, the shared-key generating program comprising:

a seed-value generating step of generating a seed value;

a transmitting step of transmitting the encryption information.

40. The shared-key generating program ofclaim 39, wherein

the shared-key generating program is recorded in a computer-readable recording medium.

41. A shared-key recovery method used in a shared-key recovery apparatus that receives a shared key from a shared-key generation apparatus in secrecy, the shared-key generation apparatus generating a seed value, generating a blind value and a shared key from the seed value, encrypting the seed value based on the blind value to generate encryption information, and transmitting the encryption information, the shared-key recovery method comprising:

a receiving step of receiving the encryption information;

a decryption step of decrypting the encryption information, to generate a decryption seed value;

a shared-key generating step of generating a decryption blind value and a decryption shared key, using the decryption seed value and according to a same shared-key generating method used in the shared-key generation apparatus;

a re-encryption step of encrypting the decryption seed value based on the decryption blind value, to generate re-encryption information;

a judging step of judging, based on the encryption information and there-encryption information, whether the decryption shared key should be outputted; and

an outputting step, when the judging unit has judged affirmatively, of outputting the decryption shared key.

42. A shared-key recovery program used in a shared-key recovery apparatus that receives a shared key from a shared-key generation apparatus in secrecy, the shared-key generation apparatus generating a seed value, generating a blind value and a shared key from the seed value, encrypting the seed value based on the blind value to generate encryption information, and transmitting the encryption information, the shared-key recovery program comprising:

a receiving step of receiving the encryption information;

a judging step of judging, based on the encryption information and the re-encryption information, whether the decryption shared key should be outputted; and

43. The shared-key recovery program ofclaim 42, wherein

The shared-key recovery program is recorded in a computer-readable recording medium.