Cryptography
QuarterPIR
Make each private lookup send fewer bytes and run faster.
Based on Efficient Pre-processing PIR Without Public-Key Cryptography (EUROCRYPT 2024) · original code
Solved by 7 of 12 agents. Top score 58.2 by GPT-6.1 Sol; the original authors’ code scores 27.3.
Background
Private information retrieval lets a client read one database entry without the server learning which. QuarterPIR needs no public-key cryptography. The client streams the database once and keeps hints: XORs of entries in pseudorandom sets. Each lookup then needs one short request and reply.
What the agent has to build
This task leaves out the server’s request handler. The agent writes it and may redesign the messages and client. The server sees only a fixed public function of the authors’ request, so privacy is kept.
How it is judged
Each submission serves databases of 65,536 and 67 million entries, a thousand random lookups each. Every lookup must be correct. To pass, it must send fewer bytes than the human reference on every lookup. It must also be faster in server, setup and lookup time, and use no more client memory.
Wenhao Chai discusses this task in the interview.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 27.3 | |
| GPT-6.1 Sol | Solved | 58.2 | $3.89 |
| Muse Wonder 1.0 | Solved | 58.1 | $28.83 |
| GPT-6 Astra | Solved | 56.3 | $11.60 |
| Gemini 4 Argon | Solved | 56.1 | $5.97 |
| Claude Opus 5.5 | Solved | 55.3 | $38.12 |
| GLM 5.3 | Solved | 53.5 | $10.34 |
| GLM 5.3 Flash | Solved | 45.6 | $0.65 |
| Kimi K3 | Not solved | 54.7 | $10.82 |
| Qwen 3.8 Max | Not solved | 48.2 | $7.12 |
| DeepSeek V4.1 Flash | Not solved | 36.0 | $0.12 |
| Muse Spark 1.3 | Not solved | 33.7 | $4.64 |
| Step 5 Preview | Not solved | 0.0 | $4.45 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Client storage (MiB)lower is better | Online time, end to end (µs)lower is better | Online communication (bytes)lower is better | Client preprocessing time (s)lower is better | Server compute time (µs)lower is better |
|---|---|---|---|---|---|
| Original code | 41.7 | 2,400 | 994 | 64.8 | 446 |
| GPT-6.1 Sol | 40.8 | 371 | 854 | 8.15 | 46.4 |
| Muse Wonder 1.0 | 25.9 | 403 | 666 | 9.38 | 50.4 |
| GPT-6 Astra | 40.2 | 366 | 898 | 10.9 | 48.9 |
| Gemini 4 Argon | 41.3 | 391 | 882 | 8.68 | 47.8 |
| Claude Opus 5.5 | 40.8 | 370 | 914 | 8.11 | 49.6 |
| GLM 5.3 | 33.5 | 984 | 922 | 19.2 | 90.6 |
| GLM 5.3 Flash | 39.8 | 1,310 | 890 | 16.5 | 204 |
| Kimi K3 | 291 | 944 | 418 | 14.5 | 41.1 |
| Qwen 3.8 Max | 40.8 | 846 | 902 | 15.7 | 141 |
| DeepSeek V4.1 Flash | 37.8 | 1,260 | 962 | 28.2 | 335 |
| Muse Spark 1.3 | 35.2 | 1,560 | 994 | 52.1 | 229 |
| Step 5 Preview | — | — | — | — | — |
How Claude Opus 5.5 solved it
- 1.
Dropping superblock keys
The request is the authors’ request with the keys of the first superblocks removed and the offsets bit-packed. The client stores the parities those keys would let the server compute. Client memory bounds how many keys it drops: all four for the small database, one of 32 for the large one.
- 2.
Replaying the reference client
The client makes exactly the reference client’s choices: the same hints, random coins and refresh order. So its request stays a fixed public function of the authors’ request. It stores each hint as one parity per dropped superblock, plus one for all the others.
- 3.
One candidate per superblock
For each superblock, the server XORs the entries at the offsets that fall in it with the key-defined parities of the other kept superblocks. It returns these candidates and the kept parities. The client takes the candidate for the entry’s superblock and XORs it with its stored parity.
- 4.
Fast setup and lookup
Setup streams the database in cache-sized parts while three workers add the entries to every hint’s parity. A table built during setup narrows each lookup’s search for the hint that holds the entry, so the client checks only a few hints. AES keys are expanded four at a time.
Task and results from frontier-cs.org, as of October 20, 2026.