Private Information Retrieval with Accountability at Erasure-Optimal Server Redundancy

What it is

SynTrace is a single-round compiler for linear private information retrieval (PIR) that identifies servers returning wrong answers. It is an ePrint preprint (2026/2639, October 2026) by Myeongjun Kim, Hyunseok Jeong, Mincheol Son and Young-Sik Kim. It has no venue yet. It applies to linear PIR schemes whose audit-query answers honestly lie in a public code. Shamir-based PIR is the worked case, and the keywords name Reed-Solomon codes.

How it works

The client mixes the retrieval query with m audit queries, using secret linear mixing and independent blinding. Syndromes computed from the audit answers reveal which servers deviated, and this happens before the item is reconstructed. The paper proves perfect query privacy, zero false identification when at most d servers deviate, and statistical realization of an accountable PIR functionality.

If more than d servers deviate, the client aborts and returns an empty identification set. The statistical error applies to that case.

Preconditions / Affected

• A coalition of at most t corrupt servers, with identification guaranteed for at most d deviators.
• Shamir-based PIR needs k = t+d+1 servers. The paper argues that tolerating d missing responses already needs this many under its privacy and download assumptions, so identification adds no servers.
• With k = t+d+1, m = d audit queries suffice given a suitable field. The paper says this is necessary only within its "syndrome-span" decoder class, not in general.

What to do

For a 32 KiB record in a 1 GiB database, the paper reports these figures. They use five servers, privacy and robustness against two corrupted servers, and error at most 2^-40.

Two tuning options follow from the abstract. Extra audit queries beyond d allow a smaller field and lower communication. Batched retrievals can share the audit queries.

Caveats

The abstract gives one workload and no implementation or timing results. The comparison is communication only. The preprint is not peer reviewed, and the page offers only the abstract, so proof details and the field-size formulas are not covered here.