Root computation problem: Difference between revisions

Latest revision as of 22:00, 2 May 2013

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^{t h}$ 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.

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. Thus, we can perform encryption by computing a power (with a "public encryption key" specifying what power to compute) but decryption is still hard if the order of the group is unknown.

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

@@ Line 11: / Line 11: @@
 ==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 <math>n</math> where <math>n</math> is the product of two large and secret primes. The order of this group is the [[Euler totient function]] of <math>n</math>, and computing this is equivalent to factorizing <math>n</math>, a problem that is believed to not have a polynomial time algorithm.
+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. Thus, we can perform encryption by computing a power (with a "public encryption key" specifying what power to compute) but decryption is still hard if the order of the group is unknown.
-The ''public encryption key'' is based on the power map <math>h \mapsto h^m</math> 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 <math>n</math>.
-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==