Paper 2026/295 Original: eprint.iacr.org/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.
- History
- 2026-02-17: last updated
- 2026-02-17: published
- Short URL
- https://ia.cr/2026/295
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}