Linear Algebra on Parallel Structures Using Wiedemann Algorithm to Solve Discrete Logarithm Problem

Abstract

Discrete logarithm problem, popularly known as DLP has been the heart of many Public Key Infrastructures that are being used today. DLP belongs to the category of hard problems. Many ideas have been proposed to solve DLP. The best-known methods are Number Field Sieve (NFS) class algorithms. The Function Field Sieve (FFS) algorithm is one of the NFS class algorithms to solve DLP in an extension field, i.e. Galois field $\text{GF}\left(2^n\right)$. This FFS involves three phases such as Function Sieving, Filtering, and Linear Algebra. Linear Algebra phase involves solving huge sparse matrices/system of linear equations. The most popular methods to solve sparse matrices are Lanczos and Wiedemann method. Recently, Wiedemann method got attention to solve the linear system of equations such as Ax = 0. This paper studies Wiedemann algorithm to solve $AX\equiv 0mod{2}^n-1$ based on the factors of $2^n-1$; since the DLP is defined over $\text{GF}\left(2^n\right)$. The different cases considered in this paper are (1) $2^n-1$ is a prime of size less than n bits, (2) $2^n-1$ is a composite number with one factor of size more than n bits, and (3) $2^n-1$ is a composite number with more than one factors of n bits. The naive Wiedemann is considered in case 1, paralleled version of Joux and Pierrot [“Nearly sparse linear algebra and application to discrete logarithms computation,” preprint Contemporary Developments in Finite Fields and Applications, 2016.] is considered in case 2 and the client-server model along with the paralleled version of Wiedemann for case 3. Algorithms for all the three cases of solving $AX\equiv 0mod{2}^n-1$ are designed, analysed, experimented, and tested under the conditions based on density and size of matrices. The experiments are carried out on the matrices obtained from filtering step of FFS. The results are analysed and reported. From the results, it is shown that the communication cost between master and the slaves is to be considered and minimum density in the matrix is to be maintained in the previous step of linear algebra of FFS, i.e. filtering step to avoid trivial solutions. The configuration of the system used for experiments is 64 bit Intel (R) Xeon (R) CPU E5-2650 v3 @ 2.30 GHz with 40 cores and Intel(R) Core i7-6500U CPU @ 2.50 GHz.

Keywords:

• Discrete log problem
• Function field sieve
• Linear algebra
• Wiedemann algorithm
• Parallelization
• Public key cryptography

DISCLOSURE STATEMENT

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is sponsored by SAG, DRDO-Defence Research and Development Organization, New Delhi under Letter No DIR/MED&CoS/SAG/P(Others)/15-16/005.

Notes on contributors

K S Spoorthi

K S Spoorthi received MTech CSIS degree from NIT Warangal. Her area of interest includes cryptography and information security. Email: [email protected]

R. Padmavathy

R Padmavathy received MTech degree from Andhra University and PhD from University of Hyderabad, India. At present, she is working as a faculty member at the National Institute of Technology, Warangal, India. Her research interests include information security, cryptology and network security.

S K Pal

S K Pal is working as a director, Directorate of Information Technology & Cyber Security and CISO. S K Pal has earlier worked at Scientific Analysis Group (SAG), Delhi, in the areas of cryptography, speech & multimedia technology and computational intelligence and has contributed in many DRDO projects. He has been conferred the DRDO Scientist of the Year award in 2012. He guides PhD students at Delhi University & other national institutions. He has 200 research publications in journals & conference proceedings. Email: [email protected]

S Ravi Chandra

S Ravi Chandra at present is working as a faculty member at the National Institute of Technology, Warangal, India. His research interests include information security, secure software engineering and privacy. Email: [email protected]