StOMR: Stateful Oblivious Message Retrieval

What it is

StOMR introduces a new key-encapsulation primitive, OMR-KEM, which lets a sender and receiver privately establish shared state without an out-of-band channel — this is the mechanism that makes the "stateful" model work at all, and it's not mentioned in the existing summary.

How it works

Classic OMR constructions (PerfOMR, SophOMR, InstantOMR) are purely public-key: a detector uses FHE to scan a bulletin board and produce a compact encrypted digest, but each sender must publish a large per-message signal for the detector to process. StOMR instead has sender and receiver maintain lightweight private state. OMR-KEM is the component that bootstraps that shared state cryptographically — replacing what would otherwise require a separate secure channel between the two parties before messaging can begin.

Preconditions / Affected

Applies to systems building anonymous messaging or blockchain privacy on OMR — i.e., designs where a recipient must scan a public/untrusted bulletin board without revealing which posts are theirs. Benefits depend on sender and receiver being able to run the OMR-KEM setup once to share private state; it does not help in settings where senders are one-off/anonymous with no prior relationship to the receiver and no feasible key-establishment step.

What to do

Compared against PerfOMR (USENIX Security '24), SophOMR (USENIX Security '26), and InstantOMR (USENIX Security '26), StOMR cuts sender signal size by ~550x, ~650x, and ~178x respectively while matching detector performance — these numbers are already in the catalog summary, but the reason they're achievable is the OMR-KEM state-sharing step, which is the actual design change to evaluate if considering adoption. Implementation is in C++; DOI 10.1145/3830454.3846701.

Caveats

The paper gives no benchmark for the OMR-KEM setup cost itself (computation/communication to establish the shared state) — only the resulting sender-signal reduction. No discussion of behavior if private state is lost or desynchronized between sender and receiver.