JP4485175B2 - Key sharing system, shared key generating device, and shared key restoring device - Google Patents

Description

  The present invention relates to a cryptographic technique as an information security technique, and more particularly to a technique for distributing a key without being known to a third party.

Conventionally, a public key cryptosystem is used to secretly transmit information from a transmitting device to a receiving device.
In the public key cryptosystem, the transmission device encrypts and transmits the communication content using the public key of the reception device, the reception device receives the encrypted communication content, and receives the received communication content in its own private key. Is used to obtain the original communication content. (For example, refer nonpatent literature 1).

  In 1996, NTRU encryption was proposed as public key encryption capable of high-speed processing (see, for example, Non-Patent Document 2). In NTRU cryptography, encryption and decryption are performed using polynomial operations that can be performed at high speed, so when compared with RSA cryptography that performs exponentiation and elliptic curve cryptography that performs scalar multiplication of points on an elliptic curve, It is possible to perform processing by software faster than conventional public key cryptography.

  However, in this NTRU cipher, when a plaintext is encrypted using a public key to generate a ciphertext, and a decrypted text is generated by decrypting a ciphertext using a regular secret key, the decrypted text is the original plaintext. And a different case occurs. This is called a decoding error. As a method for avoiding a decryption error, a method is disclosed in which additional information is added to plaintext, encrypted, and transmitted together with a plaintext hash function value (see, for example, Patent Document 1).

  On the other hand, in recent years, as a new concept of public key cryptography, a method called a key encapsulation mechanism has been proposed (see, for example, Non-Patent Document 3). This key encapsulation mechanism is an algorithm for distributing a shared key between a transmitting device and a receiving device using public key cryptography, and the transmitting device inputs the recipient's public key pk to the encryption algorithm E. A ciphertext C and a shared key K are generated, and the ciphertext C is transmitted to the receiving device. Next, the receiving apparatus inputs the secret key sk and the ciphertext C to the decryption algorithm D and obtains the same shared key K as that of the transmitting apparatus.

  After the shared key K is shared between the transmission device and the reception device using the key encapsulation mechanism in this way, the transmission device uses the shared key K to transmit the plaintext to be transmitted to the reception device. The ciphertext is generated by encryption, and the generated ciphertext is transmitted to the receiving device. The receiving device receives the ciphertext and decrypts the received ciphertext using the shared key K by the common key cryptosystem to generate a decrypted text.

In the conventional key encapsulation mechanism, information is unilaterally transmitted from the sender to the receiver, but the sender is not able to create a shared key intentionally. There is no feature.
As such a key encapsulation mechanism, an algorithm called PSEC-KEM has been disclosed (see, for example, Non-Patent Document 3 and Non-Patent Document 4). Below, the PSEC-KEM algorithm described in the nonpatent literature 4 is demonstrated.

(1) System parameters of PSEC-KEM PSEC-KEM has the following system parameters.
・ Elliptic curve: E
-A point of order n on an elliptic curve: P
-Hash function: G, H
Note that details of the elliptic curve, the order, and the hash function are described in Non-Patent Document 1, and thus description thereof is omitted here.

(2) Public key and private key of PSEC-KEM-Select an element x of Zn at random and generate W = x * P.
Here, Zn is {0, 1,. . . , N−1}, and x * P represents a point on the elliptic curve obtained by adding x points P on the elliptic curve. A method for adding points on an elliptic curve is described in Non-Patent Document 1.

The public key pk is (E, P, W, n), and the secret key sk is x.
(3) Encryption of PSEC-KEM At the time of encryption, the public key pk is input to the encryption algorithm KemE described below, and the shared key K and the ciphertext C are output. The encryption algorithm KemE will be described below.
Generate s having the same length as the output bit length of the hash function H at random.

Generate G (s) and divide G (s) to generate a and K. a is a bit string composed of a plurality of upper bits of G (s), and K is a bit string composed of the remaining bits. Here, G (s) = a || K. “||” is an operator representing bit combination. That is, when a and K are combined, G (s) is obtained.
Generate R = a * P, Q = a * W.

Generate v = s xor H (R || Q). Here, xor represents an exclusive OR operation.
-Outputs shared key K and ciphertext C = (R, v).
(4) Decryption of PSEC-KEM At the time of decryption, the ciphertext C = (R, v), the public key pk, and the secret key sk are input to the decryption algorithm ChemD described below, and the shared key K is output. The decoding algorithm KemD will be described below.

Generate Q = x * R.
Generate s = v xor H (R || Q).
Generate G (s) and divide G (s) into G (s) = a || K.
Check whether R = a * P is true. If established, the shared key K is output.
When this PSEC-KEM algorithm is applied to an encryption system that performs encrypted communication between a transmission device and a reception device, the transmission device first acquires the public key pk of the communication destination reception device, and acquires the acquired public key pk. Is input to the encryption algorithm KemE described above, the shared key K and the ciphertext C are derived, and the ciphertext C is transmitted to the receiving device.

Next, the receiving device receives the ciphertext C from the transmitting device, inputs the received ciphertext C and its own public key pk / secret key sk to the decryption algorithm KemD, and is derived by the transmitting device. A shared key K equal to is derived.
This will be described in more detail below.
Now, in the PSEC-KEM algorithm, the input of the hash function H is (a * P || a * W), and H (a * P || a * W) is added to the element s randomly generated by the encryption algorithm KemE. ) To generate v. In the decryption algorithm KemD, Q = x * R = x * (a * P) = a * (x * P) = a * W is obtained from R = a * P using the secret key sk (= x). Since the value of H (a * P || a * W) is applied to v, the random element s generated in the encryption algorithm KemE can be obtained.

Therefore, the encryption algorithm KemE and the decryption algorithm KemD can input the same value of s to the hash function G, and can derive the same shared key K. As a result, the receiving device having the secret key sk can derive the same shared key K as that derived by the transmitting device.
On the other hand, even if the other receiving device that does not know the secret key sk does not know the secret key sk (= x) even if it obtains the public key pk and receives the ciphertext C, R = a * P to Q = A * W (= (ax) * P) cannot be calculated, and the same shared key K as that derived by the transmitting apparatus cannot be derived.

  This is because other receiving devices that do not know the secret key sk can use only the public key pk, and therefore, W = x * P of the public key pk is used instead of the secret key sk (= x) for the calculation of Q. However, generally, obtaining Q = a * W (= (ax) * P) from a * P and W = x * P is called Diffie-Hellman problem on an elliptic curve, and a This is because calculation is difficult unless the values of x and x are known (for example, see Non-Patent Document 5).

That is, the PSEC-KEM algorithm uses the Diffie-Hellman problem, which is difficult to calculate a * W from a * P without using a secret key, and finally derives the shared key K, thereby If the key is not known, the shared key K cannot be derived.
As described above, the transmission device and the reception device can share the shared key K in a secret manner, and thereafter, the communication content data communicated from the transmission device to the reception device is transferred to the shared key K using secret key encryption. Encrypt using common key encryption.
JP 2002-252611 A Okamoto Tatsuaki, Yamamoto Hiroshi, “Contemporary Cryptography”, Series / Mathematics of Information Science, Industrial Books, 1997. 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. Victor Shoup, “A proposal for an ISO standard for public key encryption (version 2.1)”, [online], December 20, 2001, [searched September 29, 2002], Internet <URL: http: // shoup .net / papers / iso-2_1.pdf> Tatsuaki Okamoto, “Generic conversions for constructing IND-CCA2 public-key encryption in the random oracle model”, [online], The 5th Workshop on Elliptic Curve Cryptography (ECC 2001), October 30, 2001, [September 2002 29 days search], Internet <URL: http://www.cacr.math.uwaterloo.ca/conferences/2001/ecc/okamoto.ppt> Neal Koblitz, “Algebraic Aspects of Cryptography”, Algorithms and Computation in Mathematics Vol.3, pp.132-133, Springer-Verlag, 1998.

As described above, in the conventional PSEC-KEM algorithm, Diffie is difficult to calculate a * W from a * P without using a secret key by using a * P, a * W as the input of the hash function H. -By finally deriving the shared key K using the Hellman problem, the shared key K cannot be derived without knowing the secret key.
However, since there are no NTRU ciphers or other public key ciphers that do not use the Diffie-Hellman problem, the PSEC-KEM algorithm cannot be applied because none of them corresponds to the Diffie-Hellman problem a * P or a * W. That is, the NTRU cipher capable of high-speed processing cannot distribute the shared key by applying the PSEC-KEM algorithm which is a key encapsulation mechanism, and therefore the transmitting device and the receiving device use the shared key. There is a problem that encrypted communication from the used transmitting apparatus to the receiving apparatus is not possible.

  Therefore, in order to solve the above problem, the present invention is known to a third party from the shared key generation device to the shared key recovery device even when an encryption method that does not use the Diffie-Hellman problem is used. A key sharing system, a shared key generation device, a shared key recovery device, and a shared key that can prevent a different shared key from being derived between the shared key generation device and the shared key recovery device An object is to provide a key generation method, a shared key restoration method, a shared key generation program, and a shared key restoration program.

  In order to achieve the above object, the present invention provides a key sharing system including a shared key generating device and a shared key restoring device that generate a shared key without being known to a third party, and the shared key generating device Includes: a seed value generating unit configured to generate a seed value; a first shared key generating unit configured to generate a verification value and a shared key from the generated seed value; A first encryption unit for generating encrypted information, a second encryption unit for generating second encrypted information by encrypting the generated seed value based on the generated verification value, and Transmission means for transmitting the first encrypted information and the second encrypted information, and the shared key restoration device receives the first encrypted information and the second encrypted information; Decrypting the received first encrypted information A first decryption unit for generating one decryption verification value; and a second decryption unit for decrypting the received second encrypted information based on the generated first decryption verification value to generate a decryption seed value. And second shared key generation means for generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the first shared key generation means, and the generated first decryption Based on a verification value and the second decryption verification value, a determination means for determining whether or not to output the generated decryption shared key, and output the generated decryption shared key when it is determined to output Output means.

  According to the above configuration, the shared key generation device generates a verification value and a shared key from a seed value, encrypts the verification value to generate first encrypted information, and based on the verification value, the seed Encrypting the value to generate the second encrypted information, the shared key restoration device decrypts the first encrypted information to generate a first decryption verification value, and based on the first decryption verification value, Decrypting the second encryption information to generate a decryption seed value, and generating a second decryption verification value and a decryption shared key from the decryption seed value in the same manner as the shared key generation device, Since it is determined whether to output the generated decryption shared key based on the first decryption verification value and the second decryption verification value, it is known to the third party from the shared key generation device to the shared key restoration device Shared key can be delivered without any There is an effect that it is possible to prevent the different shared keys between the shared-key recovery apparatus is derived and.

  Here, the shared key generation apparatus further includes an acquisition unit for acquiring content, and an encryption unit for generating the encrypted content by encrypting the acquired content using the generated shared key. The transmitting means further transmits the generated encrypted content, the receiving means further receives the encrypted content, and the shared key recovery device further outputs the decrypted shared content. Decryption means for decrypting the received encrypted content using a key to generate decrypted content, and output means for outputting the generated decrypted content.

  According to this configuration, the shared key generation device generates encrypted content by encrypting the acquired content using the generated shared key, and the shared key restoration device outputs the decrypted shared Since the received encrypted content is decrypted using a key to generate decrypted content, the content can be transmitted from the shared key generating device to the shared key restoring device without being known by a third party. There is an effect.

  Further, the present invention is a shared key generation device that transmits a shared key to a partner device without being known to a third party, a seed value generation unit that generates a seed value, and a verification value from the generated seed value And a shared key generating means for generating a shared key, a first encryption means for generating the first encrypted information by encrypting the generated verification value, and a generated based on the generated verification value. A second encryption unit that encrypts the seed value to generate second encryption information; and a transmission unit that transmits the generated first encryption information and the second encryption information.

  According to this configuration, the shared key generating device generates the first encrypted information by encrypting the verification value, and generates the second encrypted information by encrypting the seed value based on the verification value. There is an effect that the security can be further improved by the heavy encryption. An unauthorized third party cannot obtain a shared key unless he / she knows two types of encryption by the first and second encryption means.

Here, the seed value generating means generates a seed value by generating a random number and using the generated random number as the seed value.
According to this configuration, the shared key generation device generates a random number, and uses the generated random number as the seed value. Therefore, the shared key generation device generates a seed value, generates a verification value and a shared key, and generates the first encryption information and the second encryption information. After generating the encryption information and transmitting the first encryption information and the second encryption information, when generating the seed value, the subsequent seed is set to be different from the seed value generated first. A value can be generated. Therefore, the first encryption information and the second encryption information transmitted by the shared key generation device are different each time. For this reason, even if an unauthorized third party intercepts and records the first encryption information and the second encryption information transmitted from the shared key generation device to the partner device, It is difficult to infer the original seed value from the first encrypted information and the second encrypted information.

Here, the shared key generation unit generates a function value by applying a one-way function to the seed value, and generates the verification value and the shared key from the generated function value.
According to this configuration, since the verification value is generated by applying a one-way function to the seed value, even if a third party can know the verification value, the seed value is obtained from the verification value. Have difficulty. For this reason, it is practically impossible to obtain a seed value from the verification value and further obtain a shared key.

Here, the shared key generation unit performs the hash function as the one-way function on the seed value to generate the function value.
According to this configuration, since the one-way function is a hash function, its calculation algorithm is well known and easy to apply.
Here, the shared key generation unit generates the verification value and the shared key by using a part of the generated function value as the verification value and the other part as the shared key.

According to this configuration, part of the function value is used as the verification value, and the other part is used as the shared key. Therefore, it is easy to generate the verification value and the shared key.
Here, the shared key generation unit generates a function value by applying a one-way function to the seed value, and generates the verification value, the shared key, and a blind value from the generated function value.
According to this configuration, since the verification value is generated by applying a one-way function to the seed value, even if a third party can know the verification value, the seed value is obtained from the verification value. Have difficulty. For this reason, it is practically impossible to obtain a seed value from the verification value and further obtain a shared key.

Here, the first encryption means performs a public key encryption algorithm on the verification value using the public key acquisition unit that acquires a public key, and the acquired public key and the generated blind value. And a public key encryption unit for generating the first encryption information.
Further, the first encryption means performs a public key encryption algorithm on the verification value by using a public key acquisition unit that acquires a public key and the acquired public key, and converts the first encryption information into the first encryption information. Including a public key encryption unit to be generated.

According to this configuration, since the first encryption unit uses a public key cryptosystem, key management is easier than in the case where a shared key cryptosystem is used.
Here, the public key encryption algorithm is based on the NTRU cryptosystem, and the public key acquisition unit acquires a public key polynomial generated by a key generation algorithm of the NTRU cryptosystem as the public key, The public key encryption unit generates a verification value polynomial from the verification value, generates a blind value polynomial from the blind value, and uses the public key polynomial as a key by an encryption algorithm of an NTRU cryptosystem, Using the blind value polynomial to disrupt the polynomial, the verification value polynomial is encrypted to generate the first encrypted information as a polynomial.

  The public key encryption algorithm is based on the NTRU cryptosystem, and the public key acquisition unit acquires a public key polynomial generated by an NTRU cryptosystem key generation algorithm as the public key, and The key encryption unit generates a verification value polynomial from the verification value, generates a blind value, generates a blind value polynomial from the generated blind value, and uses the NTRU encryption algorithm to convert the public key polynomial Using the blind value polynomial as a key and using the blind value polynomial to disturb the verification value polynomial, the verification value polynomial is encrypted to generate the first encrypted information as a polynomial.

According to this configuration, NTRU encryption can be employed.
Here, the second encryption means generates a function value by applying a one-way function to the verification value, and applies an encryption algorithm to the seed value using the generated function value. Generate encryption information.
According to this configuration, since the second encryption information is generated by applying an encryption algorithm to the seed value using a function value obtained by applying a one-way function to the verification value, an illegal third If the person does not know at least the one-way function and the encryption algorithm, the seed value cannot be obtained from the second encryption information.

Here, the second encryption unit generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value.
According to this configuration, since the encryption algorithm is exclusive OR, the calculation is easy. Inverse calculation is also possible.
Here, the second encryption unit generates the second encryption information by applying a common key encryption algorithm as the encryption algorithm to the generated function value and the seed value.

According to this configuration, since the encryption algorithm is a common key encryption algorithm, it is well-known and easy to apply. Inverse calculation is also possible.
Here, the second encryption unit generates the second encryption information by performing addition as the encryption algorithm to the generated function value and the seed value.
According to this configuration, since the encryption algorithm is addition, calculation is easy. Inverse calculation is also possible.

Here, the second encryption means generates the second encryption information by multiplying the generated function value and the seed value as the encryption algorithm.
According to this configuration, since the encryption algorithm is multiplication, calculation is easy. Inverse calculation is also possible.
Here, the second encryption unit performs the hash function as the one-way function on the verification value to generate the function value.

According to this configuration, since the one-way function is a hash function, its calculation algorithm is well known and easy to apply.
Here, the second encryption means generates an encryption information by applying an encryption algorithm to the seed value using the verification value.
According to this configuration, since the verification algorithm is used to apply an encryption algorithm to the seed value, the calculation is simple and easy to apply.

Here, the second encryption unit encrypts the seed value using the verification value and the first encryption information.
According to this configuration, since the seed value is encrypted using the verification value and the first encrypted information, an unauthorized third party does not know the verification value and the first encrypted information, The seed value cannot be obtained, and safety is increased.

Here, the second encryption means generates a function value by applying a one-way function to the verification value and the first encryption information, and encrypts the seed value using the generated function value. An algorithm is applied to generate the second encrypted information.
According to this configuration, since the one-way function and the encryption algorithm are used, even if an unauthorized third party knows the first encryption information and the second encryption information, at least the one-way function and the encryption function are used. If the algorithm is not known, the seed value cannot be obtained, and safety is increased.

Here, the second encryption unit generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value.
According to this configuration, since the encryption algorithm is exclusive OR, the calculation is easy. Inverse calculation is also possible.
Here, the shared key generation apparatus further includes an acquisition unit for acquiring content, and an encryption unit for generating the encrypted content by encrypting the acquired content using the generated shared key. The transmission means further transmits the generated encrypted content.

According to this configuration, the shared key generation device can transmit the content to the other device without being known to a third party.
Here, it is a shared key restoration device that receives a shared key from a shared key generation device without being known to a third party, the shared key generation device generates a seed value, and a verification value from the generated seed value And generating a shared key, encrypting the generated verification value, generating first encrypted information, encrypting the generated seed value based on the generated verification value, and Generate encrypted information, transmit the generated first encrypted information and the second encrypted information, and the shared key restoration device receives the first encrypted information and the second encrypted information Receiving means; first decryption means for decrypting the received first encrypted information to generate a first decryption verification value; and receiving the second decryption based on the generated first decryption verification value. A second decryptor that decrypts the encrypted information and generates a decryption seed value And a shared key generation means for generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the shared key generation device, the generated first decryption verification value and the A determination unit that determines whether or not to output the generated decryption shared key based on a second decryption verification value; and an output unit that outputs the generated decryption shared key when it is determined to output. Is provided.

According to this configuration, a shared key can be received from a shared key generation device without being known to a third party, and at this time, a different shared key is derived between the shared key generation device and the shared key restoration device. There is an effect that can be prevented.
Here, the shared key generation device acquires a public key, generates a first encryption information by applying a public key encryption algorithm to the verification value using the acquired public key, and 1 decryption means corresponds to the public key encryption algorithm in the received first encryption information using a secret key acquisition unit that acquires a secret key corresponding to the public key and the acquired secret key And a public key decryption unit that applies the public key decryption algorithm to generate the first decryption verification value.

According to this configuration, since the first decryption unit uses a public key cryptosystem, key management is easier than in the case where a shared key cryptosystem is used.
Here, the public key encryption algorithm and the public key decryption algorithm are based on the NTRU encryption method, and the shared key generation device uses the public key generated by the key generation algorithm of the NTRU encryption method as the public key. A polynomial is obtained, a verification value polynomial is generated from the verification value, a blind value is generated, a blind value polynomial is generated from the generated blind value, and the public key polynomial is keyed by an encryption algorithm of the NTRU cryptosystem. And using the blind value polynomial to disrupt the verification value polynomial, encrypting the verification value polynomial to generate the first encrypted information as a polynomial, and the receiving means as a polynomial The first encryption information is received, and the secret key acquisition unit uses the NTRU encryption key generation algorithm as the secret key. The public key decryption unit obtains a secret key polynomial generated by a gothism, and the public key decryption unit uses the secret key polynomial as a key by the decryption algorithm corresponding to the encryption algorithm of the NTRU cryptosystem, and the first as a polynomial The encrypted information is decrypted to generate a decryption verification value polynomial, and the first decryption verification value is generated from the generated decryption verification value polynomial.

