Certified DP

Overview

This repository contains a Rust-based implementation of a certified Binomial mechanism for arbitary differentially-private counting queries for the paper "Certifying Private Probabilistic Mechanisms". It is backed by curve25519-dalek, which implements Pedersen commitments over the prime-order Ristretto group.

The Prover and Verifier execute as separate processes and communicate through a localhost TCP socket.

The evaluation numbers presented in the paper were acquired on a 2.7 GHz Quad-Core Intel Core i7 processor with 16 GB RAM.

Getting started

This projects requires:
1. A Rust installation: (https://www.rust-lang.org/tools/install).
2. A C compiler: apt install gcc

To run both the prover and the verifier on a simple example with ε=1, n=1024 7-bit database entries, and a query sparsity of 7, run:

$ python3 experiment.py --db-size=1024 --max-degree=7 --dimension=7 --epsilon=1 --sparsity=7

Both processes will start and begin printing status messages. Once the query has been completed, a summary of performance statistics for both parties will be printed -- these timing outputs underly the evaluation in our paper.

Generating data used in the paper

Executing the convenience script eval/eval.sh will run each of the experiments presented in Section 5.2 and save the latency results to eval/eval-*.log. You can use these logs to regenerate Figures 4(a-d) and Table 2 using eval/eval-results.ipynb. The evaluation script will also run a census query experiment and save the latency numbers that we report in Section 5.2 to eval/census-*.log.

Census Query Example

The census query experiment (see eval/eval.sh) performs a query on a 2018 US Census PUMS dataset (https://www.census.gov/programs-surveys/acs/microdata.html). It contains AGEP (age), SEX (sex), SCHL (education) and PINCP (personal income) for 7000 anonymous respondents. We pack the data for each entry into a 37-bit database value that the Prover and Verifier operate over.

The Verifier calculates the predicates and coefficients to count the entries that satisfy "income <= 262144" and outputs the result. Note that as a result of the query, the maximum predicate degree the prover supports is 6 (enough to evaluate the higher-order income bits in each entry), while the per-entry dimension is 37. We set sparsity to 64 (appx. the sparsity of the generated query) and ask the prover to perform honest verification only (as would likely be the case if querying the Census directly).

Repository structure

experiment.py             # convenience script to run prover & verifier and log output
eval/
    *.log                 # performance logs underlying paper evaluation
    eval-results.ipynb    # data processing & figure generation
    eval.sh               # convenience script to rerun all main evaluation
census/
    census_pums_2018.csv  # raw 2018 PUMS data from census.gov
    pack_database.py      # script to pack raw data into 37-bit database for our protocol
    census_db.bin         # binary database generated by pack_database.py
src/
    config.rs             # project wide constants/configuration
    data.rs               # database loading/generation
    messages.rs           # prover <-> verifier serialization/communication
    pedersen.rs           # pedersen commitment implementation, heavily based on https://github.com/aled1027/tiny_ped_com
    bit_sigma.rs          # bit-Σ protocol implementation
    product_sigma.rs      # product-Σ protocol implementation
    bin/
  prover.rs         # primary Prover executable
  verifier.rs       # primary Verifier executable

experiment.py

experiment.py allows you to set many configuration parameters and consistently run a prover and verifier against each other.

usage: experiment.py [-h] --db-size DB_SIZE --max-degree MAX_DEGREE [--dimension DIMENSION] --epsilon EPSILON [--delta DELTA] --sparsity SPARSITY
               [--debug] [--no-logs] [--skip-dishonest] [--num-queries NUM_QUERIES] [--sparsity-experiment] [--db-file DB_FILE]
               [--census-query] [--db-dimension {16,32,64}]

Run experiment.

options:
  -h, --help            show this help message and exit
  --db-size DB_SIZE     Size of the database
  --max-degree MAX_DEGREE
                  Maximum degree of query
  --dimension DIMENSION
                  Dimension of database entries
  --epsilon EPSILON     Epsilon for differential privacy
  --delta DELTA         Delta for differential privacy
  --sparsity SPARSITY   Sparsity of the query
  --debug               Run debug binaries
  --no-logs             Do not print logs
  --skip-dishonest      Skip dishonest commitment phase
  --num-queries NUM_QUERIES
                  Number of queries to execute; timing averaged over queries
  --sparsity-experiment
                  Run sparsity evaluation experiment
  --db-file DB_FILE     Database file to use
  --census-query        Run census query
  --db-dimension {16,32,64}
                  Override of backing database entry size (e.g. entries might have a logical dimension of 34-bits, but backed by 64-bit
                  integers)