您的位置: 首页  >  文章  >  Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 学习笔记

Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 学习笔记

分类: 文章 • 2024-09-08 09:02:04

1. 引言

Bayer和Groth 2013年论文《Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists》，发表于EuroCrypt 2013。

要点：
1）基于DL assumption，实现了证明commitments c 1 , c 2 , ⋯   , c d c_1,c_2,\cdots, c_d c1​,c2​,⋯,cd​ to u 2 1 , u 2 2 , ⋯   , u 2 d u^{2^1},u^{2^2},\cdots , u^{2^d} u21,u22,⋯,u2d are well formed，Prover发送commitments c f u j = C o m ( f j u 2 j ) c_{fu_j}=Com(f_ju^{2^j}) cfuj​​=Com(fj​u2j)给Verifier。【而不需要借助pairing】
Verifier：
验证：
c j + 1 x u j − f ˉ j c f u j = C o m ( x u 2 j + 1 − ( x u 2 j + f j ) u 2 j + f j u 2 j ) = C o m ( 0 ) c_{j+1}^xu_{j}^{-\bar{f}_j}c_{fu_j}=Com(xu^{2^{j+1}}-(xu^{2^j}+f_j)u^{2^j}+f_ju^{2^j})=Com(0) cj+1x​uj−fˉ​j​​cfuj​​=Com(xu2j+1−(xu2j+fj​)u2j+fj​u2j)=Com(0)
即可。

2）基于DL assumption，构建了polynomial evaluation argument，针对的场景为：【communication cost 为 O ( log ⁡ D ) O(\log D) O(logD)，其中 D D D为polynomial degree。】

  • public info：polynomial P ( X ) P(X) P(X) of degree D D D，commitments c 0 c_0 c0​和 c v c_v cv​
  • private info： u u u和 v v v
  • relation： P ( u ) = v P(u)=v P(u)=v 且 c 0 = c o m c k ( u ) = c o m c k ( u 2 0 ) c_0=com_{ck}(u)=com_{ck}(u^{2^0}) c0​=comck​(u)=comck​(u20) 且 c v = c o m c k ( v ) c_v=com_{ck}(v) cv​=comck​(v)

3）基于本文的polynomial evaluation argument实现了membership proof和non-membership proof。要点为构建多项式 P ( X ) = ∏ i = 1 D ( X − λ i ) P(X)=\prod_{i=1}^{D}(X-\lambda_i) P(X)=∏i=1D​(X−λi​)。

Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 学习笔记

verification of a polynomial’s evaluation in a secret committed value可用于non-membership proof或membership proof。

  • 构建了a novel special honest verifier zero-knowledge argument for correct polynomial evaluation，该argument communication cost 为 O ( log ⁡ N ) O(\log N) O(logN)，其中 N N N为the polynomial degree，相比于之前的 O ( N 1 3 ) O(N^{\frac{1}{3}}) O(N31​) communication complexity有了大幅改进。
  • polynomial evaluation argument为 3-move structure，基于 discrete logarithm assumption。
  • 该polynomial evaluation argument可用于构建zero-knowledge membership and non-membership arguments with communication that is logarithmic in the size of the blacklist。
    non-membership proofs可用于design anonymous blacklisting schemes allowing online services to block misbehaving users without learning the identity of the user，同时支持blocking of single users of anonymization networks without blocking the whole network。

与普通的polynomial commitment 中的evaluation point u u u为public info不同，本文针对的场景为：（其中evaluation point u u u为secret info）

  • public info：polynomial P ( X ) P(X) P(X) of degree D D D，commitments to u u u和 v v v
  • private info： u u u和 v v v
  • relation： P ( u ) = v P(u)=v P(u)=v

针对以上场景，本文构建的polynomial evaluation argument具有如下特性：

  • 基于discrete logarithm assumption in a prime order group。
  • 标准的3-round public coin structure，且 common reference string仅有少量group elements。
  • communication 随着polynomial degree 对数增长。
  • Prover和Verifier都是computationally efficient的。
  • 使用了真实数据做了相应实现。

polynomial evaluation argument 可用于blacklisting anonymous users。
*允许匿名postings，支持阻止IP address of misbehaving users，但是直接阻止IP的方案过于crude，存在以下问题：
若one user of 匿名网络Tor abuses Wikipedia，则all users whose traffic comes out of the same Tor relay with this IP-address are blocked。因此one misbehaving user causes many innocent users to be punished。
Johnson等人 2007年论文《Nymble: Anonymous ip-address blocking》中提出了使用Nymble system来借鉴该问题。

  • 相比于直接禁用IP地址，可要求每个用户anonymously proves that she has not been blacklisted。借助本文的polynomial evaluation argument，可构建a non-membership proof，使得a user to efficiently prove that she has not been blacklisted。
  • 也可使用本文的polynomial evaluation argument来构建efficient membership proofs。Membership proofs可广泛用于白名单访问控制系统，或者如e-voting或e-auction应用中where users want to prove that their votes are valid or their bids belong to a set of approved values。

使用prime order p p p group G \mathbb{G} G和Pedersen commitment scheme。
polynomial P ( X ) = ∑ i = 1 D a i X i P(X)=\sum_{i=1}^{D}a_iX^i P(X)=∑i=1D​ai​Xi的系数为public info。
已知a list of values L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​} 和a Pedersen commitment c c c，membership proof对应为证明 c c c is a commitment to u ∈ L u\in\mathcal{L} u∈L，non-membership proof对应为证明 c c c is a commitment to u ∉ L u\notin \mathcal{L} u∈/​L：
根据Brands等人2007年论文《A practical system for globally revoking the unlinkable pseudonyms of unknown users》中的思路，可构建多项式 P ( X ) = ∏ i = 1 D ( X − λ i ) P(X)=\prod_{i=1}^{D}(X-\lambda_i) P(X)=∏i=1D​(X−λi​)，membership proof对应为证明 P ( u ) = 0 P(u)=0 P(u)=0，non-membership proof对应为证明 P ( u ) ≠ 0 P(u)\neq 0 P(u)​=0。相应的communication cost为 O ( log ⁡ D ) O(\log D) O(logD)。

1.1 polynomial evaluation argument相关研究

1.2 membership proof和non-membership proof相关研究

针对a committed u ∈ L u\in\mathcal{L} u∈L or u ∉ L u\notin \mathcal{L} u∈/​L where L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}
直观的证明方式是：

  • 对于non-membership proof，相当于证明 λ 1 ≠ u 1 ∧ ⋯ ∧ λ D ≠ u \lambda_1\neq u_1 \wedge \cdots \wedge \lambda_D\neq u λ1​​=u1​∧⋯∧λD​​=u。
  • 对于membership proof，相当于证明 λ 1 = u ∨ ⋯ ∨ λ D = u \lambda_1=u \vee \cdots \vee \lambda_D=u λ1​=u∨⋯∨λD​=u。

membership proof和non-membership proof相关研究有：

累加器[2, 9, 37, 29, 8, 38] 可提供另一种实现membership proof的机制。
non-membership 累加器在[22,39]等论文中提出。
大多数的累加器都依赖a trusted party to maintain the accumulator。
目前密码学累加器多基于strong RSA assumption或pairing-based q q q-SDH assumption，而不是discrete logarithm assumption。

2. polynomial evaluation argument

针对的场景为：

  • public info：polynomial P ( X ) P(X) P(X) of degree D D D，commitments c 0 c_0 c0​和 c v c_v cv​
  • private info： u u u和 v v v
  • relation： P ( u ) = v P(u)=v P(u)=v 且 c 0 = c o m c k ( u ) = c o m c k ( u 2 0 ) c_0=com_{ck}(u)=com_{ck}(u^{2^0}) c0​=comck​(u)=comck​(u20) 且 c v = c o m c k ( v ) c_v=com_{ck}(v) cv​=comck​(v)

通过附加zero-coefficients策略，可假设 D = 2 d + 1 − 1 D=2^{d+1}-1 D=2d+1−1。
基本思路为：

  • 1）将序号 i i i以二进制形式表示，即 i = i d ⋯ i 0 i=i_d\cdots i_0 i=id​⋯i0​，其中 i j ∈ { 0 , 1 } i_j\in\{0,1\} ij​∈{0,1}。
    可将term U i U^i Ui表示为 U i = U ∑ j = 0 d i j 2 j = ∏ j = 0 d ( U 2 j ) i j U^i=U^{\sum_{j=0}^{d}i_j2^j}=\prod_{j=0}^{d}(U^{2^j})^{i_j} Ui=U∑j=0d​ij​2j=∏j=0d​(U2j)ij​，将其替换进多项式中有：
    P ( U ) = ∑ i = 0 D a i U i = ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d ( U 2 j ) i j P(U)=\sum_{i=0}^{D}a_iU^i=\sum_{i_0,\cdots,id=0}^{1}a_{i_d\cdots i_0}\prod_{j=0}^{d}(U^{2^j})^{i_j} P(U)=∑i=0D​ai​Ui=∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​(U2j)ij​

  • 2）Prover将make commitments c 1 , c 2 , ⋯   , c d c_1,c_2,\cdots, c_d c1​,c2​,⋯,cd​ to u 2 1 , u 2 2 , ⋯   , u 2 d u^{2^1},u^{2^2},\cdots , u^{2^d} u21,u22,⋯,u2d，然后采用stantdard techniques来证明they are well-formed【见后续第8)步】，然后证明 ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d ( u 2 j ) i j = v \sum_{i_0,\cdots,id=0}^{1}a_{i_d\cdots i_0}\prod_{j=0}^{d}(u^{2^j})^{i_j}=v ∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​(u2j)ij​=v。由于 d = ⌊ log ⁡ D ⌋ d=\left \lfloor \log D \right \rfloor d=⌊logD⌋，prover仅需make a logarithmic number of commitments，将有助于keep communication low。

  • 3）为了证明 the committed powers of u u u in c 0 , c 1 , ⋯   , c d c_0,c_1,\cdots,c_d c0​,c1​,⋯,cd​ evaluate to the committed v v v，Prover引入随机值 f 0 , ⋯   , f ) d ← Z p f_0,\cdots,f)d\leftarrow \mathbb{Z}_p f0​,⋯,f)d←Zp​，构建新的多项式：
    $Q(X)= ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d ( X u 2 j + f j ) i j X 1 − i j = X d + 1 P ( u ) + X d δ d + ⋯ + X δ 1 + δ 0 \sum_{i_0,\cdots,id=0}^{1} a_{i_d\cdots i_0}\prod_{j=0}^{d}(Xu^{2^j}+f_j)^{i_j}X^{1-i_j}=X^{d+1}P(u)+X^d\delta_d+\cdots +X\delta_1+\delta_0 ∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​(Xu2j+fj​)ij​X1−ij​=Xd+1P(u)+Xdδd​+⋯+Xδ1​+δ0​

  • 4）为了证明the coefficient of X d + 1 X^{d+1} Xd+1 in the secret Q ( X ) Q(X) Q(X) is the same as v v v in a way that cancels out the δ 0 , ⋯   , δ d \delta_0,\cdots,\delta_d δ0​,⋯,δd​ coefficients。
    Prover 发送给 Verifier commitments c f 0 , ⋯   , c f d c_{f_0},\cdots , c_{f_d} cf0​​,⋯,cfd​​ to f 0 , ⋯   , f d f_0,\cdots,f_d f0​,⋯,fd​ 以及 commitments c δ 0 , ⋯   , c δ d c_{\delta_0},\cdots,c_{\delta_d} cδ0​​,⋯,cδd​​ to δ 0 , ⋯   , δ d \delta_0,\cdots,\delta_d δ0​,⋯,δd​。

  • 5）Verifier：发送random challenge x ← Z p x\leftarrow \mathbb{Z}_p x←Zp​。

  • 6）Prover：需要证明 Q ( x ) = x d + 1 v + x d δ d + ⋯ + δ 0 Q(x)=x^{d+1}v+x^d\delta_d+\cdots + \delta_0 Q(x)=xd+1v+xdδd​+⋯+δ0​。
    由于Pedersen commitment具有同态属性：
    即对于 c a = C o m ( a ) , c b = C o m ( b ) c_a=Com(a), c_b=Com(b) ca​=Com(a),cb​=Com(b)，满足： c a ⋅ c b = C o m ( a + b ) c_a\cdot c_b=Com(a+b) ca​⋅cb​=Com(a+b) 以及 c a x ⋅ c b = C o m ( a x + b ) c_a^x\cdot c_b=Com(ax+b) cax​⋅cb​=Com(ax+b)。
    于是有，Prover可open each product c j x c f j c_j^xc_{f_j} cjx​cfj​​ to f ˉ j = x u 2 j + f j \bar{f}_j=xu^{2^j}+f_j fˉ​j​=xu2j+fj​。
    Prover将 f ˉ j \bar{f}_j fˉ​j​ for j = 0 , ⋯   , d j=0,\cdots,d j=0,⋯,d 发送给Verifier。

  • 7）Verifier：根据收到的 f ˉ j \bar{f}_j fˉ​j​，计算相应的 δ ˉ = ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d f ˉ j i j x 1 − i j \bar{\delta}=\sum_{i_0,\cdots,id=0}^{1} a_{i_d\cdots i_0}\prod_{j=0}^{d}\bar{f}_j^{i_j}x^{1-i_j} δˉ=∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​fˉ​jij​​x1−ij​，验证：
    C o m ( f ˉ j ) = c j x c f j Com(\bar{f}_j)= c_j^xc_{f_j} Com(fˉ​j​)=cjx​cfj​​
    和
    C o m ( δ ˉ ) = c v x d + 1 ∏ j = 0 d c δ j x j Com(\bar{\delta})= c_v^{x^{d+1}}\prod_{j=0}^{d}c_{\delta_j}^{x^j} Com(δˉ)=cvxd+1​∏j=0d​cδj​xj​
    是否成立即可。

  • 8）为了证明commitments c 1 , c 2 , ⋯   , c d c_1,c_2,\cdots, c_d c1​,c2​,⋯,cd​ to u 2 1 , u 2 2 , ⋯   , u 2 d u^{2^1},u^{2^2},\cdots , u^{2^d} u21,u22,⋯,u2d are well formed，Prover发送commitments c f u j = C o m ( f j u 2 j ) c_{fu_j}=Com(f_ju^{2^j}) cfuj​​=Com(fj​u2j)给Verifier。

  • 9）Verifier：
    验证： c j + 1 x u j − f ˉ j c f u j = C o m ( x u 2 j + 1 − ( x u 2 j + f j ) u 2 j + f j u 2 j ) = C o m ( 0 ) c_{j+1}^xu_{j}^{-\bar{f}_j}c_{fu_j}=Com(xu^{2^{j+1}}-(xu^{2^j}+f_j)u^{2^j}+f_ju^{2^j})=Com(0) cj+1x​uj−fˉ​j​​cfuj​​=Com(xu2j+1−(xu2j+fj​)u2j+fj​u2j)=Com(0)
    即可。

添加blinding randomness，完整的zero-knowledge polynomial evaluation argument为：
【

  • communication cost约为 4 d 4d 4d group elements和 3 d 3d 3d field elements。
  • Prover computation为： 8 d 8d 8d exponentiations in G \mathbb{G} G 来计算the commitments，以及需要计算满足 ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d ( X u 2 j + f j ) i j X 1 − i j = X d + 1 P ( u ) + X d δ d + ⋯ + X δ 1 + δ 0 \sum_{i_0,\cdots,id=0}^{1} a_{i_d\cdots i_0}\prod_{j=0}^{d}(Xu^{2^j}+f_j)^{i_j}X^{1-i_j}=X^{d+1}P(u)+X^d\delta_d+\cdots +X\delta_1+\delta_0 ∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​(Xu2j+fj​)ij​X1−ij​=Xd+1P(u)+Xdδd​+⋯+Xδ1​+δ0​的 δ 0 , ⋯   , δ d \delta_0,\cdots,\delta_d δ0​,⋯,δd​，需要 2 d D 2dD 2dD multiplications in Z p \mathbb{Z}_p Zp​。
  • Verifier computation为：由于verification中使用了2次 x x x，Verifier需要 6 d 6d 6d exponentiations in G \mathbb{G} G。同时为了计算 ∑ i 0 , ⋯   , i d = 0 1 a i d ⋯ i 0 ∏ j = 0 d f ˉ j i j x 1 − i j \sum_{i_0,\cdots,id=0}^{1} a_{i_d\cdots i_0}\prod_{j=0}^{d}\bar{f}_j^{i_j}x^{1-i_j} ∑i0​,⋯,id=01​aid​⋯i0​​∏j=0d​fˉ​jij​​x1−ij​ 需要 2 D 2D 2D multiplications in Z p \mathbb{Z}_p Zp​。
  • 借助multi-exponentiation 技术可进一步reduce Prover和Verifier的计算量。
    】

Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 学习笔记

3. Non-membership argument

针对的场景为：

  • Public info: KaTeX parse error: Undefined control sequence: \proc at position 6: P(X)=\̲p̲r̲o̲c̲_{i=1}^{D}(X-\l…，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​
  • private info： u u u
  • relation： u ∉ L u\notin \mathcal{L} u∈/​L 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u)

可转换为：

  • Public info: KaTeX parse error: Undefined control sequence: \proc at position 6: P(X)=\̲p̲r̲o̲c̲_{i=1}^{D}(X-\l…，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​ 和 commitment c v c_v cv​
  • private info： u , v u,v u,v
  • relation： P ( u ) = v P(u)=v P(u)=v 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u) 且 v ≠ 0 v\neq 0 v​=0 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v)