According to this configuration, NTRU encryption can be employed.
Here, the shared key generation device generates a function value by applying a one-way function to the verification value, and applies an encryption algorithm to the seed value by using the generated function value. The second decoding means generates a decoding function value by applying the one-way function to the generated first decoding verification value, and receives the generated decoding function value using the generated decoding function value. The decrypted seed value is generated by applying a decryption algorithm corresponding to the encryption algorithm to the second encrypted information.

According to this configuration, since the second decryption means employs a two-stage calculation method of a one-way function and a decryption algorithm, an unauthorized third party can obtain the first encrypted information and the second encrypted information. Even if it is known, if at least the one-way function and the decoding algorithm are not known, the seed value cannot be obtained, and safety is increased.
Here, the shared key generation device generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value, and generates the second decryption information. The means generates the decryption seed value by performing an exclusive OR as the decryption algorithm on the generated decryption function value and the second encryption information.

According to this configuration, since the decoding algorithm is exclusive OR, the calculation is easy. Further, it is an inverse operation of the encryption algorithm.
Here, the shared key generation apparatus generates the second encryption information by applying a common key encryption algorithm as the encryption algorithm to the generated function value and the seed value, and generates the second encryption information. The decrypting means generates the decryption seed value by applying a common key decryption algorithm corresponding to the common key encryption algorithm as the decryption algorithm to the generated decryption function value and the second encryption information. .

According to this configuration, since the decryption algorithm is a shared key decryption algorithm, it is well known and easy to apply. Further, it is an inverse operation of the encryption algorithm.
Here, the shared key generation device generates the second encryption information by adding the generated function value and the seed value as the encryption algorithm, and the second decryption unit includes: The decryption seed value is generated by subtracting the generated decryption function value and the second encryption information as the decryption algorithm.

According to this configuration, since the decoding algorithm is subtraction, the calculation is easy. Further, it is an inverse operation of the encryption algorithm.
Here, the shared key generation device generates the second encryption information by multiplying the generated function value and the seed value as the encryption algorithm, and the second decryption means includes: The decryption seed value is generated by subjecting the generated decryption function value and the second encrypted information to division as the decryption algorithm.

According to this configuration, since the decoding algorithm is division, the calculation is easy. Further, it is an inverse operation of the encryption algorithm.
Here, the shared key generation device generates a function value by applying a hash function as the one-way function to the verification value, and the second decryption means adds the generated decryption value to the first decryption verification value. The hash function is applied as the one-way function to generate the decryption function value.

According to this configuration, since the one-way function is a hash function, its calculation algorithm is well known and easy to apply.
Here, the shared key generation apparatus generates second encrypted information by applying an encryption algorithm to the seed value using the verification value, and the second decryption means generates the generated first decryption Using the verification value, the decryption algorithm corresponding to the encryption algorithm is applied to the second encryption information to generate the decryption seed value.

According to this configuration, since the second encrypted information is decrypted using the first decryption verification value, the calculation is easy.
Here, the shared key generation device encrypts the seed value using the verification value and the first encryption information, and the second decryption means receives the generated first decryption verification value and the received first decryption verification value. The second encrypted information is decrypted using the first encrypted information to generate the decryption seed value.

According to this configuration, since the second encrypted information is decrypted using the first decryption verification value and the first encryption information, an unauthorized third party can use the first decryption verification value and the first encryption information. If it is not known, the seed value cannot be obtained, and safety is improved.
Here, the shared key generation device generates a function value by applying a one-way function to the verification value and the first encryption information, and uses the generated function value to generate an encryption algorithm for the seed value. To generate the second encrypted information, and the second decryption means generates the decryption function value by applying the one-way function to the first decryption verification value and the first encrypted information. Using the decryption function value, the decryption algorithm corresponding to the encryption algorithm is applied to the second encryption information to generate the decryption seed value.

According to this configuration, since the second decryption means employs a two-stage calculation method of a one-way function and a decryption algorithm, an unauthorized third party can obtain the first encrypted information and the second encrypted information. Even if it is known, if at least the one-way function and the decoding algorithm are not known, the seed value cannot be obtained, and safety is increased.
Here, the shared key generation device generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value, and generates the second decryption information. The means generates the decryption seed value by performing an exclusive OR as the decryption algorithm on the decryption function value and the second encryption information.

According to this configuration, since the decoding algorithm is exclusive OR, the calculation is easy. Further, it is an inverse operation of the encryption algorithm.
Here, the shared key generation device generates a function value by applying a one-way function to the seed value, generates the verification value and the shared key from the generated function value, and the shared key generation means A decryption function value is generated by applying the one-way function to the generated decryption seed value, and the second decryption verification value and the decryption shared key are generated from the generated decryption function value.

According to this configuration, since the second decoding verification value is generated by performing a one-way function on the decoding seed value, the second decoding verification value can be obtained even if a third party can know the second decoding verification value. It is difficult to obtain the seed value from the verification value. For this reason, it is practically impossible to obtain the seed value from the second decryption verification value and further obtain the shared key.
Here, the shared key generation device generates the function value by applying a hash function as the one-way function to the seed value, and the shared key generation unit generates the decrypted seed value The decryption function value is generated by applying the hash function as the one-way function.

According to this configuration, since the one-way function is a hash function, its calculation algorithm is well known and easy to apply.
Here, the shared key generation device generates the verification value and the shared key by using a part of the generated function value as the verification value and the other part as the shared key, The shared key generating means sets the second decryption verification value and the decryption shared key by using a part of the generated decryption function value as the second decryption verification value and the other part as the decryption shared key. Is generated.

According to this configuration, since a part of the decryption function value is the second decryption verification value and the other part is the decryption shared key, it is easy to generate the second decryption verification value and the decryption shared key. is there.
Here, the shared key generation device generates a function value by applying a one-way function to the seed value, generates the verification value, the shared key, and a blind value from the generated function value, and generates a public key. Using the acquired public key and the generated blind value, the verification value is subjected to a public key encryption algorithm to generate the first encrypted information, and the shared key generating means generates The decryption seed value is subjected to the one-way function to generate a decryption function value, and the second decryption verification value, the decryption shared key, and the decryption blind value are generated from the generated decryption function value.

According to this configuration, since the second decoding verification value is generated by performing a one-way function on the decoding seed value, the second decoding verification value can be obtained even if a third party can know the second decoding verification value. It is difficult to obtain the seed value from the verification value. For this reason, it is practically impossible to obtain the seed value from the second decryption verification value and further obtain the shared key.
Here, the shared key generation device acquires a public key, performs a public key encryption algorithm on the verification value using the acquired public key and the generated blind value, and performs the first encryption Generating information, the determination means, instead of the determination based on the first decryption verification value and the second decryption verification value, a public key acquisition unit that acquires the public key, and the acquired public key and A re-encryption unit that generates re-encrypted information by applying the public key encryption algorithm to the generated first decryption verification value or the second decryption verification value using the generated decryption blind value; A determination unit configured to determine whether or not to output the generated decryption shared key based on the received first encryption information and the generated re-encryption information.

According to this configuration, since it is determined whether to output the generated decryption shared key based on the received first encryption information and the generated re-encryption information, from the shared key generation device The shared key can be received without being known to a third party, and at this time, it is possible to prevent different shared keys from being derived between the shared key generating device and the shared key restoring device.
Here, the determination unit compares the first encrypted information and the re-encrypted information, and outputs the decryption shared key when the first encrypted information and the re-encrypted information match. Judge that. The determination means compares the first decryption verification value and the second decryption verification value, and determines that the decryption shared key is output if they match.

According to this configuration, since the decryption shared key is output when the first encrypted information and the re-encrypted information match, it is possible to reliably determine whether to output the decrypted shared key.
Here, the public key encryption algorithm is based on the NTRU cryptosystem, and the shared key generation apparatus acquires, as the public key, a public key polynomial generated by an NTRU cryptosystem key generation algorithm, A verification value polynomial is generated from the verification value, a blind value polynomial is generated from the blind value, and the public key polynomial is used as a key by an encryption algorithm of the NTRU cryptosystem, and the blind value is disturbed by the verification value polynomial. The verification value polynomial is encrypted using a value polynomial to generate the first encryption information as a polynomial, the public key acquisition unit acquires the public key polynomial, and the re-encryption unit includes: Generating a decryption verification value polynomial from the second decryption verification value; generating a decryption blind value polynomial from the decryption blind value; and The decryption verification value polynomial is encrypted using the public key polynomial as a key, and the decryption blind value polynomial is used to disturb the decryption verification value polynomial. Generate information.

According to this configuration, NTRU encryption can be employed.
Here, the shared key generation device further acquires content, encrypts the acquired content using the generated shared key, generates encrypted content, and generates the encrypted content And the receiving means further receives the encrypted content, and the shared key restoration device further decrypts the received encrypted content using the output shared decryption key. A decrypting unit for generating the decrypted content and an output unit for outputting the generated decrypted content.

  According to this configuration, the shared key generation device generates encrypted content by encrypting the acquired content using the generated shared key, and the shared key restoration device outputs the decrypted shared Since the received encrypted content is decrypted using a key to generate decrypted content, the content can be transmitted from the shared key generating device to the shared key restoring device without being known by a third party. There is an effect.

1. Embodiment 1
A content distribution system 10 as one embodiment according to the present invention will be described. The content distribution system 10 is an encryption communication system that performs encrypted communication by performing key distribution using a key encapsulation mechanism using NTRU encryption.
1.1 NTRU Encryption Method The NTRU encryption method used in the content distribution system 10 will be briefly described. The NTRU cryptosystem is a public key cryptosystem that performs encryption and decryption using polynomial operations.

Note that the public key and secret key generation method in the NTRU cryptosystem and the NTRU cryptosystem are described in detail in Non-Patent Document 2.
(1) System parameters of NTRU encryption method In the NTRU encryption method, there are integer system parameters, N, p, and q, and an encryption device and a decryption device described later have these system parameters.

In the above document, as examples of system parameters, (N, p, q) = (107, 3, 64), (N, p, q) = (167, 3, 128), (N, p, q) Three examples are given: = (503,3,256).
Hereinafter, in the present embodiment, description will be made assuming that the system parameter N = 167.
(2) Polynomial operation of NTRU cryptosystem The NTRU cryptosystem is a public key cryptosystem that performs encryption and decryption by polynomial operations as described above.

A polynomial handled in the NTRU cryptosystem is a polynomial of N-1 dimensions or less with respect to the system parameter N. For example, when N = 5, it is a polynomial such as X ^ 4 + X ^ 3 + 1. Here, “X ^ a” means X to the power of a.
Also, the public key h, the secret key f, the plaintext m, the random number r, and the ciphertext c used at the time of encryption or decryption are all expressed as polynomials of N−1 dimensions or less (hereinafter referred to as public key polynomials). h, secret key polynomial f, plaintext polynomial m, random number polynomial r, and ciphertext polynomial c).

In the polynomial calculation, the relational expression X ^ N = 1 is used for the system parameter N so that the calculation result is always a polynomial of N-1 dimensions or less.
For example, in the case of N = 5, the product of the polynomial X ^ 4 + X ^ 2 + 1 and the polynomial X ^ 3 + X is represented by the relationship of X ^ 5 = 1 when the product of the polynomial and the polynomial is x and the product of the integer and the polynomial is.
(X ^ 4 + X ^ 2 + 1) × (X ^ 3 + X)
= X ^ 7 + 2, X ^ 5 + 2, X ^ 3 + X
= X ^ 2 × 1 + 2 ・ 1 + 2 ・ X ^ 3 + X
= 2 · X ^ 3 + X ^ 2 + X + 2
It becomes.

In this way, in the polynomial calculation, the calculation is always performed so that the polynomial has N-1 dimensions or less.
(3) NTRU encryption method encryption The encryption device described later performs NTRU encryption method encryption as follows.
At the time of encryption, the plaintext polynomial m is subjected to an encryption algorithm E that is a polynomial operation using a random number polynomial r and a public key polynomial h described below,
A ciphertext polynomial c = E (m, r, h) is generated.

Here, E (m, r, h) is a result of a polynomial operation obtained by inputting a plaintext polynomial m, a random number polynomial r, and a public key polynomial h to the encryption algorithm E of the NTRU cryptosystem. The encryption algorithm E is described in detail in Non-Patent Document 2, and description thereof is omitted here.
In the NTRU cryptosystem, a parameter d for generating the random number polynomial r is determined in advance. Among the terms constituting the random number polynomial r, the random polynomial r has a coefficient “1” for d terms, a coefficient “−1” for the other d terms, and the remaining terms. Is selected such that the coefficient is "0".

That is, the random number polynomial r is a polynomial of N-1 dimensions or less, and there are N coefficients for N terms from 0 dimension (constant term) to N-1 dimensions. Among the N coefficients, the random number polynomial r has d coefficients of “1”, d coefficients of “−1”, and (N−2d) coefficients of “0”. It is chosen so that it becomes.
According to Non-Patent Document 2, when parameter N = 167, d = 18. That is, the random number polynomial r is selected so that 18 coefficients are “1”, 18 coefficients are “−1”, and 131 (= 167−36) coefficients are “0”. It is.

(4) NTRU encryption method decryption The decryption apparatus described later performs the NTRU encryption method decryption as described below.
At the time of decryption, the decryption text polynomial m ′ = D (c, f) is generated by applying the decryption algorithm D, which is a polynomial operation, to the ciphertext polynomial c using the secret key polynomial f.
Here, D (c, f) is a result of a polynomial operation obtained by inputting the ciphertext polynomial c and the secret key polynomial f into the decryption algorithm D of the NTRU cryptosystem. The decryption algorithm D is described in detail in Non-Patent Document 2, and description thereof is omitted here.

(5) Decryption error of NTRU cryptosystem By the way, in this NTRU cryptosystem, a case where the generated decrypted text polynomial m ′ is different from the plaintext polynomial m occurs. In this case, the plaintext polynomial m cannot be obtained correctly at the time of decryption. This is called a decoding error.
1.2 Configuration of Content Distribution System 10 As shown in FIG. 1, the content distribution system 10 includes a content server device 140, an encryption device 110, a decryption device 120, a playback device 150, and a monitor 155. The device 140 and the encryption device 110 are connected via the dedicated line 20, and the encryption device 110 and the decryption device 120 are connected via the Internet 130. The playback device 150 is connected to a decoding device 120 and a monitor 155 with a built-in speaker. A memory card 160 is attached to the encryption device 110, and a memory card 170 is attached to the decryption device 120.

The content server device 140 transmits content such as a movie composed of video and audio to the encryption device 110 via the dedicated line 20.
The encryption device 110 and the decryption device 120 generate the same shared key K and shared key K ′, respectively. Next, the encryption device 110 encrypts the content received from the content server device 140 using the shared key K to generate encrypted content, transmits the generated encrypted content, and the decryption device 120 transmits the encrypted content. , Decrypts the received encrypted content to generate playback content, the playback device 150 generates a video signal and an audio signal from the playback content, and the monitor 155 displays the video and outputs audio.

1.3 Configuration of Content Server Device 140 The content server device 140 is a computer system (not shown) including a microprocessor, a ROM, a RAM, a hard disk unit, a display unit, a communication unit, a keyboard, a mouse, and the like. A computer program is stored in the RAM or the hard disk unit. The content server device 140 achieves a part of its functions by the microprocessor operating according to the computer program.

The content server device 140 stores the content in advance, and the content includes a plurality of partial contents mi (1 ≦ i ≦ n). The content server device 140 reads the partial content mi in response to a request from the encryption device 110, and transmits the read partial content mi to the encryption device 110 via the dedicated line 20.
1.4 Configuration of Memory Card 160 and Memory Card 170 The memory card 160 is a card-type storage device that employs a flash memory as a storage medium, and stores a public key polynomial h in advance.

The memory card 170 is a card-type storage device similar to the memory card 160, and stores a secret key polynomial f and a public key polynomial h in advance.
Here, the secret key polynomial f and the public key polynomial h are generated by the NTRU cryptosystem and correspond to each other.
1.5 Configuration of Encryption Device 110 As shown in FIG. 2, the encryption device 110 includes a public key input unit 111, a random number generation unit 112, a first function unit 113, an encryption unit 114, a first transmission unit 117, a common key. It comprises an encryption unit 118 and a second transmission unit 119.

Specifically, the encryption device 110 is a computer system including a microprocessor, a ROM, a RAM, a communication unit, and the like. A computer program is stored in the RAM. The cryptographic apparatus 110 achieves its functions by the microprocessor operating according to the computer program.
(1) Public key input unit 111
The public key input unit 111 reads the public key polynomial h of the decryption device 120 from the memory card 160 and outputs the read public key polynomial h to the encryption unit 114.

(2) Random number generator 112
The random number generation unit 112 generates a random number s as a seed value for generating the shared key K, and outputs the generated random number s to the first function unit 113 and the encryption unit 114.
(3) First function unit 113
The first function unit 113 receives the random number s from the random number generation unit 112 and generates a function value G (s) of the random number s. Here, the function G is a hash function having an output length of 2 k bits. The hash function is a kind of one-way function. Next, the first function unit 113 sets the higher k bits of the function value G (s) as the random value u and the lower k bits of G (s) as the shared key K, thereby generating the generated function value G (s ) To generate a shared key K and a random value u, output the generated random value u to the encryption unit 114, and output the generated shared key K to the common key encryption unit 118.

(4) Encryption unit 114
The encryption unit 114 receives the public key polynomial h from the public key input unit 111, receives the random number s from the random number generation unit 112, and receives the random value u from the first function unit 113. Next, the first ciphertext c1 of the random number s is generated using the public key polynomial h and the random value u by NTRU encryption as follows. Here, the random value u is a blind value and is used to obscure the random number s to be encrypted.

For the parameter d of the NTRU cipher, the encryption unit 114 has a coefficient of d terms of the random number polynomial r of “1”, a coefficient of d terms of “−1”, and a coefficient of the remaining terms. Is generated so that the random number polynomial r having “0” can be uniquely obtained from the random value u.
For example, the encryption unit 114 sets the random value u as an initial value (random number seed) of the pseudo-random number sequence, and {0, 1,. . . , N-1} to generate 2d pseudo-random numbers so as not to overlap each other, set the coefficients of d-dimensional terms indicated by the first d pseudo-random numbers to “1”, and the remaining d pseudo-random numbers. The coefficient of d-dimensional terms each indicated by a random number is “−1”, and the coefficients of terms of other dimensions are “0”.

  Next, the encryption unit 114 determines that the value of each digit of the N-digit bit string when the random number s is expressed in binary notation so that the random number s can be applied to the encryption algorithm E of the NTRU encryption, The random number polynomial sp is constructed so as to correspond to the coefficients of. For example, the value of the lower b bits of the random number s is set as the coefficient of the term X ^ b. Specifically, when s = 110010 (bit representation), a random number polynomial sp = X ^ 5 + X ^ 2 is generated.

Next, the encryption unit 114 performs the encryption algorithm E on the random number polynomial sp using the random number polynomial r using the public key polynomial h, and
First ciphertext c1 = ciphertext polynomial E (sp, r, h) is generated.
Next, the encryption unit 114 outputs the generated first ciphertext c1 to the first transmission unit 117.
In FIG. 2, each block indicating each component of the encryption device 110 is connected to another block by a connection line. Here, each connection line indicates a path through which signals and information are transmitted. Of the plurality of connection lines connected to the block indicating the encryption unit 114, the ones with a key mark on the connection line indicate a path through which information as a key is transmitted to the encryption unit 114. ing. The same applies to the block indicating the common key encryption unit 118. The same applies to other drawings.

(5) First transmission unit 117
The first transmission unit 117 receives the first ciphertext c1 from the encryption unit 114, and transmits the first ciphertext c1 to the decryption device 120 via the Internet 130.
(6) Common key encryption unit 118
The common key encryption unit 118 has a common key encryption algorithm Sym such as a DES encryption method, for example.

  In general, in common key cryptography, a ciphertext c = Sym (m, K) is generated by applying a common key cryptography algorithm Sym to a plaintext m using an encryption key K in a device on the encryption side, and a decryption side In this apparatus, the ciphertext c is subjected to the common key encryption algorithm Sym using the encryption key K to generate the decrypted text m ′ = Sym (c, K). Here, if the encryption key K used when generating the ciphertext and the encryption key K used when generating the decrypted text are the same, m ′ = m. Since the common key encryption and the DES encryption method are described in detail in Non-Patent Document 1, detailed description thereof is omitted here.

