Welcome to the resource topic for 2025/1722
Title:
From OT to OLE with Subquadratic Communication
Authors: Jack Doerner, Iftach Haitner, Yuval Ishai, Nikolaos Makriyannis
Abstract:Oblivious Linear Evaluation (OLE) is an algebraic generalization of oblivious transfer (OT) that forms a critical part of a growing number of applications. An OLE protocol over a modulus q enables the receiver party to securely evaluate a line a\cdot X+b chosen by the sender party on a secret point x\in\mathbb{Z}_q.
Motivated by the big efficiency gap between OLE and OT and by fast OT extension techniques, we revisit the question of reducing OLE to OT, aiming to improve the communication cost of known reductions.
We start by observing that the Chinese Remainder Theorem (CRT) can be combined with a prior protocol of Gilboa (Crypto ’99) to reduce its communication cost from O(\ell^2) to \tilde O(\ell) bits, for \ell=\log q. Unfortunately, whereas Gilboa’s protocol is secure against a semi-honest sender and a malicious receiver, a direct application of the CRT technique is only semi-honest secure (it is insecure against malicious receivers). Thus, we employ number-theoretic techniques to protect our CRT-based protocol against malicious receivers, while still retaining a concrete advantage over Gilboa’s protocol (e.g., 10.2\times less communication for \ell=256). Furthermore, we obtain a fully malicious OLE-to-OT reduction by applying either information-theoretic techniques with moderate overhead, or RSA-based cryptographic techniques with very low overhead.
We demonstrate the usefulness of our results in the context of OLE applications, including a post-quantum oblivious pseudorandom function (OPRF) and distributed signatures. In particular, assuming pre-existing random OT correlations, we can use our malicious-receiver OLE protocol to realize (a single instance of) the power-residue based OPRF candidate with security against a malicious client and a semi-honest server using only 1.14 KB of communication, a 16\times improvement over the best previous protocol in this setting. Using our RSA-based fully malicious OLE protocol, we achieve a 5\times communication improvement over previous OT and EC-based distributed ECDSA protocols. Compared to other ECDSA protocols (including ones that use Paillier and class groups), the communication gains are more modest, but come at only a fraction of the computational cost as we avoid all expensive group operations.
ePrint: https://eprint.iacr.org/2025/1722
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .