Cutting-edge Research on Cryptography Theory in Response to Changes in Computing Environments

1. Background

The notion of security in cryptography is defined on the basis of the amount of computational resources (i.e., memory and computational speed) that an attacker can have. In the 1990s, when the Internet began to spread, a public key of Rivest–Shamir–Adleman (RSA) encryption, having about 512 bits, was considered secure. In 2001, when the Electronic Signature Law was enacted in Japan, public keys are required to be 1024 bits, and in the revision to that law, which has been being considered since 2008, they will soon be required to be at least 2048 bits.

Many cryptosystems are moving toward the more efficient elliptic curve approach. More advanced public key cryptography (such as identity-based cryptography based on pairing groups over elliptic curves), efficient digital signature schemes protecting privacy of the signer, and highly efficient non-interactive zero-knowledge proof systems have been developed. Cryptography naturally has the ability to control access to information through key-management methods. Regarding conventional cryptographic communication, the sender and receiver of information have a one-to-one relation. In the more complex scenario of encrypted communication, however, encrypted data are stored in the cloud and the embedded information is accessible by multiple recipients satisfying the condition specified by the sender. Some advanced cryptosystems, such as attribute-based encryption (ABE), have been developed for such purposes.

It has been shown that if a general-purpose quantum computer is developed that can handle a large number of qubits with sufficient precision so that Shor’s algorithm can be executed, it will be able to break efficient public-key cryptographic schemes, such as RSA encryption and Diffie–Hellman key exchange, currently in wide use [1]. Even if such advanced quantum computers do not become viable for several decades, it is necessary to develop cryptographic techniques that are secure against the threat such computers pose—so-called post-quantum cryptography—without waiting for quantum computers to become a reality. In fact, much research and development (R&D) and standardization of post-quantum cryptography is already underway. As well as the motive of the providers of cryptographic systems, there are two practical reasons for such effort. The first is that a new encryption method takes a very long time from development to deployment in the real world. That is, updating a system that appears to be working to a new system that is not compatible is not something that every user can do in a short time. The other reason is the concern that current privacy will be compromised by future advances in attack techniques in a manner called long-term security compromise. It is a concern that even encrypted communications may be intercepted and stored for long periods, and their content may be exposed by quantum computers created in the future. In other words, for content that would be difficult to leak after several decades, a quantum-computer attack is a threat that must be addressed in the present. Post-quantum cryptography is not executed on a quantum computer; instead, it is executed on current computers. It is therefore necessary to consider security in terms of post-quantum cryptography in the current computer environment.

The activities of NTT Secure Platform Laboratories (SC Labs) regarding quantum information processing technology are first described. The latest topics concerning post-quantum cryptography are then discussed. Finally, SC Labs’ latest research results on ABE, which is one of the functions of conventional public-key cryptography, are presented.

2. Quantum information processing

3. Toward quantum-secure networks

An example of a new security technology that uses quantum information processing is quantum cryptography (or quantum key distribution). Eavesdropping can be detected if the quantum state is destroyed when measured unnecessarily, so, secure key distribution is possible in principle. However, there are three problems with the current technology: (i) vulnerability to loss, (ii) practically limited communication distance (up to about 100 km), and (iii) inability of networking. The solution to these problems is using a quantum repeater, which makes it possible to control quantum states of light and matter with high precision and to correct quantum errors in a manner that can withstand losses. In fact, a quantum repeater is therefore a technology that is fairly comparable with constructing small to medium-scale quantum computers. To implement a quantum repeater, we have to conduct almost the same R&D as that for implementing quantum computers. At SC Labs, we are working on controlling the quantum states of light and atoms with the high precision required for quantum repeaters while increasing the scale of the quantum states that can be handled. SC Labs is also participating in the CREST project of the Japan Science and Technology Agency (JST), in which we are engaged in R&D using cavity quantum electrodynamics—which enables high-precision interaction between light and atoms.

4. Toward quantum-resistant (post-quantum) cryptography: Secure implementation and contribution to standardization

In addition to conventional cryptographic techniques such as RSA cryptography and elliptic-curve cryptography, post-quantum cryptography, which is considered to be durable against quantum cryptography, has been studied for decades. For the most basic functions, namely, encryption and signature schemes, theoretical schemes based on problems that are difficult to solve with quantum computers have been known for a long time. However, the performance of these schemes, such as processing speed and communication traffic, is remarkably inferior to that of RSA cryptography and elliptic-curve cryptography, so these schemes have been determined impractical, and implementations of post-quantum cryptography are scarce.

