Patent ID: 7773746

Claim:
An encryption system comprising an encryption device, which generates an encrypted text by encrypting a plain text according to a predetermined cryptosystem, and a decryption device which generates a decrypted text by decrypting the encrypted text according to the predetermined cryptosystem, wherein said decryption device includes: a key generation unit operable to generate elements f and g in a ring R, generate an element Fq and an element Fp, with respect to the ring R, and generate ideals p and q of the ring R, the ring R being a set of N-dimensional arrays and defining addition, subtraction and multiplication, the element Fq being an inverse number of f(mod q), and the element Fp being an inverse number of f(mod p), generate, as a public key, an element k which is congruent, modulo q, to a product derived as a result of multiplying the element g and the element Fq, and generate, as a private key, information for obtaining the element f and the element Fp; and a decryption unit operable to generate the decrypted text by decrypting the encrypted text using the private key, wherein said encryption device includes an encryption unit operable to generate the encrypted text by encrypting the plain text using the public key and an element r randomly selected from the ring R, wherein all of elements in an N-dimensional array of the N-dimensional arrays indicate 0 or 1, the N-dimensional array being the element f, g or r, or the plain text, wherein the ideal p and the ideal q are relatively prime, wherein the ideal q is expressed by q=(2^k)*R, where the ideal q is a set of multiples of (2^k) in the ring R, 2^k denotes a result of 1 multiplied k times by 2, and * denotes a multiplication of the ring R, wherein said key generation unit is further operable to generate the element f based on a non-negative integer df, which specifies a number of elements so that a value of the N-dimensional array indicates 1, generate the element g based on a non-negative integer dg, which specifies a number of elements so that the value of the N-dimensional array indicates 1, and select the element r based on a non-negative integer d, which specifies a number of elements, such that each of the elements satisfies that a value indicative of the N-dimensional array indicates 1, wherein the ideal p is expressed by p=pg*R with respect to an element pg in the ring R, where the ideal p is a set of multiples of the element pg in the ring R, whereas the ideal q is expressed by q=qg*R with respect to an element qg in the ring R, where the ideal q is a set of multiples of the element qg in the ring R, and wherein the dimension N, the elements pg and qg, and the non-negative integers df, dg and d are derived based on a conditional expression indicating a condition for preventing an occurrence of decryption failure.