。

为了实现这一目标#xff0c;论文提出了两种新的PIR方案#xff1a;SimplePIR和DoublePIR。

这两种方案的实现基于学习与错…一、介绍

这篇论文旨在实现高效的单服务器隐私信息检索PIR方案以解决在保护用户隐私的同时快速检索数据库的问题。

为了实现这一目标论文提出了两种新的PIR方案SimplePIR和DoublePIR。

这两种方案的实现基于学习与错误假设并在保持高吞吐量的同时显著降低了客户端的通信成本。

SimplePIR实现了每核心10

GB/s的服务器吞吐量接近内存带宽但需要客户端下载一个相对较大的“提示”。

DoublePIR方案通过递归地使用SimplePIR以更低的通信成本获取所需的数据库记录。

这些方案的突破点在于在保持高吞吐量的同时显著降低了客户端的通信成本填补了单服务器PIR方案设计空间中的一些空白。

通过这些创新论文为单服务器PIR方案的设计和实现提供了新的思路和解决方案。

二、背景知识

是一种基于格的加密技术它是一种在计算上难以解决的问题。

LWE问题的基本形式是给定一个由n个向量组成的矩阵A和一个向量b以及一个小的误差向量e找到一个向量s使得Aseb。

LWE问题的难度在于对于给定的A和b找到s是困难的因为误差向量e是随机的。

LWE问题是一种基础的加密原语可以用于构建各种加密方案包括私有信息检索PIR方案。

在本文中SimplePIR方案的安全性基于LWE假设即LWE问题的解决难度足以保证SimplePIR方案的安全性。

在文字提及到(,

)-LWE解释一下代表向量的维度代表整数模数代表误差分布。

因此(,

)-LWE问题描述了在给定向量维度、整数模数和误差分布的情况下解决Learning

with

(LWE)问题的难度。

这种参数化的LWE问题在密码学中具有重要意义因为不同的参数取值可以导致不同难度的LWE问题从而影响基于LWE问题构建的加密方案的安全性。

因此对于给定的、和(,

)-LWE问题的难度可以用来评估基于LWE假设的加密方案的安全性

Secret-key

encryption是一种基于LWE假设的加密方案由Regev在2005年提出。

该方案的安全性基于LWE问题的困难性即在给定矩阵A和向量b的情况下找到向量s是困难的其中b是由A和s的点积加上一个小的误差向量e得到的。

Secret-key

Regev

encryption方案的基本思想是将明文编码为一个向量并将其与一个随机向量的点积加上一个小的误差向量然后将其加密。

具体来说

详细学习格密码学与LWE问题

这个公式就是对于刚才理想问题的抽象其中A是公钥c是获得的密文u是待加密的明文这里需要注意的是u已经从一个数变成一个向量其正确性可以使用相同方式证明uc·s-A。

接下来我们将公式和图对应起来A就对应图中A矩阵c对应图中qu。

这样解密计算就相当于ans·s-hintc

D·(cs-A)

D·u我们这里知道是一个唯“1”向量相当于获得了D的其中一列的数据。

在文中也说明了这种方式将获得其中一列的数据。

至于详细的推导可以查看论文最后的证明。

2.DoublePIR

SimplePIR具有高的服务器端吞吐量但需要客户端下载和存储一个相对较大的预处理提示其大小大约为

√其中

。

然后介绍了DoublePIR这是一种新的PIR方案它通过递归应用SimplePIR来将提示大小减小到大约

220DoublePIR的提示大小比SimplePIR要小得多。

与SimplePIR一样DoublePIR的每个查询的通信成本在数据库大小

四、性能

在实际测试中发现该方案在相同条件下的确能比sealpir性能提升数倍不止。