分享论文《Private Set Intersection from Pseudorandom Correlation Generators》,目前仅在Cryptology ePrint Archive上预印刷。
该文涉及Cuckoo hashing、Oblivious key-value stores(OKVS)、IKNP类-OTE、Vector oblivious linear evaluation(VOLE)、PSI等密码原语。主要工作分为两部分:
1.用CH PSI击败OKVS PSI,或“KKRT反击”。也就是对KKRT16中的BaRK-OPRF进行了替换,从基于IKNP类-OTE替换为基于PCG类-OTE.以往基于PCG的PSI协议都是结合OKVS,本文发现PCG对基于Cuckoo hash的PSI减少通信开销的影响更深,并由此引来了一系列的优化. 比如通过置换hash减少哈希表中的元素大小,比如广义Cuckoo hash, 减少发送方往接收方发送的消息. 本文还发现KKRT16的安全分析中有一个错误,修复错误需要引入一个新的相关稳健性概念。
介绍步骤如下:
PSI功能介绍
KKRT:BaRK-OPRF介绍---安全性分析---相关鲁棒性修正---基于BaRK-OPRF的PSI构建
CH+PCG=PSI:PCG概念介绍---PCG(VOLE)协议---基于VOLE的BaRK-OPRF构建---正确性分析---KKRT-Bark-OPRF与PCG-BaRK-OPRF比较。
CH+PCG=PSI优化: 基于置换hash优化---基于广义Cuckoo hashing优化---membership Bark-OPRF ---通信开销分析---结论
2.标准模型中的高效PSI:本文的第二个贡献,设计了一个新的“基于多项式的”PSI协议。为实现上述基于多项式的PSI,我们引入了subfield ring-OLE相关的PCG概念,并展示了如何将其进行有效实例化。建立在该PCG上的新PSI协议,它具有以下特性:
·安全特性: 与KKRT框架不一样,基于多项式的PSI框架并不需要 random oracle model或tailor-made correlation-robustness assumptions,仅需要具有不可约多项式的多项式环上的ring-LPN假设。因此我们基于PCG的PSI建立在 standard model上。且恶意安全的代价仅限制在PCG的分布式短种子生成上。
·高效特性:非常低的通信量,只比ROM-based PSI[RS21]稍微大一点。虽然使用了多项式插值,但计算效率仍然很快,具体来说协议只需要:
-----receiver: a single degree-n polynomial interpolation,one FFT over a polynomial ring with degree-2n polynomials, 3 multiplications of degree-n polynomials
-----sender: a single degree-n polynomial interpolation, one FFT over a polynomial ring with degree-2n polynomials, 2 multiplications of degree-n polynomials,a single n-multipoint polynomial evaluation
·Batch non-interactive PSI.:具有集合X的客户端C可以广播其数据集的编码,然后接收每个服务器
1.在预处理阶段,C与每个服务器进行交互,在每次交互中使用O(logn)通信和计算,通信轮数很少。
2.然后,C执行单个
3.每个服务器
4.最终,给定X和
当服务器数量增加时,我们的批处理PSI协议可以为客户机带来非常大的节省,与每个服务器单独执行PSI协议相比,并提供了一个即使是最好的基于ROM的PSI协议也具有竞争力的解决方案。在此设置中,每个PSI实例的通信减少到
介绍步骤如下:
基于多项式和PCG的恶意PSI协议
批量非交互式PSI协议
KKRT16的两方PSI协议可拆分为基于CH和批处理相关密钥不经意伪随机函数(BaRK-OPRF)的结合。
BaRK-OPRF的功能如下:Alice输入集合元素x,Bob无输入,Bob输出BaRk-OPRF密钥delta和K,Alice输出BaRF-OPRF值F(x).在KKRT16中F(x)的结构如下: F(x)=...其中H是哈希函数,在构建时被要求是随机预言机。Enc是一个线性纠错码,^表示按位域。
有关为什么OPRF前面加BaRK前缀,可参考之前汇报的PPT。
接下来分析一下该OPRF结构为什么是安全的?对于
但是需要完成以上证明,需要引入有关纠错码的汉明距离相关稳健性保障纠错码具有足够大的熵。但KKRT16中的证明分析即使是在随机预言下也极易受到攻击,本文提供了一个更复杂的相关稳健性概念。
本文发现 KKRT定义的Hamming correlation robustness是无法实现的,因为目前没有任何一种Hash函数支持它的定义。从技术上讲,这个概念必须包含一些适当的条件,来防止哈希函数输入之间的冲突,可是KKRT16的定义中缺少这些适当条件来防止冲突。
我们先看一下IKNP03的原始概念: 如果称
然后KKRT16对其概念进行了修改:H是一个输入长度为n的hash函数,如果对于任意字符串
可以发现上面有一个明显的错误:针对任意字符串
或许,文章的作者认为
因此需要额外定义(a,b)也是区分的,才能满足相关鲁棒性的性质。
1.Bark-OPRF可基于IKNP类OTE进行快速且简单的构建。但并不能直接将Bark-OPRF应用于PSI协议中。从该功能示意图就能看出,每个元素x都有一个不同的密钥
2.简单讲一下CH的算法流程,通过d个hash函数将元素映射到一维表中。首先计算元素的hash值作为索引,然后看对应表中是否为空,若为空则随机选择一个进行填充。若都不为空则随机选择其中一个进行替换,对该替换值进行上述操作,若达到t次还未放进,则放入stash中。
现在基于CH和BaRK-OPRF来构建PSI.首先Bob和Alice分别采用朴素hash和Cuckoo hash构建hash表,然后逐行执行BaRK-OPRF,每一行都是同一个密钥
我们来看一看此构造的通信开销:Alice输出c·n的CH表,输出d·n的朴素哈希表,Bark-OPRF的通信开销为6kn,将系数实例化,可推算出大概需要1008n.
接下来我们将介绍该文的第一个主要贡献,如何基于PCG构造Bark-OPRF,然后在KKRT的框架下实现PSI.以及介绍带来了什么好处,和为什么能带来好处。首先先介绍一下PCG的功能和构造。
PCG的定义如下:允许两方或多方通过相关短种子的局部扩展和无交互来安全地生成有用的相关随机性的长源。目前最具代表的PCG即向量不经意线性评估简称VOLE.
本文用到的是子域VOLE,即参与方在VOLE的构建当中需要传输的向量在更小的域上,可减少通信开销。
VOLE的理想功能进行简单的描述:VOLE是一种安全两方协议,允许发送方输入标量
这里我们用19年VOLE的构造协议对VOLE进行简单的讲解。从该算法可看出分为两部分,第一部分为短种子生成,第二部分为短种子的扩展。第一阶段,参与方之间交互分布式生成
最后得到伪随机相关性向量。具体VOLE构造可参考该文献,该文献写的VOLE构造应该是最简单懂的。文章中的第一个贡献主要是如何基于VOLE来构建BarK-OPRF.所以看该文献的时候只需要知道VOLE的理想功能即可。
使用VOLE可以快速的构造BaRK-OPRF。首先Alice和Bob执行S-VOLE功能函数,Alice输出向量(u,v),Bob输出向量
Alice的集合为
我们首先对其正确性进行分析,显然:
我们再来分析一下KKRT的Bark-OPRF和本文的Bark-OPRF的的区别:
·公式中第一个不同是按位与操作换成了域内乘操作。这意味着不再需要纠错码Enc().因为
·更重要的一个区别是,VOLE可以完全去除向量u和全局标量\Delta的关联,而IKNP-OTE却不能,因为在IKNP-OTE中
1.现在我们再回过头来看一下Bark-OPRF的通信开销:l·nbit+VOLE中短种子密钥生成的通信开销,BCG19a给出的通信大小大约为0.7n.(l:元素大小)。远小于KKRT-Bark-OPRF的通信开销。
2.然后我们将这个新的Bark-OPRF插入到KKRT结构中。Alice输入1.3·l·n大小的CH表,PCG短种子交换的0.7n和接收
然而我们可以基于[PSSZ15]的置换hash做进一步的通信优化。具体来说,上一步我们将l-bit长的元素x存储的第i个bin中这样会导致一定的冗余,因为既然存储在第i个bin中即存在一个
但本文作者证明该方法带来的代价是处理存储空间的成本增加,并不划算。然后作者选择了一种广义CH,通过允许一个bin中包含多个元素,来降低hash个数。(d,k)-Cuckoo hashing:指使用k个hash将n个元素映射到(1+c)·n个bin中,每个bin中最多包含d个元素。[W+17]证明(3,2)-Cuckoo hashing 比(1,3)-Cuckoo hashing 具有更小的失败概率和更少的bin以及更少的hash函数。
1.要使用这种改进的CH变体,我们需要一个协议来处理每个bin最多d个项目的CH。直观的说,定义
2.回到上述Bark-OPRF。对于第i个bin,在Alice放置xi和Bob放置yi的地方,Alice计算H(i,vi),Bob计算H(i,Ki)− ∆yi)=H(i,∆ · (xi)− yi)+vi)。Alice放置
3.因此基于以上扩展此来构造membership BaRK-OPRF:
m: Alice在bin中输入的bit长度,
Alice和Bob执行 d个s-VOLE: 其中采用同样的标量
for j=0---d-1:
Alice发送
4.
Bob定义menbership BaRK-OPRF密钥为
OPRF定义为
5.
Alice将其输出设置为:
显然,因为
我们有:
1.接下来我们分析一下基于最新的成员-BaRK-OPRF构建PSI产生的通信开销。
---VOLE阶段,双方需要执行d个VOLE,其实也不是执行d次,而是执行一次长度为3N的向量,然后将其切分为3个等长即可。所以短种子秘密共享的通信开销仍然是单次的通信开销大约是0.7n.
---Alices需要传输z=C-u的大小,其中x的大小为
---计算交集阶段Bob需要传输OPRF(y)给Alice。一个OPRF(y)的长度为
所以整个协议的通信开销为:
再一次大幅下降通信开销,大约为188n.
1.显然PCG+CH得到了更低的通信开销相比于OKVS+PCG.
2.但随后又有一批人通过矩阵的下三角变换,得到了一个计算和通信开销更低的OKVS,从而结合PCG实现了目前PSI协议中无论是通信还是计算在各种场景下均最优的协议。有兴趣的可以看看这篇文章。为什么这个快也是有原因的,他们PCG里的LPN扩展,并不是采用经过充分验证的LPN假设。因此安全性还有待验证。
协议特征:标准模型,无需成本扩展为恶意安全,低通信,合理计算。
可推广为batch non-interactive PSI的概念:客户端与每个服务器执行小对数的通信后,客户端将其数据库的单个编码进行广播。然后可在任何时间获得和个服务器数据库的交集。
1.基于多项式的PSI协议:
接下来我们直接接受如何基于Subfield-Ring-OLE构建标准模型下的恶意PSI协议。有关协议的安全性证明,有兴趣的同学可阅读原文。
参数:假设有两方,其中发送方拥有集合
协议:
---:发送方和接收方执行子域环OLE。发送方接受一对阶为2n的均匀随机多项式
---:接收方分解
考虑一个多项式
---:接收方计算
---:接收到
并发送
---:现在接收方:
其中
3.A Batch Non-Interactive PSI
[BCG20b]所构建的PCG具有一个重要的特性就是它是可编程的:当执行seed分发协议时,接收方可确保与不同参与方执行PCG协议时它的输出
正确性分析:考虑一个多项式
假设元素x属于