Privacy & Modern Cryptography

The Problem: Traffic Analysis

Encryption hides what you say, but not who you are talking to. An adversary watching your internet connection can see that you contacted nytimes.com at 2:03 PM, even if the content is encrypted. This is traffic analysis, and it is devastatingly effective against journalists, activists, and ordinary people who simply prefer privacy.

Tor (The Onion Router) is the dominant solution, deployed at scale. Its core idea, called onion routing, was invented at the US Naval Research Laboratory in the 1990s and refined by Roger Dingledine, Nick Mathewson, and Paul Syverson.

The Onion Routing Idea

Instead of connecting directly to a destination, your Tor client:

1. Selects a chain of three volunteer relay nodes (Guard → Middle → Exit) from a globally distributed directory.
2. Establishes encrypted channels with each relay, incrementally: first with the Guard, then extends the circuit through the Guard to the Middle, then extends again to the Exit.
3. Wraps the message in three layers of encryption, one for each relay:

Client encrypts: Enc(Exit_pk, Enc(Middle_pk, Enc(Guard_pk, payload)))

Each relay peels one layer (like peeling an onion) and forwards the result. The Guard knows who you are but not your destination. The Exit knows the destination but not who you are. The Middle knows neither.

Circuit Setup: The EXTEND Protocol

The incremental circuit extension uses Diffie-Hellman key exchange through the already-established leg:

1. Client → Guard:  [CREATE, DH_half_G]         (establishes key K_G)
2. Client → Guard → Middle: [RELAY_EXTEND, DH_half_M]  (Guard forwards encrypted in K_G; establishes K_M)
3. Client → Guard → Middle → Exit: [RELAY_EXTEND, DH_half_E]  (establishes K_E)

At the end, the client holds three session keys (K_G, K_M, K_E), each unknown to all other parties.

Hidden Services (.onion)

Tor also enables hidden services: servers with no public IP address. The server picks six introduction points in the Tor network and publishes them to a distributed hash table (the HSDir). The client builds a circuit to a rendezvous point and sends a connection request through an introduction point. Both client and server then build circuits to the rendezvous point. Neither ever learns the other's real IP address.

This is why .onion addresses are 56-character strings: they are the Ed25519 public key of the service, providing both routing and authentication in one.

Limitations

Tor provides unlinkability — an adversary cannot link your identity to your traffic — but only under assumptions:

• The adversary does not control enough relays to observe both entry and exit (a global passive adversary breaks Tor through correlation attacks).
• Timing attacks on the circuit can sometimes de-anonymize users even without controlling relays.
• Browser fingerprinting at the application layer can de-anonymize even Tor users (hence the Tor Browser bundles mitigations).

Tor's security is probabilistic, not absolute, and the threat model matters enormously.

# Simplified onion encryption (conceptual, not real Tor)
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

def onion_wrap(payload: bytes, keys: list[bytes]) -> bytes:
    """Wrap payload in layers of AES-GCM encryption.
    keys = [guard_key, middle_key, exit_key]
    Each layer is peeled by the corresponding relay.
    """
    data = payload
    for key in reversed(keys):  # exit first, guard last
        nonce = os.urandom(12)
        aesgcm = AESGCM(key)
        data = nonce + aesgcm.encrypt(nonce, data, None)
    return data

def onion_peel(ciphertext: bytes, key: bytes) -> bytes:
    nonce, ct = ciphertext[:12], ciphertext[12:]
    return AESGCM(key).decrypt(nonce, ct, None)

The Question Differential Privacy Answers

A hospital wants to release statistics about patient demographics. If they release exact data, an adversary might use auxiliary information to re-identify individuals. If they release nothing, the data is useless. Differential privacy (Dwork, McSherry, Nissim, Smith, 2006) provides a mathematical definition of what it means for a data release to preserve individual privacy, and concrete mechanisms that achieve it.

The Formal Definition

