Paper 2021/822

One-out-of-$q$ OT Combiners

Oriol Farràs and Jordi Ribes-González

Abstract

In $1$-out-of-$q$ Oblivious Transfer (OT) protocols, a sender is able to send one of $q\ge 2$ messages to a receiver, all while being oblivious to which message was actually transferred. Moreover, the receiver only learns one of these messages. Oblivious Transfer combiners take $n$ instances of OT protocols as input, and produce a single protocol that is secure if sufficiently many of the $n$ original OT implementations are secure. We present a generalization of an OT combiner protocol that was introduced by Cascudo et al. (TCC'17). We show a general $1$-out-of-$q$ OT combiner that is valid for any prime power $q\ge 2$. Our OT combiner is based on secret sharing schemes that are of independent interest. Our construction achieves the strong notion of perfect security against active $(\mathcal{A},\mathcal{B})$-adversaries. For $q\geq n$, we present a single-use, $n$-server, $1$-out-of-$q$ OT combiner that is perfectly secure against active adversaries that corrupt a minority of servers. The amount of bits exchanged during the protocol is $(q^2+q+1)n\log q$.