SimplePIR——最快单服务器匿踪查询方案

11.SimplePIR

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

期刊：Usenix Security Symposium (USENIX Security)——网络安全领域四大最高级别的国际学术会议之一

一、介绍

        这篇论文旨在实现高效的单服务器隐私信息检索（PIR）方案，以解决在保护用户隐私的同时快速检索数据库的问题。为了实现这一目标，论文提出了两种新的PIR方案：SimplePIR和DoublePIR。这两种方案的实现基于学习与错误假设，并在保持高吞吐量的同时显著降低了客户端的通信成本。SimplePIR实现了每核心10 GB/s的服务器吞吐量，接近内存带宽，但需要客户端下载一个相对较大的“提示”。DoublePIR方案通过递归地使用SimplePIR，以更低的通信成本获取所需的数据库记录。这些方案的突破点在于在保持高吞吐量的同时，显著降低了客户端的通信成本，填补了单服务器PIR方案设计空间中的一些空白。通过这些创新，论文为单服务器PIR方案的设计和实现提供了新的思路和解决方案。

        本文中很有价值的观点总结：

        1.定义了一种新型的匿踪查询对比方式：数据库大小/响应时间/core。时间相同比较支持的数据库的大小。

        2.指出一个很严重的问题：通过长久保持的密钥生成的query是不安全的，与sealPIR类似的匿踪查询存在不安全性。

        3.首个基于LWE问题的匿踪查询。

二、背景知识

1.Learning with errors (LWE)
        是一种基于格的加密技术，它是一种在计算上难以解决的问题。LWE问题的基本形式是：给定一个由n个向量组成的矩阵A和一个向量b，以及一个小的误差向量e，找到一个向量s，使得As+e=b。LWE问题的难度在于，对于给定的A和b，找到s是困难的，因为误差向量e是随机的。LWE问题是一种基础的加密原语，可以用于构建各种加密方案，包括私有信息检索（PIR）方案。在本文中，SimplePIR方案的安全性基于LWE假设，即LWE问题的解决难度足以保证SimplePIR方案的安全性。在文字提及到(