A randomized algorithm M satisfies (ε, δ)-differential privacy if for all pairs of databases D, D' that differ in at most one row, and all possible outputs S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S] + δ

When δ = 0, this is pure ε-differential privacy.

Intuition: The output distribution of M barely changes when you add or remove one person's data. An adversary who observes the output of M gains almost no information about whether any particular person was in D.

• ε (epsilon) is the privacy budget: smaller ε means stronger privacy. ε = 0 would mean M outputs the same distribution regardless of D (useless). ε = ∞ means no privacy guarantee. In practice, ε = 0.1 to ε = 10 depending on sensitivity.
• δ (delta) is a small failure probability. Setting δ = 0 is strongest; δ = 1/n² is common.

The Laplace Mechanism

To release a real-valued function f(D) with pure DP:

1. Compute the sensitivity Δf = max over all D, D' differing in one row of |f(D) − f(D')|.
2. Add Laplace noise with scale Δf/ε:

M(D) = f(D) + Lap(Δf / ε)

The noise variance is 2(Δf/ε)². The utility-privacy tradeoff is explicit: smaller ε → more noise → less useful output.

Example: Count query ("how many patients have condition X?"). Sensitivity Δf = 1 (one row changes the count by at most 1). Release: count + Lap(1/ε).

The Gaussian Mechanism

For (ε, δ)-DP with δ > 0, Gaussian noise (σ ≥ Δf·√(2 ln(1.25/δ)) / ε) is sufficient. Gaussian noise has better composition properties.

Composition

DP has two key composition theorems:

• Sequential composition: k algorithms each with (ε_i, δ_i)-DP composed together gives (Σε_i, Σδ_i)-DP. The privacy cost accumulates.
• Parallel composition: if the k algorithms operate on disjoint subsets of D, the total cost is max(ε_i) — no accumulation!

Local vs. Central DP

• Central DP: a trusted curator holds the raw data and releases privatized statistics. Apple, the US Census, and Google use this model.
• Local DP: each individual randomizes their own data before sending it to a (possibly untrusted) aggregator. This is used in Google Chrome's RAPPOR and Apple's iOS telemetry. Local DP requires much more noise (a factor of √n per query) for the same utility.

The Randomized Response Technique

The oldest local DP mechanism (Warner, 1965):

• To answer a yes/no question privately: flip a coin. If heads, answer truthfully. If tails, flip another coin and answer that.
• The true answer is revealed with probability 3/4, randomized with probability 1/4.
• This achieves ε = ln 3 ≈ 1.099 local DP.
• The aggregator can debias the answers: if p̂ is the fraction answering 'yes', the true fraction is estimated as (2p̂ - 0.5).

import numpy as np

def laplace_mechanism(true_value: float, sensitivity: float, epsilon: float) -> float:
    """Privatize a real-valued query with the Laplace mechanism."""
    scale = sensitivity / epsilon
    return true_value + np.random.laplace(0, scale)

def dp_mean_query(data: list[float], epsilon: float,
                  lower: float, upper: float) -> float:
    """DP mean of clipped data. Sensitivity = (upper-lower)/n."""
    n = len(data)
    clipped = [max(lower, min(upper, x)) for x in data]
    true_mean = sum(clipped) / n
    sensitivity = (upper - lower) / n
    return laplace_mechanism(true_mean, sensitivity, epsilon)

# Example: ages in [0, 100], epsilon = 1.0
ages = [25, 32, 41, 55, 28, 19, 67, 44, 38, 52]
print(f"True mean: {sum(ages)/len(ages):.2f}")
print(f"DP mean:   {dp_mean_query(ages, 1.0, 0, 100):.2f}")

The Magic Trick

Imagine you claim to know a secret (say, the solution to a Sudoku puzzle). I want to verify you know it, but you refuse to show me the solution — perhaps because you want to sell it. Is there a way for you to convince me, without revealing anything?

Zero-knowledge proofs (ZKPs), invented by Goldwasser, Micali, and Rackoff in 1985, answer: yes, always, for any NP statement.