The common key encryption unit 118 receives a plurality of plaintexts (partial contents) mi (1 ≦ i ≦ n) from the content server device 140, receives the shared key K from the first function unit 113, and uses the received shared key K. Then, the plaintext mi (1 ≦ i ≦ n) is subjected to the common key encryption algorithm Sym to generate the common key ciphertext Ci = Sym (mi, K) (1 ≦ i ≦ n).
Next, the common key encryption unit 118 outputs the common key ciphertext Ci (1 ≦ i ≦ n) to the second transmission unit 119.

(7) Second transmitter 119
The second transmission unit 119 receives the common key ciphertext Ci (1 ≦ i ≦ n) from the common key encryption unit 118 and decrypts the received common key ciphertext Ci (1 ≦ i ≦ n) via the Internet 130. Transmit to device 120.
1.6 Configuration of Decryption Device 120 As shown in FIG. 3, the decryption device 120 includes a secret key input unit 121, a first reception unit 122, a decryption unit 123, a second function unit 126, a comparison unit 127, and a common key decryption. Part 128 and a second receiving part 129.

The decryption device 120 is a computer system similar to the encryption device 110. The decoding device 120 achieves its functions by the microprocessor operating according to the computer program.
(1) Secret key input unit 121
The secret key input unit 121 reads the secret key polynomial f and the public key polynomial h of the decryption device 120 from the memory card 170, outputs the read secret key polynomial f to the decryption unit 123, and reads the read public key polynomial h. Is output to the comparison unit 127.

(2) First receiving unit 122
The first receiving unit 122 receives the first ciphertext c1 from the encryption device 110 via the Internet 130, and outputs the received first ciphertext c1 to the decryption unit 123.
(3) Decoding unit 123
The decryption unit 123 receives the secret key polynomial f from the secret key input unit 121, receives the first ciphertext c1 from the first reception unit 122, and uses the secret key polynomial f by NTRU encryption as shown below. The first ciphertext c1 is decrypted to generate a decrypted random number s ′.

  The decryption unit 123 applies the decryption algorithm D to the first ciphertext c1 using the secret key polynomial f to generate a decrypted random number polynomial sp ′ = D (c1, f). Next, since the decrypted random number polynomial sp ′ is a decrypted text of the NTRU cipher and is represented by a polynomial, the coefficient of each term of the decrypted random number polynomial sp ′ is N digits when the decrypted random number s ′ is represented by a binary number. The decrypted random number s ′ is generated so as to correspond to each value of the bit string. For example, the coefficient of the b-dimensional term X ^ b of the decrypted random number polynomial sp ′ is the value of the lower b bits of the decrypted random number s ′.

Specifically, when the decrypted random number polynomial sp ′ = X ^ 5 + X ^ 2, a decrypted random number s ′ = 110010 (bit representation) is generated.
Next, the decryption unit 123 outputs the received first ciphertext c1 and the generated decrypted random number s ′ to the comparison unit 127, and outputs the generated decrypted random number s ′ to the second function unit 126.
(4) Second function unit 126
The second function unit 126 has the same function G algorithm as the function of the first function unit 113.

The second function unit 126 receives the decrypted random number s ′ from the decryption unit 123, generates the function value G (s ′) of the decrypted random number s ′ in the same manner as the first function unit 113, and then the function value A random value u ′ and a shared key K ′ are generated from G (s ′), and the generated random value u ′ and the shared key K ′ are output to the comparison unit 127.
(5) Comparison unit 127
As shown in FIG. 3, the comparison unit 127 includes an encryption unit 127x and a comparison operation unit 127y.

  The encryption unit 127x receives the public key polynomial h from the secret key input unit 121, receives the decrypted random number s 'from the decryption unit 123, and receives the random value u' from the second function unit 126. Next, in the same manner as the encryption unit 114, the decrypted random number s ′ is encrypted using the public key polynomial h and the random value u ′ to generate the first re-encrypted text c1 ′, and the generated first re-encrypted text c1 ′ is generated. The ciphertext c1 ′ is output to the comparison operation unit 127y.

  The comparison operation unit 127y receives the first ciphertext c1 from the decryption unit 123, receives the shared key K ′ from the second function unit 126, and receives the first re-ciphertext c1 ′ from the encryption unit 127x. Next, the first ciphertext c1 and the first re-ciphertext c1 ′ are compared to determine whether or not they match, and when it is determined that they match, the received shared key K ′ is shared. The data is output to the key decryption unit 128. If it is determined that they do not match, the received shared key K ′ is not output.

(6) Second receiving unit 129
The second receiving unit 129 receives the common key ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110 via the Internet 130, and the received common key ciphertext Ci (1 ≦ i ≦ n). To the unit 128.
(7) Common key decryption unit 128
The common key decryption unit 128 has a common key encryption algorithm Sym that is the same as the common key encryption algorithm Sym included in the common key encryption unit 118 in advance.

The common key decryption unit 128 receives the shared key K ′ from the comparison unit 127, receives the common key ciphertext Ci (1 ≦ i ≦ n) from the second reception unit 129, and receives it using the received shared key K ′. The common key ciphertext Ci (1 ≦ i ≦ n) is subjected to the common key encryption algorithm Sym to generate a decrypted text mi ′ = Sym (Ci, K) (1 ≦ i ≦ n).
Next, the common key decryption unit 128 outputs the generated decrypted text mi ′ (1 ≦ i ≦ n) to the playback device 150.

1.7 Playback device 150 and monitor 155
The playback device 150 receives the decrypted text mi ′ (1 ≦ i ≦ n) from the decryption device 120, generates a video signal and an audio signal from the received decrypted text mi ′ (1 ≦ i ≦ n), and generates the generated video signal. And the audio signal is output to the monitor 155.
The monitor 155 receives a video signal and an audio signal from the playback device 150, displays video based on the received video signal and audio signal, and outputs audio.

1.8 Operations of Encryption Device 110 and Decryption Device 120 Operations of the encryption device 110 and the decryption device 120 will be described with reference to a processing system diagram shown in FIG. 4 and a flowchart shown in FIG.
The public key input unit 111 of the encryption device 110 reads the public key polynomial h of the decryption device 120 from the memory card 160, and outputs the read public key polynomial h to the encryption unit 114 (step S101).

Next, the random number generation unit 112 generates a random number s, and outputs the generated random number s to the first function unit 113 and the encryption unit 114 (step S102).
Next, the first function unit 113 receives the random number s from the random number generation unit 112, generates a function value G (s) of the random number s (step S103), and then the first function unit 113 outputs the function value G The random value u and the shared key K are generated from (s), the random value u is output to the encryption unit 114, and the shared key K is output to the common key encryption unit 118 (step S104).

Next, the encryption unit 114 receives the public key polynomial h from the public key input unit 111, receives the random number s from the random number generation unit 112, receives the random number value u from the first function unit 113, and receives the random number u from the public key polynomial h. The first ciphertext c1 of the random number s is generated using the numerical value u, and the first ciphertext c1 is output to the first transmission unit 117 (step S105).
Next, the first transmission unit 117 receives the first ciphertext c1 from the encryption unit 114, and transmits the first ciphertext c1 to the decryption device 120 via the Internet 130 (step S106).

Next, the secret key input unit 121 of the decryption device 120 reads the secret key polynomial f and the public key polynomial h of the decryption device 120 from the memory card 170, and outputs the read secret key polynomial f to the decryption unit 123. The read public key polynomial h is output to the comparison unit 127 (step S151).
Next, the first receiving unit 122 receives the first ciphertext c1 from the encryption device 110 via the Internet 130, and outputs the first ciphertext c1 to the decryption unit 123 (step S106).

Next, the decryption unit 123 receives the secret key polynomial f from the secret key input unit 121, receives the first ciphertext c1 from the first reception unit 122, and then uses the secret key polynomial f to The decrypted random number s ′ is generated by decrypting the sentence c1, the first ciphertext c1 and the decrypted random number s ′ are output to the comparison unit 127, and the decrypted random number s ′ is output to the second function unit 126 (step S152).
Next, the second function unit 126 receives the decrypted random number s ′ from the decryption unit 123, generates a function value G (s ′) of the decrypted random number s ′ (step S153), and uses the function value G (s ′). The random value u ′ and the shared key K ′ are generated, and the random value u ′ and the shared key K ′ are output to the comparison unit 127 (step S154).

  Next, the comparison unit 127 receives the first ciphertext c1 from the decryption unit 123, receives the random value u ′ and the shared key K ′ from the second function unit 126, and generates the first re-ciphertext c1 ′. (Step S155), it is checked whether the first ciphertext c1 is a ciphertext of the decrypted random number s ′ using the random number value u ′, and the first ciphertext c1 is not a ciphertext of the decrypted random number s ′ ( Step S156), the decoding device 120 ends the process.

  The common key encryption unit 118 receives a plurality of plaintext mi (1 ≦ i ≦ n) from the outside, receives the shared key K from the first function unit 113, and uses the shared key K to obtain a plaintext mi (1 ≦ i ≦ n). ) Is subjected to a common key encryption algorithm Sym to generate a common key ciphertext Ci = Sym (mi, K) (1 ≦ i ≦ n) and a second transmission of the common key ciphertext Ci (1 ≦ i ≦ n) The data is output to the unit 119 (step S107).

Next, the second transmission unit 119 receives the common key ciphertext Ci (1 ≦ i ≦ n) from the common key encryption unit 118, transmits it to the decryption device 120 via the Internet 130 (step S108), and ends the processing. To do.
If the first ciphertext c1 is the ciphertext of the decrypted random number s ′ (step S156), the comparison unit 127 outputs the shared key K ′ to the common key decryption unit 128 (step S157). Next, the second reception unit 129 receives the ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110 via the Internet 130, and outputs it to the common key decryption unit 128 (step S108).

  Next, the common key decryption unit 128 receives the shared key K ′ from the comparison unit 127, receives the common key ciphertext Ci (1 ≦ i ≦ n) from the second reception unit 129, and uses the shared key K ′. The common key ciphertext Ci (1 ≦ i ≦ n) is subjected to the common key encryption algorithm Sym to generate a decrypted text mi ′ = Sym (Ci, K) (1 ≦ i ≦ n), and the decrypted text mi ′ (1 ≦ i ≦ n) is output to the playback device 150 (step S158), and the process ends.

1.9 Operation Verification of Content Distribution System 10 The overall operation of the content distribution system 10 according to Embodiment 1 will be described below.
First, the encryption device 110 receives the public key polynomial h of the decryption device 120, generates a random number s, and derives a random value u and a shared key K from the function value G (s). Next, the encryption device 110 encrypts the random number s with NTRU encryption using the public key polynomial h and the random value u to generate the first ciphertext c1, and decrypts the first ciphertext c1 via the Internet 130. Transmit to device 120.

That is, the encryption device 110 performs the following processing and transmits the first ciphertext c1 to the decryption device 120.
Generate a random number s.
Generate G (s) and generate u and K from G (s).
A first cipher text c1 of the random number s is generated using the public key polynomial h and the random value u.

-Output the shared key K and the first ciphertext c1.
Next, the encryption device 110 encrypts the plaintext mi (1 ≦ i ≦ n) input from the outside with the common key encryption using the derived shared key K to generate the ciphertext Ci (1 ≦ i ≦ n). It is generated and transmitted to the decryption device 120 via the Internet 130.
On the other hand, the decryption device 120 receives the private key polynomial f and the public key polynomial h of the decryption device 120, receives the first ciphertext c1 from the encryption device 110 via the Internet 130, and uses the first ciphertext c1 as the private key. Decoding is performed using the polynomial f to generate a decoded random number s ′. Next, a random value u ′ and a shared key K ′ are derived from the function value G (s ′) of the decrypted random number s ′, the decrypted random number s ′ is encrypted to generate a first re-ciphertext c1 ′, and c1 ′. If = c1, the shared key K ′ is output.

That is, the decryption device 120 performs the following process to derive the shared key K ′.
Decrypt the first ciphertext c1 using the secret key polynomial f to generate s ′.
Generate G (s ′) and generate u ′ and K ′ from G (s ′).
A first recipher text c1 ′ of s ′ is generated using the public key polynomial h and the random value u ′.
Check whether c1 ′ = c1 is true. If it is established, the shared key K ′ is output.

  Here, if the correct private key polynomial f corresponding to the public key polynomial h used in the encryption device 110 is used in the decryption device 120, the first ciphertext c1 is correctly decrypted, and the decrypted random number s ′ = s, Therefore, the random value u ′ = u derived from G (s ′) and the shared key K ′ = K. Since s ′ = s and u ′ = u hold, c1 ′ = c1 holds, and the decryption device 120 can derive the same shared key K as the encryption device 110.

  Next, the decryption device 120 decrypts the common key cipher text Ci (1 ≦ i ≦ n) from the encryption device 110 via the Internet using the derived shared key K ′ (= K) with the common key encryption. Decrypted text mi ′ (1 ≦ i ≦ n) is generated and output to the outside. Here, since the encryption key K used when generating the common key ciphertext and the encryption key K ′ used when generating the decrypted text are the same, the decrypting device 120 correctly obtains mi ′ = mi (1 ≦ i ≦ n). be able to.

When a decryption error occurs, the decrypted random number s ′ and the random number s are different, and therefore the random value u ′ and the shared key K ′ derived from G (s ′) are different from u and K, respectively. . However, in this case, since the first re-ciphertext c1 ′ is different from the first ciphertext c1 because s ′ and u ′ are different from s and u, respectively, the decryption device 120 does not output the shared key K ′.
1.10 Effect in Embodiment 1 In the conventional RSA-KEM algorithm, the shared key K is derived by inputting the element s that cannot be derived from the ciphertext C without knowing the secret key to the hash function G. However, if an attempt is made to deliver a shared key by applying the RSA-KEM algorithm, which is a key encapsulation mechanism, using NTRU encryption, a decryption error may occur. In some cases, the shared key K ′ that cannot be derived and therefore incorrect is derived.

  However, in the content distribution system, encryption device, and decryption device of Embodiment 1, in addition to the shared key, the random value u is generated from the hash function value G (s) of the random number s, and the decryption device discloses the random value u. The decrypted random number s ′ is re-encrypted using the key polynomial h to generate the first re-ciphertext c1 ′, and the shared key K ′ is used as long as the first re-ciphertext c1 ′ is not the same value as the first ciphertext c1. Since no output is performed, it is possible to prevent different keys from being derived between the encryption device and the decryption device when a decryption error occurs.

Further, the method according to the present invention can theoretically prove its safety by a method similar to the proof method described in Non-Patent Document 3.
1.11 Modifications Embodiment 1 described above is an example of implementation of the present invention, and the present invention is not limited to this embodiment at all, and various embodiments are possible without departing from the scope of the present invention. Can be implemented. The following cases are also included in the present invention.

(1) It is not limited to the parameter N = 167 of the NTRU encryption used. The parameter N may take other values.
(2) The conversion method between the value of each bit of the bit string and the coefficient of each term of the polynomial performed by the encryption unit 114 and the decryption unit 123 is not limited to the method described above, and other conversion methods may be used.

For example, the conversion from the random number s to the random number polynomial sp may be performed by using a function that makes a one-to-one correspondence between the value of each bit of the bit string and the coefficient of each term of the polynomial, The conversion may be performed using a function value table that stores bit values and coefficients of each term of the polynomial in a one-to-one correspondence.
Also, in the conversion from the random value u to the random number polynomial r, r is uniquely obtained from u, the coefficient of the d-dimensional term of r is “1”, and the coefficient of the d-dimensional term is “1”. As long as the coefficient of the term of the other dimension is set to “0”, other conversion methods may be used. For example, the random value u is converted using a function corresponding to a polynomial or a function value table. Also good.

(3) In the public key cryptosystem used by the encryption unit 114 and the decryption unit 123, the encryption unit 114 encrypts the random number s using the public key and the random value u to generate the first ciphertext c1. The decryption unit 123 only needs to be able to decrypt the first ciphertext c1 with the secret key and generate a decrypted random number s ′ equal to the random value s.
Therefore, the public key encryption used in the encryption unit 114 and the decryption unit 123 can be any public key encryption other than the NTRU encryption.

For example, if ElGamal encryption is adopted, h and f are set as the public and private keys of ElGamal encryption, respectively, and the encryption unit 114 encrypts the random number s using h and u to generate c1 and decrypts it. In the unit 123, c1 may be decoded using f to generate s ′.
Since ElGamal encryption is described in detail in Non-Patent Document 1, description thereof is omitted here.

(4) The first function unit 113 shares the function value G (s) with the random value u except that the upper k bits of the function value G (s) are the random number u and the lower k bits are the shared key K. Another method may be used if the key K is derived.
For example, the upper k / 2 bits of the function value G (s) may be the random value u and the lower k × 3/2 bits may be the shared key K. Alternatively, out of 2k bits of the function value G (s), k bits may be selected every other bit as a random value u, and the remaining k bits may be used as the shared key K.

(5) In addition to the random value u generated by the first function unit 113 and the second function unit 126, if the same value is obtained by the encryption device 110 and the decryption device 120, another generation method is adopted. May be.
For example, for an arbitrary function Func, the same value may be obtained by the encryption device 110 and the decryption device 120 as u = Func (s). That is, in the encryption device 110 and the decryption device 120,
Generate G (s) and generate K from G (s).

Generate Func (s) and set u = Func (s).
It is good.
(6) Since the random value u is not generated by the first function unit 113 and the second function unit 126, it is sufficient that the same value is obtained by the encryption device 110 and the decryption device 120. The numerical value u may be transmitted directly to the decoding device 120b.

That is, the first ciphertext c1 and the random number u may be transmitted to the decryption device 120 as follows. At this time, the random value u may be transmitted after being encrypted.
In the encryption device 110,
Generate G (s) and generate K from G (s).
The random value u is separately transmitted from the encryption device 110 to the decryption device 120.

In the decoding device 120,
Receive the random value u.
A first re-ciphertext c1 ′ is generated using the received random value u instead of the random value u ′.
At this time, the encryption device 110 may encrypt and transmit the random number value u, and the decryption device 120 may decrypt the encrypted random value u.

(7) Since the random value u only needs to be obtained by the encryption device 110 and the decryption device 120, partial information of a part of the random value u is generated by the first function unit 113 and the second function unit 126, The partial information of the remaining part of the random number u may be directly transmitted from the encryption device 110 to the decryption device 120.
For example, as described below, the encryption device 110 may transmit the first ciphertext c1 and the random value u2 to the decryption device 120.

In the encryption device 110,
(A) G (s) is generated, and K and u1 are generated from G (s).
(B) A random value u2 is generated and transmitted to the decryption device 120 separately.
(C) The random value u is generated from u = u1 xor u2.
(D) The first ciphertext c1 is generated using the random value u.

In the decoding device 120,
(E) Receive the random value u2.
(F) G (s ′) is generated, and K ′ and u1 ′ are generated from G (s ′).
(G) A random value u ′ is generated from u ′ = u1 ′ xor u2.
(H) A first re-ciphertext c1 ′ is generated using the generated random value u ′.

At this time, the encryption device 110 may encrypt and transmit the random value u2, and the decryption device 120 may decrypt the encrypted random value u2.
In (c) and (g), another operation may be used instead of the exclusive OR xor. For example, in (c) and (g), addition and subtraction may be used, respectively, and multiplication and division may be used.

  (8) The first re-ciphertext c1 ′ and the first ciphertext c1 are the same in order to prevent different shared keys from being derived between the encryption device 110 and the decryption device 120 due to the occurrence of a decryption error. In this case, instead of outputting the shared key K ′, the encryption device 110 generates a hash function value for any one or more of the random number s, the random value u, and the shared key K, and the generated hash function value is decrypted. The decryption device 120 may determine whether to output the shared key K ′ by verifying the hash function value. For example, as this hash function value, a hash function value H (s) of a random number s may be generated for an arbitrary hash function H, or a combination of a random number s, a random value u, and a shared key K, For example, a hash function value H (s || u || k) or a hash function value H (u || k) may be generated.

In this case, the first function unit 113 of the encryption device 110 may derive only the shared key K from G (s) instead of deriving the random value u and the shared key K from the function value G (s). Good.
Specific examples will be described below.
The content distribution system 10 includes an encryption device 110b and a decryption device 120b instead of the encryption device 110 and the decryption device 120, and the encryption device 110b includes a public key input unit 111, a random number generation unit 112, The decryption device 120 includes a first function unit 113b, an encryption unit 114b, a first transmission unit 117b, a common key encryption unit 118, and a second transmission unit 119. As shown in FIG. 121b, a first receiving unit 122b, a decrypting unit 123b, a second function unit 126b, a comparing unit 127b, a common key decrypting unit 128, and a second receiving unit 129. The comparison unit 127b includes a third function unit 127u and a comparison calculation unit 127v.

