主权项 |
1. A decryption method executed by a computer, the decryption method comprising:
receiving, by the computer, 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 matrixV=[v0v1v2…vn-1-vn-1v0v1…vn-2-vn-2-vn-1v0…vn-3⋮⋮⋮⋱⋮-v1-v2-v3…v0] 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, orby 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; acquiring, by the computer, 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 V−1 of the matrix V; acquiring, by the computer, an inverse w−1 of w modulo s; calculating, by the computer, 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 outputting, from the computer, the calculated value b as a plaintext which corresponds to the input vector {right arrow over (c)} or to the input value c. |