【论文阅读】Comparing encrypted data

论文阅读】Comparing encrypted data"/>

【论文阅读】Comparing encrypted data

【论文阅读】Comparing encrypted data

论文链接：.pdf

作者：Thijs Veugen

发表时间：2011

简介

该论文提出一个新的加密数据处理过程中的高效比较协议。由于其不涉及中间过程加密，因此效率较高适合于轻量级环境，其通信轮数等于输出比特数。性能高于之前的协议（至少在包含预处理复杂度在内时）

背景

有许多研究两个整数比较的安全协议（即百万富翁问题）。

混淆电路给百万富翁问题提供了第一个解决方案并且被大家不断优化改进，近来基于混淆电路的最高效实现是Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider 的方案。

使用同态加密方案有Blake 与 Kolesnikov的方案并且被针对小文本值进行微调的专用加密系统优化。

Fischlin 的系统可以计算两个二次剩余的乘积(AND)，但是需要引入误差参数 λ λ λ 保证结果的正确性，这实际上增加了计算和通信的负载

“Conditional Gate“的想法与本文的方法类似，但其环境是多方恶意模型中的门限解密。

Garay, Schoenmakers 和 Villegas 描述了在多方情况客户端-服务器环境下的一个优秀解决方案，但是由于使用恶意敌手模型，其解决方案效率较低。

KT是半诚信模型下百万富翁问题的有效解决方案，这个解决方案后来也被扩展到多方。

我们在半诚信模型下构造但可拓展为恶意模型，但这将扩大计算与通讯复杂度

实际的新比较协议（包含客户端-服务器模型）称为LSIC（Lightweight Secure Integer Comparison）

加密

[ . ] [.] [.] 表示使用 Quadratic Residues(QR) 进行单比特加密

[ ⁣ [ . ] ⁣ ] [\![.]\!] [[.]] 表示使用Paillier或DGK对整数进行加密

Paillier中的密文空间为 N 2 N^2 N2 ，这里用 N N N 代替

同态性

N是加密系统的模，通常是两个大素数的乘积（在计算复杂度分析中我们假设N是1024 bits长）

[ x ] ⋅ [ y ] = [ x ⊕ y ] m o d N [x]·[y]=[x \oplus y ] \ mod\ N [x]⋅[y]=[x⊕y] mod N

[ ⁣ [ x ] ⁣ ] ⋅ [ ⁣ [ y ] ⁣ ] = [ ⁣ [ x + y ] ⁣ ] m o d N [\![x]\!]·[\![y]\!]=[\![x + y]\!]\ mod\ N [[x]]⋅[[y]]=[[x+y]] mod N

比较计算复杂度

一般的在比较中，我们认为 mod N n N^n Nn 的平均计算复杂度为 3n/2，当 N 已知时，可以使用中国剩余定理将计算复杂度减小至 3n/4

使用欧几里得算法对数值取负 [ ⁣ [ − x ] ⁣ ] ← [ ⁣ [ x ] ⁣ ] − 1 m o d N [\![-x]\!]\gets[\![x]\!]^{-1 } \ mod \ N [[−x]]←[[x]]−1 mod N，这个方法比使用一次模乘更加高效，在Paillier加密中一次模乘的复杂度为 3 2 l o g 2 N \frac{3}{2}log_2 N 23​log2​N

除法与mod的关系

x ÷ y = ( x − ( x m o d y ) ) / y x÷y=(x-(x \ mod \ y))/y x÷y=(x−(x mod y))/y

方案设计

该方案将问题拆解成两步，首先将加密数据比较转换成两个私有整数比较，并提出一套LSIC方案用于高效比较两个私有整数。

这里从私有整数比较协议入手加以介绍。

比较两个私有整数-LSIC方案

介绍

A有一个私有未加密值 a a a ，B有一个私有未加密值 b b b ，两者长度均为 l \mathscr{l} l

