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.

**Background**

**Technological Issues**

**New Achievements**

**Future Prospects**

### About Us

**About Fujitsu**

**About Fujitsu Laboratories**

**About Kyushu University**

**About NICT**

### Reference Materials

**Implication of our joint research:**

**The details of our experiment：**

- 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.

**Comparison with the previous results:**

**Target problem and the solution：**

**Main roles of the organizations：**

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

*d*such that a =

*g*d for given

*g*and

*a*

#### 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: