Plotkin Attacks! On the (Mis)use of Raptor Codes in Asynchronous Verifiable Information Dispersal

What it is

Victor Shoup's paper (Cryptology ePrint 2026/2338) gives precise mathematical boundaries for the "reconstruct-later AVID" vulnerability in R10 and RaptorQ — exact thresholds at which the attack is provably possible, independent of the empirical demonstration already covered in the summary.

How it works

The Plotkin bound forces the existence of a nonzero input whose encoded image has low Hamming weight, which in turn yields a "bad" (f+1)-subset — a set of honest fragments that fails to determine the message. The paper states two concrete breakpoints:

• R10: every assignment of encoding symbols to honest parties contains a bad subset whenever K > ⌊log₂(2f+2)⌋.
• RaptorQ: every assignment contains a bad subset whenever K > 7·H_HDPC + ⌊log₂(2f+2)⌋, where H_HDPC is RFC 6330's number of high-density parity-check symbols.

For R10 specifically, the paper also gives explicit certificates (not just an existence proof) of bad subsets for every standardized 34 ≤ K ≤ 8192 and every n with 3f+1 ≤ n ≤ 4f ≤ 65520 — guaranteed when ESIs are assigned sequentially (0,1,...,n-1), and with probability ≥ 1/2 when ESIs are uniformly random.

Preconditions / Affected

Notably, the empirical RaptorQ attack (f = 9 to 45, summarized already) succeeds at K = f+1 — far below the f = 77 threshold at which the formal bound above first applies. This means the proven worst case and the demonstrated practical attack are two separate results: the formal bound is a conservative upper limit, while real breaks occur at much smaller parameters. Empirical attacks also succeed across F₄, F₁₆, and F₂₅₆ at K values well below the formal bound.

Caveats

The R10 guarantee of a bad subset for every assignment only holds for sequential ESI assignment; with uniformly random ESIs the paper only claims probability ≥ 1/2, not certainty. The formal thresholds above are sufficient conditions found via the Plotkin bound, not tight characterizations — actual attacks (per the empirical f-range) succeed well before the formal threshold is reached, so engineers should not treat the K/f formulas as the point below which systems are safe.