我们使用 a l ( 1 ≤ l ≤ l ) a^l(1≤l≤ \mathscr{l}) al(1≤l≤l) 来描述 ∑ i = 0 l − 1 a i 2 i \sum^{l-1}_{i=0}a_i2^i ∑i=0l−1​ai​2i

使用 a i a_i ai​ 和 b i b_i bi​ 来描述 ( 1 ≤ i ≤ l ) (1≤i≤ \mathscr{l}) (1≤i≤l) 的比特位， a 0 a_0 a0​ 与 b 0 b_0 b0​ 是其最低有效位

A、B加密数据，但只有 B 可以解密数据

原理

从 i = 1 i=1 i=1 到 i = l i=\mathscr{l} i=l 计算 ( t i + 1 = 1 ) ≡ ( a i < b i ) o r { ( a i = b i ) a n d ( t i − 1 ) } (t_{i+1}=1)≡(a_i<b_i)\ or\ \{(a_i=b_i)\ and\ (t_i-1)\} (ti+1​=1)≡(ai​<bi​) or {(ai​=bi​) and (ti​−1)}

方案设计

先从最低有效位比特开始执行程序，B 将 [ b 0 ] [b_0] [b0​] 传递给 A，

A 侧根据自己 a 0 a_0 a0​ 的情况进行处理

