零知识证明中的循环群

ZK 数学 101：循环群、生成点和离散对数问题

继续你的 ZK 数学之旅，探索循环群以及为什么由于离散对数问题的难度，它们常用于密码学。

本文是系列文章的第五部分，该系列文章逐步介绍理解零知识证明如何工作的必要数学预备知识。它解释了什么是循环群，以及为什么由于离散对数问题的难度，它们通常用于密码学。 ‍

预备知识

在阅读本文之前，你应该已经阅读了前四篇文章，因此对以下内容有一定了解：

• 模运算
• 集合论
• 群论
• 环和域

‍

循环群和生成点

循环群是指具有一个元素的群，该元素称为生成点 g，因此群中的每个元素都可以通过将群运算重复应用于 g 来“生成”。

回顾一下，群是一个集合 G，带有一个单个二元运算符（称为群运算，记为 ∗），它具有以下属性：

• 封闭性： a∗b=c 其中 a,b,c∈G
  ‍
• 单位元素：存在一个元素，当它与另一个元素进行运算时，会产生该元素本身：
  • a∗I=a
  • 其中 a 是集合中的一个元素，I 是单位元素，∗ 是二元运算符（例如，乘法、加法等）。 ‍
• 每个元素都有一个逆元，当它与元素本身进行运算时，会产生单位元素：
  • a∗ainv=I
  • 其中 a 是集合中的一个元素，ainv 是 a 的逆元，也在集合中，I 是单位元素，∗ 是二元运算符（例如，乘法、加法等）。 ‍
• 群运算是结合律 ：
  • (a∗b)∗c=a∗(b∗c)​
  • 其中 a、b 和 c 都在集合中，∗ 是二元运算符（例如，乘法、加法等）。

如果存在一个元素 g∈G，使得对于某个整数 n，G 中的每个元素都可以写成如下形式，则群 G 称为循环群：

g×g×...×g⏟n 次=gn

对于乘法群（重复的标量乘法是标量求幂）。 并且：

g+g+...+g⏟n 次=g×n

对于加法群（重复的加法是标量乘法）。 ‍

循环群的例子

• 整数集合在模 n 加法下形成一个循环群，因为所有元素都可以通过重复加 1 来生成。 ‍
• 素数 p 的模下的（非零）整数群在乘法下（表示为 Zp∗）形成一个循环群，因为每个元素都可以通过对生成点重复 应用群运算符（乘法）来生成（证明这一点超出了本文的范围，但热情的读者可以在下面的参考部分找到证明。）

请注意，[所有循环群都是阿贝尔群(交换群)] (https://math.stackexchange.com/questions/44995/are-cyclic-groups-always-abelian/44996#44996)，但并非所有阿贝尔群都是循环群。

如何在乘法群中找到生成器 并非循环群中的每个元素都是生成器，而且并非每个具有素数模的群都具有容易找到的生成点。

在乘法群 Zp∗ 中，如果且仅当满足以下条件时，元素 g 才是生成器：

gk≢1(modp) 对于所有 k，其中 1≤k<p−1 ‍ 这意味着要验证元素 g 是否为生成点，我们需要检查元素 g 的任何 小于 p−1 且大于或等于 1的幂 不等于 1。只有当它被提高到 p−1 的幂时，它才会等于 1。 为每个可能的 g 检查这一点效率很低，因此，在实践中，我们可以使用基于 p−1 分解的更有效的方法：如果 p−1=q1e1×q2e2×...×qtet，其中 qi 是 p−1 的不同素因子，那么 g 是一个生成器当且仅当：

g(p−1)/qi≢1(modp)

对于所有从 1 到 t 的素因子索引 i，其中 t 是素因子的数量。 例如：在 Z11∗ 中，由于 11−1=10=2×5（它有两个素因子，所以 t=2），我们只需要检查：

1. g102=g5≢1(mod11) ‍
2. g105=g2≢1(mod11)

以确定 g 是否为生成器。这大大减少了验证元素是否为生成器所需的检查次数。 ‍

素数阶子群

完整的乘法群 Zp∗ 的阶数（元素数）为 p−1，很少为素数。然而，密码学应用通常使用素数阶子群来增强安全性和效率。 ‍

寻找素数阶子群

如果 p−1=qr，其中 q 是 p−1 的一个大素因子，r 是余因子，那么我们可以找到 $\mathbb{Z}p^$_* 中的一个 q 阶子群。

例如，对于以下 p、q 和 r 值：

• p=23（一个素数）。 ‍
• 那么 p−1=22。 ‍
• 22 的素数分解是 2×11，所以素数因子是 2 和 11。 ‍
• 如果我们选择 q=11（较大的素数因子），那么 r=2（余因子）。

‍ 元素 h∈Zp∗ 是此子群的生成器，如果： h=grmodp，其中 g 是完整群 𝕡Zp∗ 的生成器。 ‍ 在这些素数阶子群中工作具有以下几个优点：

1. 可以使用较小的指数，从而提高计算群元素时的计算效率。 ‍
2. 在素数阶群中，ZK 证明通常更简单。 ‍
3. 某些密码协议（如 Schnorr 签名）明确要求素数阶群。

素数阶子群的概念扩展到密码学中使用的其他循环群，包括椭圆曲线群（下一篇文章的主题）。 ‍

循环群在密码学中的重要性

1. 简化计算

群是循环群意味着可以简化计算。

任何有限域 Fp 的乘法群是 p−1 阶的循环群。这意味着在 Fp 中存在一个生成器 g，使得 Fp 中的每个非零元素都可以表示为 gk，其中 k 是某个整数。 这允许将乘法和求幂简化为对指数的运算。例如，如果不直接将两个元素 a 和 b 相乘，如果已知 a=gk 且 b=gm，则它们的乘积为

a×b=gk×gm=gk+m ‍

2. 计算难度

循环群是密码学和零知识证明的基础，因为在无限域中容易解决的某些问题在限制为有限域时会变得计算困难。一个关键的例子是离散对数问题 (DLP)。 ‍

乘法群中的离散对数问题 (DLP)

离散对数问题 (Discrete logarithm problem) 会问：

给定一个生成器 g 和一个元素 h，找到一个整数 x，使得将群运算 x 次应用于 g 会得到 h。

在有限乘法循环群 𝕡Zp∗ 中，这意味着找到 x，使得：

gx≡hmod(p)

这里，g 是循环群的生成器，h 是将 g 提高到 x 的幂，然后取模 p 的结果。任务是在给定 g 和 h 的情况下确定 x，当 p 很大时，这在计算上是很困难的。

与标准对数不同 (我们可以取两边的自然对数)，循环群的模性质破坏了使对数在常规算术中易于计算的属性。

我们无法应用直接的“反函数”，因为模性质在输入和输出之间创建了一种离散的、看似随机的关系，这种关系不会保留我们在计算标准对数时利用的数学属性。

这就是我们诉诸于诸如 baby-step giant-step 或 Pollard's rho 之类的算法的原因，这些算法实际上是在搜索正确的 x，而不是直接计算它。

随着 p 变大，搜索空间呈指数级增长，并且即使对于功能强大的计算机来说，也很快变得在计算上不可行。

在加法循环群（例如椭圆曲线群，这是未来一篇文章的主题）中，问题变成了找到 x，使得：

x⋅g=h

其中 g 再次是一个生成点，x 是我们试图找到的标量，h 是一个集合元素，例如，一个椭圆曲线点。

由于椭圆曲线群需要不同的数学框架，我们将在此处关注乘法情况，并在我们讨论椭圆曲线密码学时再回到加法版本。 示例：在有限域 Fp∗ 中，给定 g 和 h，问题是找到 x，使得：2x≡23mod(p)

虽然计算幂是一种有效的计算，但找到对数的逆运算，即在给定 g (2) 和 h (23) 的情况下找到 x，被认为是困难的，尤其是在 p 变得很大时。

DLP 的计算难度确保了攻击者无法轻易地从 Diffie-Hellman 等协议中的公钥派生出私钥，从而在数字通信中提供安全性。 DLP 还允许我们隐藏秘密信息！

我们可以在循环群元素 h=gx(modp) 中“隐藏”我们的秘密 x！并通过对 h 执行计算来证明关于我们的秘密 x 的属性，而无需泄露 x 本身。这是可能的，因为循环群的同态属性和下一篇文章的主题。 ‍

循环群的例子

让我们通过一个小例子来说明生成点如何生成循环群中的所有点。

考虑乘法群 Z11∗（模 11 乘法下的 1 到 10 的整数）。让我们通过计算所有幂来验证 g=2 是该群的生成器： 21(mod11)=2​ 22(mod11)=4​ 23(mod11)=8​ 24(mod11)=5(因为16(mod11)=5) 25(mod11)=10(因为32(mod11)=10) 26(mod11)=9(因为64(mod11)=9) 27(mod11)=7(因为128(mod11)=7) 28(mod11)=3(因为256(mod11)=3) 29(mod11)=6(因为512(mod11)=6) 210(mod11)=1(因为1024(mod11)=1)

我们已经生成了 Z11 中的所有非零元素，确认 2 确实是一个生成器。

现在，回到离散对数问题：如果我们得到 g=2 和 h=9，我们需要找到 x，使得 2x≡9(mod11)。从上面的计算中，我们可以看到 x=6。对于像 11 这样的小模数，我们可以通过穷举搜索找到答案，但是对于密码学大小的模数（例如，2048 位，它会创建一个 2^2048 个可能性的搜索空间），这种方法在计算上变得不可行。不可能计算每个点来找到对应于给定 h 值的 x。 ‍

总结

循环群和离散对数问题构成了许多密码学和零知识证明系统的支柱：复杂的语句可以简化为证明对满足循环群中特定关系的值的了解，其中 DLP 确保这些值保持隐藏。

这允许证明者证明他们知道一个秘密（如离散对数），而不泄露有关秘密本身的任何信息。

循环群的数学属性使它们成为构建这些证明的理想选择。

• 循环群是指所有元素都可以通过将群运算重复应用于单个元素（生成器）来生成的群。 ‍
• 离散对数问题 (DLP) 在有限循环群中在计算上是困难的，构成了密码学安全的基础。 ‍
• 并非循环群中的所有元素都是生成器；特定的数学测试可以识别有效的生成器。 ‍
• 密码学应用通常使用素数阶子群来提高安全性和效率。 ‍
• 循环群允许简化计算，同时保持计算安全性。 ‍
• 零知识证明利用循环群来证明对秘密值的了解，而不泄露它们。

‍

参考文献

• 为什么 Zp∗ 是循环的
  • <https://kconrad.math.uconn.edu/blurbs/grouptheory/cyclicmodp.pdf?utm_source=chatgpt.com>
  • https://www.youtube.com/watch?v=3xU51PETN4U&t=1s
• Diffie-Hellman 问题
• The Gap problems
• RareSkills ZK Book
• LeastAuthority 的 ZK Moon Math Manual
• 维基百科 循环群

• 原文链接： cyfrin.io/blog/zk-math-1...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～