Crate simplepir

Expand description

A fast and efficient implementation of SimplePIR in Rust.

§Background

Private information retrieval (PIR) is a protocol for accessing information from a database hosted on a server without the server knowing anything about the information that was accessed, including the index of the information within the database. SimplePIR is a fast and efficient implementation of PIR that provides square-root communication costs and linear computation costs. To learn more about SimplePIR, check out this paper by Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan.

§Getting Started

We’ll start by specifying some basic parameters for the SimplePIR scheme. For good security and performance, a secret-key dimension (the length of the encryption key) of 2,048 is recommended. We’ll also specify the plaintext modulus, which tells us the range of numbers that can be accurately accessed and decrypted. In this example, we’ll use 2^17.

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

We’ll then create a simple database to store our data. Databases can be created at random or from an existing Matrix. This crate provides basic Matrix and Vector types for convenience.

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);

To increase performance while also decreasing memory consumption, the database can be compressed by packing three data records (numbers) into a single record.

let compressed_db = db.compress();

Now for the fun parts! There are four main functions of the SimplePIR protocol:

§Offline Phase

§`setup()`

Takes the database as input and outputs a hint for the client and for the server. This is called by the server separately and prior to the other functions. It’s very computationally heavy, but massively speeds up the “online” portion of the protocol.

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

§Online Phase

§`query()`

Takes an index into the database and outputs an encrypted query. This is called by the client.

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

The client_state variable just stores some basic information about the client’s query.

§`answer()`

Takes the matrix-vector product between the encrypted query and the entire database and outputs an encrypted answer vector. This is called by the server and is the most computationally intense part of the online phase.

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

§`recover()`

Takes the encrypted answer vector, decrypts it, and returns the desired record.

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

Now if we did everything right, this assert shouldn’t fail!

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

Structs§

ClientState: A struct that contains information about the client’s query, including the row and column index, the a-matrix of the database, the side length of the database, the client’s secret key, and the key’s length.
CompressedDatabase: A compressed version of a regular Database with 3 records packed into one.
Database: A square matrix that contains u64 data records.
Matrix: A simple 2D array type.
Vector: A simple 1D array type.

Enums§

DatabaseError: An error type for database creation errors.

Functions§

answer: Computes the matrix-vector product of the packed database and the encrypted query. The output is an encrypted vector that can be decrypted to reveal the records along the column indicated in the query.
answer_uncompressed: Computes the matrix-vector product of the non-packed database and the encrypted query. The output is an encrypted vector that can be decrypted to reveal the records along the column indicated in the query.
query: Takes an index in the length-N database and outputs an encrypted vector with all 0s except for a 1 at the column index.
recover: Takes the encrypted vector of records along the column specified in the query, decrypts it using the secret key, and returns the record at the row and column that was specified in the query.
setup: Outputs one hint for the server and one hint for the client. The server hint is the seed to generate the a-matrix for the query, which since it stays constant, can be generated ahead of time. The server hint is generated at random. The client hint is the matrix multiplication of this a-matrix with the data in the database. This also stays constant and can be generated ahead of time to save on computation.
setup_seeded: Outputs one hint for the server and one hint for the client. The server hint is the seed to generate the a-matrix for the query, which since it stays constant, can be generated ahead of time. The server hint is generated at random according to a specified seed. The client hint is the matrix multiplication of this a-matrix with the data in the database. This also stays constant and can be generated ahead of time to save on computation.

Crate simplepirCopy item path