Paper 2026/295
From OT to OLE with Almost-Linear Communication
Abstract
Following the recent work of (Doerner et al., CCS 2025), we introduce an improved reduction of OLE to OT. We prove the following: there is a perfectly-secure OLE-to-OT reduction over any $n$-bit field $\mathbb{F}$ using almost-linear communication $n\cdot 2^{O(\log^{*} n)}$ and almost-constant rounds $O((\log^{*} n)^2)$. In the course of proving our result, we also introduce new perfectly-secure protocols for computing shares of the equality and greater-than predicate on $n$-bit strings in the OT-hybrid model using $O(n)$ communication and $\log^{*} n$ rounds. These results are of independent interest.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- oblivious linear evaluationoblivious transfersecure multiparty computation
- Contact author(s)
-
couteau @ irif fr
naman kumar @ irif fr - History
- 2026-02-18: approved
- 2026-02-17: received
- See all versions
- Short URL
- https://ia.cr/2026/295
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/295,
author = {Geoffroy Couteau and Naman Kumar},
title = {From {OT} to {OLE} with Almost-Linear Communication},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/295},
year = {2026},
url = {https://eprint.iacr.org/2026/295}
}
