译自 halo2 book：background/groups.md

密码学群(cryptographic groups)

在 逆元与群(Inverses and groups) 一节中，我们引入了 群(group) 的概念。群有一个单位元和一个群运算。在本节中，我们将以加法记法书写群，即单位元是 $\mathcal{O}$，群运算是 $+$。

某些群可以用作 密码学群(cryptographic group)。冒着过度简化的风险来说，这意味着求群元素 $P$ 以给定基 $G$ 为底的离散对数(discrete logarithm)的问题——即求满足 $P=[x]G$ 的 $x$——在一般情况下是困难的。

Pedersen 承诺(Pedersen commitment)

Pedersen 承诺 [P99] 是一种以可验证的方式承诺(commit)某条秘密消息的方法。它使用两个随机的公开生成元 $G,H\in \mathbb{G},$ 其中 $\mathbb{G}$ 是阶为 $q$ 的密码学群。在 ${\mathbb{Z}}_q$ 中选取一个随机秘密 $r$，要承诺的消息 $m$ 来自 ${\mathbb{Z}}_q$ 的任意子集。承诺为

$$c=\text{Commit}(m,r)=[m]G+[r]H.$$

为打开(open)承诺，承诺者揭示 $m$ 和 $r,$ 从而允许任何人验证 $c$ 确实是对 $m$ 的承诺。

注意 Pedersen 承诺方案是同态的(homomorphic)：

$$\begin{array}{rl}\text{Commit}(m,r)+\text{Commit}(m^{\prime },r^{\prime })& =[m]G+[r]H+[m^{\prime }]G+[r^{\prime }]H\\ & =[m+m^{\prime }]G+[r+r^{\prime }]H\\ & =\text{Commit}(m+m^{\prime },r+r^{\prime }).\end{array}$$

假定离散对数假设成立，Pedersen 承诺还是完美隐藏(perfectly hiding)和计算绑定(computationally binding)的：

• 隐藏(hiding)：敌手选择消息 $m_0,m_1.$ 承诺者承诺其中一条消息 $c=\text{Commit}(m_b,r),b\in \{0,1\}.$ 给定 $c,$ 敌手猜中正确的 $b$ 的概率不超过 $\frac{1}{2}$。
• 绑定(binding)：敌手无法选出两条不同的消息 $m_0\ne m_1,$ 以及随机数 $r_0,r_1,$ 使得 $\text{Commit}(m_0,r_0)=\text{Commit}(m_1,r_1).$

向量 Pedersen 承诺(Vector Pedersen commitment)

我们可以使用 Pedersen 承诺方案的一个变体，一次性承诺多条消息 $\mathbf{m}=(m_0,\cdots ,m_{n-1})$。这一次，我们必须采样相应数量的随机公开生成元 $\mathbf{G}=(G_0,\cdots ,G_{n-1}),$ 外加像之前一样的单个随机生成元 $H$（用于隐藏）。那么，我们的承诺方案为：

$$\begin{array}{rl}\text{Commit}(\mathbf{m};r)& =\text{Commit}((m_0,\cdots ,m_{n-1});r)\\ & =[r]H+[m_0]G_0+\cdots +[m_{n-1}]G_{n-1}\\ & =[r]H+\sum _{i=0}^{n-1}[m_i]G_i.\end{array}$$

TODO：这是否是位置绑定的(positionally binding)？

Diffie–Hellman

使用密码学群的协议的一个例子是 Diffie–Hellman 密钥协商 [DH1976]。Diffie–Hellman 协议是供两个用户 Alice 和 Bob 生成共享私钥的方法。它的过程如下：

1. Alice 和 Bob 公开地约定两个素数 $p$ 和 $G,$ 其中 $p$ 很大，$G$ 是一个本原根 $(\mathrm{mod}p).$（注意 $g$ 是群 ${\mathbb{F}}_p^{\times }$ 的一个生成元。）
2. Alice 选择一个大随机数 $a$ 作为她的私钥。她计算她的公钥 $A=[a]G(\mathrm{mod}p),$ 并把 $A$ 发送给 Bob。
3. 类似地，Bob 选择一个大随机数 $b$ 作为他的私钥。他计算他的公钥 $B=[b]G(\mathrm{mod}p),$ 并把 $B$ 发送给 Alice。
4. 现在 Alice 和 Bob 都计算他们的共享密钥 $K=[ab]G(\mathrm{mod}p),$ Alice 计算为 $$K=[a]B(\mathrm{mod}p)=[a]([b]G)(\mathrm{mod}p),$$ Bob 计算为 $$K=[b]A(\mathrm{mod}p)=[b]([a]G)(\mathrm{mod}p).$$

潜在的窃听者只知道 $g,p,A=[a]G,$ 和 $B=[b]G$，却需要推导出 $K=[ab]g(\mathrm{mod}p)$：换言之，他们需要从 $A=[a]G$ 得到离散对数 $a$，或从 $B=[b]G$ 得到 $b$，而我们假定这在 ${\mathbb{F}}_p^{\times }$ 中计算上是不可行的。

更一般地，使用与 Diffie–Hellman 类似思想的协议在整个密码学领域随处可见。实例化密码学群的一种方式是用 椭圆曲线(elliptic curve)。在深入讨论椭圆曲线之前，我们先描述一些可以用于任意群的算法。

多标量乘法(Multiscalar multiplication)

TODO：Pippenger 算法(Pippenger's algorithm)

参考：https://jbootle.github.io/Misc/pippenger.pdf