×

Interpolation of functions related to the integer factoring problem. (English) Zbl 1151.94471

Ytrehus, Øyvind (ed.), Coding and cryptography. International workshop, WCC 2005, Bergen, Norway, March 14–18, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-35481-6/pbk). Lecture Notes in Computer Science 3969, 144-154 (2006).
Summary: The security of the RSA public key cryptosystem depends on the intractability of the integer factoring problem. This paper shall give some theoretical support to the assumption of hardness of this number theoretic problem.
We obtain lower bounds on degree, weight, and additive complexity of polynomials interpolating functions related to the integer factoring problem, including Euler’s totient function, the divisor sum functions, Carmichael’s function, and the RSA-function.
These investigations are motivated by earlier results of the same flavour on the interpolation of discrete logarithm and Diffie-Hellman mapping.
For the entire collection see [Zbl 1102.94002].

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI