June 18, 2012
Fujitsu Laboratories Ltd.
National Institute of Information and Communications Technology
Kyushu University

Establishes security of pairing-based cryptography and contributes to its standardization as the next-generation cryptography

June 18, 2012 - Fujitsu Laboratories Limited(), National Institute of Information and Communications Technology (NICT)() and Kyushu University(3) jointly broke a world cryptography record with the successful cryptanalysis of a 278-digit (923-bit)-long pairing-based cryptography(4), which is now becoming the next generation cryptography standard.

Until now, cryptanalysis of pairing-based cryptography of this length was thought impossible as it was estimated to take several hundred thousand years to break. Indeed, despite numerous efforts to use and spread this cryptography at the development stage, it wasn't until this new way of approaching the problem was applied that it was proven that pairing-based cryptography of this length was fragile and could actually be broken in 148.2 days. This result is used as the basis of selecting secure encryption technology, and is proving useful in the standardization of next-generation cryptography in electronic government systems in Japan and international standardization organizations.

Background

Many cryptography systems are used from the viewpoint of information security on a modern information system. Recently, much attention has been paid to the new "pairing-based" cryptography system, which is being standardized as a next-generation encryption system. The technology is attractive as it can be used for various useful applications such as "Identity-based encryption()", "keyword searchable encryption()", and "functional encryption()", which were impossible using previous public key cryptography().

Technological Issues

As cryptanalytic techniques and computers become more advanced, cryptanalytic speed accelerates, and conversely, cryptographic security decreases. Therefore, it is important to evaluate how long the cryptographic technology can be securely used. On the other hand, pairing-based cryptography has not advanced, so it was premature to evaluate its security against a new attack method.

New Achievements

As for a security evaluation of cryptographies, we succeeded with the cryptanalysis of the pairing-based cryptography of 278 digits (923 bits) by using 21 personal computers (252 cores) in 148.2 days. The cryptanalysis is the equivalent to spoofing the authority of the information system administrator. As a result, for the first time in the world we proved that the cryptography of the parameter was vulnerable and could be broken in a realistic amount of time.

This was an extremely challenging problem as it required several hundred times computational power compared with the previous world record of 204 digits (676 bits). We were able to overcome this problem by making good use of various new technologies, that is, a technique optimizing parameter setting that uses computer algebra, a two dimensional search algorithm extended from the linear search, and by using our efficient programing techniques to calculate a solution of an equation from a huge number of data, as well as the parallel programming technology that maximizes computer power.

Future Prospects

This result is not just a new world record of cryptanalysis, it also means the acquisition of valuable data that forms a technical foundation on which to estimate selection of secure encryption technology or the appropriate timing to exchange a key length. We will continue to move forward on research that pushes the boundary of the secure use of cryptography.

Glossary and Notes Tatsuo Tomita (Headquarters: Kawasaki, Kanagawa Prefecture) Dr. Hideo Miyahara Dr. Setsuo Arikawa A next-generation cryptography (proposed in 2001) based on a map called pairing, which offers many useful functionalities that could not be achieved by previous public-key cryptography. The security of pairing-based cryptography is based on the intractability of discrete logarithm problem (DLP). DLP is a problem to compute d such that a = gd for given g and aA type of public-key encryption in which the public key of a user is some unique information about the identity of the user (e.g. a user's email address). It does not require authentication of public keys unlike former public-key cryptosystems. An encryption scheme which enables searching keywords on encrypted data. An encryption scheme where an author of a document can specify access control info in a predicate logic using attributes and embed it into an encrypted document. A cryptographic system requiring two separate keys, one to encrypt the plaintext, and one to decrypt the ciphertext. One of these keys is public and the other is kept private. Introduced by Diffie and Hellman in 1976. RSA and Elliptic curve cryptography (ECC) are typical examples. About Fujitsu

Fujitsu is the leading Japanese information and communication technology (ICT) company offering a full range of technology products, solutions and services. Over 170,000 Fujitsu people support customers in more than 100 countries. We use our experience and the power of ICT to shape the future of society with our customers. Fujitsu Limited (TSE:6702) reported consolidated revenues of 4.5 trillion yen (US$54 billion) for the fiscal year ended March 31, 2012. For more information, please see http://www.fujitsu.com.

About Fujitsu Laboratories

Founded in 1968 as a wholly owned subsidiary of Fujitsu Limited, Fujitsu Laboratories Limited is one of the premier research centers in the world. With a global network of laboratories in Japan, China, the United States and Europe, the organization conducts a wide range of basic and applied research in the areas of Next-generation Services, Computer Servers, Networks, Electronic Devices and Advanced Materials. For more information, please see: http://jp.fujitsu.com/labs/en.

About NICT

The National Institute of Information and Communications Technology (NICT) is the independent administrative agency of ICT in Japan. NICT promotes the full spectrum of research and development from basic to applied research with an integrated perspective, and thus promotes the advancement of Japan as an intellectual nation that leads the international community. Moreover, NICT forms close ties with the academic and business communities in Japan as well as with research institutes overseas and returns its R&D findings to society in a broad range of fields. For more information, please visit www.nict.go.jp/en/index.html.

About Kyushu University

Kyushu University is a national, comprehensive and one of the top research universities in Japan. The university is located in Fukuoka, the largest and most active business center in Kyushu Island. Founded in 1911, Kyushu University has established itself as a leader in education and research not only in Japan but throughout the world. Celebrated its centennial in 2011, today we have 11 undergraduate schools, 18 graduate schools and more than 50 research institutes and centers. And the university consists of roughly 2,300 academic staff, 2,700 non-academic staff and 19,000 students on 6 campuses.
For more information, please visit www.kyushu-u.ac.jp.

Technical Contacts Press Contacts

All other company or product names mentioned herein are trademarks or registered trademarks of their respective owners. Information provided in this press release is accurate at time of publication and is subject to change without advance notice.

distributed by