PROBLEM TO BE SOLVED: To provide a public key encryption method which is IND-CCA security on a standard computer model and does not damage security reduction even in a multiuser environment. SOLUTION: A key generator 110 prepares a public key and a secret key designed to return encryption security to the difficulty of a Diffie-Hellman decision problem and to the security of a family of functions satisfying a specific condition. An encryption device 130 generates cryptography from a message sentence by using the public key prepared by the key generator 110. Then, a decryption device 150 decrypts the cryptography generated by the encryption device 130 by using the secret key prepared by the key generator 110. COPYRIGHT: (C)2011,JPO&INPIT