Formal Definitions: The Three Properties

A proof system (P, V) for a language L is zero-knowledge if:

1. Completeness: If x ∈ L and P knows a witness w, then V accepts with high probability.
2. Soundness: If x ∉ L, then no cheating prover P* can convince V to accept except with negligible probability.
3. Zero-knowledge: There exists a simulator S such that for any x ∈ L, the distribution of (x, S(x)) is computationally indistinguishable from a real transcript between P and V. The verifier learns nothing beyond the fact that x ∈ L.

The simulator's existence is the key: if a simulator can produce fake transcripts indistinguishable from real ones, then the real transcripts couldn't have conveyed any information (since the simulator knows no witness).

The Ali Baba Cave: A Physical Intuition

A cave has a ring-shaped passage with a magic door at the back that only opens with a secret code. Peggy claims to know the code. Victor wants to verify this.

1. Victor waits outside while Peggy enters, going either left (L) or right (R) down the passage.
2. Victor enters, randomly shouts "L" or "R".
3. Peggy exits from the side Victor shouted.

If Peggy doesn't know the code, she has a 1/2 chance of guessing which side Victor will call. After k rounds, the probability of a cheating Peggy fooling Victor is (1/2)^k. After 30 rounds, Victor is convinced to 1 in a billion that Peggy knows the code — but has learned zero information about what the code actually is.

The Schnorr Identification Protocol

A concrete, efficient ZKP for proving knowledge of a discrete logarithm:

Setup: Public parameters (G, q, g) where g generates a group G of order q. Prover knows secret x; public key is y = g^x.

Prover (knows x)           Verifier (knows y)

1. Pick random r ∈ Z_q
   Send commitment: R = g^r → 

2.                          ← Challenge: c ∈ Z_q (random)

3. Compute response: s = r + c·x mod q
   Send s →

4.                          Check: g^s == R · y^c
                            (Because g^(r+cx) = g^r · (g^x)^c = R · y^c)

This is zero-knowledge because a simulator can generate valid transcripts by picking s and c randomly, then setting R = g^s · y^{-c} — no knowledge of x required.

SNARKs: Zero-Knowledge at Scale

zk-SNARKs (Succinct Non-interactive ARguments of Knowledge) bring ZKPs to real-world scale:

• Succinct: proofs are tiny (a few hundred bytes) regardless of the computation size.
• Non-interactive: no back-and-forth; Peggy generates the proof offline, sends it once.
• Argument: soundness holds against computationally-bounded provers.

The key technique is arithmetization: convert any NP computation into a system of polynomial constraints (an R1CS or PLONK circuit), then use polynomial commitment schemes to prove the constraints are satisfied without revealing the witness.

zk-SNARKs are used in Zcash (private cryptocurrency), Ethereum's zkRollup scaling, and increasingly in privacy-preserving ML inference.

STARKs and Bulletproofs

• STARKs: like SNARKs but rely only on hash functions (post-quantum secure), at the cost of larger proof size.
• Bulletproofs: efficient range proofs (prove that a committed value is in [0, 2^64]) without a trusted setup. Used in Monero.

# Schnorr identification protocol over a prime-order group (toy integers, not real crypto)
import random

def schnorr_demo(p=23, g=5):
    """Toy Schnorr ZKP. p must be prime, g a generator of Z_p*.
    WARNING: use real libraries (cryptography.io) for production."""
    q = p - 1  # group order

    # PROVER setup
    x = random.randint(1, q-1)    # secret key
    y = pow(g, x, p)              # public key
    print(f"Secret x={x}, Public y={y}")

    # --- Protocol ---
    # Round 1: commitment
    r = random.randint(1, q-1)
    R = pow(g, r, p)
    print(f"Commitment R={R}")

    # Round 2: challenge (from verifier)
    c = random.randint(1, q-1)
    print(f"Challenge  c={c}")

    # Round 3: response
    s = (r + c * x) % q
    print(f"Response   s={s}")

    # VERIFIER check
    lhs = pow(g, s, p)             # g^s mod p
    rhs = (R * pow(y, c, p)) % p  # R * y^c mod p
    print(f"Verify: g^s={lhs} == R*y^c={rhs} → {lhs == rhs}")

