六、隐语PIR功能及使用介绍

一、PIR介绍

关于PIR的介绍，前见二、理论基础-匿踪查询（PIR）-CSDN博客

二、隐语实现PIR方式、参数

先看下隐语实现PIR的调用接口，隐语中PIR是通过PSI的三个功能模块封装实现的：

1. pir_setup

   • 定义数据预处理的一些参数

     • input_path:服务端数据文件路径，也就是服务端被查询文件的路径
     • key_columns：关键词key对应的列名
     • label_columns：想要查询的对应的标签，支持一次性查询多个标签，用逗号分隔即可
     • oprf_key_path：服务端存储的ecc密钥文件，32B，二进制文件
     • set_path：临时文件存储路径
     • num_per_query：每次查询的id数量
     • label_max_len：标签数据拼接后填充的长度大小
     • bucket_size：查询数据区分度，一般设置为一百万就足够了

     示例：

     spu.pir_setup(
         server="alice",
         input_path=f"{str(Path.home())}/workspace/alice_psi_output-new.csv",
         key_columns=["uid"],
         label_columns=["credit_card_number","credit_card_provider"],
         oprf_key_path="/tmp/alice_oprf_key",
         setup_path=f"{str(Path.home())}/workspace/alice_setup",
         num_per_query=1,
         label_max_len=100,
         bucket_size=1000000
     ) 
     

2. pir_query

   • 配置参与者所执行的查询任务

     • server：服务器端
     • client：查询客户端
     • server_setup_path：服务器临时文件存储路径，和pir_setup的一致
     • client_key_columns：客户端查询关键字
     • client_input_path：客户端想要根据关键字查询的记录
     • output_path：客户端查询结果后文件保存路径

     spu.pir_query(
         server="alice",
         client="bob",
         server_setup_path=f"{str(Path.home())}/workspace/alice_setup",
         client_key_columns=["uid"],
         client_input_path=f"{str(Path.home())}/workspace/bob_pir_query.csv",
         client_output_path=f"{str(Path.home())}/workspace/bob_pir_result.csv",
     )
     

3. pir_mem_query

基于内存查询

三、Index PIR-SealPIR

隐语目前查询分为两种方式：一种是基于索引，一种是基于关键字，索引Index PIR是基于SealPIR的，而SealPIR又基于BFV的同态方案，主要用到多项式的密文加法、明文乘密文、密文替换。

原理：客户端将查询向量(0,1)使用同态算法进行加密，加密后发送给服务端，服务端使用该数据进行累积打包查询数据加密结果，返回给客户端；客户端解密得到查询数据。
存在问题：请求的消息报文太大，包含了n个密文向量。

SealPIR主要贡献：
1、数据打包：多个数据pack到一个同态明文多项式，降低存储和计算的复杂度。查询时db_index转换为plaintext_index。 原始数据B1、B2、B3打包到到明文多项式P1，B4、B5、B6打包到到P2，用户查询B4情况下，需要将数据库的查询index转换为多项式的查询index P2，服务端返回P2的加密值，客户端同态解密得到明文多项式，再依据pack的偏移找到B4的偏移系数拼接为明文数据。
2、查询向量压缩：查询向量（例如 0,0,…,1,…,00,0,…,1,…,00,0,…,1,…,0）被压缩成单个密文，服务端通过 Expand 算法扩展为完整向量，减少通信量。 客户端查询向量压缩将原始n个密文压缩到同态明文多项式，对该明文多项式加密得到查询密文，服务端得到查询密文使用expand扩展算法得到具体n个密文向量，再使用n个向量进行同态乘得到结果。
3、支持多维查询：数据可以存储为 $n\times n$的矩阵，支持多维数据查询，每次查询可以选择矩阵的行或列查询。

4、支持多个查询：使用cuckoo hash将多个查询分配到不同的哈希桶中，支持同时进行多个查询。

四、Keyword PIR-Labeled PSI

基本原理：服务端为每条记录生成一对多项式，其中包含记录的关键词和对应的标签。具体是使用两个差值多项式，包括一个匹配多项式和一个Lable差值多项式，在匹配多项式P(key)为0情况下对应的差值多项式Q(key)的值对应三个查询值。

1.1 点值插值

• 点值插值：
  • 给定一组点值对$(x_i,y_i)$，可以通过插值多项式计算出与之对应的多项式$ P(x)$。
  • 在 PSI 中，点值对应于密文和标签的关联关系，插值多项式用于计算和匹配交集。

1.2 多项式表示

• 服务端根据数据生成 插值多项式，并将标签编码到多项式中：
  • 匹配多项式：匹配数据 ID 的多项式。
  • 标签多项式：与匹配数据关联的标签信息。

这种方式也基于BFV来实现，明文编码方式使用BatchEncode，每个位置上的数据支持基于位置的加法和乘法。

Label PSI：以《Labeled PSI from Fully Homomorphic Encryption with Malicious Security》为例大致说明一下流程。

协议流程

1. OPRF 预处理阶段

   • 发送方计算 OPRF：

     • 发送方对集合中的每个元素 $x_i$ 应用 OPRF 计算伪随机值： X ′ = { H ( F k ( x ) ) : x ∈ X } X' = \{H(F_k(x)):x\in X\} X′={H(Fk​(x)):x∈X}其中 $F_k(x)$是 OPRF 的输出，$H$ 是哈希函数。

   • 接收方计算 OPRF：

     • 接收方对集合中的每个元素 $y_i$执行类似计算： Y ′ = { H ( F k ( y ) ) : y ∈ Y } Y' = \{H(F_k(y)) : y \in Y\} Y′={H(Fk​(y)):y∈Y}

2. 标签插值多项式
   • 发送方使用插值多项式$G(x)$来压缩标签信息：
     • 若 $x\in X，则G(x)={\ell }_i$（标签）。
     • 若$x\notin X$，则 $G(x)$ 是随机值。

3. 交集计算阶段

   • 加密和查询：

     • 接收方对其 OPRF 输出进行加密并发送给发送方。
     • 发送方对密文评估多项式并返回结果。

   • 解密和结果恢复：

     • 接收方解密发送方返回的结果，验证哪些元素属于交集，并获取对应标签。

优化：

1、减少乘法次数和计算量： 客户端通过窗口机制减少发送密文个数，发送2的次方倍数。服务端可以通过分区将每个bin划分为若干个子集，每个子集对应一个差值多项式，降低相应的多项式次数。

2、使用extremal postage stamp bases减少通信量。

3、Paterson-Stockmeyer算法，减少密文乘法。