Paper 2026/1541

Batched Oblivious Transfer with Square-Root Communication

Abstract

Oblivious Transfer (OT) is a fundamental cryptographic primitive and a core building block for many multiparty cryptographic protocols. While existing OT extension techniques achieve excellent asymptotic efficiency for very large batches, their performance degrades when the total number of OTs is only moderate, since the cost of generating the required base OTs is no longer effectively amortized. In this work, we close this gap by presenting OT constructions that achieve square-root communication complexity for batched OT generation. Concretely, our protocols generate $\ell$ random OTs using $O(\lambda\sqrt{\ell})$ communication. Our constructions are inspired by recent advances in homomorphic secret sharing and techniques for distributed discrete logarithm computation, and explore complementary points in the design space. The first construction is based on the Damg{\aa}rd--Jurik cryptosystem and standard assumptions, at the cost of a one-time trusted setup. The second eliminates the need for any setup, relying instead on a power-DDH assumption over prime-order groups. For typical parameters with $\lambda=128$, our schemes require approximately $2.5$ KB and $1$ KB of communication, respectively, to generate $128$ random OTs, and outperform existing OT extension techniques for batch sizes up to $\ell \leq 2^{15}$.