When the encryption device 110b generates a hash function value of the random number s and the decryption device 120b verifies the hash function value, the encryption device 110b has a first function unit 113b as shown in the processing system diagram of FIG. , G (s) is generated (step S103), and K is generated from G (s) (step S104).
Next, the encryption unit 114b generates a random number value u, generates a random number polynomial r from the generated random number value u, and generates a first ciphertext c1 of the random number s using the random number polynomial r and the public key polynomial h. Then, the hash function value H (s) is generated (step S111).

Next, the first transmission unit 117b transmits the first ciphertext c1 (step S106) and transmits the hash function value H (s) (step S112).
Next, in the decryption device 120b, the first receiving unit 122b receives the first ciphertext c1 (step S106), and receives the hash function value H (s) (step S112).
Next, the decryption unit 123b decrypts the first ciphertext c1 using the secret key polynomial f to generate s ′ (step S152).

Next, the second function unit 126 generates G (s ′) (step S153), and generates K ′ from G (s ′) (step S154).
Next, the comparison unit 127 generates H (s ′) by the third function unit 127u (step S154), and checks whether H (s ′) = H (s) is satisfied by the comparison operation unit 127v. (Step S162), if established, the shared key K ′ is output (Step S157).

  In this case, in order to further increase the safety, the first ciphertext c1 may be generated by encrypting the random number s with additional information using the method disclosed in Patent Document 1. . That is, in FIG. 6, the encryption unit 114b generates the additional information Ra, encrypts the value of the bit combination s || Ra of s and Ra to generate the first ciphertext c1, and in FIG. The unit 123b may decrypt the first ciphertext c1 to generate s ′ || Ra ′, remove Ra ′, and generate the decrypted random number s ′.

Further, as disclosed in Patent Document 1, instead of the value of s || Ra, the value of reversible transformation F (s, Ra) of s and Ra may be used.
2. Embodiment 2
A content distribution system 10c (not shown) as another embodiment according to the present invention will be described.

  The content distribution system 10c is a system obtained by modifying the content distribution system 10 as a base. The content distribution system 10c generates a verification value a in addition to the random value u and the shared key K from the function value G (s). Instead of generating and transmitting the first ciphertext c1 obtained by encrypting the random number s, the apparatus encrypts the first ciphertext c1 obtained by encrypting the verification value a and the random number s based on the verification value a. It differs from the content distribution system 10 in that 2 ciphertext c2 is generated and transmitted.

Hereinafter, the content distribution system 10c will be described in detail focusing on the above differences.
2.1 Configuration of Content Distribution System 10c The content distribution system 10c has the same configuration as the content distribution system 10, and includes an encryption device 110c and a decryption device 120c instead of the encryption device 110 and the decryption device 120. Yes. Since other configurations are the same as those in the content distribution system 10, the description thereof is omitted.

2.2 Configuration of Encryption Device 110c The encryption device 110c has the same configuration as the encryption device 110, as shown in FIG. 9, and includes a random number generation unit 112, a first function unit 113, an encryption unit 114, and an encryption unit 110. Instead of the one transmission unit 117, a random number generation unit 112c, a first function unit 113c, an encryption unit 114c, a random number mask unit 116c, and a first transmission unit 117c are included.

Here, the random number generation unit 112c, the first function unit 113c, the encryption unit 114c, the random number mask unit 116c, and the first transmission unit 117c will be described.
(1) Random number generator 112c
The random number generation unit 112c generates a random number s as a seed value for generating the shared key K, and outputs the generated random number s to the first function unit 113b and the random number mask unit 116c.

(2) First function unit 113c
The first function unit 113c receives the random number s from the random number generation unit 112c and generates a function value G (s) of the random number s. Next, a verification value a, a shared key K, and a random value u are generated from the generated function value G (s).
Here, the function G is a hash function with an output length of 3 k bits, and the first function unit 113 c uses the upper k bits of the function value G (s) as the verification value a, and is an intermediate value between the function values G (s). Let k bits be a shared key K, and the lower k bits of the function value G (s) be a random value u.

Next, the first function unit 113c outputs the generated verification value a and the random value u to the encryption unit 114c, outputs the generated shared key K to the common key encryption unit 118, and generates the generated verification value a. It outputs to the random number mask part 116c.
(3) Encryption unit 114c
The encryption unit 114c receives the public key polynomial h from the public key input unit 111, receives the verification value a and the random value u from the first function unit 113c, and performs the public key polynomial h and the random value as follows. u is used to generate a first ciphertext c1 having a verification value a. Here, the first ciphertext c1 is a ciphertext based on the NTRU cipher.

  The encryption unit 114c is configured such that each coefficient of the d terms is “1”, each coefficient of the other d terms is “−1”, and each of the remaining terms for the parameter d of the NTRU encryption. A random number polynomial r having a coefficient of “0” is generated so as to be uniquely obtained from the random value u. Specifically, the random value u is set as the initial value (random number seed) of the pseudo-random number sequence, and {0, 1,. . . , N−1} are selected so as not to overlap, the coefficient of the dimension term indicated by the first d pseudorandom numbers is set to “1”, and is indicated by the other d pseudorandom numbers. A random number polynomial r is generated by setting the coefficient of the dimension to “−1” and the coefficients of the remaining terms to “0”.

  Next, so that the received verification value a can be applied to the NTRU encryption algorithm E, the encryption unit 114c determines that the value of each digit of the N-digit bit string when the verification value a is expressed in binary is a verification value. The verification value polynomial ap is converted to the verification value polynomial ap by configuring the verification value polynomial ap so as to correspond to the coefficient of each term of the polynomial ap. For example, the value of the lower-order b bit of the verification value a is the coefficient value of the term X ^ b. Specifically, when the verification value a = 110010 (bit representation), the verification value polynomial ap = X ^ 5 + X ^ 2 is generated.

Next, the encryption unit 114c applies the encryption algorithm E to the verification value polynomial ap using the random number polynomial r using the public key polynomial h as a key, and the first ciphertext c1 = E (ap, r, h) is generated.
Next, the encryption unit 114c outputs the generated first ciphertext c1 to the first transmission unit 117c.

(4) Random number mask part 116c
The random number mask unit 116c receives the random number s from the random number generation unit 112c, receives the verification value a from the first function unit 113c, generates a second ciphertext c2 = s xor a, and generates the generated second ciphertext c2 is output to the first transmitter 117c.
Here, xor is an operator representing an exclusive OR operation.

The random number mask unit 116c may use a shared key encryption algorithm, addition, or multiplication instead of the exclusive OR.
(5) First transmission unit 117c
The first transmission unit 117c receives the first ciphertext c1 from the encryption unit 114c, receives the second ciphertext c2 from the random number mask unit 116c, and transmits the received first ciphertext c1 and second ciphertext c2 to the Internet. The data is transmitted to the decoding device 120c via 130.

2.2 Configuration of Decoding Device 120c As shown in FIG. 10, the decoding device 120c has the same configuration as the decoding device 120, and includes a first receiving unit 122, a decoding unit 123, a second function unit 126, and Instead of the comparison unit 127, a first reception unit 122c, a decryption unit 123c, a random number mask removal unit 125c, a second function unit 126c, and a comparison unit 127c are included.

Here, the 1st receiving part 122c, the decoding part 123c, the random number mask removal part 125c, the 2nd function part 126c, and the comparison part 127c are demonstrated.
(1) First receiving unit 122c
The first reception unit 122c receives the first ciphertext c1 and the second ciphertext c2 from the encryption device 110c via the Internet 130, and outputs the received first ciphertext c1 to the decryption unit 123c. The second ciphertext c2 is output to the random number mask removal unit 125c.

(2) Decoding unit 123c
The decryption unit 123c receives the secret key polynomial f from the secret key input unit 121, receives the first ciphertext c1 from the first reception unit 122c, and uses the secret key polynomial f to The ciphertext c1 is decrypted to generate a decryption verification value a ′. Here, the decryption verification value a ′ is a decrypted text by NTRU encryption.

  The decryption unit 123c applies the decryption algorithm D to the first ciphertext c1 using the secret key polynomial f as a key to generate a decryption verification value polynomial ap ′ = D (c1, f). Here, since the decryption verification value polynomial ap ′ is a decrypted text of the NTRU cipher and is expressed by a polynomial, the decryption unit 123 c has expressed the coefficients of each term of the decryption verification value polynomial ap ′ in binary numbers. The decryption verification value polynomial ap ′ is converted into the decryption verification value a ′ so as to correspond to the value of each digit of the decryption verification value a ′ which is an N-digit bit string. For example, the coefficient of the b-dimensional term X ^ b of the decryption verification value polynomial ap ′ is set as the value of the lower b bits of the decryption verification value a ′. Specifically, in the case of the decryption verification value polynomial ap ′ = X ^ 5 + X ^ 2, the decryption verification value a ′ is converted to 10010 (bit representation).

Next, the decryption unit 123c outputs the generated decryption verification value a ′ to the random number mask removal unit 125c, and outputs the received first ciphertext c1 to the comparison unit 127c.
(3) Random number mask removal unit 125c
The random number mask removal unit 125c receives the second ciphertext c2 from the first reception unit 122c, receives the decryption verification value a ′ from the decryption unit 123c,
A decrypted random number s ′ = c2 xor a ′ is generated, and the generated decrypted random number s ′ is output to the second function unit 126c.

When the random number mask unit 116c uses a shared key encryption algorithm, addition or multiplication instead of exclusive OR, the random number mask removal unit 125c includes a shared key decryption algorithm corresponding to the shared key encryption algorithm, Subtraction or division may be used.
(4) Second function unit 126c
The second function unit 126c has an algorithm based on the same function G as the function of the first function unit 113c.

The second function unit 126c receives the decrypted random number s ′ from the random number mask removing unit 125c, and generates a function value G (s ′) of the received decrypted random number s ′. Next, similarly to the first function unit 113c, a verification value a ″, a shared key K ′, and a random value u ′ are generated from the function value G (s ′) and shared with the generated verification value a ″. The key K ′ and the random number u ′ are output to the comparison unit 127c.
(5) Comparison unit 127c
As shown in FIG. 10, the comparison unit 127c includes a comparison operation unit 127s and an encryption unit 127t.

The encryption unit 127t receives the public key polynomial h from the secret key input unit 121, receives the verification value a ″ and the random value u ′ from the second function unit 126c, and receives the received public key polynomial h and the random value u ′. , The verification value a ″ is encrypted in the same manner as the encryption unit 114c to generate the first re-ciphertext c1 ′, and the generated first re-ciphertext c1 ′ is output to the comparison operation unit 127s.
The comparison operation unit 127s receives the shared key K ′ from the second function unit 126c, receives the first ciphertext c1 from the decryption unit 123c, receives the first re-ciphertext c1 ′ from the encryption unit 127t, When the received first ciphertext c1 is compared with the received first reciphertext c1 ′, and it is determined that first ciphertext c1 = first reciphertext c1 ′, the received shared key K ′ is output to the common key decryption unit 128.

2.3 Operation of Content Distribution System 10c The overall operation of the content distribution system 10c according to the second embodiment will be described below using the processing system diagram shown in FIG.
The encryption device 110c receives the public key polynomial h of the decryption device 120c (step S101), generates a random number s (step S102), obtains a function value G (s), and verifies the verification value a from the function value G (s). A shared key K and a random value u are derived (step S121). Next, the encryption device 110c generates the first ciphertext c1 by encrypting the verification value a by the NTRU encryption using the public key polynomial h and the random value u (step S105), and generates a random number s based on the verification value a. Is encrypted to generate a second ciphertext c2 = s xor a (step S122). Next, the encryption device 110c transmits the first ciphertext c1 and the second ciphertext c2 to the decryption device 120c via the Internet 130 (step S106).

That is, the encryption device 110c performs the following processing and transmits the ciphertext C = (c1, c2) to the decryption device 120c.
(A) Generate a random number s.
(B) G (s) is generated, and a, K, and u are generated from G (s).
(C) The first cipher text c1 of the verification value a is generated using the public key polynomial h and the random value u.

(D) Generate c2 = s xor a.
Next, the encryption device 110c encrypts the plaintext mi (1 ≦ i ≦ n) received from the content server device 140 using the derived shared key K by the common key encryption method, and the ciphertext Ci (1 ≦ i ≦ n). n) is generated (step S107) and transmitted to the decryption device 120c via the Internet 130 (step S108).

  On the other hand, the decryption device 120c receives the private key polynomial f and the public key polynomial h of the decryption device 120c (step S151), and receives the first ciphertext c1 and the second ciphertext c2 from the encryption device 110c via the Internet 130. (Step S106) The first ciphertext c1 is decrypted using the secret key polynomial f to generate a decryption verification value a ′ (step S152). Next, the second ciphertext c2 is decrypted based on the decryption verification value a ′ to generate a decrypted random number s ′ = c2 xor a ′ (step S171). Next, the decryption device 120c derives the verification value a ″, the shared key K ′, and the random value u ′ from the function value G (s ′) of the decrypted random number s ′ (Step S172). Further, the verification value a ″ is encrypted to generate the first re-ciphertext c1 ′ (step S155). If c1 ′ = c1 (step S156), the shared key K ′ is output (step S157).

That is, the decryption device 120c performs the following process to derive the shared key K ′.
(A) Decrypt the first ciphertext c1 using the secret key polynomial f to generate a ′.
(B) Generate s ′ = c2 xor a ′.
(C) G (s ′) is generated, and a ″, K ′, and u ′ are generated from G (s ′).
(D) The first recipher text c1 ′ of a ″ is generated using the public key polynomial h and the random value u ′.

(E) Check whether c1 ′ = c1 holds. If it is established, the shared key K ′ is output.
Here, if the correct secret key polynomial f corresponding to the public key polynomial h used in the encryption device 110c is used in the decryption device 120c, the first ciphertext c1 is correctly decrypted and the decryption verification value a ′ = a is obtained. The decrypted random number s ′ = s generated from the second ciphertext c2 and a ′. Therefore, the verification value a ″ derived from G (s ′) = a, the shared key K ′ = K, and the random value u ′ = u. Thus, since a ″ = a and u ′ = u hold, c1 ′ = c1 holds, and the decryption device 120c can derive the same shared key K as the encryption device 110c.

  Next, the decryption device 120c receives the common key ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110c via the Internet 130 (step S108), and uses the derived shared key K ′ (= K). The received common key cipher text Ci (1 ≦ i ≦ n) is decrypted by the common key cryptosystem to generate a decrypted text mi ′ (1 ≦ i ≦ n) (step S158), and the decrypted text mi ′ (1 ≦ 1) is generated. i ≦ n) is output to the playback device 150.

Here, since the encryption key K used at the time of generating the common key ciphertext and the encryption key K ′ used at the time of generating the decrypted text are the same, the decryption device 120c determines that the correct decrypted text mi ′ = mi (1 ≦ i ≦ n). Can be obtained.
When a decryption error occurs, the decryption verification value a ′ and the verification value a are different, and therefore the decryption random number s ′ obtained from the second ciphertext c2 is different from s. Therefore, the random value u ′ and the shared key K ′ derived from G (s ′) are different from u and K, respectively. However, in this case, since a ′ and u ′ are different from a and u, respectively, the first re-ciphertext c1 ′ is different from the first ciphertext c1, and thus the decryption device 120c does not output the shared key K ′.

2.4 Effects in Embodiment 2 In the conventional RSA-KEM algorithm, the element s that cannot be derived from the ciphertext C without knowing the secret key is input to the hash function G to derive the shared key K. However, if an attempt is made to deliver a shared key by applying the RSA-KEM algorithm, which is a key encapsulation mechanism, using NTRU encryption, a decryption error may occur. In some cases, the shared key K ′ that cannot be derived and therefore incorrect is derived.

  However, the content distribution system, the encryption device, and the decryption device of the second embodiment generate the verification value a and the random value u in addition to the shared key from the hash function value G (s) of the random number s, and the decryption device is disturbed. The first re-ciphertext c1 ′ is generated by re-encrypting the decryption verification value a ′ using the numerical value u and the public key polynomial h, and the first re-ciphertext c1 ′ is not the same value as the first ciphertext c1. Since the shared key K is not output, it is possible to prevent different keys from being derived between the encryption device and the decryption device when a decryption error occurs.

Further, the method according to the present invention can theoretically prove its safety by a method similar to the proof method described in Non-Patent Document 3.
2.5 Modifications Embodiment 2 described above is an example of the implementation of the present invention, and the present invention is not limited to this embodiment at all, and various aspects can be made without departing from the scope of the present invention. Can be implemented. Of course, modifications similar to those in the first embodiment can be made, but the following cases are also included in the present invention.

(1) The conversion from the verification value a to the verification value polynomial ap may be performed by another conversion method. For example, the value of each bit of the bit string and the coefficient of each term of the polynomial may be converted using a function that has a one-to-one correspondence, or the value of each bit of the bit string and the coefficient of each term of the polynomial May be converted using a function value table stored in a one-to-one correspondence.
Further, the conversion from the random value u to the random number polynomial r may be performed by another conversion method. For example, r is uniquely obtained from u, the coefficient of the d-dimensional term is “1”, the coefficient of the d-dimensional term is “one”, and the coefficient of the other-dimensional term is “0”. If so, other conversion methods may be used. For example, the random value u may be converted using a function corresponding to a polynomial or a function value table.

  (2) The public key encryption used in the encryption unit 114c and the decryption unit 123c is the encryption unit 114c that encrypts the verification value a using the public key and the random value u to generate a first ciphertext c1. The decryption unit 123c only needs to be able to decrypt the first ciphertext c1 with the secret key and generate a decryption verification value a ′ equal to the verification value a. Accordingly, the public key encryption used in the encryption unit 114c and the decryption unit 123c may be any encryption as long as it is a public key encryption using a random number other than the NTRU encryption.

For example, in the case of ElGamal encryption, h and f are respectively used as public and private keys of ElGamal encryption, and in the encryption unit 114c, a is encrypted using h and a random value u to generate c1, and the decryption unit 123c In this case, c1 may be decoded using f to generate a ′.
(3) The random value u may be generated by the first function unit 113c and the second function unit 126c as long as the same value can be obtained by the encryption device 110c and the decryption device 120c.

For example, for an arbitrary function Func, the same value may be obtained by the encryption device 110c and the decryption device 120c as u = Func (s). That is,
Generate G (s) and generate a and K from G (s).
Generate Func (s) and set u = Func (s).
It is good.

(4) Furthermore, for the random value u, it is only necessary that the same value is obtained by the encryption device 110c and the decryption device 120c in addition to being generated by the first function unit 113c and the second function unit 126c. 110c may directly transmit the random value u to the decryption device 120c.
That is, as described below, the encryption device 110c may transmit the ciphertext C and the random number value u to the decryption device 120b. Further, the random value u may be encrypted and transmitted.

Generate G (s) and generate a and K from G (s).
The encryption device 110c separately transmits the random value u to 120b.
(5) Furthermore, for the random value u, it is only necessary to obtain the same value in the encryption device 110c and the decryption device 120c. The remaining partial information of the random number u may be directly transmitted from the encryption device 110c to the decryption device 120c.

For example, as described below, the encryption device 110c may transmit the ciphertext C and the random value u2 to the decryption device 120c. Further, the encryption device 110c may encrypt the random value u2 and transmit it.
Generate G (s) and generate a, K, u1 from G (s).
The encryption device 110c separately transmits the random value u2 to the decryption device 120c.

The encryption device 110c generates a random value u = u1 xor u2.
(6) The decryption device 120c checks whether the first ciphertext c1 is the ciphertext of the verification value a ″ obtained by the second function unit 126c, and when c1 is the ciphertext of a ″, the shared key Although the common key ciphertext Ci is decrypted using K ′, it may be checked whether the first ciphertext c1 is the ciphertext of the decryption verification value a ′.

  (7) The decryption apparatus 120c checks whether the first ciphertext c1 is the ciphertext of the verification value a ″ obtained by the second function unit 126c, and when c1 is the ciphertext of a ″, the shared key The common key ciphertext Ci is decrypted using K ′. As shown in step S156 of the processing system diagram of FIG. 12, the comparison unit 127c uses the value of a ′ decrypted by the decryption unit 123c and the second value. It may be checked whether the values of a ″ generated by the function unit 126c are equal.

  (8) In order to prevent different keys from being derived between the encryption device 110c and the decryption device 120c due to the occurrence of a decryption error, it is verified whether or not the first re-ciphertext c1 ′ has the same value as the first ciphertext c1. Then, instead of outputting the shared key K ′, the cryptographic device 110c generates a hash function value for any one or more of the random number s, the verification value a, the random value u, and the shared key K, and the generated hash function value Is transmitted to the decryption device 120c, and the decryption device 120c verifies the hash function value to determine whether or not to output the shared key K ′, and is disclosed in Patent Document 1 in order to increase security. The method that is used may be used. That is, the modification (8) of the first embodiment may be applied.

