Distance from lines under reduction modulo a random prime
A number-theoretic question that decides whether an OLE protocol needs integer commitments
Motivation
Reducing modulo a random prime is one of the oldest tricks for making a large computation small, and its usual guarantee runs one way: a nonzero integer stays nonzero modulo most primes. The question here is the robust, approximate version of that guarantee. Suppose a function on a large integer domain is far — in relative Hamming distance over a chosen set of points — from every line \(x \mapsto ax+b\). Does it stay far after reduction modulo a random prime, or can the collisions the reduction creates make it look close to some line mod \(p\)?
The answer matters wherever a protocol proves something about integers but reveals only residues. If reduction can make a cheating party’s behaviour look linear when it is not, the residues carry less information than the integer statement did, and the protocol needs extra machinery — typically integer commitments — to pin the party down.
Provenance and history
The question is raised by Doerner, Haitner, Ishai and Makriyannis, From OT to OLE with Subquadratic Communication (IACR ePrint 2025/1722), which reduces oblivious linear evaluation to oblivious transfer by combining the Chinese remainder theorem with Gilboa’s protocol, cutting communication from \(O(\ell^2)\) to \(\widetilde O(\ell)\). Protecting the CRT-based construction against a malicious sender costs a commit-and-prove functionality that the paper calls “rather costly or requires additional hardness assumptions”.
Its Section 5.3.5 removes that functionality, and the entire resulting security loss is one quantity: the worst-case gap between how far a randomized function is from every integer line and how far it is from a line modulo a uniform \(\kappa\)-bit prime. The paper conjectures the gap is exponentially small in \(\kappa\), describes the conjecture as “natural but apparently new”, and says its study “may be of independent interest”. No partial result is offered; the paper observes only that the deterministic case might be easier and would still yield a usable protocol.
One editorial note lives with the statement rather than the hub: the paper’s Definition 5.36 prints the difference in the order that makes the quantity non-positive, and hence the conjecture vacuous. The direction the rest of the paper needs is recorded on the statement page.
Parameter lattice
Two axes: which functions the worst case ranges over, and how large the domain may be relative to the modulus.
| Domain \(n \le \mathrm{poly}(\kappa)\) | Domain \(n \le 2^{c_n\kappa}\) | |
|---|---|---|
| Deterministic \(f\) | unstated: not separated by the source | the source says this variant “might be easier to prove” and still yields a protocol (Remark 5.40) — open |
| Randomized \(f\) | unstated | c/0074 — the full conjecture, open |
The application needs the full randomized version at \(c_\delta = 1/2\) and \(c_n = \log n/\kappa_s \le 4\log q + 25\kappa_s\); a proof with worse constants settles the conjecture but not automatically the protocol.