进一步转换为：

  • Public info: KaTeX parse error: Undefined control sequence: \proc at position 6: P(X)=\̲p̲r̲o̲c̲_{i=1}^{D}(X-\l…，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​ 和 commitment c v c_v cv​以及commitment c w c_w cw​
  • private info： u , v , w u,v,w u,v,w
  • relation： P ( u ) = v P(u)=v P(u)=v 且 w = v − 1 w=v^{-1} w=v−1 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v) 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u) 且 c w = C o m ( w ) c_w=Com(w) cw​=Com(w)

non-membership argument可拆分为2部分并行执行：
1）借助以上polynomial evaluation argument证明“ P ( u ) = v P(u)=v P(u)=v 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v) 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u)“；

2）借助 Chaum和Pedersen 1992年论文《Wallet databases with observers》中的思路来证明 “ w = v − 1 w=v^{-1} w=v−1 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v) 且 c w = C o m ( w ) c_w=Com(w) cw​=Com(w) “：
具体的场景为：

  • public info：generator g g g, commitment c v , c w c_v,c_w cv​,cw​
  • private info： v , w v,w v,w
  • relation： v ⋅ w = 1 v\cdot w=1 v⋅w=1 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v) 且 c w = C o m ( w ) c_w=Com(w) cw​=Com(w)

证明思路为：【multiplication argument】
Prover：commit to z 0 = g v ⋅ w z_0=g^{v\cdot w} z0​=gv⋅w，选择random s 1 ∈ Z P ∗ s_1\in\mathbb{Z}_P^* s1​∈ZP∗​，计算 a 0 = g s 1 , b 0 = c w s 1 = g w s 1 a_0=g^{s_1},b_0=c_w^{s_1}=g^{ws_1} a0​=gs1​,b0​=cws1​​=gws1​。
将commitments z 0 , a 0 , b 0 z_0,a_0,b_0 z0​,a0​,b0​发送给Verifier。
此时拆分为两组证明： z 0 = c v w ∧ c w = g w z_0=c_v^w\wedge c_w=g^w z0​=cvw​∧cw​=gw 和 z 0 = c w v ∧ c v = g v z_0=c_w^v\wedge c_v=g^v z0​=cwv​∧cv​=gv
借助 博客 基于Sigma protocol实现的零知识证明protocol集锦 “Protocol 5. Equality of the opening of 2 Pedersen commitment” 即可完成相应的证明。
Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists 学习笔记

4. membership argument

针对的场景为：

  • Public info: KaTeX parse error: Undefined control sequence: \proc at position 6: P(X)=\̲p̲r̲o̲c̲_{i=1}^{D}(X-\l…，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​
  • private info： u u u
  • relation： u ∈ L u\in \mathcal{L} u∈L 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u)

可转换为：

  • Public info: KaTeX parse error: Undefined control sequence: \proc at position 6: P(X)=\̲p̲r̲o̲c̲_{i=1}^{D}(X-\l…，以及set L = { λ 1 , ⋯   , λ D } \mathcal{L}=\{\lambda_1,\cdots,\lambda_D\} L={λ1​,⋯,λD​}，commitment c u c_u cu​和commitment c v c_v cv​
  • private info： u , v u,v u,v
  • relation： P ( u ) = v P(u)=v P(u)=v 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u) 且 c v = C o m ( v ) = C o m ( 0 ) c_v=Com(v)=Com(0) cv​=Com(v)=Com(0)

membership argument可拆分为2部分并行执行：
1）借助以上polynomial evaluation argument证明“ P ( u ) = v P(u)=v P(u)=v 且 c v = C o m ( v ) c_v=Com(v) cv​=Com(v) 且 c u = C o m ( u ) c_u=Com(u) cu​=Com(u)“；

2）借助 Schnorr 1991年论文《Efficient signature generation by smart cards》中的思路，证明 c v = C o m ( v ) = C o m ( 0 ) c_v=Com(v)=Com(0) cv​=Com(v)=Com(0)。

多项式 P ( X ) = ∏ i = 1 D ( X − λ i ) P(X)=\prod_{i=1}^{D}(X-\lambda_i) P(X)=∏i=1D​(X−λi​)的系数可computed in a binary tree fashion with the linear functions X − λ i X-\lambda_i X−λi​ as leaves。
当 p p p为an FFT friendly prime时，借助FFT，两个degree 为 n n n的多项式乘积仅需 O ( n log ⁡ n ) O(n\log n) O(nlogn) multiplications in Z p \mathbb{Z}_p Zp​。
若list为固定的，则多项式的系数仅需计算以此。
single element additions or deletions can be done using D D D multiplications。
若multiple elements are added or deleted at the same time，the per element cost can be reduced by using fast polynomial multiplication and division techniques。

相关推荐