Greyhound 是一个基于lattice的polynomial commitment scheme（PCS）。对于degree为N N N p o l y log ( N ) poly\log(N) p o l y log ( N ) O ( N ) O(\sqrt{N}) O ( N ) F q \mathbb{F}_q F q
1. 符号和相关背景 ¶ 在介绍 Greyhound 的设计思路前，先引入一些符号。
设d d d R = Z [ X ] / ( X d + 1 ) \mathcal{R} = \mathbb{Z}[X]/(X^d + 1) R = Z [ X ] / ( X d + 1 ) 2 d 2d 2 d q q q R q = Z q [ X ] / ( X d + 1 ) \mathcal{R}_q = \mathbb{Z}_q[X]/(X^d + 1) R q = Z q [ X ] / ( X d + 1 ) δ = ⌊ log q ⌋ \delta = \lfloor \log q \rfloor δ = ⌊ log q ⌋ R \mathcal{R} R R q \mathcal{R}_q R q
对整数n ≥ 1 n \geq 1 n ≥ 1 G n = I ⊗ [ 1 2 4 ⋯ 2 δ ] ∈ R q n × n δ \mathbf{G}_n = \mathbf{I} \otimes [1 ~2~ 4~ \cdots~ 2^\delta] \in \mathcal{R}_q^{n \times n\delta} G n = I ⊗ [ 1 2 4 ⋯ 2 δ ] ∈ R q n × n δ G n − 1 ： R q n → R q δ n \mathbf{G}_n^{-1} ： \mathcal{R}_q^n \to \mathcal{R}_q^{\delta n} G n − 1 ： R q n → R q δ n
例对于一个向量 t ∈ R q n \mathbf{t} \in \mathcal{R}_q^n t ∈ R q n G n − 1 ( t ) \mathbf{G}_n^{-1}(\mathbf{t}) G n − 1 ( t ) t \mathbf{t} t G n \mathbf{G}_n G n G n − 1 \mathbf{G}_n^{-1} G n − 1 G n G n − 1 ( t ) = t \mathbf{G}_n \mathbf{G}_n^{-1}(\mathbf{t}) = \mathbf{t} G n G n − 1 ( t ) = t
例如，R 10 = Z 10 [ X ] / ( X 3 + 1 ) \mathcal{R}_{10} = \mathbb{Z}_{10} [X]/(X^3+1) R 10 = Z 10 [ X ] / ( X 3 + 1 ) t = ( t 1 , t 2 ) = ( 6 + 2 X + 5 X 2 , 4 + X + 9 X 2 ) ∈ R 10 2 \mathbf{t} = (t_1, t_2) = (6+2X+5X^2, 4+X+9X^2) \in \mathcal{R}_{10}^2 t = ( t 1 , t 2 ) = ( 6 + 2 X + 5 X 2 , 4 + X + 9 X 2 ) ∈ R 10 2 δ = ⌈ log 10 ⌉ = 4 \delta = \lceil \log 10 \rceil = 4 δ = ⌈ log 10 ⌉ = 4 G 3 − 1 ( t ) \mathbf{G}_3^{-1}(\mathbf{t}) G 3 − 1 ( t ) ( 6 , 5 , 1 ) , ( 4 , 9 , 2 ) (6,5,1),(4,9,2) ( 6 , 5 , 1 ) , ( 4 , 9 , 2 ) ( 0110 , 0010 , 0101 , 0100 , 1001 , 0010 ) (0110,0010,0101,0100,1001,0010) ( 0110 , 0010 , 0101 , 0100 , 1001 , 0010 ) R q \mathcal{R}_q R q t ^ = ( 0 + X + X 2 , 0 + 0 X + 0 X 2 , 1 + 0 X + 0 X 2 , 1 + 0 X + 1 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 ) ∈ R 2 δ \hat{\mathbf{t}} = (0+X+X^2, 0+0X+0X^2, 1+0X+0X^2, 1+0X+1X^2, 0+X+0X^2, 0+X+0X^2, 0+X+0X^2, 0+X+0X^2)\in \mathcal{R}^{2 \delta} t ^ = ( 0 + X + X 2 , 0 + 0 X + 0 X 2 , 1 + 0 X + 0 X 2 , 1 + 0 X + 1 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 , 0 + X + 0 X 2 ) ∈ R 2 δ G 3 − 1 ( t ) = t ^ \mathbf{G}_3^{-1}(\mathbf{t}) = \hat{\mathbf{t}} G 3 − 1 ( t ) = t ^
G 3 = [ 1 2 2 3 2 4 0 ⋯ 0 0 ⋯ 0 1 2 2 3 2 4 0 ⋯ 0 0 ⋯ 0 1 2 2 3 2 4 ] \mathbf{G}_3 = \begin{bmatrix} 1 & 2 & 2^3 & 2^4 & 0 &&&&&&\cdots&0\\ 0 & & \cdots &0 & 1 & 2 & 2^3 & 2^4 &0 && \cdots & 0\\ 0 & &\cdots & & & & &0 & 1 & 2 & 2^3 & 2^4 \end{bmatrix} G 3 = ⎣ ⎡ 1 0 0 2 2 3 ⋯ ⋯ 2 4 0 0 1 2 2 3 2 4 0 0 1 2 ⋯ ⋯ 2 3 0 0 2 4 ⎦ ⎤ 表示上述过程的逆运算，即 G 3 t ^ = t = ( 6 + 2 X + 5 X 2 , 4 + X + 9 X 2 ) ∈ R 10 2 \mathbf{G}_3 \hat{\mathbf{t}} = \mathbf{t} = (6+2X+5X^2, 4+X+9X^2) \in \mathcal{R}_{10}^2 G 3 t ^ = t = ( 6 + 2 X + 5 X 2 , 4 + X + 9 X 2 ) ∈ R 10 2
Ajtai 承诺 ¶ 此外，介绍SIS问题与Ajtai承诺的定义。
SIS问题定义为，给定一个公开矩阵 A ∈ R q n × m \mathbf{A} \in \mathcal{R}_q^{n \times m} A ∈ R q n × m z ∈ R q m \mathbf{z} \in \mathcal{R}_q^m z ∈ R q m A z = 0 , ∣ z ∣ ≤ B \mathbf{A}\mathbf{z}=\mathbf{0}, |\mathbf{z}|\leq B Az = 0 , ∣ z ∣ ≤ B
对于一个二进制消息，通过系数填充将其填充成 R \mathcal{R} R m ∈ R n \mathbf{m} \in \mathcal{R}^n m ∈ R n
KeyGen 输入安全参数λ \lambda λ A ∈ R q n × m \mathbf{A} \in \mathcal{R}_q^{n\times m} A ∈ R q n × m Com 输入承诺密钥 A ∈ R q n × m \mathbf{A} \in \mathcal{R}_q^{n\times m} A ∈ R q n × m m ∈ R m \mathbf{m} \in \mathcal{R}^m m ∈ R m t = A m \mathbf{t} = \mathbf{Am} t = Am 关于Ajtai承诺，有3个点可以进一步讨论：1. 承诺的安全性，2. 承诺消息的范数和 3. 承诺值的压缩性质。
承诺的binding性质基于 SIS 问题，如果一个恶意的攻击者想把承诺值 t \mathbf{t} t t = A m ′ \mathbf{t} = \mathbf{Am}' t = Am ′ m − m ′ \mathbf{m-m'} m − m ′ 0 = A m − m ′ , ∣ m − m ′ ∣ ∞ ≤ 2 \mathbf{0} = \mathbf{Am-m}', |\mathbf{m-m}'|_\infty \leq 2 0 = Am − m ′ , ∣ m − m ′ ∣ ∞ ≤ 2
注意到，我们求出SIS问题的解能够满足∣ m − m ′ ∣ ∞ ≤ 2 |\mathbf{m-m}'|_\infty \leq 2 ∣ m − m ′ ∣ ∞ ≤ 2 m \mathbf{m} m m \mathbf{m} m B B B B B B ∣ m − m ′ ∣ ∞ ≤ 2 B |\mathbf{m-m}'|_\infty \leq 2B ∣ m − m ′ ∣ ∞ ≤ 2 B
承诺值的压缩性质体现在，承诺值 t ∈ R q n \mathbf{t} \in \mathcal{R}_q^n t ∈ R q n R q \mathcal{R}_q R q n n n R q \mathcal{R}_q R q m m m n < m n<m n < m
2. Greyhound的承诺方案 ¶ Greyhound承诺可以理解为一个两层Ajtai承诺。
假设要承诺一组（例如 r r r f 1 , … , f r ∈ R q m \mathbf{f}_1, \dots, \mathbf{f}_r \in \mathcal{R}_q^m f 1 , … , f r ∈ R q m f i \mathbf{f}_i f i R q \mathcal{R}_q R q m m m R q \mathcal{R}_q R q
承诺密钥为内层的公开矩阵 A ∈ R q n × m δ \mathbf{A}\in \mathcal{R}_q^{n\times m\delta} A ∈ R q n × m δ B ∈ R q n × r n δ \mathbf{B} \in \mathcal{R}_q^{n \times r n \delta} B ∈ R q n × r n δ
内层承诺：在上一节提到Ajtai承诺的消息应当为二进制字符串。因此，要使用Ajtai承诺对 f 1 , … , f r \mathbf{f}_1, \dots, \mathbf{f}_r f 1 , … , f r G − 1 \mathbf{G}^{-1} G − 1 s i ∈ R q m δ \mathbf{s}_i \in \mathcal{R}_q^{m \delta} s i ∈ R q m δ s i = G m − 1 ( f i ) \mathbf{s}_i = \mathbf{G}_m^{-1}(\mathbf{f}_i) s i = G m − 1 ( f i ) s i \mathbf{s}_i s i
t i : = A s i = A G m − 1 ( f i ) \mathbf{t}_i := \mathbf{As}_i = \mathbf{AG}^{-1}_m(\mathbf{f}_i) t i := As i = AG m − 1 ( f i ) 这样，可以得到 r r r f 1 , . . . , f r \mathbf{f}_1, ...,\mathbf{f}_r f 1 , ... , f r t 1 , . . . , t r ∈ R q n \mathbf{t}_1, ..., \mathbf{t}_r \in \mathcal{R}_q^n t 1 , ... , t r ∈ R q n
外层承诺：内层承诺完成后，我们得到了 r r r t 1 , . . . , t r ∈ R q n \mathbf{t}_1, ..., \mathbf{t}_r \in \mathcal{R}_q^n t 1 , ... , t r ∈ R q n r r r m m m O ( m r ) \mathcal{O}(mr) O ( m r ) O ( 1 ) \mathcal{O}(1) O ( 1 ) t 1 , . . . , t r \mathbf{t}_1, ..., \mathbf{t}_r t 1 , ... , t r t 1 , . . . , t r \mathbf{t}_1, ..., \mathbf{t}_r t 1 , ... , t r G − 1 \mathbf{G}^{-1} G − 1 t 1 , . . . , t r \mathbf{t}_1, ..., \mathbf{t}_r t 1 , ... , t r t ^ i = G − 1 ( t i ) \hat{\mathbf{t}}_i = \mathbf{G}^{-1}(\mathbf{t}_i) t ^ i = G − 1 ( t i )
u : = B [ t ^ 1 ⋮ t ^ r ] ∈ R q n \mathbf{u} := \mathbf{B}\begin{bmatrix} \hat{\mathbf{t}}_1 \\ \vdots \\ \hat{\mathbf{t}}_r \end{bmatrix} \in \mathcal{R}_q^n u := B ⎣ ⎡ t ^ 1 ⋮ t ^ r ⎦ ⎤ ∈ R q n 最后，对一组向量 f 1 , … , f r ∈ R q m \mathbf{f}_1, \dots, \mathbf{f}_r \in \mathcal{R}_q^m f 1 , … , f r ∈ R q m u ∈ R q n \mathbf{u} \in \mathcal{R}_q^n u ∈ R q n
3. Greyhound承诺的多项式求值 ¶ 在上一节我们只讨论了如何承诺一组向量 f 1 , … , f r ∈ R q m \mathbf{f}_1, \dots, \mathbf{f}_r \in \mathcal{R}_q^m f 1 , … , f r ∈ R q m f ( X ) = ∑ i = 0 N − 1 f i X i ∈ R q < N [ X ] f(\mathsf{X}) = \sum_{i=0}^{N-1} f_i \mathsf{X}^i \in \mathcal{R}_q^{<N}[\mathsf{X}] f ( X ) = ∑ i = 0 N − 1 f i X i ∈ R q < N [ X ]
需要注意的是， X \mathsf{X} X f f f R = = Z [ X ] / ( X d + 1 ) \mathcal{R} = = \mathbb{Z}[X]/(X^d + 1) R == Z [ X ] / ( X d + 1 ) X X X
假设 N = m ⋅ r N=m \cdot r N = m ⋅ r f f f x ∈ R q x \in \mathcal{R}_q x ∈ R q y y y f ( x ) = ∑ i = 0 N − 1 f i x i = y f(x) = \sum_{i=0}^{N-1} f_i x^i = y f ( x ) = ∑ i = 0 N − 1 f i x i = y
类似mercury，我们可以把上述求值过程用矩阵和向量的乘法表示：
f ( x ) = [ 1 x x 2 ⋯ x m − 1 ] [ f 0 f m ⋯ f ( r − 1 ) m f 1 f m + 1 ⋯ f ( r − 1 ) m + 1 f 2 f m + 2 ⋯ f ( r − 1 ) m + 2 ⋯ f m − 1 f 2 m − 1 ⋯ f r m − 1 ] [ 1 x m ( x m ) 2 ⋮ ( x m ) r ] . f(x) = [1~x~x^2~\cdots~x^{m-1}] \begin{bmatrix} f_0 & f_m & \cdots & f_{(r-1)m} \\ f_{1} & f_{m+1} &\cdots & f_{(r-1)m+1} \\ f_{2} & f_{m+2} &\cdots & f_{(r-1)m+2} \\ &&\cdots& \\ f_{m-1} & f_{2m-1} &\cdots & f_{rm-1} \end{bmatrix} \begin{bmatrix} 1 \\ x^m \\ (x^m)^2\\ \vdots \\ (x^m)^r \end{bmatrix}. f ( x ) = [ 1 x x 2 ⋯ x m − 1 ] ⎣ ⎡ f 0 f 1 f 2 f m − 1 f m f m + 1 f m + 2 f 2 m − 1 ⋯ ⋯ ⋯ ⋯ ⋯ f ( r − 1 ) m f ( r − 1 ) m + 1 f ( r − 1 ) m + 2 f r m − 1 ⎦ ⎤ ⎣ ⎡ 1 x m ( x m ) 2 ⋮ ( x m ) r ⎦ ⎤ . 因此，如果定义向量 f i = [ f ( i − 1 ) m , f ( i − 1 ) m + 1 , . . . , f i m − 1 ] ∈ R q m \mathbf{f}_i = [ f_{(i-1)m}, f_{(i-1)m+1}, ... , f_{im-1}] \in \mathcal{R}_q^m f i = [ f ( i − 1 ) m , f ( i − 1 ) m + 1 , ... , f im − 1 ] ∈ R q m f f f f 1 , … , f r ∈ R q m \mathbf{f}_1, \dots, \mathbf{f}_r \in \mathcal{R}_q^m f 1 , … , f r ∈ R q m f f f
现在，我们定义向量 a ⊤ = [ 1 x x 2 ⋯ x m − 1 ] \mathbf{a}^\top = [1~x~x^2~\cdots~x^{m-1}] a ⊤ = [ 1 x x 2 ⋯ x m − 1 ] b ⊤ = [ 1 x m … ( x m ) r ] \mathbf{b}^\top = \begin{bmatrix} 1 ~ x^m ~\dots ~ (x^m)^r \end{bmatrix} b ⊤ = [ 1 x m … ( x m ) r ] f f f
f ( x ) = a ⊤ [ f 1 ⋯ f r ] b . f(x) = \mathbf{a}^\top [\mathbf{f}_1 ~ \cdots ~\mathbf{f}_r] \mathbf{b}. f ( x ) = a ⊤ [ f 1 ⋯ f r ] b . 4. 多项式求值的证明 ¶ 多项式求值的证明包括2点：1. 多项式的承诺是正确计算的；2. 多项式求值的运算是正确的。
首先一个证明者需要对多项式 f f f s i = G m − 1 ( f i ) , t i = G n t ^ i = A s i , u = B [ t ^ 1 ⋮ t ^ r ] . \begin{align*} \mathbf{s}_i &= \mathbf{G}^{-1}_m(\mathbf{f}_i), \\ \mathbf{t}_i &= \mathbf{G}_n\hat{\mathbf{t}}_i = \mathbf{As}_i, \\ \mathbf{u} &= \mathbf{B}\begin{bmatrix} \hat{\mathbf{t}}_1 \\ \vdots \\ \hat{\mathbf{t}}_r \end{bmatrix}. \end{align*} s i t i u = G m − 1 ( f i ) , = G n t ^ i = As i , = B ⎣ ⎡ t ^ 1 ⋮ t ^ r ⎦ ⎤ . 由于G \mathbf{G} G f i = G m s i \mathbf{f}_i = \mathbf{G}_m \mathbf{s}_i f i = G m s i
证明多项式求值的正确性，即证明：f ( x ) = a ⊤ [ f 1 ⋯ f r ] b . f(x) = \mathbf{a}^\top [\mathbf{f}_1 ~ \cdots ~\mathbf{f}_r] \mathbf{b}. f ( x ) = a ⊤ [ f 1 ⋯ f r ] b . Greyhound 证明以上4个等式的思路是，由证明者计算与多项式 f i \mathbf{f}_i f i
假设协议的公开参数为承诺密钥A , B \mathbf{A,B} A , B u u u f f f
证明者首先计算f ( x ) f(x) f ( x ) w \mathbf{w} w
w ⊤ : = a ⊤ [ f 1 ⋯ f r ] . \mathbf{w}^\top := \mathbf{a}^\top[\mathbf{f}_1 ~ \cdots ~\mathbf{f}_r]. w ⊤ := a ⊤ [ f 1 ⋯ f r ] . 验证者选择一个随机挑战向量 c = ( c 1 , . . . , c r ) ∈ R q r \mathbf{c} = (c_1, ..., c_r) \in \mathcal{R}_q^r c = ( c 1 , ... , c r ) ∈ R q r
证明者发送中间承诺 ( t ^ 1 , . . . , t ^ r ) (\hat{\mathbf{t}}_1, ...,\hat{\mathbf{t}}_r) ( t ^ 1 , ... , t ^ r ) c \mathbf{c} c s i \mathbf{s}_i s i z : = [ s 1 ⋯ s r ] c = s 1 c 1 + . . . + s r c r ∈ R q m \mathbf{z} := [\mathbf{s}_1 ~ \cdots~ \mathbf{s}_r] \mathbf{c} = \mathbf{s}_1c_1 + ... +\mathbf{s}_r c_r\in \mathcal{R}_q^m z := [ s 1 ⋯ s r ] c = s 1 c 1 + ... + s r c r ∈ R q m
最后，验证者使用证明者发送的所有信息w , t ^ i , z \mathbf{w}, \hat{\mathbf{t}}_i, \mathbf{z} w , t ^ i , z
w ⊤ b = y , w ⊤ c = a ⊤ G m z , A z = c 1 G n t ^ 1 + ⋯ + c r G n t ^ r , u = B [ t ^ 1 ⋮ t ^ r ] . \begin{align}
\mathbf{w}^\top \mathbf{b} &= y, \\
\mathbf{w}^\top \mathbf{c} &= \mathbf{a}^\top \mathbf{G}_m \mathbf{z},\\
\mathbf{Az} & = c_1\mathbf{G}_n \hat{\mathbf{t}}_1 + \cdots + c_r \mathbf{G}_n \hat{\mathbf{t}}_r,\\
\mathbf{u} &= \mathbf{B}\begin{bmatrix} \hat{\mathbf{t}}_1 \\ \vdots \\ \hat{\mathbf{t}}_r \end{bmatrix}.
\end{align} w ⊤ b w ⊤ c Az u = y , = a ⊤ G m z , = c 1 G n t ^ 1 + ⋯ + c r G n t ^ r , = B ⎣ ⎡ t ^ 1 ⋮ t ^ r ⎦ ⎤ . 第一个等式实际上是在验证多项式 f ( x ) f(x) f ( x ) w \mathbf{w} w
f ( x ) = a ⊤ [ f 1 ⋯ f r ] b = w ⊤ b = y . f(x) = \mathbf{a}^\top[\mathbf{f}_1 ~ \cdots ~\mathbf{f}_r] \mathbf{b} = \mathbf{w}^\top \mathbf{b} = y. f ( x ) = a ⊤ [ f 1 ⋯ f r ] b = w ⊤ b = y . 第二个等式在挑战向量 c \mathbf{c} c f ( x ) f(x) f ( x )
w ⊤ c = a ⊤ [ f 1 ⋯ f r ] c = a ⊤ G m [ s 1 ⋯ s r ] c = a ⊤ G m z . \begin{align*} \mathbf{w}^\top \mathbf{c} &= \mathbf{a}^\top [\mathbf{f}_1 ~ \cdots ~\mathbf{f}_r] \mathbf{c} \\ & = \mathbf{a}^\top \mathbf{G}_m [\mathbf{s}_1~ \cdots ~\mathbf{s}_r] \mathbf{c} \\
& = \mathbf{a}^\top \mathbf{G}_m \mathbf{z}
\end{align*}. w ⊤ c = a ⊤ [ f 1 ⋯ f r ] c = a ⊤ G m [ s 1 ⋯ s r ] c = a ⊤ G m z . 第三个等式验证了PCS内层承诺的正确性
A z = A s 1 c 1 + . . . + A s r c r = c 1 G n t ^ 1 + ⋯ + c r G n t ^ r . \begin{align*} \mathbf{Az} & = \mathbf{A s}_1 c_1 + ... + \mathbf{A s}_r c_r\\ &= c_1\mathbf{G}_n \hat{\mathbf{t}}_1 + \cdots + c_r \mathbf{G}_n \hat{\mathbf{t}}_r. \\
\end{align*} Az = As 1 c 1 + ... + As r c r = c 1 G n t ^ 1 + ⋯ + c r G n t ^ r . 第四个等式验证了PCS的外层承诺。
这个证明可以进一步使用 Labrador 的递归证明来优化证明尺寸，通过把 (1) 中的等式改写成 Labrador 证明的标准形式，具体细节请参考Greyhound文档。
5. 使用 R q \mathcal{R}_q R q F q \mathbb{F}_q F q ¶ 在之前的介绍中，我们忽略了一个重要的问题：就是所有的运算与证明都是在 R q \mathcal{R}_q R q F q \mathbb{F}_q F q F q \mathbb{F}_q F q R q \mathcal{R}_q R q
从 F q \mathbb{F}_q F q R q \mathcal{R}_q R q F q \mathbb{F}_q F q R q \mathcal{R}_q R q R q \mathcal{R}_q R q F q \mathbb{F}_q F q
定义一种自同构映射 σ : R q → R q \sigma: \mathcal{R}_q \to \mathcal{R}_q σ : R q → R q R q \mathcal{R}_q R q σ X = X − 1 \sigma{X} = X^{-1} σ X = X − 1 a = a 0 + ∑ i = 1 d − 1 a i X i ∈ R q a = a_0 + \sum_{i=1}^{d-1} a_i X^i \in \mathcal{R}_q a = a 0 + ∑ i = 1 d − 1 a i X i ∈ R q σ ( a ) = a 0 + ∑ i = 1 d − 1 a i X − i ∈ R q \sigma(a) = a_0 +\sum_{i=1}^{d-1} a_i X^{-i} \in \mathcal{R}_q σ ( a ) = a 0 + ∑ i = 1 d − 1 a i X − i ∈ R q R q \mathcal{R}_q R q a σ a a\sigma{a} aσ a a 0 a 0 + ∑ i = 1 d − 1 a i a i = ∑ i = 0 d − 1 a i a i c a_0 a_0 + \sum_{i=1}^{d-1} a_i a_i = \sum_{i=0}^{d-1} a_i a_ic a 0 a 0 + ∑ i = 1 d − 1 a i a i = ∑ i = 0 d − 1 a i a i c a a a σ ( a ) \sigma(a) σ ( a ) X X X
先明确以下符号：F q \mathbb{F}_q F q F ( U ) = ∑ i = 0 N ′ − 1 F i U i = V ∈ F q F(U) = \sum_{i=0}^{N'-1} F_i U^i = V \in \mathbb{F}_q F ( U ) = ∑ i = 0 N ′ − 1 F i U i = V ∈ F q R q \mathcal{R}_q R q f ( x ) = ∑ i = 0 N − 1 f i x i = y ∈ R q f(x) = \sum_{i=0}^{N-1} f_i x^i = y \in \mathcal{R}_q f ( x ) = ∑ i = 0 N − 1 f i x i = y ∈ R q f f f F F F R q \mathcal{R}_q R q N − 1 N-1 N − 1 f f f N ′ − 1 N'-1 N ′ − 1 F F F N N N N ′ N' N ′
当 N ′ ≤ d N' \leq d N ′ ≤ d N ′ = d N'=d N ′ = d N ′ < d N' < d N ′ < d F F F N ′ = d N'=d N ′ = d R q \mathcal{R}_q R q F F F N = 1 N = 1 N = 1 我们定义F F F f ( x ) = f 0 σ ( x ) f(x) = f_0 \sigma(x) f ( x ) = f 0 σ ( x ) f 0 = ∑ i = 0 d − 1 F i X i ∈ R q f_0 = \sum_{i=0}^{d-1} F_i X^i \in \mathcal{R}_q f 0 = ∑ i = 0 d − 1 F i X i ∈ R q F F F ( F 0 , . . . , F N ′ − 1 ) (F_0, ..., F_{N'-1}) ( F 0 , ... , F N ′ − 1 ) σ ( x ) \sigma(x) σ ( x ) F F F U U U ( 1 , U , . . . , U N ′ − 1 ) (1, U, ..., U^{N'-1}) ( 1 , U , ... , U N ′ − 1 ) x = ∑ i = 0 d − 1 U i X i ∈ R q x = \sum_{i=0}^{d-1} U^i X^i\in \mathcal{R}_q x = ∑ i = 0 d − 1 U i X i ∈ R q σ \sigma σ σ ( x ) = 1 + ∑ i = 1 d − 1 U i X i ∈ R q \sigma(x) = 1+ \sum_{i=1}^{d-1} U^i X^i \in \mathcal{R}_q σ ( x ) = 1 + ∑ i = 1 d − 1 U i X i ∈ R q X X X R q \mathcal{R}_q R q
那么，利用上面讨论的 σ \sigma σ f ( x ) = f 1 σ ( x ) f(x) = f_1 \sigma(x) f ( x ) = f 1 σ ( x )
∑ i = 0 N ′ − 1 F i U i = V . \sum_{i=0}^{N'-1} F_i U^{i} = V. i = 0 ∑ N ′ − 1 F i U i = V . 这意味着，一个Greyhound的验证者可以通过检查 f ( x ) f(x) f ( x ) V V V F ( U ) = V F(U) = V F ( U ) = V
当 N ′ > d N' > d N ′ > d N ′ = N d N' = Nd N ′ = N d F F F ( F 0 , . . . , F N ′ − 1 ) (F_0, ..., F_{N'-1}) ( F 0 , ... , F N ′ − 1 ) N N N R q \mathcal{R}_q R q f 0 , f 1 . . . , f N − 1 ∈ R q f_0, f_1 ..., f_{N-1} \in \mathcal{R}_q f 0 , f 1 ... , f N − 1 ∈ R q f ( x ) f(x) f ( x ) N ′ = d N'=d N ′ = d 我们只需要把 F F F ( f 0 , f 1 . . . , f N − 1 ) (f_0, f_1 ..., f_{N-1}) ( f 0 , f 1 ... , f N − 1 ) ( 1 , U , . . . , U N ′ − 1 ) (1, U, ..., U^{N'-1}) ( 1 , U , ... , U N ′ − 1 ) x 1 , x 2 , . . . , x N ∈ R q x_1, x_2, ..., x_N \in \mathcal{R}_q x 1 , x 2 , ... , x N ∈ R q
f ( x ) = ∑ i = 0 N f i x i . f(x) = \sum_{i=0}^{N} f_i x_i. f ( x ) = i = 0 ∑ N f i x i . 那么，f ( x ) f(x) f ( x ) f i f_i f i x i x_i x i ∑ j = 0 d F i d + j U i d + j \sum_{j=0}^{d} F_{id+j}{U^{id+j}} ∑ j = 0 d F i d + j U i d + j f i x i f_i x_i f i x i R q \mathcal{R}_q R q i = 0 i=0 i = 0 N N N ∑ i = 0 N − 1 f i x i \sum_{i=0}^{N-1} f_i x_i ∑ i = 0 N − 1 f i x i ∑ j = 0 d F i d + j U i d + j \sum_{j=0}^{d} F_{id+j}{U^{id+j}} ∑ j = 0 d F i d + j U i d + j f ( x ) f(x) f ( x )
∑ i = 0 N − 1 ∑ j = 0 d F i d + j U i d + j = ∑ i = 0 N ′ − 1 F i U i = V . \sum_{i=0}^{N-1} \sum_{j=0}^{d} F_{id+j}{U^{id+j}} = \sum_{i=0} ^{N'-1} F_i U^i = V. i = 0 ∑ N − 1 j = 0 ∑ d F i d + j U i d + j = i = 0 ∑ N ′ − 1 F i U i = V . 现在，我们已经可以使用greyhound对任意的 F q \mathbb{F}_q F q
参考文献
[1] Ngoc Khanh Nguyen, Gregor Seiler: Greyhound: Fast Polynomial Commitments from Lattices. CRYPTO (10) 2024: 243-275.