{ [ t ] ← [ b 0 ] a 0 = 0 [ t ] ← [ 0 ] a 0 = 1 \begin{cases} [t]\gets[b_0]& a_0=0\\ [t]\gets[0]& a_0=1 \end{cases} {[t]←[b0​][t]←[0]​a0​=0a0​=1​

接下来循环处理从 i = 1 i=1 i=1 到 i = l − 1 i=\mathscr{l}-1 i=l−1

首先在 A 侧将 t = t i t=t_i t=ti​ 加以盲化并将 [ τ ] [\tau] [τ] 传递，使得 B 无法得知 t t t 的真实值

B 侧在 A 传递值的基础上计算 [ t b ] [tb] [tb]，并将 [ b i ] [b_i] [bi​] 与 [ t b ] [tb] [tb] 传递给 A

A 侧首先进行去盲，然后计算

{ [ t ] ← [ t ] ⋅ [ b i ] ⋅ [ t b ] a i = 0 [ t ] ← [ t b ] a i = 1 \begin{cases} [t]\gets[t]·[b_i]·[tb]& a_i=0\\ [t]\gets[tb]& a_i=1 \end{cases} {[t]←[t]⋅[bi​]⋅[tb][t]←[tb]​ai​=0ai​=1​

即可获得 t = t i + 1 t=t_{i+1} t=ti+1​，之后循环重复该过程得解。

盲化与去盲

已知：A 侧有 [ t ] [t] [t] ,B 侧有私钥，为了保证A侧信息不泄露，需在 A 侧对其进行盲化

投掷一枚硬币 c ∈ 0 , 1 c \in {0,1} c∈0,1：

{ [ τ ] ← [ t ] c = 0 [ τ ] ← [ 1 ] ⋅ [ t ] m o d N c = 1 \begin{cases} [\tau]\gets[t]& c=0\\ [\tau]\gets[1]·[t]\ mod \ N& c=1 \end{cases} {[τ]←[t][τ]←[1]⋅[t] mod N​c=0c=1​

在 B 侧计算 [ t b ] [tb] [tb]，并将 [ b i ] [b_i] [bi​] 与 [ t b ] [tb] [tb] 传递给 A

{ [ t b ] ← [ 0 ] b i = 0 [ t b ] ← [ τ ] b i = 1 \begin{cases} [tb]\gets[0]& b_i=0\\ [tb]\gets[\tau]& b_i=1 \end{cases} {[tb]←[0][tb]←[τ]​bi​=0bi​=1​

此时 t b = ( c ⊕ t i ) ⋅ b i tb=(c \oplus t_i)·b_i tb=(c⊕ti​)⋅bi​

在 A 侧去盲则有

{ [ t b ] ← [ t b ] ⋅ [ b i ] m o d N c = 1 [ t b ] ← [ t b ] c = 0 \begin{cases} [tb]\gets[tb]·[b_i] \ mod \ N & c=1\\ [tb]\gets[tb]& c=0 \end{cases} {[tb]←[tb]⋅[bi​] mod N[tb]←[tb]​c=1c=0​

此时 t b = t i ⋅ b i tb=t_i·b_i tb=ti​⋅bi​，即通过上述过程 A 获得了 [ t b ] [tb] [tb] 并且没有泄露 [ t ] [t] [t] 的值

Paillier 构造

将其中部分进行修改可获得 Paillier 构造：

细节说明

在大多数比较协议的实现中，随机化部分可以被跳过。只有当一个值被传递给另一个的时候，结果才应该被重新随机化。

例如：在第三行 [ t ] ← [ b 0 ] [t]\gets[b_0] [t]←[b0​]，恰巧之后 [ τ ] ← [ t ] [\tau]\gets[t] [τ]←[t]，那么如果不随机化就会导致信息泄露

加密数据比较

介绍

• 客户 A 拥有两个加密数据 [ ⁣ [ a ] ⁣ ] [\![a]\!] [[a]] 与 [ ⁣ [ b ] ⁣ ] [\![b]\!] [[b]]，长度均为 l b i t s l \ bits l bits
• 服务 B 拥有私钥并且想要比较 a 与 b
• 对 A 与 B 而言，都不知道 a 与 b 的值

原理

• a ≤ b a≤b a≤b ⟺ \iff ⟺ x = b + 2 l − a x=b+2^l-a x=b+2l−a 的首位 ⟺ \iff ⟺ x ÷ 2 l x\div2^l x÷2l（即 l + 1 l+1 l+1 比特的数值 x x x 的首位）

• 转化为 A 与 B 私有值比较，然后结合上述 LSIC 方案得解

方案

A 侧计算 [ ⁣ [ x ] ⁣ ] ← [ ⁣ [ b ] ⁣ ] ⋅ [ ⁣ [ 2 l ] ⁣ ] ⋅ [ ⁣ [ a ] ⁣ ] − 1 [\![x]\!]\gets[\![b]\!]·[\![2^\mathscr{l}]\!]·[\![a]\!]^{-1} [[x]]←[[b]]⋅[[2l]]⋅[[a]]−1

然后 A 选择一个随机值 r r r 将结果盲化，这样 B 侧虽然拥有私钥也无法获得比较结果 [ ⁣ [ z ] ⁣ ] ← [ ⁣ [ x ] ⁣ ] ⋅ [ ⁣ [ r ] ⁣ ] m o d N [\![z]\!]\gets[\![x]\!]·[\![r]\!]\ mod \ N [[z]]←[[x]]⋅[[r]] mod N

注意：这里选择的 r 比特位比 x 多 σ σ σ，但要注意其取值范围 l + 1 + σ < l o g 2 N l + 1+ σ < log_2 N l+1+σ<log2​N

A 侧计算 c ← r m o d 2 l c \gets r \ mod \ 2^\mathscr{l} c←r mod 2l

B 侧计算 d ← z m o d 2 l d \gets z \ mod \ 2^\mathscr{l} d←z mod 2l

AB两方以 cd 两值参与上述私有数值比较获得结果 [ t ] [t] [t] { ( t = 1 ) ≡ ( d < c ) } \{(t=1)≡(d<c)\} {(t=1)≡(d<c)}

最终 B 侧传输 [ z l + 1 ] [z_{\mathscr{l}+1}] [zl+1​]，A 侧计算 [ t ] ← [ z l + 1 ] ⋅ [ r l + 1 ] ⋅ [ t ] [t] \gets [z_{\mathscr{l}+1}]·[r_{\mathscr{l}+1}]·[t] [t]←[zl+1​]⋅[rl+1​]⋅[t] 即为所求。

最后10-12 加以更改则可使用 Paillier 实现

证明

Paillier下的正确性证明

最值获得的 t 应该满足： t = x ÷ 2 l t=x \div 2^l t=x÷2l

其中根据mod计算可知： x = 2 l ⋅ ( x ÷ 2 l ) + x m o d 2 l x=2^l \cdot(x\div 2^l)+x \ mod \ 2^l x=2l⋅(x÷2l)+x mod 2l（可视为 x ÷ 2 l x\div 2^l x÷2l 为其整除部分，而 x m o d 2 l ∈ [ 0 , < 2 l ) x \ mod \ 2^l\in[0,<2^l) x mod 2l∈[0,<2l) 为余数）

同理： r = 2 l ⋅ ( r ÷ 2 l ) + r m o d 2 l r=2^l \cdot(r\div 2^l)+r \ mod \ 2^l r=2l⋅(r÷2l)+r mod 2l

则： z = 2 l ⋅ ( ( r ÷ 2 l ) + ( x ÷ 2 l ) ) + r m o d 2 l + x m o d 2 l z=2^l \cdot((r\div 2^l)+(x\div 2^l))+r \ mod \ 2^l +x \ mod \ 2^l z=2l⋅((r÷2l)+(x÷2l))+r mod 2l+x mod 2l

即： z ÷ 2 l = ( r ÷ 2 l ) + ( x ÷ 2 l ) z\div 2^l=(r\div 2^l)+(x\div 2^l) z÷2l=(r÷2l)+(x÷2l)

z m o d 2 l = r m o d 2 l + x m o d 2 l z \ mod \ 2^l=r \ mod \ 2^l +x \ mod \ 2^l z mod 2l=r mod 2l+x mod 2l

根据 z m o d 2 l z \ mod \ 2^l z mod 2l 的不同大小我们可以进行分类：

1. 当 z m o d 2 l < 2 l z \ mod \ 2^l<2^l z mod 2l<2l 时

{ z ÷ 2 l = ( r ÷ 2 l ) + ( x ÷ 2 l ) z m o d 2 l = r m o d 2 l + x m o d 2 l \begin{cases} z\div 2^l=(r\div 2^l)+(x\div 2^l)\\ \\z \ mod \ 2^l=r \ mod \ 2^l +x \ mod \ 2^l\end{cases} ⎩ ⎨ ⎧​z÷2l=(r÷2l)+(x÷2l)z mod 2l=r mod 2l+x mod 2l​

且 z m o d 2 l = r m o d 2 l + x m o d 2 l ≥ r m o d 2 l z \ mod \ 2^l=r \ mod \ 2^l +x \ mod \ 2^l≥r \ mod \ 2^l z mod 2l=r mod 2l+x mod 2l≥r mod 2l

2. 当 z m o d 2 l ≥ 2 l z \ mod \ 2^l≥2^l z mod 2l≥2l 时

{ z ÷ 2 l = ( r ÷ 2 l ) + ( x ÷ 2 l ) + 1 z m o d 2 l = r m o d 2 l + x m o d 2 l − 2 l \begin{cases} z\div 2^l=(r\div 2^l)+(x\div 2^l)+1\\ \\ z \ mod \ 2^l=r \ mod \ 2^l +x \ mod \ 2^l-2^l\end{cases} ⎩ ⎨ ⎧​z÷2l=(r÷2l)+(x÷2l)+1z mod 2l=r mod 2l+x mod 2l−2l​

且 z m o d 2 l = r m o d 2 l + x m o d 2 l − 2 l < r m o d 2 l z \ mod \ 2^l=r \ mod \ 2^l +x \ mod \ 2^l-2^l<r \ mod \ 2^l z mod 2l=r mod 2l+x mod 2l−2l<r mod 2l

所以： z ÷ 2 l = ( r ÷ 2 l ) + ( x ÷ 2 l ) ≡ z\div 2^l=(r\div 2^l)+(x\div 2^l)≡ z÷2l=(r÷2l)+(x÷2l)≡

​ z m o d 2 l < 2 l ≡ z \ mod \ 2^l<2^l≡ z mod 2l<2l≡
z m o d 2 l ≥ r m o d 2 l ≡ \ z \ mod \ 2^l≥r \ mod \ 2^l≡  z mod 2l≥r mod 2l≡

​ c ≤ d ≡ c≤d≡ c≤d≡

​ t = 0 t=0 t=0

综上 x ÷ 2 l = ( z ÷ 2 l ) − ( r ÷ 2 l ) − t x\div 2^l=(z\div 2^l)-(r\div 2^l)-t x÷2l=(z÷2l)−(r÷2l)−t，其中 t t t 是 c c c 与 d d d 的比较结果

QR加密下的正确性证明

原理基本同上，但结合位运算有

z ÷ 2 l = z l + 1 + σ . . . z l + 1 = 2 ⋅ ( z l + 1 + σ . . . z l + 2 ) + z l + 1 z\div 2^l=z_{l+1+\sigma}...z_{l+1}=2 \cdot(z_{l+1+\sigma}...z_{l+2})+z_{l+1} z÷2l=zl+1+σ​...zl+1​=2⋅(zl+1+σ​...zl+2​)+zl+1​

所以： ( z ÷ 2 l ) m o d 2 = z l + 1 (z\div 2^l)\ mod \ 2=z_{l+1} (z÷2l) mod 2=zl+1​

结合上述证明有： ( x ÷ 2 l ) = ( ( z ÷ 2 l ) − ( r ÷ 2 l ) − t ) m o d 2 = ( z l + 1 − z l + 1 − t ) m o d 2 (x\div 2^l)=((z\div 2^l)-(r\div 2^l)-t)\ mod \ 2=(z_{l+1}-z_{l+1}-t) \ mod \ 2 (x÷2l)=((z÷2l)−(r÷2l)−t) mod 2=(zl+1​−zl+1​−t) mod 2

所以： x ÷ 2 l = z l + 1 ⊕ z l + 1 ⊕ t x\div 2^l=z_{l+1}\oplus z_{l+1}\oplus t x÷2l=zl+1​⊕zl+1​⊕t

结果与对比

比较计算、通信以及存储复杂度，并区分是否进行预处理（比如：比特加密中进行的预处理以及同态加密中使用的随机因子），协议的实际运用将决定是否允许使用预处理。

预处理：所有的同态系统中包含加密以及一个随机值，比如：QR中 [ x ] = g x ⋅ r 2 [x]=g^x \cdot r^2 [x]=gx⋅r2 mod N N N，其中的 g g g 就是一个固定整数（二次非剩余）， r r r 是随机选择的值。

计算复杂度：我们通过以N 为模计算乘法的次数来统计计算复杂度，因为这些构成了主要的计算负载。由于 QR 的构造，加密 0 需要一次（平方）模乘，加密 1 需要两次模乘。

通信复杂度：用 l o g 2 N log_2 N log2​N 比特的消息数来衡量的。

存储复杂度：用加密数值的数量来衡量的(大小为 l o g 2 N log_2N log2​N 比特)。

与其他方案的比较

方案	计算复杂度	通信复杂度	说明
KT	23 l + 23 2 l o g 2 N 23l+\frac{23}{2}log_2N 23l+223​log2​N	两个加密信息	安全性较弱（multiplicative hiding）导致
DGK	( 120 + 7 2 ) ⋅ l + 3 2 l ⋅ l o g 2 ( l + 2 ) (120+\frac{7}{2})\cdot l+\frac{3}{2}l\cdot log_2(l+2) (120+27​)⋅l+23​l⋅log2​(l+2)(使用预处理)	2 l 2l 2l	由于其 l l l 次解密操作导致计算量较大,通信复杂度比LSIC小
GC	200 l l l（无预处理）	LSIC的一半	一混淆电路只需要一轮通信；存储复杂度大致等于通信复杂度且与电路大小有关；其大量操作可以预处理

拓展

最大值比较算法

在论文 Machine Learning Classification over Encrypted Data 中以该文章为基础，对比较算法进行了汇总，同时基于此设计了安全的最大值比较算法。