On the generic complexity of the discrete logarithm problem in Lucas sequences

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 116-122

Résumé

In this paper, we study the generic complexity of the discrete logarithm problem over Lucas sequences. This problem was exploited in the 1990s by the New Zealand cryptographer P. Smith to create an analogue of the classic Diffie — Hellman protocol, in which exponentiation modulo an integer is replaced by the operation of adding the elements of the Lucas sequence. It is proved that, given the worst-case intractability of the discrete logarithm problem in Lucas sequences and $\text{P}=\text{BPP}$, there exists a subproblem of this problem for which there is no polynomial generic algorithm. Thus, this result justifies the application of this algorithmic problem to public-key cryptography, where generic hardness is very important, i.e., hardness for almost all inputs. To prove the theorem, we use the method of generic amplification, which allows us to construct generically hard problems from problems that are hard in the classical sense. The main component of this method is the cloning technique, which combines the input data of a problem into sufficiently large sets of equivalent input data. Equivalence is understood in the sense that the problem is solved similarly for them.

Détail

Keywords: generic complexity, Lucas sequences, discrete logarithm.