Eiichiro FUJISAKI
Tatsuaki OKAMOTO
The concept of public-key cryptosystems was first introduced in the pioneer work by Whitfield Diffie and Martin Hellman in 1976. Since then, it has completely changed the world. Indeed, without this mechanism, it would be difficult to protect the privacy of communications in large-scale networks such as the Internet.
There are many security classes for public-key cryptosystems. Among them, the security class, called indistinguishability against chosen-ciphertext attack (IND-CCA), is known to be the strongest, but public-key encryption schemes in practical use are now considered to be mandatory to satisfy this security class, after the chosen-chiphertext attack against RSA PKCS#1 encryption (included in SSL) by Bleichenbacher and the theory of Canettifs universal composability framework. A public-key cryptosystem is called IND-CCA secure if an attacker cannot learn any partial information about the plaintext behind the target ciphertext, even if it can get the decryption of any ciphertext other than the target ciphertext (as shown in Figure 1).
The achievement of the recipients is that they have proposed two generic transformations that enhance the security of public-key cryptosystems to efficiently achieve IND-CCA security.
Scheme 1 [1,3]: A public-key cryptosystem is called IND-CPA secure if any attacker who does not access the decryption oracle cannot learn any partial information about the encrypted plaintext target. It is known that IND-CPA security is strictly weaker than IND-CCA security. The recipients have proposed in [1] a generic transformation that converts any IND-CPA secure public-key encryption scheme into an IND-CCA secure one with very small cost. Since part of the plaintext space of the original scheme is used for a random salt, the size of the plaintext that can be encrypted is slightly smaller, but the size of the ciphertext is not different from that of the original scheme. The cost of encryption is almost the same as that of the original method, while decryption requires one additional encryption cost in addition to decryption under the original method. This scheme has been highly evaluated. Indeed, it was selected for the PKC Test of Time Award by the International Association for Cryptologic Research (IACR) in 2019.
Scheme 2 [2,4]: If any attacker who does not access the decryption oracle cannot completely decrypt the ciphertext and retrieve the full plaintext, the public-key cryptosystem is called OW-CPA secure. OW-CPA security is the weakest among all the security classes for public-key cryptosystems. In [2], the recipients have presented a generic transformation that can efficiently convert any OW-CPA secure public-key encryption scheme into an IND-CCA secure one. Compared with Scheme 1, the size of the ciphertext is larger by the size of the plaintext, but the computational cost of encryption and decryption is not different. Combined with Diffie-Hellman key exchange, this scheme received the Nikkei BP Technology Award 2000. This combination has been standardized in ISO/IEC 18033 and was also selected as the first recommendation for public-key encryption in the NESSIE (EU encryption standard) project [5]. Scheme 2 has been extensively cited in literature. In the ongoing post-quantum cryptography standardization project by the U.S. National Institute of Standards and Technology (NIST), most of the entries in the public-key cryptosystem employ Scheme 2 (including its variants) as a component [6].
In conclusion, the recipients have invented two methods to efficiently convert any public-key cryptosystem into a stronger one, which have provided a great influence on the theory and standardization of public-key cryptography thereafter. Thus, they definitely deserve the IEICE Achievement Award.
