Achievement Award 2013

Achievement Award

Pioneer research that leads the world record in cryptanalysis, and establishes security of next-generation cryptography

Tsuyoshi Takagi, Takeshi Shimoyama, Naoyuki Shinohara

Tsuyoshi Takagi

Takeshi Shimoyama

Naoyuki Shinohara

　Modern information systems have numerous applications that require use of confidential information; for example, Internet shopping, Internet banking, and electronic submissions to public agencies. In addition, protection of privacy data and corporate secret data coexisting with use-for-profit is becoming a problem with the spreading use of various services that utilize cloud systems through such vehicles as smart phones and tablet PCs. The next-generation cryptography “pairing-based cryptography,” which has wide application, is attracting attention as one of the best solutions to this problem. Pairing-based cryptography is a type of public key cryptosystem that uses bi-linear mapping, which is called a pairing on an elliptic curve. It can make possible a number of novel and flexible services, such as “searchable encryption”, “functional encryption” and “ID-based encryption”, which could not be provided through conventional public-key cryptography. This encryption technology is expected to offer new services and improved convenience and security of cloud type information. However, pairing-based cryptography does not have a long history in cryptography, and its security has not yet been deeply studied.
　The winners concentrated their respective specialized skills in cryptology, cryptographic skill, number theory, and computer programming to achieve a cryptanalysis world record pairing-based cryptosystem of 278 digits (923 bits), which had been thought to be impossible as it was estimated that the attack would take several hundred thousand years to break. Concurrently, they succeeded in accurately estimating the calculation resource and time necessary for the cryptanalysis. (Figure 1)
　In their experiment of breaking the pairing-based cryptography, they used the “function field sieve,” which is currently the fastest algorithm for solving the discrete logarithm problem over the characteristic 3 which is related to security of the cryptosystem. The function field sieve method comprises four processes: the polynomial selection part, the relation search part, the linear algebra part, and the individual discrete logarithm part. It is known that a number of computational complexities are especially needed for the relation search part and processing of the linear algebra part.
　There were two main points to their success in the cryptanalysis. First, they extended the previous method “line sieve” for the data search to the two-dimensional space called “lattice sieve” and they developed an algorithm that reduced the range of each degree in the searched polynomial space. Second, they proposed several mathematical formulas with which they could estimate in advance the required computational powers for their experiment of the relation search part and the linear algebra part, and then they selected the initial parameter of the smallest computational power from the theoretically possible options. (Figure. 2)

Fig 1. World records in solving the discrete logarithm problem

Fig 2. Initial value search that minimizes the total complexity

　It is possible to accurately estimate the required computational resources and time from their world record cryptanalysis of pairing-based cryptosystem; namely, they have obtained important and persuasive cryptanalysis data for selecting secure key-lengths that can be used in the future. For instance, it is shown that pairing-based cryptography whose discrete logarithm problem sizes are 1011 digits or more does not arrive at the computational complexity necessary for cryptanalysis, even if the highest-performance super computer 20 years from now were to be occupied for one year, assuming that capability improvement of the highest-performance super computer will eventually reach this level through the cryptographic skill used on this occasion. This result can lead the decision of the parameters for using it securely in advancing practical utilization of pairing-based cryptosystems.
　As mentioned above, they have been acknowledged as having promoted the spread of next-generation cryptography, and to have led this outstanding achievement of a technology that has contributed to secure utilization of cloud computing. Their work has been recognized with the IPSJ Kiyasu Special Industrial Achievement Award 2012 and the 12th Docomo Mobile Science Award (Advanced Institute for Materials Research). Their distinguished achievements are highly notable and deserving of this achievement award.

References

(１)　Takuya Hayashi, Takeshi Shimoyama, Naoyuki Shinohara, Tsuyoshi Takagi, “Breaking Pairing Based Cryptosystems Using ηT Pairing over GF(3＾97)”, ASIACRYPT 2012, Springer LNCS 7658, pp.43-60, 2012.
(２)　Naoyuki Shinohara, Takeshi Shimoyama, Takuya Hayashi, Tsuyoshi Takagi, “Key Length Estimation of Pairing-based Cryptosystems Using ηT Pairing Over GF(3＾n)”, IEICE Transactions, Vol.E97-A, No.1, pp.236-244, 2014.
(３)　Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin'ichiro Matsuo, Masaaki Shirase, Tsuyoshi Takagi, “Solving a 676-bit Discrete Logarithm Problem in GF(3＾(6n))”, Transactions Vol.E95-A, No.1, pp.204-212, 2012.
(４)　Tadashi Iyama, Shinsaku Kiyomoto, Kazuhide Fukushima, Toshiaki Tanaka, Tsuyoshi Takagi, “Implementation of Pairing Based Cryptosystem on Mobile Phones”, IEICE Transactions, Vol. J95-A, No.7, pp.579-587, 2012.
(５)　Jean-Luc Beuchat, Hiroshi Doi, Kaoru Fujita, Atsuo Inomata, Piseth Ith, Akira Kanaoka, Masayoshi Katouno, Masahiro Mambo, Eiji Okamoto, Takeshi Okamoto, Takaaki Shiga, Masaaki Shirase, Ryuji Soga, Tsuyoshi Takagi, Ananda Vithanage, Hiroyasu Yamamoto, “FPGA and ASIC Implementations of theηT Pairing in Characteristic Three” Computers & Electrical Engineering, Vol.36, No.1, pp.73-87, 2010.
(６)　Takuya Hayashi, Masaaki Shirase, Tsuyoshi Takagi, “An Experiment on Implementation of the Function Field Sieve over GF(3＾n)”, IPSJ Journal, Vol.50, No.9, pp.1956-1967, 2009.
(７)　Jean-Luc Beuchat, Nicolas Brisebarre, Jérémie Detrey, Eiji Okamoto, Masaaki Shirase, Tsuyoshi Takagi, “Algorithms and Arithmetic Operators for Computing the ηT Pairing in Characteristic Three”, IEEE Transactions on Computers, Vol.57, No.11, pp.1454-1468, 2008.