type
status
date
slug
summary
tags
category
icon
password
Committed Private Information Retrieval 阅读记录—ESORICS 2023
基本信息
Committed Private Information Retrieval
作者：Quang Cao
期刊 & 会议：ESORICS
时间：2023
JCR/CCF：CCF-B
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
研究对象
密码技术 & 应用场景
- 多服务器隐私信息检索 & 线性映射承诺（linear map commitment）&
研究动机
潜在问题
- 传统的隐私检索方法仅关注于单个安全需求-隐私性，即客户端可以在不泄露其具体检索的是数据库中的那条数据的前提下，获得数据库检索结果。然而，在现实场景中传统的PIR会面临着一些额外的安全威胁。例如，恶意攻击者可能会控制服务器，并将恶意伪造的结果作为客户端数据库检索结果返回，进而达到欺骗客户端的目标。
研究目标&贡献
研究目标
设计一个满足隐私性、鲁棒性、可验证性等更多安全需求的隐私信息检索方案，以解决传统隐私检索方法仅适用于半诚实服务器假设的问题。
主要贡献
- 基于线性映射承诺与线性隐私信息检索提出了一个新型隐私检索方案，其可以在有效保护客户端检索隐私的同时提供问询结果的验证性，以此抵御恶意服务器伪造问询结果的攻击。此外，所提方案可以保障在所有 个服务器均为恶意时客户端仍然可以丢弃恶意问询结果。然而，现有方案仅能够在 个恶意服务器的情况下提供问询结果的鲁棒性
- 基于现有的三种线性隐私信息检索方案，包括：CKGS（首个隐私信息检索方案）、WY（问询向量大小最低）以及 BE（问询结果大小最低），使用线性映射承诺构造了三种承诺隐私信息检索方案（committed PIR）
- 基于C语言、GMP库、以及blst库实现了所提的三种CPIR方案，并评估了通信与计算开销
研究基础
基础的隐私信息检索定义
- 一个标准的隐私信息检索允许一个客户端通过与 个服务器相互交互，从数据库 中检索到某一条数据 ，并且不会泄露该条数据索引 给服务器。
- 一个有限域 上 服务器的 维PIR方案包含三个概率多项式时间算法
- . 给定数据维度、索引 以及服务器数量 作为输入，客户端运行该算法输出 个问询向量以及一个辅助信息
- . 给定第 个问询向量 以及数据库数据 作为输入，服务器 运行算法，输出一个问询结果
- . 给定数据维度 、索引 、所有 个服务器的问询结果 以及辅助信息 作为输入，客户端运行该算法输出最终的检索结果
- 上述PIR的三种性质
- 正确性：
- 对于任意 ，，，，下式以不可忽略的概率成立
- 隐私性：
- 上述PIR方案具备隐私性，当且仅当在没有超过 个服务器合谋的情况下，服务器无法获得任何与客户端问询索引 有关的信息
- 表示 个服务器收到的问询向量 的组合，下面两个分布可区分的概率是可忽略的
- 线性：
- 一个PIR方案可以被称为线性，当且仅当每个服务器生成的问询回复 是 的线性组合。
- 一个PIR方案 的通信开销
Chor-Kushilevitz-Goldreich-Sudan PIR方案—CKGS
- 两个服务器，每个服务器都拥有一个数据库 的副本
- 客户端随机选择一个集合 并向服务器 和 发送问询请求
- 服务器 计算 并返回客户端
- 服务器 计算 并返回给客户端
- 由于CKGS使用的是一个特征为 2 的有限域，因此客户端可以简单叠加两个服务器返回的结果得到
- 由于子集合 是均匀随机选择的，根据Shannon定理可以知道服务器是无法获得任何与检索数据索引 有关的信息。
- CKGS要求所有服务器是半诚实的且不会合谋。因为如果两个服务器合谋的话，服务器通过将结果相减很容易就知道客户端问询的具体信息是什么。同时恶意攻击者可以通过监听CKGS中客户端上传给两个服务器的问询向量，进而获得客户端想要检索的信息是什么。
WY PIR
BE PIR
线性映射承诺（Linear Map Commitment, LMC）
- 一个有限域 上的 维LMC方案由四个概率多项式时间算法组成
- . 给定安全参数 ，维度 ，以及随机带（random tape） 作为输入，输出公开参数
- . 给定数据 以及公开参数，输出承诺值
- . 给定安全参数、数据、一个系数向量 以及一个值 作为输入，输出一个证明 ，该证明能够验证
- . 给定安全参数，承诺值，系数向量，数值，以及证据，输出
注：验证是否是线性组合
研究内容
Committed PIR
- 一个有限域 上的 个服务器的 维的基于承诺的隐私信息检索方案包含以下六个概率多项式时间算法
- . 给定数据维度 ，服务器数量 以及安全参数 作为输入，一个数据拥有者（完全可信）运行该算法输出公开参数
- . 给定公开参数 以及数据 作为输入，数据拥有者运行该算法输出承诺值
- . 给定公开参数、数据维度、服务器数量、以及索引 ，客户端运行该算法输出 个问询向量和辅助信息
- . 给定公开参数 , 第 个问询向量 以及数据库数据 作为输入，服务器 运行算法，输出一个问询结果
- . 给定公开参数 ，数据 以及问询向量 作为输入，服务器执行该算法，输出一个证据
- . 给定公开参数、数据维度、承诺值、索引、所有服务器生成的问询结果和证据以及辅助信息，客户端运行该算法，输出 或者
- 正确性与隐私性的性质与传统的PIR类似，如下图所示。
- 可验证性（这是CPIR主要创新之处）
- 安全游戏的核心思想就是恶意攻击者（本文中就是多个恶意服务器）可以伪造出多个问询结果以及对应的证据并能够通过验证，以欺骗客户端接受该恶意的问询结果。
- 挑战者运行 并返回公开参数给敌手
- 敌手选择数据 ，索引 以及集合 ，返回 给挑战者
- 挑战者运行 和 ，返回 给敌手
- 敌手对于问询向量，生成问询结果和证据
- 挑战者计算不在 中的剩余问询结果与证据
- 挑战者运行 ，如果 ，则敌手赢得游戏
注：上述游戏中的 即是恶意服务器的数量 ===⇒ -verifiable
通用的CPIR构造
通用CPIR构造详解
- 公开参数生成：完全可信的数据拥有者运行 算法生成公开参数
- 承诺值生成：完全可信的数据拥有者计算数据对应的承诺值
- 问询向量生成：客户端根据其想要检索的数据生成问询向量
- 问询结果计算：服务器计算对应问询向量的结果并返回给客户端（对于数据 和哈希 都要计算对应的问询结果）
- 证据计算：每个服务器根据问询向量与哈希值向量计算证据
- 验证与检索数据获取：客户端验证是否问询结果是否来自恶意服务器，若是需要丢弃，最终计算其想要的数据检索结果
🍊 LMC的用处在于对数据 的哈希值 做承诺，因为这些哈希值是公开的，容易被篡改，进而确保最后的 等式成立。
CKGS & LMC =⇒ CPIR
研究结果
实验设置
- 编程语言：C
- 第三方库：GMP，OpenSSL，blst
实验结果
总结与展望
xxx
参考文献
- Cao Q, Tran H Y, Dau S H, et al. Committed private information retrieval[C]//European Symposium on Research in Computer Security. Cham: Springer Nature Switzerland, 2023: 393-413.
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊
Lai-Malavolta的LMC算法
