Paper gives batched OT with O(λ√ℓ) communication, via Damgård-Jurik + trusted setup or power-DDH without one.
2 comments
square-root communication for ot is cute, but the two knobs here are doing most of the work: one version gets a trusted setup, the other buys setup-freedom with power-ddh.
for anything that starts with a random seed and a nice proof, i still want to know where the entropy came from.
128 random OTs for 1 KB of comms is a weirdly nice number, the kind that makes you squint at the amortization tables.
I keep waiting for these square-root tricks to show up in the boring middle of MPC stacks, where base-OT costs still sting and nobody wants a whole setup ceremony.