3. Summary of Embodiments 1 and 2 As described above, the present invention provides shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance. A shared key generation device that outputs, a secret number data generation unit that generates secret number data; a shared key derivation unit that converts the secret number data into random number data and the shared key data based on a predetermined process; A first encryption unit configured to encrypt the secret number data based on the public key data and the random number data to generate encrypted shared key data.

  Further, the present invention is a shared key generation device that outputs shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance, and generates secret number data A secret number data generation unit, a shared key derivation unit that converts the secret number data into verification value data, random number data, and the shared key data based on a predetermined process, the verification value data as the public key data, and the A first encryption unit for encrypting based on random number data to generate first encrypted preliminary data; and a first encryption unit for generating second encrypted preliminary data by encrypting the secret number data based on the verification value data. 2, and the encrypted shared key data includes the first encryption preliminary data and the second encryption preliminary data.

Here, the second encryption unit may generate the second encryption preliminary data by performing an exclusive OR operation on the secret number data and the verification value data.
Here, the second encryption unit may generate the second encryption preliminary data by encrypting the secret number data by a common key encryption method using the verification value data as an encryption key.

Here, the second encryption unit may generate the second encryption preliminary data by adding the verification value data to the secret number data.
Here, the second encryption unit may generate the second encrypted preliminary data by multiplying the secret number data by the verification value data.
Here, the encrypted shared key data may be bit concatenated data of the first encrypted preliminary data and the second encrypted preliminary data.

Here, the first encryption unit may generate the encrypted shared key data by encrypting with the NTRU encryption method.
Here, the first encryption unit may generate the first encryption preliminary data by performing encryption using the NTRU encryption method.
Here, the secret number data may be a randomly generated random number.

Here, the shared key derivation unit may use a one-way hash function as the predetermined process.
Further, the present invention provides a shared key restoration device that decrypts encrypted shared key data and outputs shared key data based on secret key data and public key data given in advance, wherein the encrypted shared key data A first decryption unit that decrypts the secret number data based on the secret key data to generate secret number data, and a shared key derivation unit that converts the secret number data into random number data and the shared key data based on a predetermined process And a third encryption unit that encrypts the secret number data based on the public key data and the random number data to generate re-encrypted shared key data, and the encrypted shared key data and the re-encrypted data If the shared shared key data match, the shared key data is output.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate verification value data; and the second encryption preliminary data A second decryption unit that decrypts the secret number data based on the verification value data to generate secret number data, and converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process And a third encryption unit that encrypts the verification value verification data based on the public key data and the random number data to generate third encryption preliminary data. Encryption spare data When the third encryption preliminary data matches, we output the shared key data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate verification value data; and the second encryption preliminary data A second decryption unit that decrypts the secret number data based on the verification value data to generate secret number data, and converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process A shared key derivation unit, and a third encryption unit that encrypts the verification value data based on the public key data and the random number data to generate third encryption preliminary data. Preliminary data and previous If the third encryption preliminary data matches, it outputs the shared key data.

Here, the second decryption unit may generate the secret number data by performing an exclusive OR operation on the second encryption preliminary data and the verification value data.
Here, the second decryption unit may decrypt the second encrypted preliminary data by a common key encryption method using the verification value data as an encryption key to generate the secret number data.

Here, the second decryption unit may generate the secret number data by subtracting the verification value data from the second encrypted preliminary data.
Here, the second encryption unit may generate the secret number data second secret number data by dividing the second encryption preliminary data by the verification value data.
Here, the first decryption unit may generate the shared key data by decrypting using the NTRU encryption method.

Here, the first decryption unit may generate the verification value data by decrypting using the NTRU encryption method.
Here, the shared key derivation unit may use a one-way hash function as the predetermined process.
Further, the present invention is an encryption device that generates ciphertext data obtained by encrypting plaintext data based on public key data given in advance, and includes a secret number data generation unit that generates secret number data, and the secret number A shared key derivation unit that converts data into random number data and shared key data based on a predetermined process, and generates the first encrypted preliminary data by encrypting the secret number data based on the public key data and the random number data And a second encryption unit that encrypts the plaintext data based on the shared key data to generate second encrypted preliminary data, and the ciphertext data includes: 1 encryption preliminary data and the second encryption preliminary data.

  Further, the present invention decrypts ciphertext data composed of the first encryption preliminary data and the second encryption preliminary data based on the pre-given secret key data and public key data, and outputs the decrypted text data A decryption device for decrypting the first encryption preliminary data based on the secret key data to generate secret number data; and the secret number data based on a predetermined process. A shared key derivation unit that converts random number data and shared key data; a third encryption unit that encrypts the secret number data based on the public key data and the random number data to generate third encrypted preliminary data; A decrypting unit that decrypts the second encrypted preliminary data based on the shared key and generates the decrypted text data when the first encrypted preliminary data and the third encrypted preliminary data match. And with .

  The present invention also provides an encryption device that generates ciphertext data obtained by encrypting plaintext data based on public key data given in advance, and ciphertext data based on secret key data and public key data given in advance. An encryption system including a decryption device that decrypts and outputs decrypted text data. The encryption device includes a secret number data generation unit that generates secret number data, a shared key derivation unit that converts the secret number data into random number data and shared key data based on a predetermined process, and the secret number data A first encryption unit for generating first encrypted preliminary data by encrypting based on the public key data and the random number data; and a second encrypted preliminary data by encrypting the plaintext data based on the shared key data. And the ciphertext data is composed of the first encrypted preliminary data, the second encrypted preliminary data, and the third encrypted preliminary data. The decryption device includes: a first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate secret number data; and the random number data based on a predetermined process. And a shared key deriving unit for converting the shared key data, and a third encryption unit that encrypts the secret number data based on the public key data and the random number data to generate third encrypted preliminary data. A decryption unit for decrypting the second encrypted preliminary data based on the shared key and generating the decrypted text data when the first encrypted preliminary data and the third encrypted preliminary data match. Prepare.

  As described above, the present invention has been made in view of the problems in the conventional system. By configuring a new key encapsulation mechanism to which NTRU encryption can be applied in an encryption system, an encryption device and a decryption device are provided. Different keys can be prevented from being derived from each other, and reliable encrypted communication from the transmitting device to the receiving device using the key derived by the key encapsulation mechanism can be performed.

As described above, it is possible to provide an encryption system that could not be achieved by the prior art, and its value is great.
4). Embodiment 3
A content distribution system 10d (not shown) as still another embodiment according to the present invention will be described.

The content distribution system 10d is a system obtained by modifying the content distribution system 10. Here, the content distribution system 10d will be described in detail with a focus on differences from the content distribution system 10.
4.1 Configuration of Content Distribution System 10d The content distribution system 10d has the same configuration as the content distribution system 10, and includes an encryption device 110d and a decryption device 120d instead of the encryption device 110 and the decryption device 120. Yes. Since other configurations are the same as those in the content distribution system 10, the description thereof is omitted.

The content distribution system 10d is an encryption communication system that performs encryption communication by performing key distribution using a key encapsulation mechanism using NTRU encryption, and the encryption device 110d and the decryption device 120d are connected via the Internet 130. Yes.
4.2 Configuration of Encryption Device 110d As shown in FIG. 13, the encryption device 110d includes a public key input unit 111d, a random number generation unit 112d, a first function unit 113d, an encryption unit 114d, a second function unit 115d, a random number mask. Unit 116d, first transmission unit 117d, common key encryption unit 118, and second transmission unit 119.

The encryption device 110d is a computer system similar to the encryption device 110, and the encryption device 110d achieves its functions when the microprocessor operates according to the computer program.
(1) Public key input unit 111d
The public key input unit 111d reads the public key polynomial h of the decryption device 120 from the memory card 160, and outputs the read public key polynomial h to the encryption unit 114d.

(2) Random number generator 112d
The random number generation unit 112d generates a random number s as a seed value for generating the shared key K, and outputs the generated random number s to the first function unit 113 and the random number mask unit 116.
(3) First function unit 113d
The first function unit 113d receives the random number s from the random number generation unit 112d, generates a function value G (s) of the received random number s, and generates a verification value a and a shared key K from the function value G (s). Here, the function G is a one-way function hash function having an output length of 2k bits, and the first function unit 113d uses the upper k bits of G (s) as the verification value a, and the G (s) Let the lower k bits be the shared key K.

Next, the first function unit 113d outputs the generated verification value a to the encryption unit 114d and the second function unit 115d, and outputs the generated shared key K to the common key encryption unit 118.
(4) Encryption unit 114d
The encryption unit 114d receives the public key polynomial h from the public key input unit 111d, receives the verification value a from the first function unit 113d, and uses the received public key polynomial h to verify the verification value a as follows. The first ciphertext c1 is generated. Here, the generated first ciphertext c1 is a ciphertext based on the NTRU cipher.

  The encryption unit 114d is configured such that each coefficient of d terms is “1”, each coefficient of another d term is “−1”, and each of the other terms for the parameter d of the NTRU encryption. A random number polynomial r having a coefficient “0” is randomly generated. Next, in order for the verification value a to be applicable to the cryptographic algorithm E of the NTRU cryptosystem, the value of each digit of the N-digit bit string when the verification value a is expressed in binary is used as the coefficient of each term of the verification value polynomial ap. A verification value polynomial ap is generated so as to correspond. For example, the value of the lower-order b bit of the verification value a is set as the coefficient of the term X ^ b of the verification value polynomial ap. Thus, the verification value a is converted into the verification value polynomial ap. Specifically, when the verification value a = 110010 (bit representation), the verification value polynomial ap = X ^ 5 + X ^ 2 is converted. Next, the cipher algorithm E is applied to the verification value polynomial ap using the random number polynomial r using the public key polynomial h, and the first ciphertext c1 = E (ap, r, h), which is a ciphertext polynomial. Is generated.

Next, the encryption unit 114d outputs the generated first ciphertext c1 to the second function unit 115d and the first transmission unit 117d.
(5) Second function unit 115d
The second function unit 115d receives the verification value a from the first function unit 113d, receives the first ciphertext c1 from the encryption unit 114d, and performs a function of the verification value a and the first ciphertext c1 as shown below. A value H (a, c1) is generated.

Here, the function H is a hash function and is a kind of one-way function.
Since the first ciphertext c1 is an NTRU ciphertext and is expressed by a polynomial, the second function unit 115d has N digits when the coefficient of each term of the first ciphertext c1 is expressed in binary. The first ciphertext bit string c1 ′ is generated so as to correspond to the value of each digit of the first ciphertext bit string c1 ′. For example, the coefficient of the b-dimensional term X ^ b of the first ciphertext c1 is set as the value of the lower-order b bit of the first ciphertext bit string c1 ′. Thus, the first ciphertext c1 is converted into the first ciphertext bit string c1 ′. Specifically, when the first ciphertext c1 = X ^ 5 + X ^ 2, the first ciphertext bit string c1 ′ is converted to 10010 (bit representation).

Next, the second function unit 115d inputs the bit combination a || c1 ′ between the verification value a and the first ciphertext bit string c1 ′ to the hash function H, and the function value H (a, c1) = H ( a || c1 ′). Here, “||” is an operator indicating bit combination.
Next, the second function unit 115d outputs the generated function value H (a, c1) to the random number mask unit 116d.

(6) Random number mask part 116d
The random number mask unit 116d receives the random number s from the random number generation unit 112d and receives the function value H (a, c1) from the second function unit 115d. Next, the second ciphertext c2 = s xor H (a, c1) is generated, and the generated second ciphertext c2 is output to the first transmission unit 117d.
Note that the random number mask unit 116d may use a shared key encryption algorithm, addition, or multiplication instead of the exclusive OR xor.

(7) First transmission unit 117d
The first transmission unit 117d receives the first ciphertext c1 from the encryption unit 114d, receives the second ciphertext c2 from the random number mask unit 116d, and transmits the received first ciphertext c1 and second ciphertext c2 to the Internet. The data is transmitted to the decoding device 120d via 130.
(8) Common key encryption unit 118 and second transmission unit 119
The common key encryption unit 118 and the second transmission unit 119 are the same as the common key encryption unit 118 and the second transmission unit 119 included in the encryption device 110, respectively, except for the following points.

The common key encryption unit 118 receives the shared key K from the first function unit 113d.
4.3 Configuration of Decryption Device 120d As shown in FIG. 14, the decryption device 120d includes a secret key input unit 121d, a first reception unit 122d, a decryption unit 123d, a third function unit 124d, a random number mask removal unit 125d, It includes a four-function unit 126d, a comparison unit 127d, a common key decryption unit 128, and a second reception unit 129.

The decoding device 120d is a computer system similar to the decoding device 120, and the decoding device 120d achieves its functions when the microprocessor operates according to the computer program.
The common key decryption unit 128 and the second reception unit 129 are the same as the common key decryption unit 128 and the second reception unit 129 included in the decryption device 120, respectively, and thus description thereof is omitted here.

(1) Private key input unit 121d
The secret key input unit 121d reads the secret key polynomial f of the decryption device 120d from the memory card 170, and outputs the read secret key polynomial f to the decryption unit 123d.
(2) First receiving unit 122d
The first reception unit 122d receives the first ciphertext c1 and the second ciphertext c2 from the encryption device 110d via the Internet 130, and the received first ciphertext c1 is decrypted by the decryption unit 123d and the third function unit 124d. And the received second ciphertext c2 is output to the random number mask removing unit 125d.

When the random number mask unit 116d uses a shared key encryption algorithm, addition or multiplication instead of exclusive OR, the random number mask removal unit 125d includes a shared key decryption algorithm corresponding to the shared key encryption algorithm, Subtraction or division may be used.
(3) Decoding unit 123d
The decryption unit 123d receives the secret key polynomial f from the secret key input unit 121d, receives the first ciphertext c1 from the first reception unit 122d, and uses the secret key polynomial f to The ciphertext c1 is decrypted to generate a decryption verification value a ′. Here, the decryption verification value a ′ is a decrypted text by NTRU encryption.

  The decryption unit 123d performs the decryption algorithm D on the first ciphertext c1 using the secret key polynomial f, and generates a decryption verification value polynomial ap ′ = D (c1, f). Next, since the decryption verification value polynomial ap ′ is a decrypted text of the NTRU cipher and is represented by a polynomial, the decryption unit 123d determines that each coefficient of the decryption verification value polynomial ap ′ sets the decryption verification value a ′ to 2 A decryption verification value a ′ is generated so as to correspond to the number of each digit of the N-digit bit string when expressed in decimal. For example, the coefficient of the b-dimensional term X ^ b of the decryption verification value polynomial ap ′ is set as the value of the lower b bits of the decryption verification value a ′. Thus, the decryption verification value polynomial ap ′ is converted into the decryption verification value a ′. Specifically, in the case of the decryption verification value polynomial ap ′ = X ^ 5 + X ^ 2, the decryption verification value a ′ is converted to 10010 (bit representation).

Next, the decryption unit 123d outputs the generated decryption verification value a ′ to the third function unit 124d and the comparison unit 127d.
(4) Third function part 124d
The third function unit 124d has the same function H algorithm as the function of the second function unit 115d.

The third function unit 124d receives the first ciphertext c1 from the first reception unit 122d, and receives the decryption verification value a ′ from the decryption unit 123d. Next, similarly to the second function unit 115d, a function value H (a ′, c1) of the verification value a ′ and the first ciphertext c1 is generated, and the generated function value H (a ′, c1) is generated. This is output to the random number mask removing unit 125d.
(5) Random number mask removal unit 125d
The random number mask removing unit 125d receives the second ciphertext c2 from the first receiving unit 122d, receives the hash function value H (a ′, c1) from the third function unit 124d, and then decrypts the random number s ′ = c2 xor H (a ′, c1) is generated, and the generated decrypted random number s is output to the fourth function unit 126d.

(6) Fourth function unit 126d
The fourth function unit 126d has the same function G algorithm as the function of the first function unit 113d.
The fourth function unit 126d receives the decrypted random number s ′ from the random number mask removing unit 125d, and generates a hash function value G (s ′) of the decrypted random number s ′. Next, similarly to the first function unit 113d, a verification value a ″ and a shared key K ′ are generated from the function value G (s ′), and the generated verification value a ″ and the shared key K ′ are generated. The data is output to the comparison unit 127d.

(7) Comparison unit 127d
The comparison unit 127d receives the decryption verification value a ′ from the decryption unit 123d, receives the verification value a ″ and the shared key K ′ from the fourth function unit 126d, and then decrypts the verification value a ′ and the verification value a. It is checked whether or not ″ is equal. If the decryption verification value a ′ and the verification value a ″ are equal, the shared key K ′ is output to the common key decryption unit 128.

(8) Common key decryption unit 128 and second reception unit 129
The common key decryption unit 128 receives the shared key K ′ from the comparison unit 127d.
Since the common key decryption unit 128 is the same as the common key decryption unit 128 included in the decryption device 120 with respect to other points, description thereof is omitted here.
In addition, the second receiving unit 129 is the same as the second receiving unit 129 included in the decoding device 120, and thus description thereof is omitted here.

4.4 Operation of Content Distribution System 10d The operation of the content distribution system 10d will be described with reference to the flowchart shown in FIG. 15 and the processing system diagram shown in FIG.
The public key input unit 111d receives the public key polynomial h of the decryption device 120d from the memory card 160, and outputs the public key polynomial h to the encryption unit 114d (step S201).

Next, the random number generation unit 112d generates a random number s and outputs the random number s to the first function unit 113d and the random number mask unit 116d (step S202).
Next, the first function unit 113d receives the random number s from the random number generation unit 112d and generates a function value G (s) of the random number s (step S203). Then, the first function unit 113d generates a verification value a and a shared key K from the function value G (s), and outputs the verification value a to the encryption unit 114d and the second function unit 115d. Is output to the common key encryption unit 118 (step S204).

Next, the encryption unit 114d receives the public key polynomial h from the public key input unit 111d, and receives the verification value a from the first function unit 113d. Then, the encryption unit 114d generates the first ciphertext c1 with the verification value a using the public key polynomial h, and outputs the first ciphertext c1 to the second function unit 115d and the first transmission unit 117d ( Step S205).
Next, the second function unit 115d receives the verification value a from the first function unit 113d, receives the first ciphertext c1 from the encryption unit 114d, and receives the function value H () of the verification value a and the first ciphertext c1. a, c1) is generated, and the function value H (a, c1) is output to the random number mask unit 116 (step S206).

Next, the random number mask unit 116d receives the random number s from the random number generation unit 112d, receives the function value H (a, c1) from the second function unit 115d, and the random number mask unit 116d receives the second ciphertext c2 = s xor. H (a, c1) is generated, and the second ciphertext c2 is output to the first transmitter 117d (step S207).
Next, the first transmission unit 117d receives the first ciphertext c1 from the encryption unit 114d, receives the second ciphertext c2 from the random number mask unit 116d, and transmits the first ciphertext c1 and the second ciphertext c2 to the Internet. It transmits to the decoding device 120d via 130 (step S208).

  Next, the common key encryption unit 118 receives a plurality of plaintext mi (1 ≦ i ≦ n) from the content server device 140, receives the shared key K from the first function unit 113d, and uses the shared key K to read the plaintext mi. (1 ≦ i ≦ n) is subjected to the common key encryption algorithm Sym to generate a common key ciphertext Ci = Sym (mi, K) (1 ≦ i ≦ n), and the common key ciphertext Ci (1 ≦ i ≦ n) n) is output to the second transmitter 119 (step S209).

Next, the second transmission unit 119 receives the common key ciphertext Ci (1 ≦ i ≦ n) from the common key encryption unit 118, transmits it to the decryption device 120d via the Internet 130 (step S210), and ends the processing. To do.
On the other hand, the secret key input unit 121d receives the secret key polynomial f of the decryption device 120d from the memory card 170, and outputs the secret key polynomial f to the decryption unit 123 (step S251).

Next, the first reception unit 122d receives the first ciphertext c1 and the second ciphertext c2 from the encryption device 110d via the Internet 130, and the first ciphertext c1 is decrypted by the decryption unit 123d and the third function unit 124d. And the second ciphertext c2 is output to the random number mask removing unit 125d (step S208).
Next, the decryption unit 123d receives the secret key polynomial f from the secret key input unit 121, receives the first ciphertext c1 from the first reception unit 122d, and then uses the secret key polynomial f to The sentence c1 is decrypted to generate a decryption verification value a ′, and the decryption verification value a ′ is output to the third function unit 124d and the comparison unit 127d (step S252).

Next, the third function unit 124d receives the first ciphertext c1 from the first reception unit 122d, receives the decryption verification value a ′ from the decryption unit 123d, and then performs the same process as the second function unit 115d. The verification value a ′ and the function value H (a ′, c1) of the first ciphertext c1 are generated, and the function value H (a ′, c1) is output to the random number mask removal unit 125d (step S253).
Next, the random number mask removing unit 125d receives the second ciphertext c2 from the first receiving unit 122d, receives the hash function value H (a ′, c1) from the third function unit 124d, and then receives the decrypted random number s ′. = C2 xor H (a ′, c1) is generated, and the decrypted random number s is output to the fourth function unit 126d (step S254).