As the emergence of quantum computers has recently become a visible threat, this threat has finally started to be seriously considered. Proposing and implementing faster and higher-performance post-quantum-cryptography technologies have become important research topics. In particular, in lattice-based cryptography, which is regarded as promising for post-quantum cryptography, new schemes have been proposed and implemented by adding several ideas and optimizations to conventional schemes that have strong security foundations, and they have demonstrated performance comparable to that of RSA encryption. Implementation experiments on virtual private network software have also begun [3].

While theoretical security foundations have been thoroughly investigated, vulnerabilities concerning implementation (such as side-channel attacks and fault attacks) have not been considered. Moreover, efficient new schemes often require sampling from discrete Gaussians distributions and rejection sampling, which are not used in the conventional cryptographic schemes; thus, secure implementations of them are new challenges. To address these implementation issues, SC Labs assessed security against implementation attacks, especially against the lattice-based signature scheme, and discovered numerous vulnerabilities [4, 5, 6, 7, 8]. For example, in a previous study [4], which targeted multiple implementations of the BLISS scheme, a fast lattice-based signature, we showed that measuring power consumption and processing time when a signature is generated makes it possible to completely recover the secret key by using algebra and number theory. We are proposing countermeasures and implementation schemes to overcome the above-mentioned vulnerabilities and are verifying their security. We also proposed and implemented lattice-based signature schemes that provide strong security against implementation attacks while maintaining the highest level of performance [9, 10, 11].

The above-mentioned studies had a significant impact on the ongoing post-quantum cryptography standardization process launched by the National Institute of Standards and Technology (NIST) in 2016 (hereafter, NIST Post-Quantum Cryptography (PQC) standardization). In particular, the implementation vulnerabilities of the BLISS scheme [4] are being considered as implementation threats in the design policy of a candidate called Dilithium. According to reported results [4], almost all lattice-based signatures in the NIST PQC standardization avoided sampling from discrete Gaussian distribution. Even after the start of the NIST PQC standardization, SC Labs contributed to the successful results regarding safe implementation of Dilithium and Falcon [6, 8, 10, 11] and to completely defeating and eliminating a scheme with weak security foundations [12].

5. Recent topic 1: Quantum computers and cryptography

6. Recent topic 2: ABE

Although public-key cryptography can be divided into several main themes, this article focuses on one, attribute-based cryptography with practical efficiency. For public-key cryptography, a sender of information encrypts the information with a recipient’s public key into a ciphertext and only the recipient who has the corresponding private key can decipher the ciphertext to access the information. ABE schemes allow the sender to freely specify the recipient without limiting the information to a single recipient. More specifically, a policy is embedded in the ciphertext, and attributes of the recipient are embedded in the secret key. A recipient can then receive information only if their attributes match the policy in the ciphertext. Therefore, the logic is embedded in the ciphertext and secret key, and it is possible to restrict information exchange.

Many ABE schemes have been proposed; nevertheless, they are insufficient in terms of implementing them in actual systems. One problem is scalability of attributes. Many ABEs require that all attributes used are determined at the initialization of a system, that is, we can thereafter no longer add attributes. To attain scalability, it is desirable to be able to add attributes at any time. Another problem is data size. In the case of some methods, the size of the ciphertext increases in proportion to the size of the embedded policy and number of attributes used. This dependence has been undesirable because it occupies storage. Therefore, various performance criteria have been considered in regard to actual use; however, an ABE scheme that reaches practically desirable levels in relation to all those criteria had not yet been proposed. Given this situation, we developed an ABE scheme that possesses all the properties desirable in terms of practicality.

References

