A Framework for Filtering Step of Number Field Sieve and Function Field Sieve

ABSTRACT

Public key cryptography is based on two popular mathematical hard problems namely the integer factorization and discrete logarithm problem. Number Field Sieve (NFS) and Function Field Sieve (FFS) are the most efficient and widely used algorithms to solve integer factorization and discrete logarithm problems. The main phases of these algorithms are polynomial selection, relation collection and linear algebra. Among these steps, relation collection and linear algebra are the most computationally costly. The filtering step is used in between relation collection and linear algebra step, which employs several strategies to reduce the coefficient matrix size and makes the matrix suitable for linear algebra, so that linear algebra takes comparatively lesser time. This paper presents a complete framework for the filtering step in the NFS class of algorithms. In this paper, the filtering step is considered as two main sub-phases. The two phases are namely matrix construction and matrix reduction. In the first sub-phase, the relations collected from the relation collection step are structured to represent in a matrix form. The main goal of this phase is to construct a relation from the smooth elements obtained in the relation collection phase along with the other necessary inputs with respect to NFS class of algorithms. The second sub-phase deals with matrix reduction in which various strategies such as duplicate removal, singleton removal, clique removal and merge are applied to reduce the overall matrix size preserving the sparsity at the same time. Algorithms for the first and second phases are designed and analyzed in the paper. The experiments are conducted on the relations collected from standard tool CADO-NFS and the results are reported. From the results, it is shown that the filter map structure presented in the current work for matrix representation helps to improve the overall performance of filtering module. Specifically, the method to handle duplicates in the matrix instead of the traditional method improves the duplicate removal module of filtering. Additionally, an optimized clique removal method of filtering which is introduced in the present work further improves the performance of filtering.

Keywords:

• Cryptography
• Number field sieve
• Function field sieve
• Filtering

Acknowledgments

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

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 GF is Galois Field.

Additional information

Funding

This work was supported by Defence Research and Development Organisation [DIR/MEDCoS/SAG/P(Others)/15-16/005]. DIR/MEDCoS/SAG/P(Others)/15-16/005

Notes on contributors

Rahul Janga

Rahul Janga received MTech CSIS degree from NIT Warangal. His 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 includes 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. Dr 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 was conferred the DRDO Scientist of the Year award in 2012. Dr Pal guides PhD students at Delhi University and other national institutions. He has 200 research publications in journals and conference proceedings.Email: [email protected]

S. Ravichandra

S Ravi Chandra 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]