最新批量匿踪查询顶会论文：Vectorized Batch Private Information Retrieval

目录

一. 概要

二.背景知识

1.Learning with errors (LWE)（简单了解下，同态性质更关键！！！） 

2.Somewhat Homomorphic Encryption (SHE)

3.Vectorized Homomorphic Encryption

4.传统的批量匿踪查询（batchPIR）

三、方案说明

1.单条匿踪查询：

A 数据库多维度拆解：

B 密文流转优化：

C 向量查询完整流程：

2.批量匿踪查询：

A 响应合并：

B 完整的批量匿踪查询协议：

··············· ·码字辛苦--点赞支持--引用注名···················

一. 概要

本文的摘要是介绍了一种名为Vectorized BatchPIR的批量私人信息检索（BatchPIR）方案，该方案通过使用单个密文检索多个数据库条目实现了低通信和低计算的目标。作者观察到可以通过使用向量化RLWE同态加密的变体来节省通信，并设计了一种方法来合并加密独立条目的密文。在下载一个包含256个条目的批次时，该方案的摊销通信开销是不安全基线的19.2倍，比最先进的PIR方案好7.5倍，比现有的BatchPIR方案好两个数量级。贡献点在于提出了一种新的BatchPIR方案，实现了低通信和低计算的目标。

本文的主要贡献是介绍了一种名为Vectorized BatchPIR的批量私人信息检索（BatchPIR）方案，该方案通过使用单个密文检索多个数据库条目实现了低通信和低计算的目标。作者设计了一种向量化RLWE同态加密的变体，并提出了一种合并加密独立条目的方法。该方案的通信开销比不安全基线好7.5倍，比最先进的PIR方案好两个数量级。

二.背景知识

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方案的安全性。在文字提及到(