Next, the fourth function unit 126d receives the decrypted random number s ′ from the random number mask removing unit 125, generates the hash function value G (s ′) of the decrypted random number s ′ (step S255), and the first function unit 113d Similarly, a verification value a ″ and a shared key K ′ are generated from the function value G (s ′), and the verification value a ″ and the shared key K ′ are output to the comparison unit 127d (step S256). .
Next, the comparison unit 127d receives the decryption verification value a ′ from the decryption unit 123, receives the verification value a ″ and the shared key K ′ from the fourth function unit 126d, and receives the decryption verification value a ′ and the verification value a. Whether or not '' is equal is checked. If not equal (step S257), the process is terminated.

If the decryption verification value a ′ and the verification value a ″ are equal (step S257), the comparison unit 127d outputs the shared key K ′ to the common key decryption unit 128 (step S258).
Next, the second receiving unit 129 receives the ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110d via the Internet 130, and outputs it to the common key decryption unit 128 (step S210).
Next, the common key decryption unit 128 receives the shared key K ′ from the comparison unit 127d, receives the common key ciphertext Ci (1 ≦ i ≦ n) from the second reception unit 129, and uses the shared key K ′. The common key ciphertext Ci (1 ≦ i ≦ n) is subjected to the common key encryption algorithm Sym to generate a decrypted text mi ′ = Sym (Ci, K) (1 ≦ i ≦ n), and the decrypted text mi ′ (1 ≦ i ≦ n) is output to the outside (step S259), and the process is terminated.

4.5 Operation Verification of Content Distribution System 10d The overall operation of the content distribution system 10d will be described below.
The encryption device 110d receives the public key polynomial h of the decryption device 120d, generates a random number s, and derives the verification value a and the shared key K from the function value G (s). Next, the encryption device 110d generates the first ciphertext c1 by encrypting the verification value a with the NTRU cipher using the public key polynomial h, and generates a function value H (a, a from the verification value a and the first ciphertext c1. c1) is generated, and the second ciphertext c2 = s xor H (a, c1) is generated from the random number s and the function value H (a, c1). Next, the encryption device 110d transmits the first ciphertext c1 and the second ciphertext c2 to the decryption device 120d via the Internet 130.

That is, the encryption device 110d performs the following processing and transmits the ciphertext C = (c1, c2) to the decryption device 120d.
Generate a random number s.
Generate G (s) and generate a and K from G (s).
Generate the first ciphertext c1 with the verification value a using the public key polynomial h.

Generate c2 = s xor H (a, c1).
Output the shared key K and the ciphertext C = (c1, c2).
Next, the encryption device 110d uses the derived shared key K to encrypt the plaintext mi (1 ≦ i ≦ n) input from the content server device 140 with the common key encryption, and the ciphertext Ci (1 ≦ i ≦ n). n) is generated and transmitted to the decryption device 120d via the Internet 130.

  On the other hand, the decryption device 120d receives the first ciphertext c1 and the second ciphertext c2 from the encryption device 110d via the Internet 130, using the secret key polynomial f of the decryption device 120d as input, and receives the first ciphertext c1. Decryption is performed using the secret key polynomial f to generate a decryption verification value a ′. A function value H (a ′, c1) is generated from the decryption verification value a ′ and the first ciphertext c1, and a decryption random number s ′ = c2 xor H (from the second ciphertext c2 and the function value H (a ′, c1). a ′, c1) is generated. Next, the decryption device 120d derives the verification value a ″ and the shared key K ′ from the function value G (s ′) of the decrypted random number s ′, and if the verification value a ″ = a ′, the shared key K ′. Is output.

That is, the decryption device 120d performs the following process to derive the shared key K ′.
Decrypt the first ciphertext c1 using the secret key polynomial f to generate a ′.
Generate s ′ = c2 xor H (a ′, c1).
Generate G (s ′) and generate a ″, K ′ from G (s ′).
Check whether a ″ = a ′ holds. If it is established, the shared key K ′ is output.

  Here, if the correct private key polynomial f corresponding to the public key polynomial h used in the encryption device 110d is used in the decryption device 120d, the first ciphertext c1 is correctly decrypted and the decryption verification value a ′ = a is obtained. The decrypted random number s ′ = s generated from the second ciphertext c2 and H (a ′, c1). Therefore, the verification value a ″ derived from G (s ′) = a, and the shared key K ′ = K. Since a ″ = a ′ holds, the decryption device 120d can derive the same shared key K as the encryption device 110d.

Next, the decryption device 120d receives the common key ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110d via the Internet 130 using the derived shared key K ′ (= K) and receives the received common key. The ciphertext Ci (1 ≦ i ≦ n) is decrypted with the common key cipher to generate a decrypted text mi ′ (1 ≦ i ≦ n) and output to the playback device 150.
Here, since the encryption key K used at the time of generating the common key ciphertext and the encryption key K ′ used at the time of generating the decrypted text are the same, the decrypting device 120d correctly obtains mi ′ = mi (1 ≦ i ≦ n). Can do.

4.6 Effects in Embodiment 3 In the conventional PSEC-KEM algorithm, a * P and a * W are used as the input of the hash function H, and a * W is calculated from a * P without using a secret key. Finally, the shared key K is derived using the Diffie-Hellman problem, which makes it difficult to derive the shared key K unless the secret key is known. Therefore, the NTRU cipher and other public key ciphers that do not use the Diffie-Hellman problem have no equivalent to the Diffie-Hellman problem, a * P, a * W, and the PSEC-KEM algorithm cannot be applied. There is a point.

However, since the content distribution system, encryption apparatus, and decryption apparatus of the present invention use the hash function H as the verification value a and its ciphertext c1, applying the PSEC-KEM algorithm, NTRU encryption and other public keys Encryption can be used.
In NTRU cryptography, a plaintext is encrypted by using a public key to generate a ciphertext, and a decrypted text is generated by decrypting a ciphertext by using a regular secret key. Different cases occur (for example, see Non-Patent Document 2). When such a decryption error occurs, the decryption device obtains an incorrect decryption verification value a ′, but since the verification value a ″ obtained from G (s ′) is not equal to a ′, the shared key Do not output K '. Therefore, even if a decryption error occurs, it is possible to prevent the wrong key from being shared between the encryption device and the decryption device.

In addition, since the decryption device does not perform the process of generating the ciphertext again, the amount of calculation can be reduced as compared with the prior art.
As a result, a key encapsulation mechanism can be configured using NTRU encryption, and key distribution can be performed between the encryption device and the decryption device using NTRU encryption.
Further, the method according to the present invention can theoretically prove its safety by a method similar to the proof method described in Non-Patent Document 3.

4.7 Modifications The embodiment described above is an example of the implementation of the present invention, and the present invention is not limited to this embodiment, and can be variously modified without departing from the scope of the present invention. It can be implemented. The following cases are also included in the present invention.
(1) It is not limited to the parameter N = 167 of the NTRU encryption used. The parameter N may take other values.

(2) The bit string / polynomial conversion method performed by the encryption unit 114d, the second function unit 115d, the decryption unit 123d, and the third function unit 124d is not limited to this method, and other conversion methods may be used.
For example, the conversion may be performed using a function or a table of function values in which a bit string and a polynomial correspond one-to-one.

Further, for example, the conversion may be performed using the conversion method described in the modification (1) of the second embodiment.
(3) In the public key cryptosystem used in the encryption unit 114d and the decryption unit 123d, the encryption unit 114d encrypts the verification value a with the public key to generate the first ciphertext c1, and the decryption unit 123d The decryption verification value a ′ equal to the verification value a may be generated by decrypting the first ciphertext c1 with the secret key.

Accordingly, any public key cryptography other than the NTRU cipher can be used as the public key cryptography used in the encryption unit 114d and the decryption unit 123d.
For example, if RSA encryption is adopted, h and f are respectively used as public and private keys of RSA encryption, and the encryption unit 114d encrypts a using h to generate c1, and the decryption unit 123d , C1 may be decoded using f to generate a ′.

Further, for example, if ElGamal encryption is adopted, h and f are set as public and private keys of ElGamal encryption, respectively, and the encryption unit 114d generates a random number r and encrypts a using h and r, and c1 And the decoding unit 123d decodes c1 using f to generate a ′.
Since RSA encryption and ElGamal encryption are described in detail in Non-Patent Document 1, description thereof will be omitted here.

(4) The first function unit 113d uses the function value G (s) and the verification value a as well as the verification value a for the upper k bits of the function value G (s) and the shared key K for the lower k bits. Other methods may be used if the shared key K is derived.
(5) The second function unit 115d may use another method as long as the function value H (a, c1) is derived from the verification value a and the first ciphertext c1.

For example, a function value may be derived by inputting a # c1 to the function H for an arbitrary binary operation #. In the NTRU cipher, the first ciphertext c1 is a polynomial. Therefore, the first ciphertext c1 is converted into the first ciphertext bit string c1 ′, and a # c1 ′ is input to the function H to derive the function value. Also good.
(6) Furthermore, the second function unit 115d may use another method as long as the function value is derived using the verification value a.

For example, the second function unit 115d may output H (a) or may output the verification value a as it is. That is, in the encryption device 110d, the second ciphertext c2 may be derived as: • c2 = s xor H (a), or • c2 = s xor a.
In these cases, the third function unit 124d of the decoding device 120d respectively
・ H (a ') or ・ a'
Is output.

(7) The random number mask unit 116d derives the second ciphertext c2 from the random number s and the function value H (a, c1), and the random number mask removal unit 125d performs the second ciphertext c2 and the function value H (a, c1). Other methods may be used as long as the random number s can be derived from c1).
For example, the random number mask unit 116d converts the second ciphertext c2 into: c2 = s + H (a, c1), or c2 = s · H (a, c1)
May be derived as

5). Embodiment 4
A content distribution system 10e (not shown) as still another embodiment according to the present invention will be described.
The content distribution system 10e is a system that is a modification of the content distribution system 10d shown in the third embodiment, and the encryption device uses the function value G (s) in addition to the verification value a and the shared key K. Content distribution in which a numerical value u is generated, the verification value a is encrypted using the random value u, and the first ciphertext c1 is generated, and the determination method when the decryption device outputs the shared key K Different from the system 10d.

Here, the content distribution system 10e will be described in detail focusing on differences from the content distribution system 10d.
5.1 Configuration of Content Distribution System 10e The content distribution system 10e has the same configuration as the content distribution system 10d, and includes an encryption device 110e and a decryption device 120e instead of the encryption device 110d and the decryption device 120d. Yes. Other configurations are the same as those in the content distribution system 10d, and thus the description thereof is omitted.

The content distribution system 10e is a system that performs key distribution using NTRU encryption. The encryption device 110e and the decryption device 120e are connected via the Internet 130.
5.2 Configuration of Encryption Device 110e The encryption device 110e includes a public key input unit 111d, a random number generation unit 112d, a first function unit 113e, an encryption unit 114e, a second function unit 115d, a random number mask, as shown in FIG. Unit 116d, first transmission unit 117d, common key encryption unit 118, and second transmission unit 119.

  The public key input unit 111d, the random number generation unit 112d, the second function unit 115d, the random number mask unit 116d, the first transmission unit 117d, the common key encryption unit 118, and the second transmission unit 119 are constituent elements that constitute the encryption device 110d. Since they are the same, the description thereof will be omitted, and the configuration and operation of the first function unit 113e and the encryption unit 114e that are different from the components constituting the encryption device 110d will be described here.

(1) First function unit 113e
The first function unit 113e receives the random number s from the random number generation unit 112d and generates a function value G (s) of the received random number s. Next, a verification value a, a shared key K, and a random value u are generated from the generated function value G (s) as described below.
Here, the function G is a hash function having an output length of 3 k bits, and the first function unit 113e uses the upper k bits of G (s) as the verification value a and shares k bits in the middle of G (s). The key K is used, and the lower k bits of G (s) are the random value u.

Next, the first function unit 113e outputs the generated verification value a to the encryption unit 114e and the second function unit 115d, outputs the generated shared key K to the common key encryption unit 118, and generates the generated random value. u is output to the encryption unit 114e.
(2) Encryption unit 114e
The encryption unit 114e receives the public key polynomial h from the public key input unit 111d, and receives the verification value a and the random value u from the first function unit 113e. Next, as shown below, the first ciphertext c1 of the verification value a is generated using the public key polynomial h and the random value u. Here, the first ciphertext c1 is a ciphertext based on the NTRU cipher. The random value u is a blind value and is used to obscure the verification value a that is the object of encryption.

For the parameter d of the NTRU cipher, the encryption unit 114e is such that each coefficient of d terms is “1”, each coefficient of other d terms is “−1”, and each of the remaining terms A random number polynomial r having a coefficient of “0” is generated so as to be uniquely obtained from the random value u.
Specifically, for example, the encryption unit 114e sets the random value u as an initial value (random number seed) of the pseudo-random number sequence, and {0, 1,. . . , N−1} to generate non-overlapping 2d pseudorandom numbers, set the coefficient of the dimension term indicated by the first d pseudorandom numbers to “1”, and the dimension of the dimension indicated by the next d pseudorandom numbers The random coefficient r is generated by setting the coefficient of the term to “−1” and the coefficient of the remaining dimension to “0”.

Next, the encryption unit 114e generates the first ciphertext c1 = E (ap, r, h) using the generated random number polynomial r in the same manner as the encryption unit 114d.
Next, the encryption unit 114e outputs the generated first ciphertext c1 to the second function unit 115d and the first transmission unit 117d.
5.3 Configuration of Decryption Device 120e As shown in FIG. 18, the decryption device 120e includes a secret key input unit 121e, a decryption unit 123e, a third function unit 124d, a random number mask removal unit 125d, a fourth function unit 126e, and a comparison. Unit 127e, common key decryption unit 128, and second reception unit 129.

  Here, the third function unit 124d, the random number mask removal unit 125d, the common key decryption unit 128, and the second reception unit 129 are the same as the respective constituent elements included in the decryption device 120d, and thus the description thereof is omitted. The configuration and operation of the secret key input unit 121e, the decryption unit 123e, the fourth function unit 126e, and the second comparison unit 127e, which are different from the components included in the decryption device 120d, will be described.

(1) Private key input unit 121e
The secret key input unit 121e receives the secret key polynomial f and the public key polynomial h of the decryption device 120e from the memory card 170, outputs the secret key polynomial f to the decryption unit 123e, and outputs the public key polynomial h to the comparison unit 127e. Output.
(2) Decoding unit 123e
The decryption unit 123e receives the secret key polynomial f from the secret key input unit 121e, and receives the first ciphertext c1 from the first reception unit 122d. Next, using the secret key polynomial f, the first ciphertext c1 is decrypted to generate a decryption verification value a ′, the generated decryption verification value a ′ is output to the third function unit 124d, and the received first The ciphertext c1 is output to the comparison unit 127e.

(3) Fourth function unit 126e
The fourth function unit 126e has an algorithm based on the same function G as the function of the first function unit 113e.
The fourth function unit 126e receives the decrypted random number s ′ from the random number mask removing unit 125d, and generates a hash function value G (s ′) of the received decrypted random number s ′. Next, similarly to the first function unit 113e, a verification value a ″, a shared key K ′, and a random value u ′ are generated from the function value G (s ′), and the verification value a ″ and the shared key K are generated. 'And the random value u' are output to the comparison unit 127e.

(4) Comparison unit 127e
As shown in FIG. 18, the comparison unit 127e includes a comparison operation unit 127p and an encryption unit 127q.
The encryption unit 127q receives the public key polynomial h from the secret key input unit 121e, and receives the verification value a ″ and the random value u ′ from the fourth function unit 126e. Next, using the received public key polynomial h and the random value u ′, the received verification value a ″ is encrypted in the same manner as the encryption unit 114d to generate the first re-ciphertext c1 ′. The generated first re-ciphertext c1 ′ is output to the comparison operation unit 127p.

  The comparison operation unit 127p receives the first ciphertext c1 from the decryption unit 123b and receives the first re-ciphertext c1 'from the encryption unit 127q. Next, the received first ciphertext c1 and the first re-ciphertext c1 'are compared to determine whether c1' = c1. If c1 '= c1, the received shared key K' is output to the common key decryption unit 128. If c1 '= c1, the received shared key K' is not output.

5.4 Operation Verification of Content Distribution System 10e The overall operation of the content distribution system 10e will be described below with reference to the processing system diagram shown in FIG.
The encryption device 110e receives the public key polynomial h of the decryption device 120e (step S201), generates a random number s (step S202), generates a function value G (s) (step S203), and functions value G (s) The verification value a, the shared key K, and the random value u are derived from (step S204e). Next, the encryption device 110e encrypts the verification value a with the NTRU cipher using the public key polynomial h and the random value u to generate the first ciphertext c1 (step S205), and the verification value a and the first encryption A function value H (a, c1) is generated from the sentence c1 (step S206), and a second ciphertext c2 = s xor H (a, c1) is generated from the random number s and the function value H (a, c1) (step S206). S207). Next, the encryption device 110b transmits the first ciphertext c1 and the second ciphertext c2 to the decryption device 120e via the Internet 130 (step S208).

That is, the encryption device 110e performs the following processes (a) to (d), and transmits the ciphertext C = (c1, c2) to the decryption device 120e.
(A) Generate a random number s.
(B) Generate G (s) and generate a, K, u from G (s).
(C) The first cipher text c1 of the verification value a is generated using the public key polynomial h and the random value u.

(D) Generate c2 = s xor H (a, c1).
Next, using the derived shared key K, the encryption device 110e encrypts the plaintext mi (1 ≦ i ≦ n) input from the content server device 140 with the common key encryption, and the ciphertext Ci (1 ≦ i ≦ n). n) is generated (step S209) and transmitted to the decryption device 120e via the Internet 130 (step S210).

  On the other hand, the decryption device 120e receives the private key polynomial f and the public key polynomial h of the decryption device 120e (steps S251 and S251e), and the first ciphertext c1 and the second ciphertext c2 from the encryption device 110e via the Internet 130. (Step S208), the first ciphertext c1 is decrypted using the secret key polynomial f to generate a decryption verification value a ′ (step S252). Next, a function value H (a ′, c1) is generated from the decryption verification value a ′ and the first ciphertext c1 (step S253), and a decryption random number is derived from the second ciphertext c2 and the function value H (a ′, c1). s ′ = c2 xor H (a ′, c1) is generated (step S254). Next, the decryption device 120e generates a function value G (s ′) of the decrypted random number s ′ (step S255), and from the generated function value G (s ′), the verification value a ″, the shared key K ′, and the random number A numerical value u ′ is derived (step S256e). Next, the verification value a ″ is encrypted to generate the first re-ciphertext c1 ′ (step S261). If c1 ′ = c1 (step S257e), the shared key K ′ is output (step S258). .

That is, the decryption device 120e performs the following processes (a) to (e) to derive the shared key K ′.
(A) Decrypt the first ciphertext c1 using the secret key polynomial f to generate a ′.
(B) Generate s ′ = c2 xor H (a ′, c1).
(C) G (s ′) is generated, and a ″, K ′, u ′ are generated from G (s ′).

(D) A first recipher text c1 ′ of a ″ is generated using the public key polynomial h and the random value u ′.
(E) Check whether c1 ′ = c1 holds. If it is established, the shared key K ′ is output.
Here, if the correct private key polynomial f corresponding to the public key polynomial h used in the encryption device 110e is used in the decryption device 120e, the first ciphertext c1 is correctly decrypted and the decryption verification value a ′ = a is obtained. The decrypted random number s ′ = s generated from the second ciphertext c2 and H (a ′, c1). Therefore, the verification value a ″ derived from G (s ′) = a, the shared key K ′ = K, and the random value u ′ = u. Since a ″ = a and u ′ = u hold, c1 ′ = c1 holds, and the decryption device 120e can derive the same shared key K as the encryption device 110e.

  Next, the decryption device 120e receives the common key ciphertext Ci (1 ≦ i ≦ n) from the encryption device 110e via the Internet 130 using the derived shared key K ′ (= K) (step S210). The received common key cipher text Ci (1 ≦ i ≦ n) is decrypted with the common key cipher to generate a decrypted text mi ′ (1 ≦ i ≦ n) (step S259), and the generated decrypted text mi ′ (1 ≦ i ≦ n) is output to the playback device 150.

