Decryption method, recording medium storing decryption program, decryption device, key generation method, and recording medium storing key generation program

A decryption device comprising:

• a ciphertext reception unit that receives an input of an n-dimensional vector {right arrow over (c)}=(c, 0, . . . ,0) whose elements other than a first element are all zero, or an input of a value c that is the first element of the vector {right arrow over (c)}, the vector {right arrow over (c)} being a ciphertext obtained
• by encrypting a plaintext being an integer not less than 0 and less than s with a public key
• which is associated with an n×n invertible matrix
• V
• =
• [
• v
• 0
• v
• 1
• v
• 2
• …
• v
• n
• -
• 1
• -
• v
• n
• -
• 1
• v
• 0
• v
• 1
• …
• v
• n
• -
• 2
• -
• v
• n
• -
• 2
• -
• v
• n
• -
• 1
• v
• 0
• …
• v
• n
• -
• 3
• ⋮
• ⋮
• ⋮
• ⋱
• ⋮
• -
• v
• 1
• -
• v
• 2
• -
• v
• 3
• …
• v
• 0
• ]
• defined as a secret key of homomorphic cryptography by using n integers v0, . . . , vn−1, and
• which is a matrix B being an Hermite normal form of the matrix V, or
• by performing a certain operation on a plurality of ciphertexts without decrypting the plurality of ciphertexts, each of the plurality of ciphertexts being obtained by encrypting each of a plurality of plaintexts being an integer not less than 0 and less than s with the matrix B;
• a first acquisition unit that acquires an element w which is coprime to s and which is one of elements of a matrix W=dV−1 defined by a determinant d of the matrix B and an inverse matrix V1 of the matrix V;
• a second acquisition unit that acquires an inverse w−1 of w modulo s;
• a calculation unit that calculates a value b=[c×w]d×w−1 mod s using a value [c×w]d to which c×w mod d is regulated to be included in an interval [−d/2, d/2);
• and
• a plaintext output unit that outputs the value b calculated by the calculation unit as a plaintext which corresponds to the vector {right arrow over (c)} received by the ciphertext reception unit or to the value c received by the ciphertext reception unit.

A key generation method executed by a computer, the key generation method comprising:

• generating n integers v0, . . . , vn−1 by the computer;
• judging, by the computer, whether a first condition, a second condition, and a third condition hold true with respect to the generated n integers v0, . . . , vn−1, wherein
• the first condition is a condition that an inverse matrix V−1 exists for an n×n matrix
• V
• =
• [
• v
• 0
• v
• 1
• v
• 2
• …
• v
• n
• -
• 1
• -
• v
• n
• -
• 1
• v
• 0
• v
• 1
• …
• v
• n
• -
• 2
• -
• v
• n
• -
• 2
• -
• v
• n
• -
• 1
• v
• 0
• …
• v
• n
• -
• 3
• ⋮
• ⋮
• ⋮
• ⋱
• ⋮
• -
• v
• 1
• -
• v
• 2
• -
• v
• 3
• …
• v
• 0
• ]
• defined by the n integers v0, . . . , vn−1,
• the second condition is a condition that a matrix B
• which is in an Hermite normal form,
• whose (1, j)-th element is 0 for all j where 1<j≦n,
• whose (i,j)-th element is 0 for all i and j where 1<i≦n, 1<j≦n, and i≠j, and
• whose (i, i)-th element is 1 for all i where 1<i<n is derivable from the matrix V, and
• the third condition is a condition that an element coprime to a predetermined positive integer s exists in n×n elements of a matrix W=dV−1 defined by a determinant d of the matrix B and the inverse matrix V−1 of the matrix V;
• repeating the generating of the n integers v0, . . . , vn−1 by the computer until the n integers v0, . . . , vn−1 which let the first condition, the second condition, and the third condition hold true are obtained;
• outputting, from the computer, the matrix B as a public key for homomorphic cryptography whose plaintext space is a set of integers which are not less than 0 and less than s, when the n integers v0, . . . , vn−1 which let the first condition, the second condition, and the third condition hold true are obtained.