schnorr_demo()

The Dream: Computing on Encrypted Data

You upload encrypted medical records to a cloud server. The server runs a machine learning model on your data and returns an encrypted result. You decrypt the result and get your diagnosis. The cloud server, at no point, ever saw your plaintext data.

This is homomorphic encryption (HE) — encryption that is compatible with computation. The cloud operates entirely in ciphertext space, yet the mathematics guarantee the result decrypts correctly.

The Algebraic Idea

A scheme is homomorphic with respect to an operation ⊕ if:

Dec(Enc(a) ⊕ Enc(b)) = a ⊕ b

• Partially homomorphic: supports one operation (add or multiply) unboundedly. Example: RSA supports unlimited multiplications.
• Somewhat homomorphic (SHE): supports both add and multiply, but only a limited number of times before noise corrupts the ciphertext.
• Fully homomorphic (FHE): supports both add and multiply unboundedly, thus can evaluate any Boolean circuit. This is the holy grail.

Craig Gentry's Breakthrough (2009)

For decades, FHE was an open problem. Craig Gentry solved it in his 2009 PhD thesis, with a construction based on lattice problems.

The key insight is bootstrapping: SHE schemes accumulate noise with each operation. When noise gets too large, decryption fails. Bootstrapping evaluates the decryption circuit homomorphically — the scheme decrypts itself, resetting the noise level. This works as long as the decryption circuit is simpler than the scheme can handle — a beautiful self-referential argument.

Modern FHE Schemes

BFV / BGV (integer arithmetic)

These schemes operate on vectors of integers modulo a large prime. Addition is component-wise; multiplication is polynomial convolution modulo a cyclotomic polynomial. Batching allows SIMD-style computation on thousands of values in parallel.

CKKS (approximate arithmetic)

CKKS (Cheon-Kim-Kim-Song, 2017) is designed for real and complex numbers. The plaintext is approximately recovered — there is inherent precision loss. This is ideal for ML inference where exact arithmetic is not required.

TFHE / FHEW (gate-by-gate)

These schemes evaluate Boolean gates one at a time, each in ~1ms. Any Boolean circuit can be evaluated. Bootstrapping happens after every gate, keeping noise low.

Practical Performance (2024)

FHE is 10^3 to 10^6 times slower than plaintext computation, depending on the scheme and operation. The gap is closing fast:

• CKKS can evaluate a ResNet-20 on encrypted images in ~1 minute.
• Hardware accelerators (Google, Intel, IBM) are bringing latency to seconds.
• Libraries: Microsoft SEAL, OpenFHE, HElib, TFHE-rs.

The Learning With Errors Foundation

Almost all modern FHE schemes rely on the Learning With Errors (LWE) hardness assumption:

• Given many samples (A, b) where b = As + e (mod q), for secret s and small error vector e, find s.
• This is believed hard even for quantum computers, making FHE post-quantum secure.

# FHE conceptual pseudocode using CKKS-style approximate arithmetic
# In practice: pip install tenseal
import tenseal as ts

def fhe_dot_product_demo():
    # Setup: generate FHE context with CKKS scheme
    ctx = ts.context(
        ts.SCHEME_TYPE.CKKS,
        poly_modulus_degree=8192,
        coeff_mod_bit_sizes=[60, 40, 40, 60]
    )
    ctx.generate_galois_keys()  # for rotation operations
    ctx.global_scale = 2**40   # precision parameter

    # Plaintext vectors (client sees these)
    x = [1.0, 2.0, 3.0, 4.0]
    weights = [0.1, 0.5, 0.3, 0.1]

    # Encrypt x (sent to server)
    enc_x = ts.ckks_vector(ctx, x)

    # Server computes dot product on ENCRYPTED data
    # (server never sees x)
    enc_result = enc_x.dot(weights)

    # Client decrypts result
    result = enc_result.decrypt()
    print(f"FHE result: {result[0]:.4f}")
    print(f"True result: {sum(a*b for a,b in zip(x,weights)):.4f}")

