NTT develops a new cryptographic technique to enhance the security of post-quantum public-key encryption

Nippon Telegraph and Telephone Corporation (NTT) has developed a new cryptographic technique to enhance the security of post-quantum public-key encryption*1. Adapting the new technique, we can easily enhance the security of a certain type of post-quantum public-key encryption scheme without any drastic loss of efficiency.

The details of these research results were presented at EUROCRYPT 2018*2, which is one of the top international conferences organized by the International Association for Cryptologic Research (held in Israel, from April 29 to May 3).

Background

Public-key encryption is necessary to protect private or highly confidential information such as credit card numbers transmitted over the Internet. For example, HTTPS (often indicated by the padlock icon in web browsers) uses several cryptographic primitives including public-key encryption. However, it is thought that quantum computers will break widely used public-key encryption schemes such as RSA and ECC. Therefore, we should replace such cryptosystems with cryptosystems that are considered to be resistant to quantum attacks (post-quantum cryptosystems) before large-scale practical quantum computers become available. The National Institute of Standards and Technology (NIST) has been working on post-quantum cryptography standardization since 2015.

Secure communications in the real world require public-key encryption schemes that not only achieve confidentiality but also prevent messages from being forged meaningfully. We call such security "chosen-ciphertext attack (CCA) security"*3. In the past, several cryptographers and security engineers reported vulnerabilities of systems/protocols that use public-key encryption schemes whose CCA-securities are not proven. (For example, Bleichenbacher reported chosen-ciphertext attacks against RSA PKCS#1v1.5*4.) Therefore, CCA-security is becoming a de facto standard security notion of public-key encryption. To continue secure communications after the quantum computer age, we will require CCA-secure post-quantum public-key encryption.

Features

NTT has developed a new security-enhancing technique that converts a post-quantum public-key encryption scheme that is not proven to be CCA-secure into a CCA-secure one. Adapting the new technique, we can easily enhance the security of a certain type of post-quantum public-encryption scheme without any drastic loss of efficiency. The new technique can be combined with several existing post-quantum public-key encryption schemes. For example, at least seven candidates of NIST post-quantum cryptography standardization can adopt the new technique.

Key Points

Cryptographers and security engineers have studied conversions from a public-key encryption scheme whose CCA-security is not proven to CCA-secure public-key encryption scheme. Since 2010, they have further examined whether such conversions will be secure or not even after quantum computers are developed. Several researchers have succeeded in showing that such conversions are effective against attacks using quantum computers. Unfortunately however, they incur the loss of efficiency because they require the security level to be degraded from, say, 128- to 64-bit security. If we accept this loss of efficiency, we will use inefficient public-key encryption schemes. This means that a public key, a secret key, and a ciphertext become long and encryption and decryption take longer and require more energy. Thus, we prefer to convert a public-key encryption scheme whose CCA-security is not proven into a CCA-secure one without the loss of efficiency. Previously, no such conversions have been effective against attacks using quantum computers. NTT has succeeded in developing such conversion.

Our new conversion enhances the security by adding to the decryption process a system that detects falsified ciphertext as existing conversions do. In the existing conversions, when the system in decryption detects invalidity of a given ciphertext, the system outputs an error symbol different from messages. This error symbol leaks information of whether a ciphertext generated by a (quantum) attacker is invalid or not because an error symbol is easily distinguished from messages. The leakage allows a (quantum) attacker to speed up attacks. To prevent this speed up, previous researchers prepared a public-key encryption scheme with a higher security level, but this incurs the loss of efficiency.

In our new technique, when the system in decryption detects invalidity of a given ciphertext, the system outputs a pseudo-random message instead of an error symbol. A (quantum) attacker cannot determine whether the ciphertext it generated is valid or invalid. Using this idea (and more), we succeed in proving that the public-key encryption scheme obtained by our conversion is CCA-secure against quantum attackers without loss of efficiency.

Plans

NTT will continue to research post-quantum cryptography and develop cryptographic technology for secure communications even after quantum computers are developed.

Keywords: