轻量级加法同态算法

轻量级加法同态算法

潘无穷，顾洪良

潘无穷，顾洪良, 蚂蚁集团. E-mail: wuqiong.pwq@antgroup.com.

我们发现目前的加法同态算法基本都是基于公钥体制的，少数的几个基于对称体制的加法同态算法，都被陆续发现有安全问题。因此，我们尝试设计了一种基于对称体制的加法同态算法，并寄希望因为不需要满足“公钥和私钥不同”，而获得更高的性能。与Paillier等标准的加法同态算法相比，目标将加解密的消耗从模幂降为模乘，将密文加的消耗从模乘降为模加。

目前算法存在一些安全问题，我们正在修正中。 网站不允许撤稿，只能以这种方式先更新一下。

1 变量

𝐗𝐠:𝐡subscript𝐗:𝐠𝐡\mathbf{X_{g:h}}bold_X start_POSTSUBSCRIPT bold_g : bold_h end_POSTSUBSCRIPT：

Xg:hsubscript𝑋:𝑔ℎX_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT是指X𝑋Xitalic_X从第g𝑔gitalic_g比特到第hℎhitalic_h比特的数据(含g𝑔gitalic_g，不含hℎhitalic_h；g≤h𝑔ℎg\leq hitalic_g ≤ italic_h;第00比特为最低位)。若X𝑋Xitalic_X为负数，令Xg:h=−|X|g:hsubscript𝑋:𝑔ℎsubscript𝑋:𝑔ℎX_{g:h}=-|X|_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT = - | italic_X | start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT。

Xg:∞subscript𝑋:𝑔X_{g:\infty}italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT指X𝑋Xitalic_X从第g𝑔gitalic_g比特到最高位的数据（含g𝑔gitalic_g）。

记Xg:h¯=2g⁢Xg:hsubscript𝑋¯:𝑔ℎsuperscript2𝑔subscript𝑋:𝑔ℎX_{\overline{g:h}}=2^{g}X_{g:h}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : italic_h end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT，Xg:∞¯=2g⁢Xg:∞subscript𝑋¯:𝑔superscript2𝑔subscript𝑋:𝑔X_{\overline{g:\infty}}=2^{g}X_{g:\infty}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : ∞ end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT

数据结构：算法及证明过程中部分变量采用下面的数据结构：

高位随机数(ρ𝜌\rhoitalic_ρ) ∥∥\|∥ 明文区(η𝜂\etaitalic_η) ∥∥\|∥ 缓冲区(α𝛼\alphaitalic_α) ∥∥\|∥ 低位随机数(ρ𝜌\rhoitalic_ρ)

•

高、低位随机数各ρ𝜌\rhoitalic_ρ比特,用于存放随机数。

•

明文区为η𝜂\etaitalic_η（例如64）比特。

•

缓冲区为α𝛼\alphaitalic_α(例如32)比特，用于解决低位随机数运算进位对明文的影响，要求密文的最大加减法运算次数为2α−4superscript2𝛼42^{\alpha-4}2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT。

•

上述变量满足2⁢ρ+α+η=γ2𝜌𝛼𝜂𝛾2\rho+\alpha+\eta=\gamma2 italic_ρ + italic_α + italic_η = italic_γ。

密钥：{p,q,a,b}𝑝𝑞𝑎𝑏\{p,q,a,b\}{ italic_p , italic_q , italic_a , italic_b }，其中p,q𝑝𝑞p,qitalic_p , italic_q为γ𝛾\gammaitalic_γ（例如1024）比特大素数，且明文区和缓冲区对应的位置为0，即pρ:ρ+η+α=0subscript𝑝:𝜌𝜌𝜂𝛼0p_{\rho:\rho+\eta+\alpha}=0italic_p start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，qρ:ρ+η+α=0subscript𝑞:𝜌𝜌𝜂𝛼0q_{\rho:\rho+\eta+\alpha}=0italic_q start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0；a,b𝑎𝑏a,bitalic_a , italic_b为γ𝛾\gammaitalic_γ比特。