Here, since the encryption key K used when generating the common key ciphertext and the encryption key K ′ used when generating the decrypted text are the same, the decryption device 120e correctly obtains mi ′ = mi (1 ≦ i ≦ n). be able to.
5.5 Effect in Content Distribution System 10e In the conventional PSEC-KEM algorithm, a * P and a * W are used as the input of the hash function H, and a * W is calculated from a * P without using a secret key. Finally, the shared key K is derived using the Diffie-Hellman problem, which makes it difficult to derive the shared key K unless the secret key is known. Therefore, since there is no equivalent to a * P and a * W of the Diffie-Hellman problem in other public key ciphers that do not use the Diffie-Hellman problem, including the NTRU cipher, there is a problem that the PSEC-KEM algorithm cannot be applied. There is a point.

However, in the content distribution system, encryption device, and decryption device of the present invention, the input of the hash function H is the verification value a and its ciphertext c1, so that, as in the third embodiment, NTRU encryption or other public key encryption is used. Can be applied.
If a decryption error occurs, the decryption device obtains an incorrect decryption verification value a ′, but c1 ′ is not equal to c1, and therefore does not output the shared key K ′. Therefore, even if a decryption error occurs, it is possible to prevent the wrong key from being shared between the encryption device and the decryption device.

As a result, a key encapsulation mechanism can be configured using NTRU encryption, and key distribution can be performed between the encryption device and the decryption device using NTRU encryption.
Further, the method according to the present invention can theoretically prove its safety by a method similar to the proof method described in Non-Patent Document 3.
5.6 Modifications The embodiment described above is an example of the implementation of the present invention, and the present invention is not limited to this embodiment at all, and in various modes without departing from the gist thereof. It can be implemented. Of course, modifications similar to those of the third embodiment can be made, but the following cases are also included in the present invention.

(1) The conversion method from the random value u to the random number polynomial r performed by the encryption unit 114e is not limited to this method, and other conversion methods may be used as long as r is uniquely obtained from u. For example, the random value u may be converted using a function corresponding to a polynomial or a function value table.
Further, for example, the conversion may be performed using the conversion method described in the modification (1) of the second embodiment.

  (2) The public key cipher used by the encryption unit 114e and the decryption unit 123e is to generate the first ciphertext c1 by encrypting the verification value a using the public key and the random value u in the encryption unit 114e. The decryption unit 123e only needs to be able to decrypt the first ciphertext c1 with the secret key and generate a decryption verification value a ′ equal to the verification value a. Therefore, the public key cryptography used in the encryption unit 114e and the decryption unit 123e can be any public key cryptography that uses a random number other than the NTRU cipher.

For example, in the case of ElGamal encryption, h and f are respectively used as public and private keys of ElGamal encryption, and the encryption unit 114e generates a c1 by encrypting a using h and the random value u. In 123e, c1 may be decoded using f to generate a ′.
(3) The random value u may be generated by the first function unit 113e and the fourth function unit 126e as long as the same value can be obtained by the encryption device 110e and the decryption device 120e.

For example, for an arbitrary function Func, the same value may be obtained by the encryption device 110e and the decryption device 120e as u = Func (s). That is,
Generate G (s) and generate a and K from G (s).
Generate Func (s) and set u = Func (s).
It is good.

(4) Furthermore, since the random value u is not generated by the first function unit 113e and the fourth function unit 126e, it is sufficient that the same value can be obtained by the encryption device 110e and the decryption device 120e. May transmit the random number u directly to the decryption device 120e.
That is, as described below, the ciphertext C and the random value u may be transmitted to the decryption device 120e.

Generate G (s) and generate a and K from G (s).
The encryption device 110e separately transmits the random value u to the decryption device 120e.
Further, the encryption device 110e may encrypt the random value u and transmit it.
(5) Furthermore, since the random value u only needs to be obtained by the encryption device 110e and the decryption device 120e, partial information composed of a part of the random value u is represented by the first function unit 113e and the fourth function. The remaining partial information of the random value u generated by the unit 126e may be directly transmitted from the encryption device 110e to the decryption device 120e.

For example, the ciphertext C and the random value u2 may be transmitted to the decryption device 120e as follows.
Generate G (s) and generate a, K, u1 from G (s).
The encryption device 110e separately transmits the random value u2 to the decryption device 120e.
Generate a random value u by u = u1 xor u2.

Further, the encryption device 110e may encrypt and transmit the random value u2.
(6) The decryption device 120e checks whether the first ciphertext c1 is the ciphertext of the verification value a ″ obtained by the fourth function unit 126e, and when c1 is the ciphertext of a ″, the shared key Although the common key ciphertext Ci is decrypted using K ′, the same check method as that of the decryption device 120d of the third embodiment may be used.

That is, as shown in the processing system diagram of FIG. 20, the same check may be performed as follows using the same decoding unit 123d and comparison unit 127d as the decoding device 120d.
(A) The first ciphertext c1 is decrypted using the secret key polynomial f to generate a ′ (step S252).
(B) Generate s ′ = c2 xor H (a ′, c1) (step S254).

(C) G (s ′) is generated (step S255), and a ″, K ′, and u ′ are generated from G (s ′) (step S256e).
(D) It is checked whether or not a ″ = a ′ is satisfied (step S257). If established, the shared key K ′ is output (step S258).
In addition, this check may be a check of whether or not the first ciphertext c1 is a ciphertext of the decryption verification value a ′.

7). Summary of Embodiment 3 and Embodiment 4 As described above, the present invention uses shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance. A shared key generation device that outputs a secret number data generation unit that generates secret number data, a shared key derivation unit that converts the secret number data into verification value data and the shared key data based on a predetermined process, A first encryption unit that encrypts the verification value data based on the public key data to generate first encrypted preliminary data; and converts the verification value data into converted verification value data based on a predetermined process. And a second encryption unit that encrypts the secret number data based on the conversion verification value data to generate second encrypted preliminary data, and the encrypted shared key data includes: The first It consists of encryption preliminary data and the second encryption preliminary data.

  Further, the present invention is a shared key generation device that outputs shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance, and generates secret number data A secret number data generating unit, a secret key data and the first encryption preliminary data that are converted into verification value data and the shared key data based on a predetermined process, and the verification value data A first encryption unit that generates first encrypted preliminary data by encrypting based on public key data; a verification value conversion unit that converts the verification value data into converted verification value data based on a predetermined process; A second encryption unit that encrypts the secret number data based on the conversion verification value data to generate second encrypted preliminary data, and the encrypted shared key data includes the first encrypted preliminary data And the second It consists of encryption preliminary data.

  Further, the present invention is a shared key generation device that outputs shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance, and generates secret number data A secret number data generating unit, a shared key derivation unit that converts the secret number data into verification value data, random number data, and the shared key data based on a predetermined process, and the verification value data as the public key data A first encryption unit that encrypts based on the random number data to generate first encryption preliminary data, a verification value conversion unit that converts the verification value data into converted verification value data based on a predetermined process, A second encryption unit that encrypts the secret number data based on the conversion verification value data to generate second encrypted preliminary data, and the encrypted shared key data includes the first encrypted preliminary data And said Composed of two encryption preliminary data.

  Further, the present invention is a shared key generation device that outputs shared key data and encrypted shared key data obtained by encrypting the shared key data based on public key data given in advance, and generates secret number data A secret number data generating unit, a shared key derivation unit that converts the secret number data into verification value data, random number data, and the shared key data based on a predetermined process, and the verification value data as the public key data A first encryption unit configured to generate first encrypted preliminary data by encrypting based on the random number data; converting the verification value data and the first encrypted preliminary data into converted verification value data based on a predetermined process; A verification value conversion unit for converting, and a second encryption unit for encrypting the secret number data based on the conversion verification value data to generate second encrypted preliminary data, wherein the encrypted shared key data is The above Wherein the first encryption preliminary data and a second encryption preliminary data.

Here, the secret number data may be a randomly generated random number.
Here, the shared key derivation unit may use a one-way hash function as the predetermined process.
Here, the first encryption unit may generate the first encryption preliminary data by performing encryption using the NTRU encryption method.

Here, the verification value conversion unit may use a one-way hash function as the predetermined process.
Here, the verification value conversion unit may use the verification value data as it is as the conversion verification value data as a predetermined process.
Here, the second encryption unit may generate the second encryption preliminary data by performing an exclusive OR operation on the secret number data and the conversion verification value data.

Here, the second encryption unit may generate the second encryption preliminary data by encrypting the secret number data by a common key encryption method using the conversion verification value data as an encryption key. .
Here, the second encryption unit may generate the second encryption preliminary data by adding the conversion verification value data to the secret number data.

Here, the second encryption unit may generate the second encryption preliminary data by multiplying the secret number data by the conversion verification value data.
Here, the encrypted shared key data may be bit concatenated data of the first encrypted preliminary data and the second encrypted preliminary data.
Further, the present invention is effective when the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data is decrypted based on the secret key data given in advance and the shared key data is output. A key recovery device, wherein the first encryption preliminary data is decrypted based on the secret key data to generate verification value data; and the verification value data is converted into a predetermined process. A verification value conversion unit for converting into conversion verification value data; a second decryption unit for generating secret number data by decoding the second encrypted preliminary data based on the conversion verification value data; and the secret number data A verification value verification data and a shared key derivation unit that converts the verification value verification data into the shared key data based on a predetermined process, and outputs the shared key data when the verification value data matches the verification value verification data .

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on pre-assigned secret key data, and outputs the shared key data A key recovery device, wherein the first encryption preliminary data is decrypted based on the secret key data to generate verification value data, the verification value data, and the first encryption preliminary data A verification value conversion unit that converts data into converted verification value data based on a predetermined process; and a second decryption that generates secret number data by decrypting the second encrypted preliminary data based on the converted verification value data And a shared key derivation unit that converts the secret number data into verification value verification data and the shared key data based on a predetermined process, and when the verification value data matches the verification value verification data , Share And it outputs the data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on pre-assigned secret key data, and outputs the shared key data A key recovery device, wherein the first encryption preliminary data is decrypted based on the secret key data to generate verification value data; and the verification value data is converted into a predetermined process. A verification value conversion unit for converting into conversion verification value data; a second decryption unit for generating secret number data by decoding the second encrypted preliminary data based on the conversion verification value data; and the secret number data And a shared key derivation unit that converts the verification value verification data, the random number data, and the shared key data based on a predetermined process, and when the verification value data and the verification value verification data match, the shared key data Output That.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on pre-assigned secret key data, and outputs the shared key data A key recovery device, wherein the first encryption preliminary data is decrypted based on the secret key data to generate verification value data, the verification value data, and the first encryption preliminary data A verification value conversion unit that converts data into converted verification value data based on a predetermined process; and a second decryption that generates secret number data by decrypting the second encrypted preliminary data based on the converted verification value data And a shared key derivation unit that converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process, and the verification value data matches the verification value verification data When to And it outputs the shared key data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate verification value data, and outputs the verification value data to a predetermined value. A verification value conversion unit for converting into converted verification value data based on the processing; a second decryption unit for decoding the second encrypted preliminary data based on the converted verification value data to generate secret number data; A shared key derivation unit that converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process, and encrypts the verification value verification data based on the public key data and the random number data. And third and a third encryption unit for generating encrypted preliminary data, the first encryption preliminary data and the third cipher preliminary data if it matches, outputs the shared key data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate verification value data, and outputs the verification value data to a predetermined value. A verification value conversion unit for converting into converted verification value data based on the processing; a second decryption unit for decoding the second encrypted preliminary data based on the converted verification value data to generate secret number data; A shared key derivation unit that converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process, and encrypts the verification value data based on the public key data and the random number data. And a third encryption unit for generating third encryption preliminary data, wherein the first encryption preliminary data the third encryption preliminary data if it matches, outputs the shared key data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encrypted preliminary data based on the secret key data to generate verification value data, the verification value data, and the first A verification value conversion unit that converts one encryption preliminary data into conversion verification value data based on a predetermined process, and generates the secret number data by decrypting the second encryption preliminary data based on the conversion verification value data A second decryption unit; a shared key derivation unit that converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process; and the verification value verification data as the public key data. And before And a third encryption unit that generates third encrypted preliminary data by encrypting based on random number data, and when the first encrypted preliminary data and the third encrypted preliminary data match, the sharing Output key data.

  Further, the present invention decrypts the encrypted shared key data composed of the first encrypted preliminary data and the second encrypted preliminary data based on the secret key data and the public key data given in advance, thereby sharing the shared key data. A first decryption unit that decrypts the first encrypted preliminary data based on the secret key data to generate verification value data, the verification value data, and the first A verification value conversion unit that converts one encryption preliminary data into conversion verification value data based on a predetermined process, and generates the secret number data by decrypting the second encryption preliminary data based on the conversion verification value data A second decryption unit; a shared key derivation unit that converts the secret number data into verification value verification data, random number data, and the shared key data based on a predetermined process; and the verification value data as the public key data Turbulence And a third encryption unit that generates third encrypted preliminary data by encrypting based on the data, and the shared key when the first encrypted preliminary data matches the third encrypted preliminary data Output data.

Here, the shared key derivation unit may use a one-way hash function as the predetermined process.
Here, the first decryption unit may generate the verification value data by decrypting using the NTRU encryption method.
Here, the verification value conversion unit may use a one-way hash function as the predetermined process.

Here, the verification value conversion unit may use the verification value data as it is as the conversion verification value data as a predetermined process.
Here, the second decryption unit may generate the secret number data by performing an exclusive OR operation on the second encryption preliminary data and the conversion verification value data.
Here, the second decryption unit may generate the secret number data by decrypting the second encryption preliminary data by a common key encryption method using the conversion verification value data as an encryption key. .

Here, the second decryption unit may generate the secret number data by subtracting the conversion verification value data from the second encrypted preliminary data.
Here, the second encryption unit may generate the secret number data by dividing the second encryption preliminary data by the conversion verification value data.
Further, the present invention is an encryption device that generates ciphertext data obtained by encrypting plaintext data based on public key data given in advance, and includes a secret number data generation unit that generates secret number data, and the secret number A shared key derivation unit that converts data into verification value data and shared key data based on a predetermined process; and a first encryption preliminary data generated by encrypting the verification value data based on the public key data An encryption unit, a verification value conversion unit that converts the verification value data into conversion verification value data based on a predetermined process, and a second encryption by encrypting the secret number data based on the conversion verification value data A second encryption unit that generates preliminary data; and a third encryption unit that generates the third encrypted preliminary data by encrypting the plaintext data based on the shared key data. Said Wherein the first encryption preliminary data and the second encryption preliminary data and a third encryption preliminary data.

  Further, the present invention decrypts ciphertext data composed of the first cipher spare data, the second cipher spare data, and the third cipher spare data on the basis of pre-given secret key data. A decryption device for outputting data, wherein the first encryption preliminary data is decrypted based on the secret key data to generate verification value data; and the verification value data is subjected to a predetermined process. A verification value conversion unit for converting into converted verification value data based on the above, a second decryption unit for decoding the second encrypted preliminary data based on the converted verification value data and generating secret number data, and A shared key derivation unit that converts secret number data into verification value verification data and shared key data based on a predetermined process, and when the verification value data matches the verification value verification data, Preliminary data before And decoding based on the shared key data and a decoding unit configured to generate the decrypted text data.

  The present invention also provides an encryption device that generates ciphertext data obtained by encrypting plaintext data based on public key data given in advance, and decrypts ciphertext data based on secret key data given in advance. An encryption system including a decryption device that outputs sentence data. The encryption device includes a secret number data generation unit that generates secret number data, a shared key derivation unit that converts the secret number data into verification value data and shared key data based on a predetermined process, and the verification value data. A first encryption unit which generates first encrypted preliminary data by encrypting based on the public key data, and a verification value conversion unit which converts the verification value data into converted verification value data based on a predetermined process; A second encryption unit that encrypts the secret number data based on the conversion verification value data to generate second encrypted preliminary data, and encrypts the plaintext data based on the shared key data. A third encryption unit for generating the encryption preliminary data, and the ciphertext data is composed of the first encryption preliminary data, the second encryption preliminary data, and the third encryption preliminary data . The decryption device includes: a first decryption unit that decrypts the first encryption preliminary data based on the secret key data to generate the verification value data; and the verification value data based on a predetermined process. A verification value conversion unit for converting into converted verification value data, a second decryption unit for generating the secret number data by decoding the second encrypted preliminary data based on the conversion verification value data, and the secret number And a shared key derivation unit that converts data into verification value verification data and shared key data based on a predetermined process, and when the verification value data matches the verification value verification data, the third encryption preliminary data And a decrypting unit that decrypts data based on the shared key data and generates the decrypted text data.

As described above, the present invention has been made in view of the problems in the conventional system. In the encryption system, the encryption device and the decryption device are configured by configuring a key encapsulation mechanism to which the NTRU encryption can be applied. Keys can be distributed using NTRU cryptography.
As described above, it is possible to provide an encryption system that could not be achieved by the prior art, and its value is great.

8). Other Modifications Although the present invention has been described based on the above-described embodiment, it is needless to say that the present invention is not limited to the above-described embodiment. The following cases are also included in the present invention.
(1) Instead of the encryption device transmitting each ciphertext to the decryption device via the Internet, the encryption device writes each ciphertext to a recording medium such as a DVD, and the decryption device reads each ciphertext from the recording medium. May be read out.

  (2) The NTRU cipher used in the present invention may be an ERU (Efficient Embedded Security Standard) NTRU cipher other than the method described in Non-Patent Document 2. For EESS NTRU ciphers, see "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://ceesstandards.org, May 2003. Is described in detail. For this reason, a detailed description thereof is omitted here, but a brief description will be given below.

  In the EESS NTRU cipher, the random number polynomial r is a polynomial in which d coefficients are 1 and (N−d) coefficients are 0, or a polynomial calculated using such a plurality of polynomials. is there. Therefore, in the above embodiment, when generating the random number polynomial r, if it is generated so as to be such a polynomial, the EESS NTRU cipher can be used instead of the NTRU cipher, and the same effect can be obtained. can get.

(3) The content distribution system may be configured as follows.
The content distribution system includes a content server device, an encryption device, a broadcast device, a reception device, a decryption device, a playback device, and a monitor.
The encryption device and the decryption device correspond to the encryption device 110 and the decryption device 120 of the content distribution system 10.

  The content server device and the encryption device are connected via a dedicated line, and the content server device transmits content such as a movie composed of video and audio to the encryption device via the dedicated line. The encryption device and the broadcasting device are connected via a dedicated line. The encryption device transmits each ciphertext to the broadcasting device, and the broadcasting device multiplexes each ciphertext and broadcasts it on a digital broadcast wave.

  The receiving device and the decoding device are connected, and the decoding device and the playback device are connected. The receiving device receives the digital broadcast wave, extracts each ciphertext from the received digital broadcast wave, and transmits each extracted ciphertext to the decryption device. The decryption device receives each ciphertext, generates playback content using each received ciphertext, and outputs the generated playback content to the playback device. The playback device is connected to a monitor incorporating a decoding device and a speaker. The playback device receives the playback content, generates a video signal and an audio signal from the received playback content, and the monitor displays the video and outputs audio.

(4) The content server device and the encryption device may be configured as an integrated device. Further, the decoding device and the playback device may be configured as an integrated device.
(5) In each of the above embodiments, the memory card 160 stores the public key polynomial h in advance, and the memory card 170 stores the secret key polynomial f and the public key polynomial h in advance, and the encryption device 110 and the decryption device 120 acquire the public key polynomial and the secret key polynomial from the memory card 160 and the memory card 170, respectively, but are not limited thereto.

The encryption device 110 may store a public key polynomial in advance, and the decryption device 120 may store a public key polynomial and a secret key polynomial in advance.
Also, the key management device generates a secret key polynomial and a public key polynomial, transmits the generated secret key polynomial and public key polynomial to the decryption device 120 in a secret and secure manner, and sends the generated public key polynomial to the encryption device 110. It may be transmitted.

(6) The content distributed in the content distribution system is not limited to content such as a movie composed of video and audio. There may be moving images, still images, audio, music, documents, novels, databases generated by DB software, electronic table data generated by spreadsheet software, computer programs, and other computer data.
Further, the content may be key information used for encryption and decryption, digital signature, signature verification, and the like, instead of the above-mentioned copyrighted work.

  For example, as shown by the above embodiments, the encryption device and the decryption device share a shared key, and the encryption device encrypts the content key using the shared key to generate an encrypted content key. The content is encrypted using the content key to generate encrypted content, and the generated encrypted content key and the generated encrypted content are transmitted to the decryption device. The decryption device receives the encrypted content key and the encrypted content, decrypts the encrypted content key using the shared key, generates a content key, and decrypts the encrypted content using the generated content key Content may be generated.

