simplepir-rs

Rust中SimplePIR的快速高效实现。

背景

私有信息检索 (PIR) 是一种协议，用于从服务器上托管的数据库访问信息，而服务器不知道访问的信息，包括数据库中信息的索引。SimplePIR 是 PIR 的一种快速高效实现，提供平方根通信成本和线性计算成本。要了解更多关于 SimplePIR 的信息，请查看 Alexandra Henzinger、Matthew M. Hong、Henry Corrigan-Gibbs、Sarah Meiklejohn 和 Vinod Vaikuntanathan 撰写的这篇论文 这篇论文。

入门

我们将从指定 SimplePIR 方案的一些基本参数开始。为了良好的安全和性能，建议密钥长度（加密密钥的长度）为 2,048。我们还将指定明文模数，它告诉我们可以准确访问和解密的数字范围。在这个例子中，我们将使用 2^17。

use simplepir::{Matrix, Database};
let secret_dimension = 2048;
let mod_power = 17;
let plaintext_mod = 2_u64.pow(mod_power);

然后我们将创建一个简单的数据库来存储我们的数据。数据库可以是随机创建的，也可以从现有的矩阵创建。这个包提供了简单的矩阵和向量类型以方便使用。

let matrix = Matrix::from_data(
    vec![
        vec![1, 2, 3, 4],
        vec![5, 6, 7, 8],
        vec![9, 10, 11, 12],
        vec![13, 14, 15, 16],
    ]
);
let db = Database::from_matrix(matrix, mod_power);

为了在提高性能的同时减少内存消耗，可以将数据库通过将三个数据记录（数字）打包成一个记录来压缩。

let compressed_db = db.compress();

现在到了有趣的部分！

SimplePIR 协议有四个主要功能

第一个功能在“离线”阶段运行。

setup()

接受数据库作为输入，并输出客户端和服务器用的提示。这由 服务器 分别在其他函数之前调用。这非常计算密集，但极大地加快了协议的“在线”部分。

let (server_hint, client_hint) = setup(&compressed_db, secret_dimension);

接下来三个功能在“在线”阶段运行。

query()

接受数据库中的一个索引并输出加密查询。这由 客户端 调用。

let index = 0;
let (client_state, query_cipher) = query(index, 4, secret_dimension, server_hint, plaintext_mod);

client_state 变量仅存储有关客户端查询的一些基本信息。

answer()

将加密查询与整个数据库进行矩阵-向量乘法运算，输出加密的答案向量。这由服务器调用，是在线阶段计算最密集的部分。

let answer_cipher = answer(&compressed_db, &query_cipher);

恢复()

接收加密的答案向量，对其进行解密，并返回所需的记录。

let record = recover(&client_state, &client_hint, &answer_cipher, &query_cipher, plaintext_mod);

如果我们一切操作正确，这个断言不应该失败！

assert_eq!(database.get(index).unwrap(), record);

但是它快吗？

是的。

SimplePIR是一种非常高效的PIR协议。在线阶段性能最关键的部分answer()函数具有线性时间复杂度，在测量的硬件上以内存带宽速度运行。query()和recover()函数也运行得非常快。

基准测试

以下基准测试是在一台联想ThinkPad X1 Carbon第6代，搭载英特尔酷睿i7-8650U @ 4.2 GHz，16GB内存的Manjaro Linux系统上进行的。显然，这些结果会根据所使用的硬件有很大的不同。所使用的数据库大小为3600×3600（约104 MB），密钥维度为2,048。

记录的内存带宽约为10-12 GB/s。《code>answer()》函数实际上能通过高效的打包实现超出内存带宽约2倍。