QuarterPIR, a EUROCRYPT 2024 scheme, lets a client read a database without revealing what it reads. Muse Wonder 1.0 cut its bytes per lookup by 27%, with privacy unchanged. We build the scheme up from a 16-entry example to show how.
In its FrontierCS 2 run on the QuarterPIR task, Muse Wonder 1.0 cut the bytes of each private lookup by 27%, with privacy unchanged. The fix is a trick from RAID-6 disk arrays: two checksums can rebuild two lost values. Every model on the leaderboard ran the task once, and seven of twelve passed. No other passing run saved more than 96 of the 1,760 bytes per lookup. Muse Wonder 1.0 saved 480.
FrontierCS 2 removes the core of a paper’s released code, and an agent writes it back. The authors’ code is the human reference. A run passes only if its final version beats it on every metric of every hidden workload.
QuarterPIR, a EUROCRYPT 2024 scheme by Ghoshal, Zhou and Shi [1], lets a client read one database entry without the server learning which. The task removes the server’s request handler, and the agent may redesign both messages. A pass needs fewer bytes on every lookup, faster times and no more client memory.
Picture the database as rows of entries. The client prepares for lookups by reading the whole database once, and from that one pass it keeps hints. A hint is one entry per row, such as B, G, I and O. The client stores only the XOR of their values, the hint’s parity \(h\).
Think of four people and their pay. You remember only the total pay of the four. Later you ask for the total with one of them swapped for a stranger whose pay you know. The difference gives you the pay of the person you swapped out. Whoever answers sees four names and cannot tell which one you care about.
A hint works the same way. To read G, the client asks for the parity of B, F, I and O, with G swapped for a spare entry F whose value it stored. XORing the reply with \(h\) leaves \(G \oplus F\), and one more XOR gives G.
The client keeps many hints, enough that every entry lies in some hint. Each hint serves one lookup. For every row the client also keeps backup hints to replace used ones. Each backup hint stores its parity and the value of its own entry in that row.
A real database has thousands of rows, so a request cannot name an entry in each. QuarterPIR puts the rows in groups, 128 rows to a group. In the example, rows 1 and 2 form group 1, and rows 3 and 4 form group 2. A key is 16 bytes that the server expands into one position per row of a group. A hint has one key per group, and its keys rebuild its entries, so the client stores only a short id and the parity.
A request sends one key per group and one list. The list writes out the positions of one group, the group of the wanted entry, with the wanted entry swapped for a spare. That group gets random bytes in place of a key, so the server cannot tell which group the list is for.
The server XORs what each key picks in its group. That XOR is the group parity, \(K_b\) for group \(b\). It then tries the list in each group in turn, together with the group parities of the other groups. That gives one candidate per group, and the client keeps the candidate of its own group.
A hint serves one lookup. After reading G, the client replaces the used hint with a backup hint for row 2, say A, H, L, M. At setup it stored that hint’s parity, its parity in group 1, \(A \oplus H\), and the value of H. It swaps H for G, which it just read, so the new parity is \(h' = A \oplus G \oplus L \oplus M\). The keys do not change, so in group 1 they still pick A and H. Ghoshal, Zhou and Shi [1] show that this keeps the table of hints distributed as before.
Now the client reads M with this hint, as Figure 3 follows. Group 2 holds M, so it goes as the list L, N, with N in place of M. Group 1 must go as a key. The old key picks A and H, with no G. The server must see a key that picks G, or over time the hints it sees would lack the entries read before, and that would reveal them. The paper makes the same point [1]. So the client draws a fresh key that picks G, and that key also picks a new entry in row 1, D.
The server’s candidate for group 2 is the list plus the group parity of group 1, \(L \oplus N \oplus D \oplus G\). XORing it with \(h'\) gives \(A \oplus D \oplus M \oplus N\). The client knows N, which leaves M and an error, \(A \oplus D\). It cannot remove the error alone, because it does not know D.
The fix is the group parity of group 1, \(K_1 = D \oplus G\). The hint’s own parity in group 1 is \((A \oplus H) \oplus H \oplus G = A \oplus G\). XORing the two gives \(A \oplus D\), and M follows.
The client cannot ask for \(K_1\) alone, since that would reveal that its last read lay in group 1. So the server sends the group parity of every group, every time. At full size that is 32 values, 512 bytes, half the reply.
Muse Wonder 1.0 sends two sums of the group parities instead of all of them. The group parities of the server and the hint’s own parities agree in every group but two: the group of the wanted entry and the group of the inserted one. The client knows both groups. A plain sum and a weighted sum give it two equations, and it solves for the difference it needs.
Addition is XOR, and the weights multiply in the finite field with \(2^{128}\) elements, so each sum is 16 bytes. The client stores one extra value per backup hint. At full size the reply falls from 1,024 bytes to 544.
The checksums are not tied to QuarterPIR. A later scheme by Shi, Peng, Li, Hong and Zhou [2], to appear at IEEE S&P 2027, uses a technique similar to QuarterPIR’s, and the same checksums could nearly halve its reply as well.
The benchmark fixes what the server may see, so a new reply needs no new proof. The server receives only a public function of the request of the authors’ client.
All 4,000 lookups returned the right entry. The run scored 58.1, against 27.3 for the human reference.
The checksums were in the first submission. The rest of the run made the code faster.
The patch below is the final submission, the code the hidden workloads scored.
Every other passing run saved 8 to 96 bytes per lookup. GPT-6.1 Sol scored highest, 58.2, with fewer bytes on the small database and faster timings. Kimi K3 sent 736 bytes but kept 606.8 MB on the client, and failed.
Twelve models tried to beat the code that the SVG-EAR authors released for their ECCV 2026 sparse-attention method, and none passed. We show what each run tried, which of its 48 checks it missed, and by how much.
BBQ, an NSDI 2024 circuit, picks the next packet a network card sends. Gemini 4 Argon and Claude Opus 5.5 each gave it a faster clock than its authors did, one with the same memory and one with registers in its place. We build the circuit up from a 16-priority example to show both.