明文：m𝑚mitalic_m，满足m∈[−2η−1,2η−1−1]𝑚superscript2𝜂1superscript2𝜂11m\in[-2^{\eta-1},2^{\eta-1}-1]italic_m ∈ [ - 2 start_POSTSUPERSCRIPT italic_η - 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_η - 1 end_POSTSUPERSCRIPT - 1 ]的整数，且执行同态运算后m𝑚mitalic_m仍需保证在该范围内。

密文：(x,y)𝑥𝑦(x,y)( italic_x , italic_y ), 为ψ𝜓\psiitalic_ψ比特(ψ≥2⁢γ𝜓2𝛾\psi\geq 2\gammaitalic_ψ ≥ 2 italic_γ,这里暂时取ψ𝜓\psiitalic_ψ为2⁢γ2𝛾2\gamma2 italic_γ,例如2048)。

2 加密

加密的核心思想与算法一相同，把明文分成两个分片，然后把两个分片按照前述数据结构使用随机数“夹在中间”，最后再分别将两个分片隐藏在近似公因子问题的误差部分中，具体过程如下：

生成两个ρ𝜌\rhoitalic_ρ比特正随机数ξ,ζ𝜉𝜁\xi,\zetaitalic_ξ , italic_ζ，一个γ𝛾\gammaitalic_γ比特正随机数τ𝜏\tauitalic_τ，定义明文m𝑚mitalic_m的秘密分享为：

{u=2ρ+η+α⁢ξ+2ρ+α⁢m+ζ−τρ:ρ+η+α¯v=τcases𝑢superscript2𝜌𝜂𝛼𝜉superscript2𝜌𝛼𝑚𝜁subscript𝜏¯:𝜌𝜌𝜂𝛼𝑣𝜏\left\{\begin{array}[]{l}u=2^{\rho+\eta+\alpha}\xi+2^{\rho+\alpha}m+\zeta-\tau%

_{\overline{\rho:\rho+\eta+\alpha}}\\

v=\tau\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_u = 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT italic_ξ + 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT italic_m + italic_ζ - italic_τ start_POSTSUBSCRIPT over¯ start_ARG italic_ρ : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL italic_v = italic_τ end_CELL end_ROW end_ARRAY

计算密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )：

{x=(a⁢u)%⁢p+r1⁢py=(b⁢v)%⁢q+r2⁢qcases𝑥percent𝑎𝑢𝑝subscript𝑟1𝑝𝑦percent𝑏𝑣𝑞subscript𝑟2𝑞\left\{\begin{array}[]{l}x=(au)\%p+r_{1}p\\

y=(bv)\%q+r_{2}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = ( italic_a italic_u ) % italic_p + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = ( italic_b italic_v ) % italic_q + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT italic_q end_CELL end_ROW end_ARRAY

, 其中r1,r2subscript𝑟1subscript𝑟2r_{1},r_{2}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT是分别满足[0,2ψ/p−1],[0,2ψ/q−1]0superscript2𝜓𝑝10superscript2𝜓𝑞1[0,2^{\psi}/p-1],[0,2^{\psi}/q-1][ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_p - 1 ] , [ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_q - 1 ]的均匀分布的随机数。

3 同态加

记(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )和(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )为两个密文，则它们的和(x,y𝑥𝑦x,yitalic_x , italic_y)的计算方法为：

x=x1+x2𝑥subscript𝑥1subscript𝑥2x=x_{1}+x_{2}italic_x = italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT + italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，y=y2+y2𝑦subscript𝑦2subscript𝑦2y=y_{2}+y_{2}italic_y = italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT + italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT

4 同态减

记(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )和(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )为两个密文，则它们的差(x,y𝑥𝑦x,yitalic_x , italic_y)的计算方法为：

x=x1−x2𝑥subscript𝑥1subscript𝑥2x=x_{1}-x_{2}italic_x = italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT - italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，y=y2−y2𝑦subscript𝑦2subscript𝑦2y=y_{2}-y_{2}italic_y = italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT - italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT

5 解密

令M′=(a−1⁢x)%⁢p+(b−1⁢y)%⁢qsuperscript𝑀′percentsuperscript𝑎1𝑥𝑝percentsuperscript𝑏1𝑦𝑞M^{{}^{\prime}}=(a^{-1}x)\%p+(b^{-1}y)\%qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q，则

若Mρ+α−1:ρ+α′=0subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼0M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 0,

当m≥0𝑚0m\geq 0italic_m ≥ 0时，m=Mρ+α:ρ+α+η′𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT

当m<0𝑚0m<0italic_m < 0时，m=Mρ+α:ρ+α+η′−2η𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂superscript2𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}-2^{\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT

若Mρ+α−1:ρ+α′=1subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼1M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 1,

当m−1≥0𝑚10m-1\geq 0italic_m - 1 ≥ 0时，m=Mρ+α:ρ+α+η′+1𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂1m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}+1italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT + 1

当m−1<0𝑚10m-1<0italic_m - 1 < 0时，m=Mρ+α:ρ+α+η′+1−2η𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂1superscript2𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}+1-2^{\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT + 1 - 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT

6 解密思路

假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由

(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…，(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加减得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT。对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT；v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。

由加密、同态加和同态减部分可知

{x=a⁢∑i=1w(−1)σ⁢(i)⁢ui+r1′⁢py=b⁢∑i=1w(−1)σ⁢(i)⁢vi+r2′⁢qcases𝑥𝑎superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑟1′𝑝𝑦𝑏superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖superscriptsubscript𝑟2′𝑞\left\{\begin{array}[]{l}x=a\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+r_{1}^{{}^{%

\prime}}p\\

y=b\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}+r_{2}^{{}^{\prime}}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = italic_a ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = italic_b ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q end_CELL end_ROW end_ARRAY

, 其中(−1)σ⁢(i)=1superscript1𝜎𝑖1(-1)^{\sigma(i)}=1( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT = 1代表对相应密文做加法，(−1)σ⁢(i)=−1superscript1𝜎𝑖1(-1)^{\sigma(i)}=-1( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT = - 1代表对相应密文做减法。r1′superscriptsubscript𝑟1′r_{1}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT, r2′superscriptsubscript𝑟2′r_{2}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT分别对应为p𝑝pitalic_p, q𝑞qitalic_q前的系数和。

即

{∑i=1w(−1)σ⁢(i)⁢ui≡a−1⁢x(modp)∑i=1w(−1)σ⁢(i)⁢vi≡b−1⁢y(modq)casessuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞\left\{\begin{array}[]{l}\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}\equiv a^{-1}x%

\pmod{p}\\

\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}\equiv b^{-1}y\pmod{q}\end{array}\right.{ start_ARRAY start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER end_CELL end_ROW start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER end_CELL end_ROW end_ARRAY

记

∑i=1w(−1)σ⁢(i)⁢ui=(a−1⁢x(modp))+t⁢psuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝𝑡𝑝\displaystyle\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}=(a^{-1}x\pmod{p})+tp∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + italic_t italic_p

(1)

∑i=1w(−1)σ⁢(i)⁢vi=(b−1⁢y(modq))+s⁢qsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞𝑠𝑞\displaystyle\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(b^{-1}y\pmod{q})+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_s italic_q

则有∑i=1w(−1)σ⁢(i)⁢ui+∑i=1w(−1)σ⁢(i)⁢vi=(a−1⁢x(modp))+(b−1⁢y(modq))+t⁢p+s⁢q=M′+t⁢p+s⁢qsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑎1𝑥pmod𝑝annotatedsuperscript𝑏1𝑦pmod𝑞𝑡𝑝𝑠𝑞superscript𝑀′𝑡𝑝𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(a^{-1%

}x\pmod{p})+(b^{-1}y\pmod{q})+tp+sq=M^{{}^{\prime}}+tp+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_t italic_p + italic_s italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q，注意，此时t𝑡titalic_t和s𝑠sitalic_s可以为负。

由于p𝑝pitalic_p的ρ𝜌\rhoitalic_ρ到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0，t⁢p𝑡𝑝tpitalic_t italic_p可以看成t𝑡titalic_t与p𝑝pitalic_p的高位部分和低位部分分别相乘。当t𝑡titalic_t比较小的时候，t𝑡titalic_t与p𝑝pitalic_p的低位部分相乘最高影响到ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α位，则t⁢p𝑡𝑝tpitalic_t italic_p的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0。同理，(t⁢p+s⁢q)𝑡𝑝𝑠𝑞(tp+sq)( italic_t italic_p + italic_s italic_q )的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0，从而(t⁢p+s⁢q)𝑡𝑝𝑠𝑞(tp+sq)( italic_t italic_p + italic_s italic_q )最多只会对M′superscript𝑀′M^{\prime}italic_M start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT明文区产生一位的影响。若第ρ+α+η−1𝜌𝛼𝜂1\rho+\alpha+\eta-1italic_ρ + italic_α + italic_η - 1位为0，说明低位没有向高位产生借位，则，∑i=1wui+∑i=1wvisuperscriptsubscript𝑖1𝑤subscript𝑢𝑖superscriptsubscript𝑖1𝑤subscript𝑣𝑖\sum_{i=1}^{w}u_{i}+\sum_{i=1}^{w}v_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT与M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位相同；若第ρ+α+η−1𝜌𝛼𝜂1\rho+\alpha+\eta-1italic_ρ + italic_α + italic_η - 1位为1，说明低位向高位产生了借位，则，∑i=1wui+∑i=1wvisuperscriptsubscript𝑖1𝑤subscript𝑢𝑖superscriptsubscript𝑖1𝑤subscript𝑣𝑖\sum_{i=1}^{w}u_{i}+\sum_{i=1}^{w}v_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT等于M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位的值加1。从而解密过程成立。

严格的证明参见下一章。

7 解密正确性证明

假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由

(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…,(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加减得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。

由加密章节可知，(ui+vi)ρ+α:ρ+α+η=misubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂subscript𝑚𝑖(u_{i}+v_{i})_{\rho+\alpha:\rho+\alpha+\eta}=m_{i}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，(ui+vi)ρ:ρ+αsubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝜌𝛼(u_{i}+v_{i})_{\rho:\rho+\alpha}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_α end_POSTSUBSCRIPT = 0或1。

定理：

解密算法正确。

Proof.

由

{x=a⁢∑i=1w(−1)σ⁢(i)⁢ui+r1′⁢py=b⁢∑i=1w(−1)σ⁢(i)⁢vi+r2′⁢qcases𝑥𝑎superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑟1′𝑝𝑦𝑏superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖superscriptsubscript𝑟2′𝑞\left\{\begin{array}[]{l}x=a\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+r_{1}^{{}^{%

\prime}}p\\

y=b\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}+r_{2}^{{}^{\prime}}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = italic_a ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = italic_b ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q end_CELL end_ROW end_ARRAY

可知，存在t𝑡titalic_t和s𝑠sitalic_s使得∑i=1w(−1)σ⁢(i)⁢ui=(a−1⁢x)%⁢p+t⁢psuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖percentsuperscript𝑎1𝑥𝑝𝑡𝑝\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}=(a^{-1}x)\%p+tp∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + italic_t italic_p,

∑i=1w(−1)σ⁢(i)⁢vi=(b−1⁢y)%⁢q+s⁢qsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖percentsuperscript𝑏1𝑦𝑞𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(b^{-1}y)\%q+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q + italic_s italic_q

则

∑i=1w(−1)σ⁢(i)⁢(ui+vi)=∑i=1w(−1)σ⁢(i)⁢ui+∑i=1w(−1)σ⁢(i)⁢vi=(a−1⁢x)%⁢p+t⁢p+(b−1⁢y)%⁢q+s⁢q=(∑i=1w(−1)σ⁢(i)⁢ui)%⁢p+t⁢p+(∑i=1w(−1)σ⁢(i)⁢vi)%⁢q+s⁢q=M′+t⁢p+s⁢qsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖percentsuperscript𝑎1𝑥𝑝𝑡𝑝percentsuperscript𝑏1𝑦𝑞𝑠𝑞percentsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖𝑝𝑡𝑝percentsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖𝑞𝑠𝑞superscript𝑀′𝑡𝑝𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})\\

=\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}\\

=(a^{-1}x)\%p+tp+(b^{-1}y)\%q+sq\\

=(\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i})\%p+tp+(\sum_{i=1}^{w}(-1)^{\sigma(i)}v_%

{i})\%q+sq\\

=M^{{}^{\prime}}+tp+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + italic_t italic_p + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q + italic_s italic_q = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) % italic_p + italic_t italic_p + ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) % italic_q + italic_s italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q

由于ui<2⁢psubscript𝑢𝑖2𝑝u_{i}<2pitalic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_p，从而−2⁢p<(−1)σ⁢(i)⁢ui<2⁢p2𝑝superscript1𝜎𝑖subscript𝑢𝑖2𝑝-2p<(-1)^{\sigma(i)}u_{i}<2p- 2 italic_p < ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_p, 从而−2⁢w⁢p<∑i=1w(−1)σ⁢(i)⁢ui<2⁢w⁢p2𝑤𝑝superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖2𝑤𝑝-2wp<\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}<2wp- 2 italic_w italic_p < ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_w italic_p，可知t∈(−2⁢w,2⁢w)𝑡2𝑤2𝑤t\in(-2w,2w)italic_t ∈ ( - 2 italic_w , 2 italic_w )，同理可知s∈(−2⁢w,2⁢w)𝑠2𝑤2𝑤s\in(-2w,2w)italic_s ∈ ( - 2 italic_w , 2 italic_w )。

则上式可以改写为M′=∑i=1w(−1)σ⁢(i)⁢(ui+vi)−t⁢p−s⁢q=∑i=1w(−1)σ⁢(i)⁢(ui+vi)+t′⁢p+s′⁢qsuperscript𝑀′superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖𝑡𝑝𝑠𝑞superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscript𝑡′𝑝superscript𝑠′𝑞M^{{}^{\prime}}=\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})-tp-sq=\sum_{i=1}^{%

w}(-1)^{\sigma(i)}(u_{i}+v_{i})+t^{{}^{\prime}}p+s^{{}^{\prime}}qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) - italic_t italic_p - italic_s italic_q = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q，其中t′=−tsuperscript𝑡′𝑡t^{{}^{\prime}}=-titalic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = - italic_t, s′=−ssuperscript𝑠′𝑠s^{{}^{\prime}}=-sitalic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = - italic_s，t′∈(−2⁢w,2⁢w)superscript𝑡′2𝑤2𝑤t^{{}^{\prime}}\in(-2w,2w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w )，s′∈(−2⁢w,2⁢w)superscript𝑠′2𝑤2𝑤s^{{}^{\prime}}\in(-2w,2w)italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w )。

M′=∑i=1w(−1)σ⁢(i)⁢(ui+vi)+t′⁢p+s′⁢q=∑i=1w((−1)σ⁢(i)⁢(ui+vi)ρ+α+η:∞¯+(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯+(−1)σ⁢(i)⁢(ui+vi)0:ρ+α)+t′⁢p0:ρ+t′⁢pρ+α+η:∞¯+s′⁢q0:ρ+s′⁢qρ+α+η:∞¯=(∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α+η:∞¯+t′⁢pρ+α+η:∞¯+s′⁢qρ+α+η:∞¯)+∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯+(∑i=1w(−1)σ⁢(i)⁢(ui+vi)0:ρ+α+t′⁢p0:ρ+s′⁢q0:ρ)superscript𝑀′superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscript𝑡′𝑝superscript𝑠′𝑞superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜂superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑡′subscript𝑝¯:𝜌𝛼𝜂superscript𝑠′subscript𝑞:0𝜌superscript𝑠′subscript𝑞¯:𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜂superscript𝑡′subscript𝑝¯:𝜌𝛼𝜂superscript𝑠′subscript𝑞¯:𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌M^{{}^{\prime}}=\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})+t^{{}^{\prime}}p+s%

^{{}^{\prime}}q\\

=\sum_{i=1}^{w}((-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha+\eta:%

\infty}}+(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta%

}}+(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha})+t^{{}^{\prime}}p_{0:\rho}+t^%

{{}^{\prime}}p_{\overline{\rho+\alpha+\eta:\infty}}+s^{{}^{\prime}}q_{0:\rho}+%

s^{{}^{\prime}}q_{\overline{\rho+\alpha+\eta:\infty}}\\

=(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha+\eta:%

\infty}}+t^{{}^{\prime}}p_{\overline{\rho+\alpha+\eta:\infty}}+s^{{}^{\prime}}%

q_{\overline{\rho+\alpha+\eta:\infty}})+\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v%

_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}+(\sum_{i=1}^{w}(-1)^{\sigma(i)%

}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:%

\rho})italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT + ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT ) + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT + ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT )

由于(ui+vi)ρ:ρ+αsubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝜌𝛼(u_{i}+v_{i})_{\rho:\rho+\alpha}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_α end_POSTSUBSCRIPT = 0或1，当加法次数w<2α−4𝑤superscript2𝛼4w<2^{\alpha-4}italic_w < 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT时，|∑i=1w(−1)σ⁢(i)⁢(ui+vi)0:ρ+α|≤∑i=1w(ui+vi)0:ρ+α=∑i=1w(ui+vi)0:ρ+1<2ρ+1*2α−4<2ρ+α−2superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscriptsubscript𝑖1𝑤subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscriptsubscript𝑖1𝑤subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌1superscript2𝜌1superscript2𝛼4superscript2𝜌𝛼2\left|\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}\right|\leq%

