Iftach Haitner, Stellar Development Foundation, Tel-Aviv University
Gil Segev, Hebrew University of Jerusalem, Coinbase
Abstract
The Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman () problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the problem, their security analysis yields that an attacker running in time and issuing random-oracle queries breaks the security of their protocol with probability at most , where is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for , it does not provide any guarantee already for and ).
In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman () problem and present a tight reduction from the security of the protocol to the hardness of solving . That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the problem. Second, we reduce the hardness of the problem to that of the decisional Diffie-Hellman () problem without incurring a multiplicative loss. Our key observation is that although and have the same assumed concrete hardness, relying on the hardness of enables our reduction to efficiently test the correctness of the solutions it produces.
Concretely, in groups in which no better-than-generic algorithms are known for the problem, our analysis yields that an attacker running in time and issuing random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most (i.e., we eliminate the above multiplicative term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution.
@misc{cryptoeprint:2025/493,
author = {Iftach Haitner and Gil Segev},
title = {Tighter Concrete Security for the Simplest {OT}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/493},
year = {2025},
url = {https://eprint.iacr.org/2025/493}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.