type
status
date
slug
summary
tags
category
icon
password
Private Stateful Information Retrieval-ACM SIGSAC’18 阅读记录
基本信息
Private Stateful Information Retrieval
作者：
Sarvar Patel, Giuseppe Persiano, Kevin Yeo
期刊 & 会议：
ACM SIGSAC
时间：
2018
JCR/CCF：
CCF-A
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
研究对象
密码技术 & 应用场景
- 计算性隐私信息检索
研究动机
潜在问题
- 在传统的PIR中，服务器的计算开销通常是与数据库大小线性相关的，即
- 在传统的PIR中，服务器通常在问询回复阶段需要进行大量的密文运算。例如，对于XPIR，SealPIR来说，服务器需要针对一个长度为的数据库计算多次同态乘法和同态加法等运算。为此，服务器的计算开销非常高。
研究目标&贡献
主要贡献
- 提出了一种新的Oblivious Constrained Partitions构造方法以及Private Batched Sum Retrieval的相关定义及安全模型
- 首次提出了Private Stateful Private Information Retrieval的概念，并给出了PSIR的定义、安全模型、以及通用构造方法
- 提出了第一个Private Stateful Private Information Retrieval方案
研究基础
Fisher-Yates shuffle算法
该算法主要用于将一个给定的有限集合进行混淆，生成一个随机排列后的新集合。这个算法生成的随机排列是等概率的（均匀随机）。
Oblivious Constrained Partitions
一个OCP方案由两个算法(OCP.GenerateSeed,OCP.ExtractPartition)组成。
- OCP.GenerateSeed(). 给定安全参数，整数，以及一个约束子集，输出一个关于划分的简短的描述，其中某一个，是一个种子，是一个整数。
- OCP.ExtractPartition(). 给定一个关于划分的描述，输出一个实际的划分()。
正确性：对于任意，一个OCP方案需要满足当OCP.GenerateSeed()时，有OCP.ExtractPartition()，其中是一个正确划分且成立的概率是不可忽略的。
Obliviousness：对于任意，任意多项式时间敌手都不能以不可忽略的概率区分给定的元素是否属于约束子集（敌手获得划分的描述信息的前提下无法知道有关约束子集的有关信息），即下式成立。
:
- 挑战者随机选择一个约束子集
- 敌手选择两个元素并发送给挑战者
- 挑战者随机选择，设置并计算OCP.GenerateSeed()，最后返回给敌手
- 敌手根据接收到的种子，输出自己的猜测
Private Batched Sum Retrieval
给定个子集，客户端的目标是在不泄露所有c个子集的有关信息给服务器的前提下获得每个子集中所有元素的和，即
PBSR的安全模型与PIR类似，不同之处在于传统PIR是敌手无法区分给定的两个问询，而PBSR是敌手无法区分两个集合
Private Stateful Information Retrieval
一个状态隐私信息检索方案PSIR由以下五个概率多项式时间算法(PSIR.Init,PSIR.Query,PISR.Reply,PSIR.Extract,PSIR.UpdateState)组成。
- . 给定安全参数，客户端可以存储的数据库记录数量，以及数据库作为输入，输出一个初始化状态.
- . 给定待检索索引,以及客户端当前状态作为输入，输出检索问询以及更新后的客户端状态.
- . 给定问询请求以及数据库作为输入，输出问询回复.
- . 给定问询回复以及当前客户端状态作为输入，输出待检索数据库记录.
- 给定客户端状态和数据库作为输入，输出更新后的客户端状态.
正确性：给定任意安全参数，数据库大小以及客户端存储能力，一个PSIR方案对于诚实客户端集合中的每个客户端所发送的问询请求需要满足下式成立：
隐私性：
- 诚实客户端和恶意客户端的集合分别为和，在游戏开始前就给定（非自适应性）
- 敌手的view可以获得所有诚实客户端的状态信息以及次问询信息
- 自适应性的游戏中，恶意客户端会随着游戏的进行自适应变化
研究内容
OCP算法构造与证明
OCP算法构造思路总览
ExtractSubset() & ExtractCondSubset()子算法
- ExtractSubset：根据给定的随机密钥种子，通过伪随机数生成器，生成一个集合，其中每个元素且
- ExtractCondSubset：为ExtractSubset函数输出的划分集合生成对应的描述，即. 这个描述可以确保的第位是约束子集中的元素
OCP.ExtractPartition的核心算法
显然，当时，，。这样就可以确保每列的第r行是约束子集中的元素。
OCP证明
Private Batched Sum Retrieval
所有的数据库条目都被下载，然后对应集合进行叠加。
Private Stateful Imformation Retrieval
PSIR方案构造的主要思路
- Offline：在掉线阶段，客户端和服务器进行交互，执行一个Private Batched Information Retrieval协议以获得c个数据条目集合的所有元素的和
- Online：在线阶段，客户端选择一个不包含目标检索数据的数据条目集合。同时，客户端针对数据库的索引生成一个满足的划分并发送关于这个划分的简短描述信息给服务器。
- Online：服务器在接收到划分的描述信息后，重构出数据库的划分。随后计算每个划分中所有元素的和。
- Online：服务器将所有划分的元素和视为新的数据库，客户端与服务器执行一个安全的PIR检索，获得第个划分的所有元素和。最后，客户端计算
Private Stateful Imformation Retrieval
PSIR方案具体内容
- Offline阶段执行PSIR.Init：使用ExtractSubset生成c个数据条目索引集合。随后，客户端和服务器之间执行一个简单的PBSR协议（即客户端根据所生成的所有个数据库条目索引集合下载对应的数据库条目，然后计算每个数据库条目索引集合所对应的所有数据库条目的和）
- Online阶段执行PSIR.Query：客户端从自己保存的所有个数据库条目索引集合中选择一个未被使用过的(和的作用就是保障不重复选择同一个数据库条目索引集合)。随后，通过OCP.GenerateSeed生成包含约束子集的划分的描述。同时，客户端执行一个PIR协议，生成待检索数据索引所对应的问询请求(用于检索数据库中第个数据库条目)
- Online阶段执行PSIR.Reply：服务器根据划分的描述，通过OCP.ExtractPartition重构出划分并对数据库进行划分。随后，计算每个数据库划分的所有元素和，得到个数据，视为新的数据库。最后通过执行所选PIR协议的Reply生成针对待检索数据索引的问询请求的响应回复（Response）并返回给客户端。
- Online阶段PSIR.Extract：客户端接收到服务器对索引的问询回复（Response）后，通过所选PIR协议重构出数据条目，最后计算检索数据，即
- Offline阶段执行PSIR.UpdateState：在所有的c个约束子集全部使用后，客户端需要与服务器重新执行PSIR.Init来重新生成满足条件的个新的约束子集，并更新自己的状态。
commnucation & client storage
- 每次问询的通信开销：每个客户端运行OCP.GenerateSeed生成，即个整数以及个长度为的种子。同时，客户端与服务器还会执行一个PIR协议（即针对数据库）
- 客户端存储开销：客户端需要存储个数据库条目集合的每个集合的所有元素和，一共c个元素。
总结
Problems
- 直观的看，文章中的PBSR协议就是客户端去下载所有数据库记录，然后根据划分计算每个数据库条目集合的所有元素和。该PBSR虽然不涉及复杂的计算，服务器的计算开销会被降低。但是，PBSR对客户端的计算开销的通信能力有着很高的要求。
- 为什么是? （是执行的PIR协议的通信开销，是什么开销？）
- 为什么是个问询请求？
- 虽然离线阶段服务器不需要执行复杂的计算（对应PBSR），但是所提的PSIR方案客户端在离线阶段的通信开销是与数据库大小呈线性
- 虽然PSIR中在线阶段服务器需要执行的PIR是基于新数据库（即），但是OCP.ExtractPartition的计算开销还是，所以服务器在线阶段的计算开销仍然还是与数据库大小线性相关。
参考文献
- Janson, Svante. "Tail bounds for sums of geometric and exponential variables, 2014." URL http://www2. math. uu. se/~ svante/papers/sjN14. pdf (1973).
- Patel, Sarvar, Giuseppe Persiano, and Kevin Yeo. "Private stateful information retrieval." Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018.
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