Interactive visualization of PIR communication costs
Key Privacy Property (Paper model): For a given database and parameter set, every query uses the same amount of communication, regardless of which entry is requested.
Query size scales with database size N (via N/t indicator vector), and response size scales with entry size. If sizes varied with the target index, traffic analysis could reveal what's being queried.
Key Privacy Property (Implementation): For fixed parameters (d, ell, coefficient size), query size is constant because the client sends only shard_id plus an RGSW ciphertext.
Database growth is handled by sharding, which keeps query size fixed but reveals shard granularity (which shard/range is accessed). Response size still scales with entry size; server time grows with shard count.
1. Protocol Flow
Key: One round-trip: client sends encrypted query, server computes on ciphertexts, returns encrypted result.
2. Size Breakdown
Key: Three paper protocols (InsPIRe_0, InsPIRe^(2), InsPIRe) with different query structures. InsPIRe_0 and InsPIRe^(2) use LWE indicators only; InsPIRe adds RGSW for polynomial evaluation.
Paper model: query breakdown includes the LWE indicator vector, which scales with N/t.
Sizes shown reflect single-modulus serialization (crt_moduli length 1). The default CRT mode stores two residues per coefficient and approximately doubles the serialized size.
Upload Keys (packing/KS matrices)
Upload Query (indicator / RGSW)
Download (RLWE response)
3. Parameter Effects (InsPIRe^1)
Key: Sizes scale linearly with ring dimension (d) and gadget length (l). Select variant in Section 2 to update calculations.
102420484096
32 B64 B128 B
234
Query Size (seeded)
96 KB
Response Size (binary)
512 KB
Total per Query
742 KB
4. Server Processing Visualization
Key: Server processes one shard using parallel external products. Processing time is ~3ms regardless of total database size.
Step 1: Shard Selection
Step 2: External Product (Parallel)
Step 3: Response Assembly
4.5. LWE-to-RLWE Packing (InsPIRe^1/^2)
Key: Pack d LWE ciphertexts into 1 RLWE using Galois automorphisms. Two approaches available.
Why packing? After external product, each column's value is in coefficient 0 of its RLWE.
Simple "shift and add" fails because noise spreads to ALL coefficients.
Automorphisms permute coefficients in a controlled way that preserves encryption structure.
Algorithm Steps
Extract LWE from each column RLWE (coeff 0)
Convert LWE a-vectors back to RLWE form
Recursively pair: ct_even + y·ct_odd
Apply automorphism τ_t and key-switch
Add scaled b-values to final result
Result
Column k's value appears at coefficient k of the packed RLWE, scaled by d.
coeff[k] = message[k] × d
Complexity
Keys: log(d) automorphism key-switching matrices Operations: O(n·log(d)) key-switches for n columns For d=2048: 11 KS matrices, ~948ms server time
InspiRING Innovation: Instead of log(d) key-switching matrices,
use only 2 matrices (K_g, K_h) by pre-rotating a single matrix offline using generator powers.
This is based on Google's reference implementation.
Algorithm Steps
Offline: Compute generator powers g^i mod 2d
Offline: Pre-rotate K_g by τ_{g^i} for all i
Offline: Backward recursion for gadget inversions
Online: Single matrix-vector multiply
Online: Add b-values at positions
Key Insight
Generator g=3 has order d/2 in Z*_{2d}. Pre-rotating ONE matrix by g^i
replaces storing log(d) separate matrices.
τ_{g^i}(K_g) for i ∈ [0, n)
Performance (d=2048)
Keys: 2 matrices (K_g, K_h) vs 11 Packing keys: 64 bytes (seeds) vs 1056 KB (11 KS matrices) Online (16 LWEs):115 μs Offline (16 LWEs): 6.1 ms (amortized)
Fused Multiply-Accumulate
mul_acc_ntt_domain() avoids intermediate allocations in inner loops
Pre-cached bold_t_ntt
Zero NTT conversions in online phase - pure pointwise operations
Metric
Tree Packing
InspiRING
Improvement
KS Matrices
11
2
5.5x
Packing Key Material
1056 KB (11 KS matrices)
64 bytes (seeds)
16,000x
Online Time (16 LWEs)
~4ms (legacy)
115 μs
35x
Offline Precomputation
N/A
6.1 ms
amortized
5. Database Size Comparison
Key:Query size scales with N/t (indicator vector length). Response size scales with entry size. For a fixed database, all queries use the same communication regardless of which entry is requested.
Paper model: query grows with N/t; totals increase with database size.
Database Size
Entries
Shards
Query Size
Response Size
Total
Server Time
Varies with N -->
O(N/t) query, O(entry) response
O(log N)
32 KB
1,024
1
192 KB
32 KB
224 KB
~1 ms
2 MB
65,536
32
192 KB
32 KB
224 KB
~1.5 ms
32 MB
1,048,576
512
192 KB
32 KB
224 KB
~3 ms
3.2 GB
100,000,000
48,829
192 KB
32 KB
224 KB
~3 ms
73 GB (Ethereum)
2,400,000,000
1,171,875
192 KB
32 KB
224 KB
~3 ms
All Variants Summary (d=2048, 32-byte entries)
Variant
Query
Response
Total
Reduction
Notes
InsPIRe^0
192 KB
545 KB
737 KB
baseline
Full query + unpacked
InsPIRe^1
192 KB
32 KB
224 KB
3.3x
Packed response
InsPIRe^2
96 KB
32 KB
128 KB
5.7x
Seeded + packed
Appendix: Lattice Cryptography Foundations
InsPIRe's security is based on the hardness of lattice problems. These visualizations explain the core concepts.
A.1 Lattice Basics & Shortest Vector Problem
A lattice is a regular grid of points. Security comes from the hardness of finding short vectors.
A.2 RLWE Error Distribution
Gaussian noise hides the secret. Without noise, the problem would be easy linear algebra.
A.3 Polynomial Ring Structure
R_q = Z_q[X]/(X^d + 1): Polynomials with cyclic structure. Multiplication by X rotates coefficients.