type
status
date
slug
summary
tags
category
icon
password
Private Information Retrieval with Sublinear Online Time-阅读记录EUROCRYPTO’20
基本信息
Private Information Retrieval with Sublinear Online Time
作者：
Henry Corrigan-Gibbs and Dmitry Kogan
期刊 & 会议：
Eurocrypto
时间：
2020
JCR/CCF：
CCF-A
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
研究对象
密码技术 & 应用场景
- 计算性隐私信息检索 & 计算效率优化 & 次线性
研究动机
潜在问题
- 对于PIR而言，服务器在每次问询时必须要遍历完整的数据库，否则就会造成隐私泄露（若部分数据库条目未被遍历，那么敌手就可以知道该部分内容不是发起问询请求的客户端所感兴趣的）。为此，对于传统的PIR方案而言，即便其可以实现次线性的通信开销和客户端计算开销。但是，它们的服务器计算开销通常都是与数据库大小线性相关的，即（是数据库大小）。同时，传统PIR中服务器的计算开销与数据库大小呈线性，使得其落地实现变得非常困难。
研究目标&贡献
主要贡献
- 提出了一个双服务器的PSIR方案，可以实现在离线阶段服务器计算开销为；在线阶段的服务器计算开销为；在线阶段的通信开销可以降低至（当单向函数存在的前提下）；方案的总体通信开销为.
- 拓展1.中的双服务器PSIR方案，使得其可以通过重复使用单次离线阶段生成的hints来完成在线阶段的多次自适应问询。拓展后的方案可以保持每个在线问询的计算开销还是。同时，在次在线问询后，平均总体计算开销（包括在线和离线阶段）降低至.
- 通过将标准的单服务器PIR方案与线性同态加密结合，提出了一个单服务器的PSIR方案。该方案的总体通信开销和服务器计算开销均为。当全同态加密存在时，该PSIR方案的通信开销和在线阶段服务器计算开销降低至.
- 对于任意的PSIR方案（服务器不以编码方式存储数据库并且不会保存额外的状态信息），离线阶段的通信为比特，在线阶段检索数据库的比特，需要满足.
研究基础
Puncturable Pseudorandom Function
一个在密钥空间和punctured密钥空间上的PRF方案由以下三个概率多项式时间算法组成.
- . 给定安全参数，输入空间大小参数，该随机算法一个密钥.
- . 给定密钥和一个输入，输出一个punctured密钥.
- . 给定一个密钥，输出一个值.
正确性：
Game：不会泄露任何与有关的信息
- 敌手选择安全参数和输入域大小，并发送一个点给挑战者
- 挑战者分别计算，最后返回给敌手
- 敌手输出其猜测值
不可预测性：
- 敌手选择安全参数和输入域大小，并发送一个点给挑战者
- 挑战者分别计算，最后返回给敌手
- 敌手输出一个值，当且仅当时敌手赢得游戏
Ps:从输入域中随机选择一个值的概率是
A toy protocol
- Online阶段的删除元素的概率：从个集合中选择一个包含的集合（事件B）的概率为，从中删除一个（事件A）的概率为，因此。但是=。这个地方的概率文章中的计算似乎有问题。
- 发送所有个集合的通信复杂度为的原因如下：
3-SUM问题
给定一个集合，其(,+)是一个阿贝尔群，能否找到一个三元组使得
3-SUM indexing问题
给定两个集合，其中是一个阿贝尔群，对于一个目标值，能否从找到两个数使得
研究内容
Puncturable Pseudorandom set
- 一个在密钥空间和punctured密钥空间上的PRS方案由以下三个概率多项式时间算法组成.
- . 给定安全参数，输入空间大小参数，该随机算法一个密钥.
- . 给定密钥和一个输入，输出一个punctured密钥.
- . 给定一个密钥，输出一个值.
- 挑战者分别计算，最后返回给敌手
- 敌手输出其猜测值，当且仅当时，敌手赢得游戏。
正确性：，生成的S是一个长度为s(n)的[n]的子集（s(n)是一个关于n的多项式函数）并且需要满足对于所有, 成立。
不可预测性：
Game：不会泄露任何与有关的信息
敌手无法获得任何信息的情况下，等价于在中随机选择一个，概率为
- 基于PRF构造的PRS
Puncturable Pseudorandom set有关证明
Proposition34的证明思路（伪随机性）
- 构造hybrid分布
显然，，，所以可以得到下式
- 构造一个攻击PRS的敌手
根据PRS中的安全游戏可知，敌手赢得游戏的概率如下式所示：
对于每部分概率的推导：https://www.lotus.bond/article/paper-17
定理3的证明思路
根据PRS的构造可知：
- PRS中的，所以set keys的长度为
- PRS中的，所以punctured keys的长度为
考虑三类敌手，是PRS中的敌手；是PPRF中的敌手；是PRF中的敌手
详细的概率分析过程见：https://www.lotus.bond/article/paper-17
基于PRG构造的PRS
基于PRG的PRS构造可知：
- set key是一个伪随机生成器密钥，为比特
- punctured key是一个整数元组，为
对offline阶段的优化
基本方案的掉线阶段需要发送所有已经划分的个集合给服务器，通信复杂度为.为降低通信复杂度和存储开销，提出上述优化方法。
Shifting PRS
需要满足以下两点性质成立：
- 存在一个安全的PRS方案，那么必然会存在一个安全的shifting PRS方案
- 以下两个分布不可区分（为什么要满足这个要求？）
证明思路：将左式中的GenWith按照Shifting PRS的定义去展开，然后再一直按照shifting PRS的定义进行展开，最后再根据Shifting PRS的定义进行合并，即可得到右式。
这一性质主要用于后续Multi-query offline/online PIR构造时确保，更新后的新客户端密钥与更新前的密钥是计算不可区分的，即生成的初始客户端密钥与后续每次问询结束后的更新后的新密钥是计算不可区分的。
offline/online PIR
- Setup(). 给定安全参数和数据库长度，输出一个客户端密钥和一个hint请求.
- Hint. 给定一个数据库以及hint问询请求，输出一个hint .
- Query(). 给定客户端密钥以及待检索数据索引，输出问询请求.
- Answer. 给定一个问询请求以及数据库，输出一个问询回复.
- Reconstruct. 给定问询回复以及hint ，输出待检索数据.
正确性：
安全性：
Two server offline/online PIR with sublinear online time
- Offline：
- Setup：生成一个PRS的密钥，选择一个集合。
- Hint：根据PRS的密钥和就可以获得一个关于[n]的划分，即，随后根据和shift进行移位得到[n]的所有划分，并对每个划分对应的所有数据库数据计算和，得到hint集合
- Online：
- 寻找j的过程就是去找到待检索数据索引位于[n]的所有划分中的那一个划分。如果存在这样的表示。如果这样的j不存在，选择一个划分。这两种情况都可以确保
- 根据得到的密钥生成一个集合，随后计算对应数据库条目的和并返回给客户端。客户端将与相减即可。
b=0且j存在，表示从中删除的元素是；b=1且j存在，表示从中删除的元素
这个地方应该是j不存在或者的时候输出
- PRS的安全证明表示需要大于才能满足不可预测性。但是构造中要求每个划分的大小，并且，为什么？
这个应该是跟Two-server PIR with sublinear online time方案的安全分析有关，后续看完证明再补充
- 寻找j的过程可以通过一个哈希表来实现（），简单模拟如下（不考虑存在多个j的情况）
- 离线阶段对于所有m个集合，服务器需要计算每个集合的所有元素和，因此计算开销为，即
- 在线阶段，服务器仅需要计算中的所有元素之和，因此计算开销为
- 离线阶段，客户端仅需要生成一个，根据PRS的构造可知，计算开销为；在线阶段中，客户端问询时，需要找到，计算开销为；其余阶段的开销基本上可忽略不计。因此客户端的总体计算开销为
- 离线阶段，客户端需要向服务器发送一个PRS的，一个集合，通信开销为
- 离线阶段，服务器计算的hint是一个m长的二进制集合，即，通信开销为
- 在线阶段，客户端发送的问询请求是一个punctured key，通信开销为
- 在线阶段，服务器返回的问询回复是一个单比特，通信开销为
注：以上只考虑单次执行PIR过程中的所有计算和通信开销。
的证明思路
- 是攻击PIR方案的敌手，是攻击单个基础PIR实例的敌手（这是因为为了增加检索的成功率，必须要执行次基础PIR方案），得到如下不等式：
- 是方案运行失败的概率（如果PIR使用的是完美安全的PRS，那么该概率为）。根据之前证明的PRS伪随机不可区分性质，一个PRS生成的与从中随机选择个元素之间不可区分的概率为。这里只考虑失败情况下的不可区分。
- 下面继续推导单个PIR实例攻击成功的概率：第二个问询生成是第一个问询生成过程的重写，显然是相同的，第三个问询生成与第二个问询生成是计算不可区分的。第三个问询分布与计算不可区分，因此可以得到
- 综合上述式子可得：
上面的算法存在一个问题：任意的仅可以使用一次。假设如果存在两次问询，使得，那么服务器会在问询回复阶段得到两个集合和，通过对比这两个集合，服务器可以很容易获得待检索的索引，进而获得数据库目标检索条目。
Mlti-Query offline/online PIR
- Setup(). 给定安全参数和数据库长度，输出一个客户端密钥和一个hint请求.
- Hint. 给定一个数据库以及hint问询请求，输出一个hint .
- Query(). 给定客户端密钥以及待检索数据索引，输出两个问询请求以及更新后的客户端密钥.
- Answer. 给定一个问询请求以及数据库，输出一个问询回复.（）
- Reconstruct. 给定问询回复以及hint ，输出待检索数据以及一个更新的hint.
construction of the multi-query offline/online PIR
- Offline: 客户端生成m个PRS密钥，并作为hint问询发送给服务器，服务器计算每个对应的数据库元素和得到hint
- Online：
- 问询阶段：通过Genwith生成一个新的PRS密钥，使得，以确保后续问询的正确性。当且找到这样的j成立时，
- 重构阶段：是中缺少对应数据库条目的和，因此就是，同样的补上其实就是所对应的数据库条目和，就是更新后客户端密钥所对应的新hint。
存在的问题：在重构时的判断条件应该是或者才是正确的
证明分析过程：
- 离线阶段，服务器和客户端之间的通信开销包括和，即，为保持检索的正确性，需要执行次，因此为。通过伪随机生成器，客户端可以不再传输个PRS密钥给服务器，而是一个比特的随机种子，服务器可以根据这个随机种子生成所有的PRS密钥。因此可以将通信开销降低为，当
- 离线阶段，服务器需要计算个所对应的数据库条目的和，因此服务器计算开销为，执行次为
- 在线阶段，服务器只需要计算一个所对应的数据库条目的和，因此服务器计算开销为，执行次为
- 在线阶段的全部通信开销包括两个问询以及两个问询回复，执行次为()
- 在线阶段服务器需要计算两个所对应的数据库条目和，执行次为
- 在线阶段客户端的计算主要集中在寻找使得，执行次为
- 离线阶段客户端需要存储的信息为hint和，即
Single-server single query offline/online PIR
思路：将一个双服务single query offline/online PIR转换为一个单服务器的PIR，需要实现不能获得任何离线阶段hint问询的有关信息，这样就可以让客户端在离线和在线阶段与同一个服务器进行交互，实现一个单服务器PIR
Single-server single query offline/online PIR构造
上面这个离线阶段本质上就是等价于：给定一个初始集合以及一个长度为的移位集合，然后计算hint集合：
- 客户端发送一个向量（仅在的位置为1，其余位置为0）的同态密文给服务器，而不是直接将发送给服务器
- 对于数据库，服务器生成一个循环矩阵，这个循环矩阵就包括了（因为），随后根据线性同态的性质，计算（对应着明文的矩阵向量乘积）
- 客户端可以根据使用一个bacthed PIR去检索得到所有的密文，这样就不会泄露给服务器。
- 最后获得检索数据后，使用解密算法就可以获得所有的
- 在线阶段与two server single query offline/online PIR保持一致即可，只不过不再需要去额外与另一个服务器进行交互，直接与离线阶段的服务器进行交互即可。
分析：
通信和计算开销分析，仅offline阶段，online阶段与前面保持一致
- 通信开销：客户端需要上传n个同态加密密文，客户端需要接收batched PIR的问询回复（此时数据库大小为m，即m个的密文），因此总体通信开销为
- 计算开销：服务器需要计算一个向量矩阵乘法（原本复杂度为），通过FTT加速后可降低为，服务器还需要计算PIR的m个问询回复
安全性分析：
服务器的视角：1）一个向量v加密得到的密文；2）一个Batched PIR的问询请求（对于索引）；3）客户端在线问询请求（对于索引）
只需要证明对于任意两个待检索索引，服务器的视角是计算不可区分的就可以了。
- 初始游戏是就是上面描述的对于待检索索引的服务器视角
- Game1是将向量v替换为一个空向量，然后加密得到密文，由于同态加密算法的语义安全，Game1，Game0不可区分
- Game2是将检索索引替换为一个固定的检索索引集合，由于PIR的隐私性要求，Game2与Game1不可区分
- Game3是将客户端在线问询请求的索引替换为，由于之前所证明的双服务器PIR方案的隐私性要求，Game3,Game2不可区分
- Game4是将索引以及向量v替换回去，同样基于同态加密和PIR的安全要求，Game4是与Game3不可区分
- 因此Game4与Game0是不可区分的，所以对于任意两个待检索索引，服务器的视角是不可区分的。
Yao’s Box Problem
对于两个多项式时间算法可以以的优势解决Yao’s Box问题，该算法需要满足以下性质：
- 需要输出一个长度最多为C比特的字符串
- 最多可以发起T次预言机问询
- 对于任意，都有，不可以直接向问询
通过一个offline/online PIR方案可以构造一个解决Yao‘s Box问题的多项式时间算法
思路：将所有的视为一个数据库，因此可以通过一个offline/online PIR去检索得到所对应的数据库条目
因此，
总结与展望
问题
- Single-Query two server offline/online PIR方案中，单次执行时检索失败的概率为，是一个不可忽略的概率。因此需要并行执行个方案，将失败的概率上界降低至。
- Online阶段的删除元素的概率：从个集合中选择一个包含的集合（事件B）的概率为，从中删除一个（事件A）的概率为，因此。但是=。这个地方的概率文章中的计算似乎有问题。
显然，，；；，而不是
参考文献
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