Paper 2017/1011

Efficient and Universally Composable Protocols for Oblivious Transfer from the CDH Assumption

Eduard Hauck and Julian Loss

Abstract

Oblivious Transfer (OT) is a simple, yet fundamental primitive which suffices to achieve almost every cryptographic application. In a recent work (Latincrypt `15), Chou and Orlandi (CO) present the most efficient, fully UC-secure OT protocol to date and argue its security under the CDH assumption. Unfortunately, a subsequent work by Genc et al. (Eprint `17) exposes a flaw in their proof which renders the CO protocol insecure. In this work, we make the following contributions: We first point out two additional, previously undiscovered flaws in the CO protocol and then show how to patch the proof with respect to static and malicious corruptions in the UC model under the stronger Gap Diffie-Hellman (GDH) assumption. With the proof failing for adaptive corruptions even under the GDH assumption, we then present a novel OT protocol which builds on ideas from the CO protocol and can be proven fully UC-secure under the CDH assumption. Interestingly, our new protocol is actually significantly more efficient (roughly by a factor of two) than the CO protocol. This improvement is made possible by avoiding costly redundancy in the symmetric encryption scheme used in the CO protocol. Our ideas can also be applied to the original CO protocol, which yields a similar gain in efficiency.