# fhe_dot_product_demo()  # requires: pip install tenseal

The Millionaires' Problem

Alice and Bob both want to know who is richer, but neither is willing to reveal their net worth. Can they determine who has more money without either learning the other's balance?

This is Yao's Millionaires' Problem (1982), and it inaugurated the field of secure multiparty computation (MPC). The general result is stunning: any function of private inputs can be computed by a group of parties such that no party learns anything beyond the output.

Formal Setting

In an MPC protocol:

• n parties P_1, ..., P_n each hold private inputs x_1, ..., x_n.
• They wish to jointly compute f(x_1, ..., x_n).
• Security: no coalition of t corrupted parties learns anything about the honest parties' inputs beyond what is revealed by the output.

Two corruption models:

• Semi-honest (passive): corrupted parties follow the protocol but try to infer extra information from their transcripts.
• Malicious (active): corrupted parties can deviate arbitrarily.

Garbled Circuits (Yao's Protocol)

Yao's garbled circuit protocol computes any Boolean function in two rounds:

1. Circuit garbling (by Alice, the "garbler"):

   • Represent f as a Boolean circuit.
   • For each wire w, pick two random labels (L^0_w, L^1_w) representing 0 and 1.
   • For each gate (AND, OR, etc.), encrypt the output labels under the input labels: Enc(L^a_w1, L^b_w2) → L^{gate(a,b)}_w3
   • Alice sends the garbled tables and her own input wire labels (for her actual inputs).

2. Oblivious Transfer (for Bob's inputs):

   • Bob needs the wire labels for his bits, but without Alice learning which bit he holds.
   • They run an oblivious transfer protocol (OT): Alice sends both labels for Bob's wire; Bob receives only the label corresponding to his bit; Alice learns nothing.

3. Evaluation (by Bob, the "evaluator"):

   • Bob evaluates the garbled circuit gate by gate, obtaining the output labels.
   • A final decoding table translates output labels back to bits.

Round complexity: 2. Communication: O(|circuit|) labels.

Secret Sharing: The BGW Protocol

Ben-Or, Goldwasser, Wigderson (1988) gave an MPC protocol for any number of parties using Shamir secret sharing:

Shamir (t, n) Secret Sharing:

• To share secret s: pick a random polynomial p(x) of degree t with p(0) = s. Give party i the share p(i).
• Any t+1 parties can reconstruct s (by Lagrange interpolation). Any t parties learn nothing.

Addition of two shared values [a] and [b] is free: each party adds their shares locally, giving [a+b].

Multiplication is expensive: requires an interaction round to reduce the degree of the product polynomial.

With t < n/2 (or t < n/3 for malicious security), BGW is information-theoretically secure — no computational assumptions needed.

Oblivious Transfer (OT): The Atomic Primitive

OT is the fundamental primitive underlying all MPC:

• 1-out-of-2 OT: sender has (m_0, m_1); receiver has bit b; receiver gets m_b; sender learns nothing about b; receiver learns nothing about m_{1-b}.
• OT can be built from RSA, DDH, or LWE assumptions.
• OT extension (Ishai et al., 2003): from k base OTs, compute n >> k OTs using only symmetric crypto. This makes OT cheap at scale.

Applications

• Private set intersection (PSI): two hospitals compute the intersection of patient IDs without revealing non-matching IDs. Used for COVID contact tracing.
• Privacy-preserving auctions: parties submit bids; winner is determined without revealing losing bids.
• Threshold signatures: a private key is split among k parties; t of them must cooperate to sign.

# Shamir secret sharing over a finite field
def shamir_share(secret: int, n: int, t: int, prime: int) -> list:
    """Split secret into n shares, any t+1 can reconstruct."""
    import random
    coeffs = [secret] + [random.randrange(prime) for _ in range(t)]
    return [(i, sum(c * pow(i, j, prime) for j, c in enumerate(coeffs)) % prime)
            for i in range(1, n + 1)]

def lagrange_reconstruct(shares: list, prime: int) -> int:
    """Reconstruct secret from any t+1 shares via Lagrange interpolation."""
    def mod_inv(a, m):
        return pow(a, m - 2, m)  # Fermat's little theorem (prime m)
    
    secret = 0
    xs = [s[0] for s in shares]
    for i, (xi, yi) in enumerate(shares):
        num = den = 1
        for j, xj in enumerate(xs):
            if i != j:
                num = (num * (-xj)) % prime
                den = (den * (xi - xj)) % prime
        secret = (secret + yi * num * mod_inv(den, prime)) % prime
    return secret

prime = 2**127 - 1  # Mersenne prime
secret = 42
shares = shamir_share(secret, n=5, t=2, prime=prime)
print("Shares:", shares[:3])
print("Reconstructed:", lagrange_reconstruct(shares[:3], prime))

What Is a Blockchain?

A blockchain is a replicated, append-only log secured by cryptographic linking and maintained by a distributed consensus protocol. The fundamental problem it addresses: how do mutually distrustful parties agree on a shared history of transactions, without a trusted central authority?

The Cryptographic Building Blocks

Hash pointer: Instead of a regular pointer to previous data, a hash pointer stores both the address and the cryptographic hash of the data there. Changing any historical data invalidates all subsequent hashes — the chain structure makes tampering evident.

Merkle tree: Transactions in a block are organized into a Merkle tree. The root hash commits to all transactions. A Merkle proof (also called SPV proof) proves that a specific transaction is in a block using only O(log n) hashes — you don't need to download all transactions.

Merkle Root
   /     \
  H12    H34
 /  \   /  \
H1  H2 H3  H4
|   |  |   |
T1  T2 T3  T4

To prove T3 is in the block: provide (H4, H12). The verifier computes H34 = Hash(H3 || H4), Root = Hash(H12 || H34).

Proof of Work: Nakamoto Consensus

Bitcoin's innovation was Nakamoto consensus: use proof of work (PoW) to make block creation expensive, so a rational adversary would need to control >50% of the network's computation to rewrite history.

To create a valid block, a miner must find a nonce such that:

Hash(block_header || nonce) < target

This is a hash preimage puzzle. The expected number of hashes needed is (max_hash_value / target). The network adjusts target to maintain a 10-minute block time.

Longest chain rule: honest nodes always extend the longest valid chain. If an adversary controls less than 50% of the hash rate, their private chain grows slower than the honest chain — eventually they can never catch up. This is the 51% attack threshold.

Proof of Stake

PoW wastes electricity. Proof of Stake (PoS), used in Ethereum post-Merge (2022), replaces computation with economic stake:

• Validators lock up ("stake") cryptocurrency as collateral.
• They are selected to propose and attest to blocks proportional to their stake.
• Dishonest behavior (double-signing) is punished by slashing — the validator's stake is burned.

PoS achieves finality (Casper FFG, Gasper) with 2/3+ honest stake, under the economic assumption that honest validators don't want to lose their stake.

Smart Contracts

Ethereum extended Bitcoin's scripts into Turing-complete smart contracts: programs stored on-chain and executed by every validator. The EVM (Ethereum Virtual Machine) is a sandboxed stack machine. Gas limits prevent infinite loops.

// Simple Solidity smart contract
contract SimpleEscrow {
    address public buyer;
    address public seller;
    uint public amount;
    
    constructor(address _seller) payable {
        buyer = msg.sender;
        seller = _seller;
        amount = msg.value;
    }
    
    function release() public {
        require(msg.sender == buyer);
        payable(seller).transfer(amount);
    }
}

ZK-Rollups: Blockchains Meet ZKPs

zkRollups combine blockchains with zero-knowledge proofs for scalability:

• Hundreds of transactions are processed off-chain.
• A zk-SNARK proof is generated, attesting that all state transitions were valid.
• Only the proof (a few hundred bytes) is posted to the main chain.
• The chain verifies the proof in O(1) time — 10-100x throughput improvement with full cryptographic security.

StarkNet uses STARKs; zkSync and Polygon Hermez use PLONKish SNARKs.

# Simplified blockchain structure in Python
import hashlib, json, time

def sha256(data: str) -> str:
    return hashlib.sha256(data.encode()).hexdigest()

class Block:
    def __init__(self, index, transactions, prev_hash, difficulty=4):
        self.index = index
        self.timestamp = time.time()
        self.transactions = transactions
        self.prev_hash = prev_hash
        self.nonce = 0
        self.hash = self.mine(difficulty)

    def compute_hash(self):
        content = json.dumps({
            'index': self.index, 'ts': self.timestamp,
            'txns': self.transactions, 'prev': self.prev_hash,
            'nonce': self.nonce
        }, sort_keys=True)
        return sha256(content)

    def mine(self, difficulty):
        prefix = '0' * difficulty
        while True:
            h = self.compute_hash()
            if h.startswith(prefix):
                return h
            self.nonce += 1

genesis = Block(0, ['coinbase'], '0' * 64)
b1 = Block(1, ['Alice->Bob: 5 BTC'], genesis.hash)
print(f"Genesis: {genesis.hash[:20]}...")
print(f"Block 1: {b1.hash[:20]}... (prev={b1.prev_hash[:12]}...)")

The Problem

You want to look up the 42nd entry in a public database. The trivial solution — just ask the server for entry 42 — reveals your query. Private Information Retrieval (PIR) lets you retrieve a database entry without the server learning which entry you want.

Trivial solution: download the entire database. This achieves perfect privacy but has O(n) communication cost. PIR seeks sub-linear communication.

Information-Theoretic PIR

With a single server, information-theoretic PIR requires downloading the entire database (Chor et al., 1998). This is a fundamental lower bound: if you don't download everything, the server can infer something about your query.

With two non-colluding servers, Chor et al. showed a protocol with O(n^{1/3}) communication:

1. Client splits query index i into a random set S₁ and S₁ ⊕ {i} (symmetric difference).
2. Send S₁ to server 1, S₁ ⊕ {i} to server 2.
3. Each server XORs together all database bits indexed by their set.
4. Client XORs the two responses to get bit i.

The intuition: each server sees a random set that is completely independent of i (since S₁ is random).

Computational PIR

Under cryptographic assumptions (like LWE), a single server can support PIR with polylogarithmic communication per query. The SealPIR protocol (2018) uses FHE: the client encrypts the query under BFV, the server evaluates the selection circuit homomorphically, and returns the encrypted database entry.

Computation-communication tradeoffs make computational PIR practical for small databases (millions of entries) today.

ORAM: Hiding Access Patterns

PIR hides what you read. Oblivious RAM (ORAM) additionally hides the pattern of reads and writes — crucial when the access sequence itself reveals information.

Goldreich and Ostrovsky (1996) showed that any ORAM requires Ω(log n) overhead. PathORAM achieves O(log n) and is used in SGX enclaves and private cloud storage.

# Two-server information-theoretic PIR (Chor et al. 1998)
import random

def two_server_pir(database: list[int], index: int) -> int:
    """Retrieve database[index] without either server learning index.
    database: list of bits (0 or 1)"""
    n = len(database)
    # Client: pick random set S1 ⊆ {0,...,n-1}
    S1 = set(i for i in range(n) if random.random() < 0.5)
    # S2 = S1 ⊕ {index} (symmetric difference)
    S2 = S1.symmetric_difference({index})

    # Server 1: XOR bits at positions in S1
    response1 = 0
    for i in S1:
        response1 ^= database[i]

    # Server 2: XOR bits at positions in S2
    response2 = 0
    for i in S2:
        response2 ^= database[i]

    # Client reconstructs
    return response1 ^ response2

db = [0, 1, 1, 0, 1, 0, 0, 1]  # 8-bit database
for idx in range(len(db)):
    retrieved = two_server_pir(db, idx)
    assert retrieved == db[idx]
print("All PIR queries correct!")

Why Intuition Fails

Early cryptographers defined security as "the adversary cannot find the key" or "the ciphertext looks random." These definitions, while reasonable-sounding, failed: they didn't capture subtle information leakages (does the ciphertext reveal the length of the message? The parity of the plaintext?), and they were hard to use in proofs.

Modern cryptography replaced intuition with formal definitions and a simulation-based security framework. This is arguably the intellectual centerpiece of the entire field.

Semantic Security / IND-CPA

An encryption scheme is IND-CPA (indistinguishable under chosen-plaintext attack) if no efficient adversary can win the following game:

1. Challenger generates key K.
2. Adversary A queries the encryption oracle (can encrypt any plaintexts of its choice).
3. A submits two equal-length messages m_0, m_1.
4. Challenger picks random b ∈ {0,1}, returns Enc(K, m_b).
5. A outputs a guess b'.
6. A wins if b' = b.

A scheme is IND-CPA secure if Pr[A wins] ≤ 1/2 + negl(λ) for all efficient A.

This is equivalent to semantic security (Goldwasser-Micali): no efficient A can compute any predicate of the plaintext from the ciphertext.

The Simulation Paradigm

For protocols (not just encryption), security is defined via ideal-world / real-world comparison:

• Ideal world: there is a trusted party T. All parties send inputs to T; T computes the function and returns outputs.
• Real world: parties run the actual protocol with each other.

A protocol is secure if for every adversary A in the real world, there exists a simulator S (operating in the ideal world) such that no distinguisher can tell the two worlds apart.

This definition is powerful because:

1. It captures all possible attacks simultaneously (if the real and ideal worlds are indistinguishable, no attack works).
2. It composes: universal composability (UC) (Canetti, 2001) ensures that protocols remain secure when composed with other protocols — crucial for building complex systems.

Composability: Why It Matters

Many natural-looking security definitions are not composable. A protocol that is secure in isolation may break when run alongside other protocols. UC-security is the gold standard: a UC-secure protocol for functionality F can be replaced by the ideal functionality F in any larger protocol, without affecting security.

The theory is beautiful but the proofs are demanding — UC security proofs are often longer than the protocols themselves. In practice, most deployed protocols use simpler sequential composition arguments.

# IND-CPA game simulation (abstract, for pedagogical clarity)
from typing import Callable
import random

def ind_cpa_game(
    enc: Callable,   # enc(key, msg) -> ciphertext
    adversary: Callable,  # adversary(oracle, c) -> bit
    key_gen: Callable,
    num_trials: int = 10000
) -> float:
    """Estimate adversary's advantage in the IND-CPA game."""
    wins = 0
    for _ in range(num_trials):
        key = key_gen()
        # Adversary gets encryption oracle
        oracle = lambda m: enc(key, m)
        # Adversary submits two messages (we just use 'a' and 'b')
        m0, m1 = b'message_zero_____', b'message_one______'
        # Challenger picks random bit
        b = random.randint(0, 1)
        challenge = enc(key, m1 if b == 1 else m0)
        # Adversary guesses
        guess = adversary(oracle, challenge, m0, m1)
        if guess == b:
            wins += 1
    advantage = abs(wins / num_trials - 0.5)
    return advantage

# A secure scheme: adversary cannot do better than random guessing
# advantage ≈ 0.0 means IND-CPA secure