Skip to content

FUNCTIONS CAN BE SHARED

Split Point

Function secret sharing · DPF · 2-server PIR

Watch two random-looking key trees unfold level by level, XOR their leaves into a single lit point, and use that point to pull one book off a 65,536-book shelf with a query smaller than one page.

THE IDEA

Share the instruction, not the answer

A distributed point function turns “put a 1 at secret position α” into two compact keys. Either key alone expands into noise; expanded together and XORed, they leave exactly one 1. Each server can then scan a public shelf without learning which record its share helped retrieve.

01 · TREE MICROSCOPE

One point, split across two trees

ONE LIT POINT AT α = 11
Expansion level
4 / 4
Server 0k0 share
Server 1k1 share
XOR
Combinedpoint function
Correction wordfinal output correction
Control bitsβ = 1
PrimitiveAES-128-CTR → 2(λ + 1) bits
Inspect the serialized key and construction
k0 serialized bytes

Each level carries a 16-byte seed correction plus two packed control bits. AES-128-CTR is the named PRG: the node seed is its key, a fixed counter emits two child seeds and two control bits, exactly the BGI requirement.

No published known-answer vectors were found for this exact randomized tree-DPF variant. The test suite instead checks every supported domain against an independently built point vector.

02 · PRIVATE SHELF

Fetch one of 65,536 records

Both servers scan everything. Neither receives α.

1CLIENTGen(α) → k0, k1
2TWO SERVERSXOR-fold the shelf
3CLIENTanswer0 XOR answer1

Ready to scan 65,536 records in this browser.

RECONSTRUCTION OUTPUT No record reconstructed yet

Run the fetch to reveal both server receipts, the client’s XOR result, and the byte-for-byte shelf comparison.

03 · QUERY SCALE

Logarithmic keys, full-length baseline

One DPF key290 bytes
Chor XOR query8,192 bytes · 65,536 bits
Root material
17 B
Per-level corrections
272 B
Final correction
1 B
Measured total
290 B

17 + (17 × log₂ 65,536) + 1 = 290 bytes

04 · TRUST BOUNDARY

Break the non-collusion assumption

HONEST SCOPE

What this is, and what it is not

This page implements the two-party BGI tree DPF with AES-128-CTR and real full-domain XOR PIR in your browser. It is not production crypto: the TypeScript is written for inspection, has no side-channel hardening, and keeps ephemeral key material only in memory.

Built here
  • DPF Gen, Eval, EvalAll, and strict key serialization for domains 24 through 216.
  • Two independent server folds and client reconstruction against shelf[α].
  • Collusion and unauthenticated-answer failures, both off by default.
  • Malformed keys, out-of-domain points, and wrong-length answers fail closed.
  • Records wider than the 16-byte AES block are folded in full; record width does not alter the one-bit DPF output.
Deliberate non-goals
  • Three or more servers: this is strictly a two-key construction.
  • Multi-point, interval, or comparison FSS: this shares one point function only.
  • Incremental DPF: the VDAF draft’s IDPF is a different construction.
  • Verifiable DPF: servers do not prove honest evaluation.
  • Malicious-secure PIR: answer tampering is detected only by the teaching oracle.
  • Query batching: each fetch carries one point query.
  • Single-server PIR: two non-colluding servers are essential; see Shelf Oracle.
Boundary probes
  • α outside the domain: Gen and the shelf control reject it before either server runs.
  • Domain size 1: refused as degenerate; this lab starts at 24.
  • All-zero seed: allowed. Its real AES expansion begins computing….
  • Malformed key: reserved bits, wrong correction count, invalid controls, and truncation name their cause.
  • Wrong-length answer: client reconstruction rejects mismatched or empty answers.
  • Record wider than AES: the 17-byte boundary test folds every byte without truncation.

Primary sources

Gilboa & Ishai, Distributed Point Functions and Their Applications (EUROCRYPT 2014) · Boyle, Gilboa & Ishai, Function Secret Sharing (EUROCRYPT 2015) · Boyle, Gilboa & Ishai, Function Secret Sharing: Improvements and Extensions · Chor et al., Private Information Retrieval (FOCS 1995)