赞
踩
隐私信息检索(Private information retrieval, PIR)是对信息检索(information retrieval, IR)的一种扩展,最早在[CKGS95]中提出,用于保护用户查询信息,防止数据持有方得到用户的检索条件。
PIR协议目标可以定义为:Alice有共
N
N
N行的数据库D,每一行的数据大小为
L
L
L。Bob希望查询获得其中指定位置的某一行,但是不想告诉Alice自己查询的是哪一行。
隐私信息检索协议(PIR)需要满足正确性和安全性两方面的要求:
PIR按服务器数量可以分类为单服务器(Single Server)和多服务器(Multi-Server)方案,按查询类型可以分为Index PIR和Keyword PIR。
隐语目前支持的PIR有:
pir_setup(
key_columns (str, List[str]) – Column(s) used as pir key
label_columns (str, List[str]) – Column(s) used as pir label
oprf_key_path (str) – Ecc oprf secret key path, 32B binary format. Use an absolute path.
setup_path (str) – Offline/Setup phase output data dir. Use an absolute path.
num_per_query (int) – Items number per query.
label_max_len (int) – Max number bytes of label, padding data to label_max_len Max label bytes length add 4 bytes(len).
)
pir_query(server: str, config: Dict, protocol='KEYWORD_PIR_LABELED_PSI')
{
# client config
alice: {
'input_path': '/path/intput.csv',
'key_columns': 'id',
'output_path': '/path/output.csv',
},
# server config
bob: {
'oprf_key_path': '/path/oprf_key.bin',
'setup_path': '/path/setup_dir',
},
}
pir_memory_query(server: str, config: Dict, protocol='KEYWORD_PIR_LABELED_PSI') { # client config alice: { 'input_path': '/path/intput.csv', 'key_columns': 'id', 'output_path': '/path/output.csv', }, # server config bob: { 'input_path': '/path/server.csv', 'key_columns': 'id', 'label_columns': 'label', 'num_per_query': '1', 'label_max_len': '20', }, }
BFV SHE方案定义在固定多项式环 R = Z / ( x n + 1 ) R=\mathbb{Z}/(x^{n}+1) R=Z/(xn+1)上,明文是 R t = Z t / ( x n + 1 ) R_t=\mathbb{Z_t}/(x^n+1) Rt=Zt/(xn+1)中的多项式即: a 0 + a 1 x + ⋯ + a n − 1 x n − 1 + a n − 1 x n − 1 a_0+a_1x+\dots + a_{n-1}x^{n-1}+a_{n-1}x^{n-1} a0+a1x+⋯+an−1xn−1+an−1xn−1
在BFV SHE方案中,密钥
s
s
s是一个从二项多项式(系数为0或1)采样的多项式。密文包括两个来自环
R
q
=
Z
q
(
x
n
+
1
)
R_q=Z_q(x^n+1)
Rq=Zq(xn+1)的多项式,
(
c
0
,
c
1
)
=
(
a
,
b
+
e
+
m
)
(c_0,c_1)=(a,b+e+m)
(c0,c1)=(a,b+e+m),其中
a
a
a是从
R
q
R_q
Rq中均匀采样的,
b
=
a
⋅
s
+
e
b=a\cdot s+e
b=a⋅s+e,
e
e
e是一个表示噪声的多项式,它的系数是从有界高斯分布里采样出来的。可以通过计算
u
=
c
1
−
c
0
⋅
s
=
e
+
m
u=c_1-c_0\cdot s=e+m
u=c1−c0⋅s=e+m来解密,
e
e
e是很小的噪声,这样就可以恢复出原文
m
m
m。
密文扩展因子
F
F
F:密文大小与明文大小之间的比率:
F
=
2
l
o
g
q
l
o
g
t
F=\frac{2logq}{logt}
F=logt2logq
SHE的同态运算会引起噪声的增长,当噪声超过一定限制时,无法解密得到明文,所以要适当选择SHE算法的参数,及控制同态运算的噪声增长。
密文是一对模
q
q
q的多项式,而明文是模
t
t
t的多项式。密文扩展因子直接影响PIR的响应大小。PIR的主要任务之一就是减少
F
F
F。
BFV方案中,执行密文乘法运算时噪声增长很快,因此要避免使用密文乘法操作。
HE-Based PIR的原理就是将查询向量使用HE加密后发送给服务端,服务端使用该加密向量与服务器数据做内积运算并返回带查询数据的加密结果给客户端,最后由客户端解密返回结果获取PIR结果。
请求消息报文太大,包含n个密文向量。
将多个数据pack到一个HE明文
假设数据库中数据长度为
288
288
288字节(SealPIR论文中给出的长度),BFV参数选择:多项式次数
8192
8192
8192,明文模
16
16
16bit,举例说明一下packing的效果:
将查询向量压缩为一个密文
为了显著减少通信量,SealPIR方案在服务端添加一个额外的Expand操作得到查询密文向量。查询向量
(
0
,
…
,
0
,
1
,
0
,
…
,
0
)
(0, \ldots, 0, 1, 0, \ldots, 0)
(0,…,0,1,0,…,0) 压缩到一个HE明文多项式为例,查询向量中的每个分量对应为HE明文多项式中的系数。
a
0
+
a
1
x
+
⋯
+
a
N
−
2
x
N
−
2
+
a
N
−
1
x
N
−
1
=
E
(
x
query
index
)
a_0 + a_{1^x} + \cdots + a_{{N-2}^{x^{N-2}}} + a_{{N-1}^{x^{N-1}}} = E(x^{\text{query}_{\text{index}}})
a0+a1x+⋯+aN−2xN−2+aN−1xN−1=E(xqueryindex)其中:
a
i
=
0
,
if
i
≠
q
u
e
r
y
i
n
d
e
x
,
a_i = 0, \quad \text{if } i \neq query_{index},
ai=0,if i=queryindex,
a
i
=
1
,
if
i
=
q
u
e
r
y
i
n
d
e
x
a_i = 1, \quad \text{if } i = query_{index}
ai=1,if i=queryindex
对查询明文进行加密,得到
E
(
a
0
+
a
1
x
+
…
+
a
N
−
2
x
N
−
2
+
a
N
−
1
x
N
−
1
)
=
E
(
x
query
index
)
E\left(a_0 + a_{1^x} + \ldots + a_{{N-2}^{x^{N-2}}} + a_{{N-1}^{x^{N-1}}}\right) = E(x^{\text{query}_{\text{index}}})
E(a0+a1x+…+aN−2xN−2+aN−1xN−1)=E(xqueryindex)
服务端接收到查询密文后,执行Expand算法,得到查询密文向量:
(
E
(
0
)
,
…
,
E
(
0
)
,
E
(
1
)
,
E
(
0
)
,
…
,
E
(
0
)
)
(E(0), \ldots, E(0), E(1), E(0), \ldots, E(0))
(E(0),…,E(0),E(1),E(0),…,E(0))
还是以上面packing的参数举例,每个HE明文可以pack
56
56
56条数据库数据,客户端查询时,将
d
b
i
d
x
db_{idx}
dbidx转换为
p
l
a
i
n
i
n
d
e
x
plain_{index}
plainindex,即对HE明文数据库进行查询,最多可以查询
8192
8192
8192个HE明文,转换成数据库数据,最多可以查询
8192
×
56
=
458
,
752
8192 \times 56 = 458,752
8192×56=458,752条数据,不能满足实际业务中的需求。
为了满足实际将查询向量压缩到多个HE明文来表示查询向量,对于百万数据来讲,需要
c
e
i
l
(
1000000
/
8192
)
=
123
ceil(1000000/8192)=123
ceil(1000000/8192)=123个HE明文,对应
123
123
123个HE密文,才能表示百万数据的查询向量。为了进一步压缩查询密文的数量,可以使用下面的多维表示方法。
Expand算法的详细描述和证明可以参考[SealPIR]论文中的内容。
将数据库一维向量转换为多维向量
查询时将数据库表示为
n
∗
n
\sqrt{n}\ast \sqrt{n}
n
∗n
的二维矩阵,减少查询向量的长度。
以上面packing的参数为例,将数据库表示为
2
2
2维数据时,通过两个查询密文可以查询的数据量是
8192
×
8192
×
56
≈
37
8192 \times 8192 \times 56 \approx 37
8192×8192×56≈37亿,已经能满足绝大多数的数据库查询任务。数据库数据量为
n
n
n,通过packing后得到HE明文数量为
n
′
n'
n′,
F
F
F是密文扩张因子,二维查询流程如下:
服务端:
客户端:
支持多查询
基本原理:点值表示得到插值多项式系数表示。
客户端可以通过窗口技术,服务端采用分区技术减少乘法计算次数。
使用extremak postage stamp bass 减少通信开销
Paterson-Stockmeyer 算法减少密文乘法
隐语Label PSI 主要工作
setup阶段
- 选择参数。
- 对id数据进行PRF计算,前128bit根据截取用于匹配,后128bit作为对称算法密钥加密label。
- 根据PRF前128bit将数据插入Simple Hash。
- 对Simple Hash 每一行分别划分bin bundle,并计算matching polynomial 和label polynomial。
- 将插值多项式系数packing到同态算法明文。
Query 阶段
- 请求参数。
- 执行OPRF。
- 计算查询值得同态密文幂集合。
- 使用同态私钥解密服务端返回的同态密文。
- 满足匹配条件时,使用OPRF的后128bit解密得到label。
隐语Label PSI的主要参数
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。