valar-ypir-0.1.2 has been yanked.

YPIR

This is a fork of the YPIR implementation of the YPIR scheme for single-server private information retrieval, introduced in "YPIR: High-Throughput Single-Server PIR with Silent Preprocessing".

This fork has been audited by Zellic. The audit report is available in audits/zellic-audit-report.pdf.

Client-side code is considered frozen in this repository. Server-side code remains open to changes. This is because these changes can only affect performance, they cannot break client privacy. A server-side change could break integrity, as could a malicious server. However, all authentication of data retrieved is not done at the cryptographic layer in YPIR, but instead is an application-layer concern. In our usages within voting and spendability, authentication is explicitly addressed (via merkle path authentication checks against a trusted merkle root, or recursive proofs post-Tachyon).

Running

To build and run this code:

Ensure you are running on Ubuntu (at least 22.04), and that AVX-512 is available on the CPU (you can run lscpu and look for the avx512f flag). Our benchmarks were collected using the AWS r6i.16xlarge instance type, which has all necessary CPU features.
Run sudo apt-get update && sudo apt-get install -y build-essential libssl-dev pkg-config.
Install Rust using rustup using curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh.

Select 1) Proceed with installation (default) when prompted
After installation, configure the current shell as instructed by running source "$HOME/.cargo/env"

Run git clone https://github.com/valargroup/ypir.git and cd ypir.
Run cargo run --release -- 1073741824 to run YPIR on a random database consisting of 1073741824 bits (~134 MB). The first time you run this command, Cargo will download and install the necessary libraries to build the code (~2 minutes); later calls will not take as long. Stability warnings can be safely ignored. See below for details on how to interpret the measurements.

We have tested the above steps on a fresh AWS r6i.16xlarge Ubuntu 22.04 instance and confirmed they work.

Options

To pass arguments, make sure to run cargo run --release -- <ARGS> (the -- is important). Passing --verbose or setting the environment variable RUST_LOG=debug will enable detailed logging. All PIR results are checked for correctness. The full command-line parameters are as follows:

Usage: cargo run --release -- [OPTIONS] <NUM_ITEMS> [ITEM_SIZE_BITS] [NUM_CLIENTS] [TRIALS] [OUT_REPORT_JSON]

Arguments:
  <NUM_ITEMS>        Number of items in the database
  [ITEM_SIZE_BITS]   Size of each item in bits (optional, default 1), values over 8 are unsupported
  [NUM_CLIENTS]      Number of clients (optional, default 1) to perform cross-client batching over
  [TRIALS]           Number of trials (optional, default 5) to run the YPIR scheme 
                     and average performance measurements over (with one additional warmup trial excluded)
  [OUT_REPORT_JSON]  Output report file (optional) where results will be written in JSON

Options:
  -v, --verbose  Verbose mode (optional) if set, the program will print debug logs to stderr
  -h, --help     Print help
  -V, --version  Print version

Interpreting measurements

This is an annotated version of the output of running RUST_LOG=debug cargo run --profile release-with-debug --bin server 8589934592 1 (testing on a 1 GB database), detailing what each measurement means:

{
  "offline": {
    // Bytes uploaded by the client in the offline phase
    "uploadBytes": 0,

    // Bytes downloaded by the client in the offline phase
    "downloadBytes": 0,
    
    // Server computation time, in milliseconds, in the offline phase. 
    // Includes any precomputation that must be performed on the plaintext database.
    "serverTimeMs": 3965,
    
    // Not used.
    "clientTimeMs": 0,
    
    // Time spent precomputing just the SimplePIR hint.
    "simplepirPrepTimeMs": 2539,

    // Bytes that the client *would* have to download, in the offline phase,
    // if they were performing SimplePIR (rather than YPIR) 
    // using this implementation (SimplePIR* in the paper).
    "simplepirHintBytes": 29360128,

    // Similarly, bytes that the client *would* have to download, 
    // in the offline phase DoublePIR (DoublePIR* in the paper).
    "doublepirHintBytes": 14680064
  },
  "online": {
    // Bytes uploaded by a single client in the online phase.
    "uploadBytes": 604160,
    
    // Bytes downloaded by a single client in the online phase.
    "downloadBytes": 12288,

    // Bytes that the client *would* have to download, in the online phase,
    // if they were performing SimplePIR (SimplePIR* in the paper).
    "simplepirRespBytes": 28672,

    // Bytes that the client *would* have to download, in the online phase,
    // if they were performing DoublePIR (DoublePIR* in the paper).
    "doublepirRespBytes": 12288,

    // Server computation time, in milliseconds, in the online phase.
    // This is the average time over 5 trials, after a warmup trial.
    "serverTimeMs": 402,

    // Time that the client took to generate the query.
    "clientQueryGenTimeMs": 530,

    // Time that the client took to decode the response (may round down to 0ms).
    "clientDecodeTimeMs": 0,

    // Time spent in the first pass of YPIR (the 'SimplePIR' phase)
    "firstPassTimeMs": 9,

    // Time spent in the second pass of YPIR (the 'DoublePIR' phase)
    "secondPassTimeMs": 3,

    // Time spent performing LWE-to-RLWE conversion
    "ringPackingTimeMs": 387,

    // Not used.
    "sqrtNBytes": 8192,

    // The full set of measured server computation times.
    "allServerTimesMs": [
      401,
      403,
      402,
      401,
      401
    ],
    // The standard deviation of the measured server computation times.
    "stdDevServerTimeMs": 0.8
  }
}

Server & Client

You can run YPIR as a standalone HTTP server using a command like:

$ RUST_LOG=debug cargo run --profile release-with-debug --features http_server --bin server 32768 262144 --is-simplepir --inp-file ../passwords-data/hibp-passwords.bin -p 8989 --hint-file ../passwords-data/hibp-passwords-2-hint.bin

Acknowledgements

YPIR is based on DoublePIR, and this implementation uses matrix-vector multiplication routines based on the ones in ahenzinger/simplepir. We also use a fork of spiral-rs for Spiral to handle RLWE ciphertexts.

Citing

Please cite the original work as:

@inproceedings{MW24,
  author    = {Samir Jordan Menon and David J. Wu},
  title     = {{YPIR}: High-Throughput Single-Server {PIR} with Silent Preprocessing},
  booktitle = {{USENIX} Security Symposium},
  year      = {2024}
}

This fork is maintained by valargroup.

valar-ypir 0.1.2