PUBLIC KEY ENCRYPTION SYSTEM BASED ON QUADRATIC RESIDUOSITY ASSUMPTION OF HIGHER DIMENSIONS

摘要

A public-key encryption system. Encryption of a k-bit plaintext m is performed by picking a random generating ciphertext and outputting the ciphertext. N is a non-prime integer (preferably the product of two primes p and q), y is an element in multiplicative group of integers modulo N, and k is an integer larger than 1. Decryption of ciphertext c using private key is performed by recovering such that holds and outputting plaintext m, wherein denotes the 2k-th power residue symbol modulo p, which is defined. Also provided are an encryption device (100) and a decryption device (100). The encryption scheme provides better bandwidth than the Goldwasser-Micali encryption scheme.