Root computation problem

Definition

The root computation problem is a problem usually asked in the context of an encoding of a group or multi-encoding of a group. The input is an element $g$ of the group and an integer $m$ such that we are promised that the group is powered over all primes dividing $m$, so every element has a unique $m^{th}$ root. In the finite case, this is equivalent to requiring that $m$ is relatively prime to the order of the group. The goal is to find the unique $h$ such that $h^m=g$. Note that uniqueness follows from the fact that kth power map is bijective iff k is relatively prime to the order.

Related problems

• Power computation problem
• Element order-finding problem
• Order-finding problem

Relation with cryptography

The RSA algorithm is based on the idea that the root computation problem is much harder than the power computation problem if the order of the group is unknown. Specifically, the group is the multiplicative group of invertible elements in the ring of integers mod $n$ where $n$ is the product of two large and secret primes. The order of this group is the Euler totient function of $n$, and computing this is equivalent to factorizing $n$, a problem that is believed to not have a polynomial time algorithm.

The public encryption key is based on the power map $h\mapsto h^m$ and the private decryption key is based on the root map that inverts this. The idea is that even though the encryption key is public, the decryption key cannot be obtained from it without knowledge of the factorization of $n$.

This means that if a black box group algorithm is found that does not rely on the order-finding problem, that would break RSA.

Solution

Solution dependent on power computation and order-finding

• Black-box group algorithm for root computation problem based on power computation problem and order-finding problem