一个group内有：
- an identity
- a group operation
对于加法group，其identity为 O \mathcal{O} O，group operation为 + + +。
某些group可用作cryptographic group。基于的DLP假设为： 已知base G G G和group element P P P，找到 x x x使得 P = [ x ] G P=[x]G P=[x]G是很难的。
instantiate cryptographic group的方法之一是使用椭圆曲线。
2. Pedersen commitmentPedersen commitment为： a way to commit to a secret message in a verifiable way.
Pedersen commitment中有2个random public generators G , H ∈ G G,H\in\mathbb{G} G,H∈G，其中 G \mathbb{G} G为a cryptographic group of order p p p。 r r r为random secret chosen in Z q \mathbb{Z}_q Zq，message m m m 来自于 any subset of Z q \mathbb{Z}_q Zq，相应的Pedersen commitment为： c = C o m m i t ( m , r ) = [ m ] G + [ r ] H c=Commit(m,r)=[m]G+[r]H c=Commit(m,r)=[m]G+[r]H
为了open该commitment，committer需公开 m m m和 r r r，从而允许任意人来verify that c c c is indeed a commitment to m m m。
Pedersen commitment scheme具有同态性： C o m m i t ( m , r ) + C o m m i t ( m ′ , r ′ ) = C o m m i t ( m + m ′ , r + r ′ ) Commit(m,r)+Commit(m',r')=Commit(m+m',r+r') Commit(m,r)+Commit(m′,r′)=Commit(m+m′,r+r′)
假设DLP成立，则Pedernsen commmitment具有perfectly hiding和computationally binding属性：
- perfectly hiding：adversary 选择messages m 0 , m 1 m_0,m_1 m0,m1，committer commits to one of these messages c = C o m m i t ( m b , r ) , b ∈ { 0 , 1 } c=Commit(m_b,r), b\in\{0,1\} c=Commit(mb,r),b∈{0,1}。已知 c c c，adversary猜中 b b b的概率不高于 1 2 \frac{1}{2} 21。
- computationally binding：adversary无法找到两个不同的messages m 0 ≠ m 1 m_0\neq m_1 m0=m1 和 randomness r 0 , r 1 r_0,r_1 r0,r1，使得 C o m m i t ( m 0 , r 0 ) = C o m m i t ( m 1 , r 1 ) Commit(m_0,r_0)=Commit(m_1,r_1) Commit(m0,r0)=Commit(m1,r1)。
对于多个消息 m ⃗ = ( m 1 , m 2 , ⋯ , m n ) \vec{m}=(m_1,m_2,\cdots,m_n) m =(m1,m2,⋯,mn)，相应有多个random public generators G ⃗ = ( G 0 , G 1 , ⋯ , G n − 1 ) \vec{G}=(G_0,G_1,\cdots,G_{n-1}) G =(G0,G1,⋯,Gn−1) 以及 一个random generator H H H，相应的vector pedersen commitment scheme为： C o m m i t ( m ⃗ ; r ) = C o m m i t ( ( m 0 , ⋯ , m n − 1 ) ; r ) = [ r ] H + ∑ i = 0 n − 1 [ m i ] G i Commit(\vec{m};r)=Commit((m_0,\cdots,m_{n-1});r)=[r]H+\sum_{i=0}^{n-1}[m_i]G_i Commit(m ;r)=Commit((m0,⋯,mn−1);r)=[r]H+∑i=0n−1[mi]Gi
4. Diffie-Hellman另一个使用cryptographic groups的例子就是Diffie-Hellman key aggrement [DH1976]。
Diffie-Hellman protocol针对的场景为：有2个用户Alice和Bob，需要生成一个共享私钥，具体的流程为：
- 1）Alice和Bob publicly agree on two prime numbers p , G p, G p,G，其中 p p p很大， G G G为a primitive root ( m o d p ) \pmod p (modp)。（注意， g g g为a generator of the group F p × \mathbb{F}_p^{\times} Fp×。）
- 2）Alice选择large random number a a a作为其私钥，计算其公钥 A = [ a ] G ( m o d p ) A=[a]G\pmod p A=[a]G(modp)，Alice将其公钥 A A A发送给Bob。
- 3）类似地，Bob选择large random number b b b作为其私钥，计算其公钥 B = [ b ] G ( m o d p ) B=[b]G\pmod p B=[b]G(modp)，Bob将其公钥 B B B发送给Alice。
- 4）Alice和Bob可计算其共享key K = [ a b ] G ( m o d p ) K=[ab]G\pmod p K=[ab]G(modp)，其中Alice的计算方式为： K = [ a ] B ( m o d p ) = [ a ] ( [ b ] G ) ( m o d p ) K=[a]B\pmod p=[a]([b]G)\pmod p K=[a]B(modp)=[a]([b]G)(modp)；Bob的计算方式为： K = [ b ] A ( m o d p ) = [ b ] ( [ a ] G ) ( m o d p ) K=[b]A\pmod p=[b]([a]G)\pmod p K=[b]A(modp)=[b]([a]G)(modp)。
而对于窃听者，其仅可监听到 g , p , A = [ a ] G , B = [ b ] G g,p,A=[a]G, B=[b]G g,p,A=[a]G,B=[b]G，除非其可破解DLP获得 a a a或 b b b值（可假设其为computationally infeasible in F p × \mathbb{F}_p^{\times} Fp×），否则该窃听者无法生成 K = [ a b ] g K=[ab]g K=[ab]g。
5. Multiscalar multiplicationPippenger’s algorithm，详细见：
- Jonathan Bootle课件 Efficient Multi-Exponentiation
[1] Halo2 学习笔记——背景资料之Cryptographic groups
