DECRYPTION METHOD, RECORDING MEDIUM STORING DECRYPTION PROGRAM, DECRYPTION DEVICE, KEY GENERATION METHOD, AND RECORDING MEDIUM STORING KEY GENERATION PROGRAM

摘要

A decryption method includes receiving an input of an n-dimensional vector whose elements other than a first element are all zero, or of the first element. The vector is a ciphertext obtained by encrypting a plaintext being an integer not less than 0 and less than s with a public key, or by performing an operation on a plurality of ciphertexts without decrypting them. The public key is associated with an n×n invertible matrix V defined as a secret key of homomorphic cryptography by using n integers, and is a matrix B being an Hermite normal form of V. The decryption method also includes: acquiring an element w which is coprime to s and which is one of elements of a matrix W=dV⁻¹ defined by a determinant d of B and V⁻¹; acquiring w⁻¹ modulo s; calculating b=[c×w]_d×w⁻¹ mod s; and outputting b as a plaintext.