基本信息

📢

One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval

作者：Alexandra Henzinger

期刊 & 会议：USENIX

时间：2023

JCR/CCF：CCF-A

相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）

PPT：https://www.usenix.org/system/files/sec23_slides_henzinger.pdf

原文：https://www.usenix.org/system/files/sec23summer_27-henzinger-prepub.pdf

视频：

代码：https://github.com/ahenzinger/simplepir

研究对象

研究动机

研究目标&贡献

研究基础

✨

相关背景知识汇总

• 通吐量(throughput) ：数据库大小与服务器回答一次问询所需的时间之间的比率

Kushilevitz and Ostrovsky方案（首个单服务器PIR方案）

• PIR服务器将一个N条记录的数据库划分为一个 维矩阵

• 客户端向服务器发送一个 的向量 （仅索引"j"位置为1，其余位置为0）的密文

• 如果加密方案满足线性同态，服务器可以计算矩阵向量乘积 并返回该结果给客户端

• 客户端解密服务器返回的密文获得

• 该方法的整体开销会随着 增长而增长（这是基于同态的单服务器PIR的通病）

• 该方法的主要开销在于需要在密文状态下完成大量的线性同态计算操作，这也是需要解决的问题关键所在

• 证书透明度(Certificate Transparency)场景下的签名证书时间戳审计（SCT）
• 服务器拥有一个字符串集合 S，客户端想要去测试一个具体的字符串 $\sigma$ (即一个SCT) 是否在集合 S 中。由于 $\sigma$ 会泄露客户端访问的具体网站是什么，因此需要PIR技术。
• 谷歌使用了一种方法，但是这种方法只能实现 $k$-匿名，其中 $k=2000$。

• -LWE 困难假设
• 给定一个秘密 ，整数 ，整数模 ，以及一个 上的噪声分布 ，均匀随机选择矩阵 ，一个秘密的向量 ，一个噪声向量 ，以及一个随机向量 ，使得下面两个分布是计算不可区分.

• 一个在明文空间 以及数据库大小 上的具备预处理的PIR方案包括以下四个概率多项式时间算法：
• Setup(db) (). 给定数据库 db 作为输入，输出服务器和客户端的辅助信息 ()
• Query() (). 给定索引 作为输入，输出秘密的客户端状态 和 数据库问询
• Answer(db, , ) ans. 给定服务器辅助信息 ，数据库 db，以及数据库问询 作为输入，输出问询结果 ans
• Recover(,ans) . 给定秘密的客户端状态 ，客户端辅助信息 以及问询结果 ans，输出记录
• 正确性

• 布隆过滤器：本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

研究内容

💫

核心技术

• SimplePIR和DoublePIR的整体思路
• SimplePPIR：Kushilevitz and Ostrovsky 等人基于线性同态加密的单服务器PIR方案的主要开销在于需要密文状态下完成大量的线性同态计算操作。为此本文针对这一点，利用Regev等人的基于LWE的加密算法的优势，使得服务器可以在客户端问询前提前进行预计算很大部分的操作，以便于后续快速计算矩阵向量积 。同时，由于这种预处理操作仅依赖于数据库 以及Regev加密算法的公开参数，因此在后续可以复用，以回答其他客户端发起的问询。在后续的每次问询中，服务器仅需要粗略地计算 字节数据库上的 个32比特整数乘法和加法即可。



• DoublePIR：本文发现客户端在每次问询时下载的辅助信息hint以及 的加密向量并不是完全使用了。客户端仅需要使用hint中的部分信息以及加密向量中的某一位即可获得其想要问询的结果。为此，本文在一种递归结构下使用了SimplePIR以进一步削减开销。

• SimplePIR方案具体内容

 

• 通信与计算开销分析：

• 预处理阶段分析

• 问询阶段分析

• DoublePIR具体内容
• 从SimplePIR中可以看出，想要恢复出客户端问询位置的数据库元素，必须要获得辅助信息矩阵 以及 问询回复向量 ans。
• DoubelPIR的核心思想就是在SimplePIR生成的辅助信息矩阵 和问询回复向量 ans 上面执行了第二次的SimplePIR，以获得客户端问询位置的数据库元素。进而，客户端不再需要下载很大的辅助信息矩阵了。

• 通信与计算开销分析

• 私有近似集隶属度数据结构
• 私有近似集隶属度问题：客户端拥有一个秘密的字符串 ，服务器拥有一个字符串集合 ，客户端想要在不泄露隐私的前提下检测字符串 是否在集合 中。不同于隐私集合求交，此时的服务器字符串集合 是公开的
• 对于基于哈希函数的布隆过滤器，如果问询字符串 是敌手选择，敌手可以很容易地找到字符串 和 使得 成立，因此会一直将错误的字符串 识别为集合 中的元素之一
• 新的数据结构

研究结果

🔬

实验结果

• 通吐量

 

• 通信开销

• 通信开销与服务器吞吐量 trade-off

• 通信开销（数据库大小为）

 

• 吞吐量随着 Batch Queries 的大小变化

总结与展望

参考文献

• Henzinger A, Hong M M, Corrigan-Gibbs H, et al. One Server for the Price of Two: Simple and Fast {Single-Server} Private Information Retrieval[C]//32nd USENIX Security Symposium (USENIX Security 23). 2023: 3889-3905.