Geodesic
On the generic complexity of the discrete logarithm problem in Lucas sequences
Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 116-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: generic complexity, Lucas sequences, discrete logarithm. 
@article{PDM_2024_4_a9,
     author = {A. N. Rybalov},
     title = {On the generic complexity of the discrete logarithm problem in {Lucas} sequences},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {116--122},
     publisher = {mathdoc},
     number = {4},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_4_a9/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On the generic complexity of the discrete logarithm problem in Lucas sequences
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 116
EP  - 122
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_4_a9/
LA  - ru
ID  - PDM_2024_4_a9
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On the generic complexity of the discrete logarithm problem in Lucas sequences
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 116-122
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_4_a9/
%G ru
%F PDM_2024_4_a9
A. N. Rybalov. On the generic complexity of the discrete logarithm problem in Lucas sequences. Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 116-122. http://geodesic.mathdoc.fr/item/PDM_2024_4_a9/

[1] Smith P. J. and Lennon M. J. J., “LUC: a new public key system”, Proc. IFIP/Sec'93 (Toronto, Canada, 1993), 103–117 | MR | Zbl

[2] Smith P. and Skinner C., “A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms”, LNCS, 917, 1995, 355–364 | MR

[3] Bleichenbacher D., Bosma W., and Lenstra A., “Some remarks on Lucas-based cryptosystems”, LNCS, 963, 1995, 386–396 | MR | Zbl

[4] Kapovich I., Miasnikov A., Schupp P., and Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[5] Rybalov A. N., “On generic complexity of the quadratic residuosity problem”, Prikladnaya Diskretnaya Matematika, 2015, no. 2(28), 54–58 (In Russian) | MR | Zbl

[6] Rybalov A. N., “On generic complexity of the discrete logarithm problem”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 93–97 (In Russian) | Zbl

[7] Rybalov A. N., “On generic complexity of the problem of finding roots in groups of residues”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 95–100 (In Russian) | Zbl

[8] Impagliazzo R. and Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC (El Paso), ACM, 1997, 220–229 | MR

[9] Rosser J. B. and Schoenfeld L., “Approximate formulas for some functions of prime numbers”, Illinois J. Math., 6:1 (1962), 64–94 | DOI | MR | Zbl