FancyPIR：考虑通信与计算权衡的无状态批量私有信息检索方法

《IEEE Open Journal of Circuits and Systems》：FancyPIR : Stateless Batch Private Information Retrieval with Communication-Computation Trade-Offs

　　摘要：现有的私有信息检索协议在实际应用中表现较为良好。然而，通信开销仍是大规模应用面临的重大障碍。一种自然的解决方法是通过同时查询多个条目来分摊通信开销。近期研究提出了批量私有信息检索（多查询私有信息检索）协议，旨在优化单服务器场景下的渐进复杂度。本文介绍了FancyPIR，这是一种无状态的批量私有信息检索解决方案，它试图在不依赖预处理提示的情况下，在通信成本与计算成本之间取得平衡。FancyPIR旨在在控制计算成本的同时降低通信开销。为此，该方案采用了两种主要策略：首先，减少初始化（离线阶段）时的循环次数以及服务器响应（在线阶段）中的乘法运算次数，从而减轻计算负担；其次，在在线阶段利用向量化同态加密对多个查询进行打包并合并响应，大幅降低通信开销。具体而言，对于从包含220个条目（每个条目大小为256字节）的数据库中检索256个条目的情况，与现有最佳解决方案相比，FancyPIR的通信开销降低了8.4～104倍，同时初始化时间也缩短了1.9～3倍。综合考虑通信和计算成本，对于不同的数据库规模，FancyPIR还能将服务器的运营成本降低8.5～59倍。