On the generic complexity of the problem of~computing~the Euler function

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 3 (2024), pp. 110-117

Résumé

We study the generic complexity of the problem of the Euler function computation. This problem has important applications in modern cryptography. For example, the cryptographic strength of the famous public key encryption system RSA is based on the assumption of its hardness. We prove that under the condition of worst-case hardness and $\text{P} = \text{BPP}$ there is no polynomial strongly generic algorithm for this problem. For a strongly generic polynomial algorithm, there is no efficient method for random generation of inputs on which the algorithm cannot solve the problem. Thus, this result justifies the application of the problem of computing the Euler function in public key cryptography. To prove this theorem, we use the method of generic amplification, which allows us to construct generically hard problems from the problems that are hard in the classical sense. The main feature 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 in a similar way for them.

Détail

Keywords: generic complexity, Euler function.