(Efficient Probabilistic Public-Key Encryption)

More information could be found in Dr. Okamoto's paper given here as pdf or postscript or zipped postscript format

Introduction: (http://info.ntt.co.jp/news/news98e/980416.html)

NTT Develops Secure Public-Key Encryption Scheme

Nippon Telegraph and Telephone Corporation (NTT) announced today the development of Efficient Probabilistic Public-Key Encryption (EPOC), a highly secure and mathematically verified public-key encryption scheme that encrypts information on the transmission side with a public-key (encryption key) and then decrypts it on the receiver side with a secret-key (decryption key).


Encryption technology has become necessary to prevent information on the Internet from being monitored by others without authorization. Public-key encryption is being widely researched as a practical means of encrypting communication for security.


The paramount feature of any public-key encryption schemes is ensuring that figuring out the decryption key from the encryption key is as difficult as possible, to prevent unauthorized use of ciphered information. The RSA [1] scheme uses factoring and the elliptic curve encryption scheme [2] uses elliptic curve discrete logarithms, both of which can take a supercomputer a very long time to determine the key. It has not been verified, however, that either scheme provides the necessary security to prevent ciphered information from being broken by a method other than factoring or elliptic curve discrete logarithms. The Rabin encryption scheme [3], which also uses factoring, offers no algorithm other than factoring for computing the complete plain-text, but it has not been proven that any bit of plain-text cannot be computed.


EPOC is a practical scheme in that the computer computation workload for encrypting and decrypting is about the same as that for the RSA and elliptic curve encryption schemes. Also, EPOC is a highly secure scheme which uses a trapdoor discrete logarithm [4] as the key mathematical technique and can be broken only by factoring. Factoring is difficult to accomplish, even with a supercomputer, and the probability that an efficient solution to factoring will be found soon is very low, because mathematicians have been studying the problem for years. EPOC ensures that partial, as well as whole, texts cannot be broken.

Finally, EPOC uses probabilistic encryption, so re-encrypted text is encrypted differently each time, unlike the Rabin and RSA scheme, which use deterministic encryption. NTT now plans to incorporate EPOC in systems for enhanced security on the Internet. Public-key encryption is used primarily for key distribution, because computation load is greater than that for secret-key encryption [5], so EPOC will be used in existing encryption modules for key distribution.


Other applications will also be developed. In particular, EPOC is suitable for electronic voting and anonymous telecommunication since it has a homomorphic property, unlike the RSA, Rabin and elliptic curve encryption schemes. The theoretical details will be presented at Eurocrypt '98 in Finland this June.



 [1]: The RSA scheme was developed by Rivest, Shamir, and Adleman in 1978 and is based on the difficulty of factoring. It was the first public-key encryption scheme.

[2]: The elliptic curve encryption scheme was proposed independently by Miller and Koblitz in 1985 and is based on the difficulty of elliptic curve discrete logarithms. The basic technique is based on a scheme developed by Diffie and Hellman in 1976.

[3]: The Rabin scheme was developed by Rabin in 1979 and is based on the difficulty of factoring. It was the first public-key encryption scheme to verify the impossibility of breaking a complete text without factoring the public-key.

[4]: A trapdoor discrete logarithm is a newly discovered discrete logarithm problem that can be solved only if a secret-key is known.

[5]: Secret-key encryption differs from public-key encryption in that the sender and the receiver use the same key for encryption and decryption.