4
$\begingroup$

The strong RSA assumption is that the following problem is hard to solve.

"Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such that $y^r=z$."

The RSA assumption can be written as "it is computationally difficult to find a non-trivial relation in the RSA group $(\mathbb{Z}/pq\mathbb{Z})^*$". So when considering Cayley graphs, the problem of finding relationship between generating elements can be viewed as finding cycles in the Cayley graph, since cycles give relationships between generating elements.

(As an example, suppose a Cayley graph is generated by the elements $s$ and $t$. When we trace along $sttstt$, suppose we have traced along a cycle of length 6. Then because it is a cycle, $st^2st^2=e$, which actually represents a relationship between the generating elements $s$ and $t$.)

When we consider a situation of finding $y$ such that $y^r=z$ as mentioned above, we don't know which cycle gives this particular relationship right?

Is there way to connect this with the length of the cycle, so that we have some kind of an idea which type of cycle gave the above relationship?

Also, another question came to my mind is, when finding $y$, we might be able to use an algebraic method by making use of a private key or some data relevant to the cryptosystem considered. But if we hope to try to give a solution to $y$ though the process of finding a cycle in the graph, it is going to be very difficult, right?

I mean it'll be difficult even for the sender and receiver of a message, because finding cycles take time, even when done using an algorithm, right?

Thanks a lot in advance.

$\endgroup$
2
  • 1
    $\begingroup$ “since cycles give relationships between generating elements.” can you expand on this? how? your assertions in the question are quite vague. $\endgroup$
    – kodlu
    Apr 13, 2020 at 8:31
  • $\begingroup$ Yes, sure @kodlu I have now added more information in the question. Thanks. $\endgroup$ Apr 13, 2020 at 18:39

1 Answer 1

2
$\begingroup$

By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$ From this, we should be able to write: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$ Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.

We can then write all the quantities you talk about in terms of the generators $g_q, g_p$. Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$. Then your equation: $$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$ Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$. You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure. If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$.

I believe we can read off the length of any cycle fairly easily. In particular, a cycle is a path from $(0,0)$ in $\mathbb{Z}^2$ to $(k_q, k_p)$ such that $k_q\equiv ry_q-z_q\bmod (q-1)$ and $k_p\equiv ry_pz_p\bmod(p-1)$. The length of the shortest path from $(0,0)$ to $(k_q, k_p)$ is therefore $|k_q| + |k_p|$, which is the length of your cycle. As $k_q\equiv 0\bmod(q-1)$ (and similarly for $k_p$), we see that the length of any cycle must be of the form $|a_p|(p-1) + |a_q|(q-1)$ for non-zero integers $a_p, a_q$, which puts some restrictions on which possible lengths are achievable (this is related to the Frobenius coin problem). There are likely upper bounds on $a_p$ and $a_q$ which come from the group relations of the type $g_q^{q-1}$, but this requires defining a good notion of "trivial" cycle first.


As for the computability of this, it can be efficiently computed if you know the factorization of $N = pq$ (all of the discussion above does this), and (likely) can't without this. I don't know if there are any gains to rewriting RSA in this way (I don't see any immediately), and don't guarantee the computations above are correct, but they seem vaguely right to me at least.

One thing to worry about is compact representation of the edges. All of the above required knowing the factorization of $N$. If we remove this, then we can abstractly view the cayley graph will as a graph on $\phi(N)$ vertices, which as $p,q\approx 2^{n/2}$ will be $\phi(N)\approx 2^n$. Vertices can be communicated by indexing into $[\phi(N)]$, and since the graph is 4-regular (I think, edges from each vertex being $\{g_p, g_p^{-1}, g_q, g_q^{-1}\})$ each particular edge can be efficiently described. But I don't know how you can efficiently transmit the entire graph, as there are $O(2^n)$ edges, meaning that treating it as an abstract graph means you cannot efficiently communicate it.

Of course there are efficient ways to "compress" the graph (this must implicitly be done in traditional RSA-based cryptosystems), but its unclear how much of that compression will generalize to other groups, which appears to be your intention.

$\endgroup$
8
  • $\begingroup$ Many many thanks @Mark $\endgroup$ Apr 14, 2020 at 13:05
  • $\begingroup$ Yes @Mark my intention is to extend the notion of the strong RSA assumption to other groups such as $(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes \mathbb{Z}_q$ and would like to clarify certain questions related to the above which I posted as a question at crypto.stackexchange.com/questions/79963/… $\endgroup$ Apr 14, 2020 at 13:09
  • 1
    $\begingroup$ The first thing I would worry about if I were you is an efficient way to communicate the underlying cayley graph. Even in what I wrote above, you actually can't simply index into $[\phi(N)]$ (as $\phi(N)$ must be kept secret for the security of the RSA assumption). So even in this particular case, it's unclear how you can represent the Cayley graph (let alone compute on it) without knowing $\phi(N)$. $\endgroup$
    – Mark
    Apr 14, 2020 at 17:39
  • 1
    $\begingroup$ @BuddhiniAngelika Oops, that's actually incorrect. $g_q$ is order $q-1$, so we have that $g_q^{ry_q-z_q} = e\implies ry_q-z_q\equiv 0\bmod q-1$. As for why we can go from $g_q^{ry_q-z_q}g_p^{ry_p-z_p} = e\implies g_q^{ry_q-z_q} = e\land g_p^{ry_p-z_q}$, I think you should be able to argue this from the assumption that neither of the $g_q, g_p$ is generated from the other. I'm assuming there's some statement along the lines of "In the free abelian group on two generators $a, b$, every element is of the form $a^k b^j$". We then take that statement down to the quotient. $\endgroup$
    – Mark
    May 10, 2020 at 19:50
  • 1
    $\begingroup$ Meaning that our group is really just the free abelian group on two generators, quotiented by the relations that the generators have order $q-1$ and $p-1$. I'm assuming that "unique factorization upstairs implies unique factorization downstairs" essentially, which I imagine is the case and shouldn't be too hard to prove. $\endgroup$
    – Mark
    May 10, 2020 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.