Tighter Concrete Security for the Simplest OT

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 (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> and issuing <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> </mml:math> random-oracle queries breaks the security of their protocol with probability at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>≤</mml:mo> <mml:msup> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>·</mml:mi> <mml:mi>t</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> </mml:mrow> </mml:math> is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>256</mml:mn> </mml:mrow> </mml:math>, it does not provide any guarantee already for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>48</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>40</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math>). 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 the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH 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 DDH problem, our analysis yields that an attacker running in time <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> and issuing <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>t</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> (i.e., we eliminate the above multiplicative <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:math> 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.