Authenticated PIR

WARNING: This software is not production-ready and it might contain security vulnerabilities.

This code accompanies the paper "Verifiable private information retrieval" by Simone Colombo, Kirill Nikitin, Henry Corrigan-Gibbs, David J. Wu and Bryan Ford, to appear at USENIX Security 2023.

This repository contains the code for multi-server and single-server authenticated-PIR schemes and the code for the proof of concept application Keyd, a privacy-preserving PGP public keys directory based on multi-server authenticated PIR.

Overview

The code in this repository is organizes as follows:

• lib/client: clients for all the authenticated and unauthenticated PIR schemes.
• lib/database: databases for all the authenticated and unauthenticated PIR schemes, except the database for the Keyd PGP key.
• lib/ecc: error correcting code (ECC) for the single-server authenticated-PIR scheme based on integrity authentication; currently, we implement a simple repetition code.
• lib/field: field for the multi-server scheme for complex queries.
• lib/fss: function-secret-sharing scheme.
• lib/matrix: matrix operations for the single-server authenticated-PIR scheme that relies on the LWE assumption.
• lib/merkle: Merkle tree implementation.
• lib/monitor: CPU monitoring and benchmarking tools.
• lib/pgp: utilities to create the PGP key-server database for Keyd.
• lib/proto: gRPC protocol files for deployment.
• lib/query: queries for the multi-server authenticated scheme for complex queries, i.e., available privately-computed statistics.
• lib/server: servers for all the authenticated and unauthenticated PIR schemes.
• lib/utils: various utilities.
• cmd/: clients for Keyd, both local Go clients and the web front end.
• data/: data, i.e., PGP keys, for Keyd.
• scripts/: various useful scripts.

The dump of the SKS PGP key directory can be downloaded here. The sks* file must be placed in the data/sks folder.

Setup

To run the code in this repository install Go (tested with Go 1.17.5 and 1.19.5) and a C compiler (tested with GCC 9.4.0).

To reproduce the evaluation results, install GNU Make, Python 3, Fabric, NumPy and Matplotlib.

We obtain our evaluation results on machines equipped with two Intel Xeon E5-2680 v3 (Haswell) CPUs, each with 12 cores, 24 threads, and operating at 2.5 GHz. Each machine has 256 GB of RAM, and runs Ubuntu 20.04 and Go 1.17.5. However, the code runs on any machine equipped with the softwares listed above.

If the machine do not support one or more of the -march=native, -msse4.1, -maes, -mavx2 or -mavx C compiler flags, it is possible to remove the appropriate flags from lib/matrix/matrix128.go and lib/matrix/matrix.go. Any flag modification is likely to negatively impact performance.

Correctness tests

To run all basic correctness tests, execute go test This command prints performance measurements to stdout. The entire test suite takes about 6 minutes to run and it should terminate with a PASS, indicating that all tests have passed.

The branch sid enables to run the tests using less physical machines than the servers used by the different experiments. We decided not to merge this branch into the main branch because multi-server (authenticated) PIR schemes need non-colluding, i.e., different, servers for security.

Citation

@inproceedings{colombo23authenticated,
  author    = {Simone Colombo and Kirill Nikitin and Henry Corrigan-Gibbs and David J. Wu and Bryan Ford},
  title     = {Authenticated private information retrieval},
  booktitle = {USENIX Security},
  year      = {2023}
}