\sum_{i=1}^{w}(u_{i}+v_{i})_{0:\rho+\alpha}=\sum_{i=1}^{w}(u_{i}+v_{i})_{0:%

\rho+1}<2^{\rho+1}*2^{\alpha-4}<2^{\rho+\alpha-2}| ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT | ≤ ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + 1 end_POSTSUBSCRIPT < 2 start_POSTSUPERSCRIPT italic_ρ + 1 end_POSTSUPERSCRIPT * 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 2 end_POSTSUPERSCRIPT。

由于t′∈(−2⁢w,2⁢w)superscript𝑡′2𝑤2𝑤t^{{}^{\prime}}\in(-2w,2w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w ), 从而|t′|<2⁢w≤2*2α−4=2α−3superscript𝑡′2𝑤2superscript2𝛼4superscript2𝛼3\left|t^{{}^{\prime}}\right|<2w\leq 2*2^{\alpha-4}=2^{\alpha-3}| italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT | < 2 italic_w ≤ 2 * 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT = 2 start_POSTSUPERSCRIPT italic_α - 3 end_POSTSUPERSCRIPT, 同理, |s′|<2α−3superscript𝑠′superscript2𝛼3\left|s^{{}^{\prime}}\right|<2^{\alpha-3}| italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT | < 2 start_POSTSUPERSCRIPT italic_α - 3 end_POSTSUPERSCRIPT, 易得|(t′⁢p0:ρ+s′⁢q0:ρ)|<2ρ+α−2superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌superscript2𝜌𝛼2\left|(t^{{}^{\prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:\rho})\right|<2^{\rho+%

\alpha-2}| ( italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 2 end_POSTSUPERSCRIPT。

由上述分析可得，|(∑i=1w(−1)σ⁢(i)⁢(ui+vi)0:ρ+α+t′⁢p0:ρ+s′⁢q0:ρ)|<2ρ+α−1superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌superscript2𝜌𝛼1\left|(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{%

\prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:\rho})\right|<2^{\rho+\alpha-1}| ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 1 end_POSTSUPERSCRIPT。

下面进行分类讨论：

情况1. (∑i=1w(−1)σ⁢(i)⁢(ui+vi)0:ρ+α+t′⁢p0:ρ+s′⁢q0:ρ)≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌0(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_%

{0:\rho}+s^{{}^{\prime}}q_{0:\rho})\geq 0( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) ≥ 0

此时有Mρ+α−1:ρ+α′=0subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼0M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 0，即未产生借位。

当∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha%

+\eta}}\geq 0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ≥ 0时，Mρ+α:ρ+α+η′=(∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯)ρ+α:ρ+α+η=(∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η)=∑i=1w(−1)σ⁢(i)⁢misubscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}%

