Keyword PIR

Standard PIR retrieves rows by numeric index, but real applications — like looking up an Ethereum address or transaction hash — need lookup by key. Keyword PIR solves this via eg cuckoo hashing. Performance scales with DB size, not key-space size.

Multi-paradigm comparison of three PIR approaches — additive HE (SealPIR), somewhat HE (MulPIR), and number-theoretic (Gentry-Ramzan) — applied to keyword-based queries (lookup by key, not index).
Source: Ali et al., "Communication-Computation Trade-offs in PIR" (S&P 2021).

Communication vs Server Time

• GR vs ClientAidedGR: GR has ~10× less comm but ~12× more server time.
• SealPIR vs MulPIR (large entries): MulPIR has ~5× less comm but slightly more server time.
• SealPIR vs MulPIR (small entries): MulPIR is worse on both axes — trade-off does not hold here.

Server Time by Configuration

Server computation time across database configurations, grouped by paradigm.

Communication Breakdown

Query upload + response download for each paradigm and configuration.

Client Time

Client-side computation (query generation + response decoding).

Distributional PIR

A compiler framework that lifts any batch-PIR scheme into a distributional-PIR scheme, exploiting skewed query distributions for sub-linear server work in expectation. Benchmarks are for the compiled output (CrowdSurf system), not a standalone scheme.
Source: Lazzaretti et al., "Distributional Private Information Retrieval" (2025).

Reported Metrics

Concrete benchmarks for variants with measured data. Many configs report only relative improvements (see footnotes).

Compiler Overhead vs Underlying Schemes

DistributionalPIR variants compared against the index-PIR schemes they wrap (SimplePIR, Respire, YPIR).