Cayley图中圈给出的生成元素之间的关系

Question

强RSA假设是以下问题很难解决。

“给定随机选择的RSA模n和随机z \in \mathbb{Z}_n^*，找到r>1和y \in \mathbb{Z}_n^*这样的y^r=z。”

RSA假设可以写成“在RSA群(\mathbb{Z}/pq\mathbb{Z})^*中很难找到一个非平凡关系”。因此，当考虑Cayley图时，在Cayley图中，寻找生成元素之间关系的问题可以看作是寻找圈，因为循环给出了生成元素之间的关系。

(例如，假设由元素s和t生成Cayley图。当我们沿着sttstt跟踪时，假设我们沿着一个长度为6的循环进行跟踪。那么因为它是一个循环，所以st^2st^2=e，它实际上代表了生成元素s和t之间的关系。)

当我们考虑找到像上面提到的y这样的y^r=z的情况时，我们不知道哪个循环给出了这种特殊的关系，对吗？

有没有办法把这个和周期的长度联系起来，这样我们就能知道哪种类型的循环给出了上面的关系？

另外，我想到的另一个问题是，当找到y时，我们可以通过使用私钥或与考虑的密码系统相关的数据来使用代数方法。但是，如果我们希望通过在图中找到循环的过程给出y的解决方案，这将是非常困难的，对吗？

我的意思是，即使对消息的发送者和接收者来说，这也是很困难的，因为寻找周期需要时间，即使使用算法也是如此，对吗？

提前谢谢。

Answer 1

根据中国剩余定理，我们可以这样写：(\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})：(\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，其中e是群的恒等元，[g_q, g_p]是交换子等。本质上，这是两个生成元上的自由交换群，受由D2表示的生成元的阶的关系。

然后，我们可以用发电机g_q, g_p写出你所谈论的所有数量。说z = g_q^{z_q}g_p^{z_p}和y = g_q^{y_q}g_p^{y_p}。然后你的方程式：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给了我们“循环”。特别是，如果您将Cayley图看作是形式g_q^{x}g_p^{y}的顶点(因此我们可以将其形象化为\mathbb{Z}^2的某个子集)，这就减少了寻找循环的问题，比如(ry_q \equiv z_q \bmod (q-1))和(ry_p\equiv z_p\bmod (p-1))。您可能希望强制执行一些非琐碎的条件(如ry_q\neq z_q和ry_p\neq z_p)，我不确定。如果您想要找到最小/最大长度周期，那么您可以找到最小/最大的非平凡(y_q, y_p)，例如ry_q \equiv z_q\bmod (q-1)和ry_p\equiv z_p\bmod(p-1)。注意，如果您知道N = pq的因式分解，您可以很容易地计算y_q \equiv r^{-1}z_q\bmod(q-1)和y_p\equiv r^{-1}z_p\bmod(p-1) (假设r在两个环中是可逆的)，然后通过搜索陪集r^{-1}z_q + (q-1)\mathbb{Z}找到具有所需属性的特定代表(y_p, y_q)。

我相信我们可以相当容易地读出任何周期的长度。特别是，循环是从(0,0) In \mathbb{Z}^2到(k_q, k_p)的一条路径，这样k_q\equiv ry_q-z_q\bmod (q-1)和k_p\equiv ry_pz_p\bmod(p-1)就可以实现。因此，从(0,0)到(k_q, k_p)的最短路径的长度是|k_q| + |k_p|，这是周期的长度。作为k_q\equiv 0\bmod(q-1) (以及类似于k_p)，我们看到任何循环的长度都必须是非零整数a_p, a_q的|a_p|(p-1) + |a_q|(q-1)形式，这就限制了可能的长度是可实现的(这与Frobenius硬币问题有关)。a_p和a_q的上限可能来自于g_q^{q-1}类型的组关系，但这需要首先定义一个“琐碎”循环的好概念。

至于它的可计算性，如果您知道N = pq的因式分解(上面所有的讨论都是这样做的)，并且(很可能)没有它，就可以有效地计算它。我不知道用这种方式重写RSA是否有什么好处(我没有立即看到)，也不保证上面的计算是正确的，但至少在我看来它们似乎是正确的。

需要担心的一件事是边缘的紧凑表示。所有这些都要求了解N的因式分解。如果我们去掉这一点，我们就可以抽象地将cayley图看作是\phi(N)顶点上的一个图，而p,q\approx 2^{n/2}将是\phi(N)\approx 2^n。顶点可以通过索引到[\phi(N)]来传递，而且由于图是4-正则的(我认为，来自每个顶点的边是\{g_p, g_p^{-1}, g_q, g_q^{-1}\}) )，可以有效地描述每个特定的边。但我不知道如何有效地传输整个图，因为有O(2^n)边，这意味着将它作为抽象图处理意味着无法有效地沟通它。

当然，有一些有效的方法来“压缩”图形(这必须在传统的基于RSA的密码系统中隐式地完成)，但还不清楚这种压缩中有多少会推广到其他组，这似乎是您的意图。