[1]	P. W. Shor, “Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput., Vol. 26, No. 5, pp. 1484–1509, 1997.
[2]	F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum Supremacy Using a Programmable Superconducting Processor,” Nature, Vol. 574, pp. 505–510, 2019.
[3]	Post-quantum Cryptography VPN, https://github.com/Microsoft/PQCrypto-VPN
[4]	T. Espitau, P.-A. Fouque, B. Gerard, and M. Tibouchi, “Side-channel Attacks on BLISS Lattice-based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers,” Proc. of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 1857–1874, Dallas, Texas, USA, Oct. 2017.
[5]	J. Bootle, C. Delaplace, T. Espitau, P.-A. Fouque, and M. Tibouchi, “LWE Without Modular Reduction and Improved Side-channel Attacks against BLISS,” Advances in Cryptology, ASIACRYPT 2018, LNCS, Vol. 11272, pp. 494–524, Springer, 2018.
[6]	T. Espitau, P.-A. Fouque, B. Gérard, and M. Tibouchi, “Loop-abort Faults on Lattice-based Signature Schemes and Key Exchange Protocols,” IEEE Trans. Comput., Vol. 67, No. 11, pp. 1535–1549, 2018.
[7]	M. Tibouchi and A. Wallet, “One Bit Is All It Takes: A Devastating Timing Attack on BLISS’s Non-constant Time Sign Flips,” Journal of Mathematical Cryptology, Special Issue on MathCrypt 2019, De Gruyter, to appear.
[8]	P.-A. Fouque, P. Kirchner, M. Tibouchi, A. Wallet, and Y. Yu, “Uprooting the Falcon Tree?: How to Recover Secret Keys from Gram-Schmidt Norms,” IACR Cryptology ePrint Archive, Report 2019/1180, 2019.
[9]	G. Barthe, S. Belaïd, T. Espitau, P.-A. Fouque, B. Grégoire, M. Rossi, and M. Tibouchi, “Masking the GLP Lattice-based Signature Scheme at Any Order,” Advances in Cryptology – EUROCRYPT 2018, LNCS, Vol. 10821, pp. 354–384, Springer, 2018.
[10]	P.-A. Fouque, B. Gérard, V. Migliore, and M. Tibouchi, “Masking Dilithium: Efficient Implementation and Side-channel Evaluation,” Applied Cryptography and Network Security, ACNS 2019, LNCS, Vol. 11464, pp. 344–362, Springer, 2019.
[11]	G. Barthe, S. Belaid, T. Espitau, P.-A. Fouque, M. Rossi, and M. Tibouchi, “GALACTICS: Gaussian Sampling for Lattice-based Constant-time Implementation of Cryptographic Signatures, Revisited,” Proc. of ACM CCS 2019, pp. 2147–2164, London, UK, Nov. 2019.
[12]	J. Bootle, M. Tibouchi, and K. Xagawa, “Cryptanalysis of Compact-LWE,” Topics in Cryptology – CT-RSA 2018, LNCS, Vol. 10808, pp. 80–97, Springer, 2018.
[13]	A. Hosoyamada, Y. Sasaki, S. Tani, and K. Xagawa, “Improved Quantum Multicollision-finding Algorithm,” Post-Quantum Cryptography, PQCrypto 2019, LNCS, Vol. 11505, pp. 350–367, Springer, 2019.
[14]	A. Hosoyamada and Y. Sasaki, “Cryptanalysis against Symmetric-key Schemes with Online Classical Queries and Offline Quantum Computations,” Topics in Cryptology, CT-RSA 2018, LNCS, Vol. 10808, pp. 198–218, Springer, 2018.
[15]	X. Bonnetain, A. Hosoyamada, M. Naya-Plasencia, Y. Sasaki, and A. Schrottenloher, “Quantum Attacks without Superposition Queries: The Offline Simon’s Algorithm,” Advances in Cryptology, ASIACRYPT 2019, LNCS, Vol. 11921, pp 552–583, Springer, 2019.
[16]	T. Saito, K. Xagawa, and T. Yamakawa, “Tightly-secure Key-encapsulation Mechanism in the Quantum Random Oracle Model,” Advances in Cryptology, EUROCRYPT 2018, Part III, LNCS, Vol. 10822, pp. 520–551, 2018.
[17]	K. Xagawa and T. Yamakawa, “(Tightly) QCCA-secure Key-encapsulation Mechanism in the Quantum Random Oracle Model,” Post-Quantum Cryptography, PQCrypto 2019, LNCS, Vol. 11505, pp. 249–268, Springer, 2019.
[18]	A. Hosoyamada and K. Yasuda, “Building Quantum-one-way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions,” Advances in Cryptology, ASIACRYPT 2018, Part I, LNCS, Vol. 11272, pp. 275–304, 2018.
[19]	A. Hosoyamada and T. Iwata, “4-Round Luby-Rackoff Construction is a qPRP,” Advances in Cryptology, ASIACRYPT 2019, LNCS, Vol. 11921, pp. 145–174, Springer, 2019.
[20]	M. Hhan, K. Xagawa, and T. Yamakawa, “Quantum Random Oracle Model with Auxiliary Input,” Advances in Cryptology, ASIACRYPT 2019, LNCS, Vol. 11921, pp 584–614, Springer, 2019.