Multi-disjoint syndrome decoding
Several sparse errors sharing one random parity-check matrix, with disjoint supports
Motivation
Shuffling is enough for secure addition: if many clients each split their input into additive shares and all the shares arrive at a server in a uniformly random order, the server learns the sum and — with enough shares — essentially nothing else. That observation, due to Ishai, Kushilevitz, Ostrovsky and Sahai, is the basis of secure aggregation and of private information retrieval in the shuffle model. Its cost is the number of shares each client must send, and the information-theoretic analyses of the paradigm are pessimistic about it.
Replacing the information-theoretic analysis by a computational one cuts that number sharply, and the computational problem it lands on is new: several sparse error vectors share one uniformly random parity-check matrix, and their supports are forced to be pairwise disjoint, because that is what one client’s shuffled shares look like. This hub is about that problem — multi-disjoint syndrome decoding — and specifically about the evidence for its hardness that is missing.
Provenance and history
The problem is introduced by Gascón, Ishai, Kelkar, Li, Ma and Raykova, Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model (IACR ePrint 2024/870), as Definitions 7 and 8, together with a binary-error variant. The paper gives two kinds of evidence for hardness. First, a reduction from standard decisional syndrome decoding (dual LPN), which it says is not tight and does not correspond to an efficient distinguisher. Second, a conjecture that Sendrier’s DOOM algorithm — information-set decoding extended to exploit multiple syndromes — is the best attack; its concrete parameters are set from that conjecture.
Missing is the check the community applies to any new LPN-style assumption: the linear test framework of Boyle, Couteau, Gilboa, Ishai, Kohl and Scholl, under which one bounds the bias of every fixed linear functional of the samples. For standard LPN and regular LPN that bound follows from the dual distance of the underlying code, and it rules out the whole class of attacks that only take linear combinations. The source names this route and reports, in Section 3.3.1, that it does not know how to carry it out.
Parameter lattice
One axis: how the error vectors are structured. The other: what evidence exists.
| Reduction from SD | Best-attack conjecture | Linear-test bias | |
|---|---|---|---|
| Standard LPN / SD | — | ISD is the benchmark | bounded, via dual distance |
| Regular LPN | known | ISD, no speedup from regularity | bounded |
| MDSD (this hub) | non-tight, in the source | DOOM conjectured optimal | c/0067 — open |
| beMDSD over a large field | non-tight, in the source | DOOM conjectured optimal | unstated: the source does not separate it, and the error alphabet changes which linear combinations cancel |