(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}})_{\rho+\alpha:\rho+%

\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\rho+\alpha:\rho+%

\alpha+\eta})=\sum_{i=1}^{w}(-1)^{\sigma(i)}m_{i}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT。

当∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha%

+\eta}}<0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT < 0时，Mρ+α:ρ+α+η′=(2ρ+α+η+∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯)ρ+α:ρ+α+η=(2η+∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η)=2η+∑i=1w(−1)σ⁢(i)⁢misubscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscript2𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\rho+\alpha+\eta}+\sum_{i=1%

}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}})_%

{\rho+\alpha:\rho+\alpha+\eta}=(2^{\eta}+\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+%

v_{i})_{\rho+\alpha:\rho+\alpha+\eta})=2^{\eta}+\sum_{i=1}^{w}(-1)^{\sigma(i)}%

m_{i}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_α + italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT ) = 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT。

情况2. (∑i=1w(−1)σ⁢(i)⁢(ui+vi)0:ρ+α+t′⁢p0:ρ+s′⁢q0:ρ)<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌0(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_%

{0:\rho}+s^{{}^{\prime}}q_{0:\rho})<0( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) < 0

此时有Mρ+α−1:ρ+α′=1subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼1M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 1，即低位向明文区产生借位。

当∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯−2ρ+α≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha%

+\eta}}-2^{\rho+\alpha}\geq 0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ≥ 0时，Mρ+α:ρ+α+η′=(∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯−2ρ+α)ρ+α:ρ+α+η=(∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η−1)=∑i=1w(−1)σ⁢(i)⁢mi−1subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂1superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖1M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}%

(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}-2^{\rho+\alpha})_{\rho%

+\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\rho+%

\alpha:\rho+\alpha+\eta}-1)=\sum_{i=1}^{w}(-1)^{\sigma(i)}m_{i}-1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 1 ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - 1。

当∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯−2ρ+α<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha%

+\eta}}-2^{\rho+\alpha}<0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT < 0时，Mρ+α:ρ+α+η′=(2ρ+α+η+∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η¯−2ρ+α)ρ+α:ρ+α+η=(2η+∑i=1w(−1)σ⁢(i)⁢(ui+vi)ρ+α:ρ+α+η−1)=2η+∑i=1w(−1)σ⁢(i)⁢mi−1subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscript2𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂1superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖1M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\rho+\alpha+\eta}+\sum_{i=1%

}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}-2%

^{\rho+\alpha})_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\eta}+\sum_{i=1}^{w}(-1)^{%

\sigma(i)}(u_{i}+v_{i})_{\rho+\alpha:\rho+\alpha+\eta}-1)=2^{\eta}+\sum_{i=1}^%

{w}(-1)^{\sigma(i)}m_{i}-1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_α + italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 1 ) = 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - 1。

综上所述，解密算法成立。

∎

8 局限性说明

1、解密方可知密文产生过程经历的加法次数的大概范围；

2、加法次数具有上限；

9 总结

目前算法存在一些安全问题，我们正在修正中。 网站不允许撤稿，只能以这种方式先更新一下。

蚂蚁集团

潘无穷,顾洪良

wuqiong.pwq@antfin.com

January 7, 2024

；