Chapter Summary

This chapter introduces the most common computationally intractable mathematical problems on which the security of public-key cryptosystems banks. We also describe some algorithms known till date for solving these difficult computational problems.

To start with, we enumerate these computational problems. The first problem in the row is the integer factorization problem (IFP) and its several variants. Some problems that are provably or believably equivalent to the IFP are the totient problem, problems associated with the RSA algorithm, and the modular square root problem. The next class of problems includes the discrete logarithm problem (DLP) and its variants on elliptic curves (ECDLP) and hyperelliptic curves (HECDLP). The Diffie–Hellman problem (DHP) and its variants (ECDHP, HECDHP) are believed to be equivalent to the respective variants of the DLP. Finally, the subset sum problem (SSP) and two related problems, namely the shortest vector problem (SVP) and the closest vector problem (CVP) on lattices, are introduced.

The subsequent sections are devoted to an algorithmic study of these difficult problems. We start with IFP. We first present some fully exponential algorithms like trial division, Pollard’s rho method, Pollard’s p – 1 method and Williams’ p + 1 method. Next we describe the modern genre of subexponential algorithms. The quadratic sieve method (QSM) is discussed at length together with its heuristic improvements like incomplete sieving, large prime variation and the multiple polynomial variant. We also describe TWINKLE, a hardware device that efficiently implements the sieving stage of the QSM. We then discuss the elliptic curve method (ECM) and the number field sieve method (NFSM) for factoring integers. The NFSM turns out to be the asymptotically fastest known algorithm for factoring integers.

The (finite field) DLP is discussed next. The older square-root methods, such as Shanks’ baby-step–giant-step method (BSGS), Pollard’s rho method and the Pohlig–Hellman method (PHM), take exponential running times in the worst case. The PHM for a field is, however, efficient if q – 1 has only small prime factors. Next we discuss the modern family of algorithms collectively known as the index calculus method (ICM). For prime fields, we discuss three variants of the ICM, namely the basic method, the linear sieve method (LSM) and the number field sieve method (NFSM). We also discuss three variants of the ICM for fields of characteristic 2: the basic method, the linear sieve method and Coppersmith’s algorithm. Another interesting variant is the cubic sieve method (CSM) covered in the exercises. We explain Gordon and McCurley’s polynomial sieving in connection with Coppersmith’s algorithm.

The next section deals with algorithms for solving the ECDLP. For a general elliptic curve, the exponential square-root methods are the only known algorithms. For some special classes of curves, more efficient methods are proposed in the literature. The MOV reduction based on Weil pairing reduces ECDLP on a curve over to DLP in the finite field for some suitable . This k is small and the reduction is efficient for supersingular curves. The SmartASS method (also called the anomalous method) reduces the ECDLP in an anomalous curve to the computation of p-adic discrete logarithms. This reduction solves the original DLP in polynomial time. In view of these algorithms, it is preferable to avoid supersingular and anomalous curves in cryptographic applications. The xedni calculus method (XCM) is discussed finally. This algorithm works by lifting a curve over to a curve over . Experimental and theoretical evidences suggest that the XCM is not an efficient solution to the ECDLP.

We then devote a section to the study of an index calculus method to solve the HECDLP. For hyperelliptic curves of small genus, this method leads to a subexponential algorithm (the ADH–Gaudry algorithm).

Many of the above subexponential methods require solving a system of linear congruences over finite rings. This (inherently sequential) linear algebra part often turns out to be the bottleneck of the algorithms. However, the fact that these equations are necessarily sparse can be effectively exploited, and some faster algorithms can be used to solve these systems. We study four such algorithms: structured Gaussian elimination, the conjugate gradient method, the Lanczos method and the Wiedemann method.

In the last section, we study the subset sum problem. We first reduce the SSP to problems associated with lattices. We finally present the lattice-basis reduction algorithm due to Lenstra, Lenstra and Lovasz.

Several other computationally intractable problems have been proposed in the literature for building cryptographic systems. Some of these problems are mentioned in the annotated references of Chapter 5. Due to space and time limitations, we will not discuss these problems in this book.