Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

Question

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain like the Gaussian integers, what is the resistance to attacks based on factoring with classical computing techniques?

As far as I know they are still vulnerable to quantum computing attacks as factoring in most (all?) of these rings is reducible to the hidden subgroup problem for finite Abelian groups, but for classical attacks involving number field sieving, are these rings as difficult to factor as the integers?

For instance, if I composed a key in classical RSA of 2048 bits, is 1024bits of the real part and 1024 bits of the quadratic coefficient equivalent? (1024bits a + 1024bits bi for example for Gaussian integers?)

Are there any tricks to make it easier to factor or do discrete log in these fields, like there are in polynomials?

Answer 1

There are three distinct computational problems related to RSA. They are:

• FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$;
• ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$;
• RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an element $b \in \mathbb{Z}_n$ such that $b^e = a \mod n$.

For the integers, the following reductions are known:

• Given the factorization of a number $n$, it is easy to find the order: $\lambda = \varphi(n) = \varphi(p) \varphi(q) = (p-1)(q-1)$.

• Given the order of the multiplicative group modulo $n$, it is easy to find the inverse exponent (if it exists): $d = e^{-1} \mod \lambda$. Given the inverse exponent, it is easy to solve the RSA problem: $b = a^{d} = b^{ed} = b^1 \mod n$.

• Given the order $\lambda$ of the multiplicative group modulo $n$, there exists an efficient way to calculate the prime factors of $n$.

• However, no algorithm is known that can turn an RSA problem solver into an algorithm that either finds the order $\lambda$ or factorizes $n$.

We can write these relations concisely as FACTORIZATION $\equiv_p$ ORDER $\geq_p$ RSA Problem.

Note: RSA is secure based on the assumption that the RSA problem is hard. This assumption implies, in turn, that factorization is hard. This assumption is weaker than the assumption that factorization is hard.

You correctly note that it is possible to define an analogue of RSA on other unique factorization domains (UFDs). However, on all the UFDs, factorization is either easy, or equivalent to factorization over the integers.* For example: there is a polynomial-time algorithm for factoring polynomials in one variable (see this survey). Factorization over the Gaussian integers reduces to factorization over the real integers (see this stackexchange answer).

*: I should qualify this statement by saying that not all UFDs are known. Perhaps there does exist a UFD where factorization is harder than it is for the integers. But finding this would be a scientific breakthrough because its applications to cryptography would be great.

Lastly, I should not that quantum computers might not be able to factorize efficiently in just any UFD. Shor's algorithm for factorization first finds the order $\lambda$ of the muliplicative group modulo $n$, and then uses this value to find the prime factors of $n$. The quantum algorithm to find the order will translate to any group. However, the reduction from FACTORIZATION to ORDER might not hold for all UFDs.