(7) The present invention may be the method described above. Further, the present invention may be a computer program that realizes these methods by a computer, or may be a digital signal composed of the computer program.
The present invention also provides a computer-readable recording medium such as a flexible disk, hard disk, CD-ROM, MO, DVD, DVD-ROM, DVD-RAM, BD (Blu-ray Disc). ), Recorded in a semiconductor memory or the like. Further, the present invention may be the computer program or the digital signal recorded on these recording media.

Further, the present invention may transmit the computer program or the digital signal via an electric communication line, a wireless or wired communication line, a network represented by the Internet, a data broadcast, or the like.
The present invention may be a computer system including a microprocessor and a memory, wherein the memory stores the computer program, and the microprocessor operates according to the computer program.

In addition, the program or the digital signal is recorded on the recording medium and transferred, or the program or the digital signal is transferred via the network or the like, and is executed by another independent computer system. It is good.
(8) The above embodiment and the above modifications may be combined.

The content distribution system described above is used in a management, repetitive, and continuous manner in an industry that supplies digital works such as music, movies, and novels to users from content suppliers. . The encryption device and the decryption device that constitute the content distribution system are manufactured and sold in the electrical equipment industry that manufactures electrical appliances and the like.
In particular, it is suitable in the industry where digitalized works are stored in a recording medium such as a DVD and distributed to the market, distributed via a network, or broadcast.

FIG. 1 is a conceptual diagram showing a configuration of a content distribution system 10 and a connection form between components. FIG. 2 is a block diagram showing the configuration of the encryption device 110. FIG. 3 is a block diagram illustrating a configuration of the decoding device 120. FIG. 4 is a processing system diagram showing operations of the encryption device 110 and the decryption device 120. FIG. 5 is a flowchart showing operations of the encryption device 110 and the decryption device 120. FIG. 6 is a block diagram showing the configuration of the encryption device 110b. FIG. 7 is a block diagram illustrating a configuration of the decoding device 120b. FIG. 8 is a processing system diagram showing operations of the encryption device 110b and the decryption device 120b. FIG. 9 is a block diagram illustrating a configuration of the encryption device 110c. FIG. 10 is a block diagram illustrating a configuration of the decoding device 120c. FIG. 11 is a processing system diagram showing operations of the encryption device 110c and the decryption device 120c. FIG. 12 is a processing system diagram showing the operation of a modified example of the encryption device 110c and the decryption device 120c. FIG. 13 is a block diagram illustrating a configuration of the encryption device 110d. FIG. 14 is a block diagram illustrating a configuration of the decoding device 120d. FIG. 15 is a flowchart showing operations of the encryption device 110d and the decryption device 120d. FIG. 16 is a processing system diagram showing operations of the encryption device 110d and the decryption device 120d. FIG. 17 is a block diagram illustrating a configuration of the encryption device 110e. FIG. 18 is a block diagram illustrating a configuration of the decoding device 120e. FIG. 19 is a processing system diagram showing operations of the encryption device 110e and the decryption device 120e. FIG. 20 is a processing system diagram showing the operation of a modification of the encryption device 110e and the decryption device 120e.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 Content delivery system 110 Encryption apparatus 111 Public key input part 112 Random number generation part 113 1st function part 114 Encryption part 117 1st transmission part 118 Common key encryption part 119 2nd transmission part 120 Decryption device 121 Private key input part 122 1st 1 receiving unit 123 decrypting unit 126 second function unit 127 comparing unit 128 common key decrypting unit 129 second receiving unit 130 Internet 140 content server device 150 reproducing device 155 monitor 160 memory card 170 memory card

Claims (51)

A key sharing system composed of a shared key generating device and a shared key restoring device that generates a shared key without being known to a third party,
The shared key generation device includes:
Seed value generating means for generating a seed value;
First shared key generation means for generating a verification value and a shared key from the generated seed value;
A first encryption means for encrypting the generated verification value to generate first encrypted information;
Second encryption means for encrypting the generated seed value based on the generated verification value to generate second encrypted information;
Transmission means for transmitting the generated first encrypted information and the second encrypted information,
The shared key restoration device includes:
Receiving means for receiving the first encrypted information and the second encrypted information;
First decryption means for decrypting the received first encrypted information to generate a first decryption verification value;
Second decryption means for decrypting the received second encrypted information based on the generated first decryption verification value to generate a decryption seed value;
Second shared key generation means for generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the first shared key generation means;
Determining means for determining whether to output the generated decryption shared key based on the generated first decryption verification value and the second decryption verification value;
An output means for outputting the generated decryption shared key when it is determined to output the key sharing system. The shared key generation device further includes:
Acquisition means for acquiring content;
Encrypting the acquired content using the generated shared key, and generating encrypted content, and
The transmission means further transmits the generated encrypted content,
The receiving means further receives the encrypted content,
The shared key recovery device further includes:
Decryption means for decrypting the received encrypted content using the output decryption shared key to generate decrypted content;
The key sharing system according to claim 1, further comprising output means for outputting the generated decrypted content. A shared key generation device that transmits a shared key to a partner device without being known to a third party,
Seed value generating means for generating a seed value;
Shared key generation means for generating a verification value and a shared key from the generated seed value;
A first encryption means for encrypting the generated verification value to generate first encrypted information;
Second encryption means for encrypting the generated seed value based on the generated verification value to generate second encrypted information;
A shared key generation apparatus comprising: transmission means for transmitting the generated first encryption information and the second encryption information. The shared key generation device according to claim 3, wherein the seed value generation unit generates the seed value by generating a random number and using the generated random number as the seed value. The shared key generation unit generates a function value by applying a one-way function to the seed value, and generates the verification value and the shared key from the generated function value. Shared key generator. The shared key generation apparatus according to claim 5, wherein the shared key generation unit generates the function value by applying a hash function to the seed value as the one-way function. The shared key generation unit generates the verification value and the shared key by using a part of the generated function value as the verification value and the other part as the shared key. The shared key generation apparatus according to claim 5. The shared key generation unit generates a function value by applying a one-way function to the seed value, and generates the verification value, the shared key, and a blind value from the generated function value. 4. The shared key generation device according to 3. The first encryption means includes
A public key acquisition unit for acquiring a public key;
A public key encryption unit that generates a first encryption information by applying a public key encryption algorithm to the verification value using the acquired public key and the generated blind value. The shared key generation device according to claim 8. The public key encryption algorithm is based on the NTRU encryption method,
The public key acquisition unit acquires, as the public key, a public key polynomial generated by an NTRU encryption key generation algorithm, the public key encryption unit generates a verification value polynomial from the verification value, and the blind A blind value polynomial is generated from the value, and the verification value polynomial is encrypted by using the public key polynomial as a key and the blind value polynomial to disturb the verification value polynomial by the encryption algorithm of the NTRU cryptosystem. The shared key generation device according to claim 9, wherein the first encryption information as a polynomial is generated. The first encryption means includes
A public key acquisition unit for acquiring a public key;
The shared key according to claim 3, further comprising: a public key encryption unit that generates a first encryption information by applying a public key encryption algorithm to the verification value using the acquired public key. Key generator. The public key encryption algorithm is based on the NTRU encryption method,
The public key acquisition unit acquires, as the public key, a public key polynomial generated by a key generation algorithm of an NTRU cryptosystem, the public key encryption unit generates a verification value polynomial from the verification value, and a blind value A blind value polynomial is generated from the generated blind value, and the public key polynomial is used as a key by the NTRU encryption algorithm, and the blind value polynomial is used to disturb the verification value polynomial. The shared key generation apparatus according to claim 11, wherein the verification value polynomial is encrypted to generate the first encryption information as a polynomial. The second encryption means generates a function value by applying a one-way function to the verification value, and uses the generated function value to apply an encryption algorithm to the seed value to generate the second encryption information. The shared key generation apparatus according to claim 3, wherein the shared key generation apparatus generates the shared key. The second encryption unit generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value. 14. The shared key generation device according to 13. The second encryption means generates the second encryption information by applying a common key encryption algorithm as the encryption algorithm to the generated function value and the seed value. Item 14. The shared key generation device according to Item 13. The said 2nd encryption means produces | generates the said 2nd encryption information by performing addition as the said encryption algorithm with respect to the said generated function value and the said seed value. Shared key generator. The second encryption information is generated by multiplying the generated function value and the seed value as the encryption algorithm by generating the second encryption information. Shared key generator. The shared key generation apparatus according to claim 13, wherein the second encryption unit generates the function value by applying a hash function as the one-way function to the verification value. The shared key generation apparatus according to claim 3, wherein the second encryption unit generates second encryption information by applying an encryption algorithm to the seed value using the verification value. The shared key generation device according to claim 3, wherein the second encryption unit encrypts the seed value using the verification value and the first encryption information. The second encryption means generates a function value by applying a one-way function to the verification value and the first encryption information, and applies an encryption algorithm to the seed value using the generated function value. The shared key generation device according to claim 20, wherein the second encrypted information is generated. The second encryption unit generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value. The shared key generation device according to 21. The shared key generation device further includes:
Acquisition means for acquiring content;
Encrypting the acquired content using the generated shared key, and generating encrypted content, and
The shared key generation apparatus according to claim 3, wherein the transmission unit further transmits the generated encrypted content. A shared key restoration device that receives a shared key from a shared key generation device without being known to a third party,
The shared key generation device generates a seed value, generates a verification value and a shared key from the generated seed value, encrypts the generated verification value, generates first encrypted information, and generates And encrypting the generated seed value based on the verification value generated to generate second encrypted information, transmitting the generated first encrypted information and the second encrypted information,
The shared key restoration device includes:
Receiving means for receiving the first encrypted information and the second encrypted information;
First decryption means for decrypting the received first encrypted information to generate a first decryption verification value;
Second decryption means for decrypting the received second encrypted information based on the generated first decryption verification value to generate a decryption seed value;
Shared key generation means for generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the shared key generation device;
Determining means for determining whether to output the generated decryption shared key based on the generated first decryption verification value and the second decryption verification value;
An output unit that outputs the generated decryption shared key when it is determined to output the shared key recovery apparatus. The shared key generation device acquires a public key, and uses the acquired public key to generate a first encryption information by applying a public key encryption algorithm to the verification value,
The first decoding means includes
A secret key acquisition unit for acquiring a secret key corresponding to the public key;
A public key decryption unit configured to apply a public key decryption algorithm corresponding to the public key encryption algorithm to the received first encrypted information using the acquired secret key to generate the first decryption verification value; 25. The shared key restoration apparatus according to claim 24, comprising: The public key encryption algorithm and the public key decryption algorithm are based on the NTRU cryptosystem,
The shared key generation device acquires, as the public key, a public key polynomial generated by an NTRU encryption key generation algorithm, generates a verification value polynomial from the verification value, generates a blind value, A blind value polynomial is generated from the blind value, and the public key polynomial is used as a key by an encryption algorithm of the NTRU cryptosystem, the blind value polynomial is used to disturb the verification value polynomial, and the verification value polynomial is Encrypting to generate the first encrypted information as a polynomial;
The receiving means receives the first encrypted information as a polynomial;
The secret key acquisition unit acquires a secret key polynomial generated by a key generation algorithm of the NTRU cryptosystem as the secret key,
The public key decryption unit decrypts the first encrypted information as a polynomial by using the secret key polynomial as a key by a decryption algorithm corresponding to the encryption algorithm of the NTRU cryptosystem, and a decryption verification value polynomial 26. The shared key restoration device according to claim 25, wherein the first decryption verification value is generated from the generated decryption verification value polynomial. The shared key generation device generates a function value by applying a one-way function to the verification value, and uses the generated function value to apply an encryption algorithm to the seed value to obtain the second encryption information. Generate
The second decryption means generates the decryption function value by applying the one-way function to the generated first decryption verification value, and uses the generated decryption function value to receive the second cipher 25. The shared key restoration apparatus according to claim 24, wherein the decryption algorithm corresponding to the encryption algorithm is subjected to decryption algorithm to generate the decryption seed value. The shared key generation device generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value,
The second decryption unit generates the decryption seed value by performing an exclusive OR as the decryption algorithm on the generated decryption function value and the second encryption information. 27. The shared key recovery device according to 27. The shared key generation device generates the second encryption information by applying a common key encryption algorithm as the encryption algorithm to the generated function value and the seed value,
The second decryption unit applies the common key decryption algorithm corresponding to the common key encryption algorithm as the decryption algorithm to the generated decryption function value and the second encryption information, thereby obtaining the decryption seed value. 28. The shared key restoration device according to claim 27, wherein: The shared key generation device generates the second encryption information by performing addition as the encryption algorithm to the generated function value and the seed value,
28. The second decryption unit generates the decryption seed value by performing subtraction as the decryption algorithm on the generated decryption function value and the second encryption information. The shared key recovery device described. The shared key generation device generates the second encryption information by multiplying the generated function value and the seed value as the encryption algorithm,
28. The second decryption unit generates the decryption seed value by performing division as the decryption algorithm on the generated decryption function value and the second encryption information. The shared key recovery device described. The shared key generation device generates a function value by applying a hash function to the verification value as the one-way function,
28. The shared key according to claim 27, wherein the second decryption unit generates the decryption function value by applying the hash function as the one-way function to the generated first decryption verification value. Restore device. The shared key generation device generates second encryption information by applying an encryption algorithm to the seed value using the verification value,
The second decryption means applies the decryption algorithm corresponding to the encryption algorithm to the second encryption information using the generated first decryption verification value to generate the decryption seed value. 25. The shared key restoration apparatus according to claim 24, wherein The shared key generation device encrypts the seed value using the verification value and the first encryption information,
The second decryption means decrypts the second encrypted information using the generated first decryption verification value and the received first encrypted information to generate the decryption seed value. The shared key recovery apparatus according to claim 24. The shared key generation device generates a function value by applying a one-way function to the verification value and the first encryption information, and uses the generated function value to apply an encryption algorithm to the seed value Generating the second encrypted information;
The second decryption means generates a decryption function value by applying the one-way function to the first decryption verification value and the first encryption information, and uses the generated decryption function value to generate the second encryption 35. The shared key restoration apparatus according to claim 34, wherein the decryption algorithm corresponding to the encryption algorithm is subjected to decryption information to generate the decryption seed value. The shared key generation device generates the second encryption information by performing an exclusive OR as the encryption algorithm on the generated function value and the seed value,
36. The second decryption unit generates the decryption seed value by performing an exclusive OR as the decryption algorithm on the decryption function value and the second encryption information. The shared key recovery device described. The shared key generation device generates a function value by applying a one-way function to the seed value, generates the verification value and the shared key from the generated function value,
The shared key generation means generates a decryption function value by applying the one-way function to the generated decryption seed value, and generates the second decryption verification value and the decryption shared key from the generated decryption function value. 25. The shared key restoration apparatus according to claim 24, wherein the shared key restoration apparatus is generated. The shared key generation device generates a function value by applying a hash function to the seed value as the one-way function,
The shared key restoration unit according to claim 37, wherein the shared key generation unit generates the decryption function value by performing the hash function as the one-way function on the generated decryption seed value. apparatus. The shared key generation device generates the verification value and the shared key by using a part of the generated function value as the verification value and the other part as the shared key,
The shared key generation means uses a part of the generated decryption function value as the second decryption verification value and the other part as the decryption shared key, whereby the second decryption verification value and the decryption shared value 38. The shared key recovery apparatus according to claim 37, wherein the key is generated. The shared key generation device generates a function value by applying a one-way function to the seed value, generates the verification value, the shared key, and a blind value from the generated function value, acquires a public key, Using the acquired public key and the generated blind value, the verification value is subjected to a public key encryption algorithm to generate the first encryption information,
The shared key generation means generates a decryption function value by applying the one-way function to the generated decryption seed value, and generates the second decryption verification value, the decryption shared key, and the generated decryption function value. 25. The shared key restoration apparatus according to claim 24, wherein a decryption blind value is generated. The shared key generation device acquires a public key, and generates a first encryption information by applying a public key encryption algorithm to the verification value using the acquired public key and the generated blind value And
The determination means, instead of the determination based on the first decryption verification value and the second decryption verification value,
A public key acquisition unit for acquiring the public key;
Using the acquired public key and the generated decryption blind value, generate the re-encrypted information by applying the public key encryption algorithm to the generated first decryption verification value or the second decryption verification value A re-encryption unit to
And a determination unit that determines whether or not to output the generated decryption shared key based on the received first encryption information and the generated re-encryption information. 40. The shared key recovery device according to 40. The determination unit compares the first encrypted information and the re-encrypted information, and determines that the decryption shared key is output when the first encrypted information and the re-encrypted information match. 42. The shared key restoration apparatus according to claim 41, wherein The public key encryption algorithm is based on the NTRU encryption method,
The shared key generation apparatus acquires, as the public key, a public key polynomial generated by an NTRU encryption key generation algorithm, generates a verification value polynomial from the verification value, and generates a blind value polynomial from the blind value The verification value polynomial is encrypted using the public key polynomial as a key and the blind value polynomial is used to disturb the verification value polynomial by the encryption algorithm of the NTRU cryptosystem, Generating first encrypted information;
The public key acquisition unit acquires the public key polynomial,
The re-encryption unit generates a decryption verification value polynomial from the second decryption verification value, generates a decryption blind value polynomial from the decryption blind value, and uses the public key polynomial as a key by an NTRU encryption algorithm. The decrypted verification value polynomial is encrypted using the decrypted blind value polynomial to disrupt the decrypted verification value polynomial, and the re-encrypted information as a polynomial is generated. 42. A shared key recovery apparatus according to 41. 25. The shared key according to claim 24, wherein the determination unit compares the first decryption verification value and the second decryption verification value, and determines that the decryption shared key is output if they match. Restore device. The shared key generation device further acquires content, encrypts the acquired content using the generated shared key, generates encrypted content, and transmits the generated encrypted content ,
The receiving means further receives the encrypted content,
The shared key recovery device further includes:
Decryption means for decrypting the received encrypted content using the output decryption shared key to generate decrypted content;
The shared key restoration apparatus according to claim 24, further comprising: an output unit that outputs the generated decrypted content. A shared key generation method used in a shared key generation device that transmits a shared key to a partner device without being known to a third party,
A seed value generation step for generating a seed value;
A shared key generation step of generating a verification value and a shared key from the generated seed value;
A first encryption step of encrypting the generated verification value to generate first encrypted information;
A second encryption step of encrypting the generated seed value based on the generated verification value to generate second encrypted information;
And a transmission step of transmitting the generated first encryption information and the second encryption information. A shared key generation program used in a shared key generation device that transmits a shared key to a partner device without being known to a third party,
A seed value generation step for generating a seed value;
A shared key generation step of generating a verification value and a shared key from the generated seed value;
A first encryption step of encrypting the generated verification value to generate first encrypted information;
A second encryption step of generating second encrypted information by encrypting the generated seed value based on the generated verification value;
A shared key generation program, comprising: a transmission step of transmitting the generated first encryption information and the second encryption information. The shared key generation program according to claim 48, wherein the shared key generation program is recorded on a computer-readable recording medium. A shared key restoration method used in a shared key restoration device that receives a shared key from a shared key generation device without being known to a third party,
The shared key generation device generates a seed value, generates a verification value and a shared key from the generated seed value, encrypts the generated verification value, generates first encrypted information, and generates And encrypting the generated seed value based on the verification value generated to generate second encrypted information, transmitting the generated first encrypted information and the second encrypted information,
The shared key restoration method includes:
Receiving the first encrypted information and the second encrypted information; and
A first decryption step of decrypting the received first encrypted information to generate a first decryption verification value;
A second decryption step of decrypting the received second encryption information based on the generated first decryption verification value to generate a decryption seed value;
A shared key generation step of generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the shared key generation device;
A determination step of determining whether to output the generated decryption shared key based on the generated first decryption verification value and the second decryption verification value;
An output step of outputting the generated decryption shared key when it is determined to output the shared key restoration method. A shared key restoration program used in a shared key restoration device that receives a shared key from a shared key generation device without being known to a third party,
The shared key generation device generates a seed value, generates a verification value and a shared key from the generated seed value, encrypts the generated verification value, generates first encrypted information, and generates And encrypting the generated seed value based on the verification value generated to generate second encrypted information, transmitting the generated first encrypted information and the second encrypted information,
The shared key restoration program includes:
Receiving the first encrypted information and the second encrypted information; and
A first decryption step of decrypting the received first encrypted information to generate a first decryption verification value;
A second decryption step of decrypting the received second encryption information based on the generated first decryption verification value to generate a decryption seed value;
A shared key generation step of generating a second decryption verification value and a decryption shared key from the generated decryption seed value by the same method as the shared key generation device;
A determination step of determining whether to output the generated decryption shared key based on the generated first decryption verification value and the second decryption verification value;
An output step of outputting the generated decryption shared key when it is determined to output the shared key restoration program. The shared key restoration program according to claim 50, wherein the shared key restoration program is recorded on a computer-readable recording medium.

Images