Fujitsu Breaks Next Generation Cryptography Record
Fujitsu Laboratories Limited, National Institute of Information and Communications Technology (NICT) and The Japanese Kyushu University 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.
Pairing-based cryptography is 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 a.
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. The researchers proved that pairing-based cryptography of this length was fragile and could actually be broken in 148.2 days.
The result is used as the basis of selecting secure encryption technology and canbe proved useful in the standardization of next-generation cryptography in electronic government systems in Japan and international standardization organizations.
"Pairing-based" cryptography systems 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.
As for a security evaluation of cryptographies, the researchers 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 it was 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). The researchers overcome this problem by making good use of various new technologies such as a technique optimizing parameter setting that uses computer algebra, a two dimensional search algorithm extended from the linear search, and by using 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.
"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," Fujitsu said. "We will continue to move forward on research that pushes the boundary of the secure use of cryptography."
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. The researchers proved that pairing-based cryptography of this length was fragile and could actually be broken in 148.2 days.
The result is used as the basis of selecting secure encryption technology and canbe proved useful in the standardization of next-generation cryptography in electronic government systems in Japan and international standardization organizations.
"Pairing-based" cryptography systems 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.
As for a security evaluation of cryptographies, the researchers 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 it was 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). The researchers overcome this problem by making good use of various new technologies such as a technique optimizing parameter setting that uses computer algebra, a two dimensional search algorithm extended from the linear search, and by using 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.
"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," Fujitsu said. "We will continue to move forward on research that pushes the boundary of the secure use of cryptography."
