Home > Press Release > NICT, Kyushu University and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography
NICT, Kyushu University and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography
Establishes security of pairing-based cryptography and contributes to its standardization as the next-generation cryptography
The National Institute of Information and Communications Technology (NICT)*1, Kyushu University*2, and Fujitsu Laboratories Limited*3 jointly broke a world cryptography record with the successful cryptanalysis of a 278-digit (923-bit)-long pairing-based cryptography, 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.
About Us
Reference Materials
- Optimizing the initial parameters by mathematical formulas
We proposed several mathematical formulas with which we can estimate the required computational powers of our experiment in advance, and then we have selected the initial parameter of the smallest computational power from the theoretically possible ones. - Data searching technology using two-dimensional space
Our cryptanalysis has to search the seed of the solution from the huge data base. The previous world-top record used the “line sieve” for this data search, but we extended it to the two-dimensional space called “lattice sieve”, and then its speed was accelerated dozens of times by using our own modification. - Computing the solution of equations of massive numerical data
We applied the “Lanczos method” for computing the solution of huge systems of equations obtained from massive numerical data. We improved the computational speed several times by optimizing the program for our computational environments. - Parallel programming for maximal usage of our computational power
Our programming code achieved the maximal potential of our computational resources by using the SIMD operation equipped in the recent general-purpose computers. This optimization made our cryptanalysis several time faster.
The main roles of the organizations are as follows.
- NICT : Establishment of a theory of reducing the computing time, optimization of the parameter of the attacking algorithms, preparation of computers
- Kyushu University : Management of project promotion, programming, administration of the computers, execution of the computer experiment
- Fujitsu Laboratories : Design of algorithms, parallelization of the program, management of the promotion of execution of the computer experiment
Glossary
Technical Contacts
Software Systems Laboratories Secure Computing Laboratory,
Takeshi Shimoyama, Ph.D.
Tel: 044-754-2681
E-mail:
Institute of Mathematics for Industry
Professor Tsuyoshi Takagi
Tel: 092-802-4456
E-mail:
Network Security Research Institute, Security Fundamentals Laboratory,
Naoyuki Shinohara, Ph.D.
Tel: 042-327-5343
E-mail:
Press Contact
Public and Investor Relations Division
Inquiries: https://www-s.fujitsu.com/global/news/contacts/inquiries/index.html
Public Relations Office
Tel:092-642-2106
E-mail:
Public Relations Department
Tel:042-327-6923
E-mail: