Actively Secure OT Extension with Optimal Overhead

Abstract

We describe an actively secure OT extension protocol in the random oracle model with efficiency very close to the passively secure IKNP protocol of Ishai et al. (Crypto 2003). For computational security parameter $\kappa$, our protocol requires $\kappa$ base OTs, and is the first practical, actively secure protocol to match the cost of the passive IKNP extension in this regard. The added communication cost is only additive in $O(\kappa )$, independent of the number of OTs being created, while the computation cost is essentially two finite field operations per extended OT. We present implementation results that show our protocol takes no more than 5 % more time than the passively secure IKNP extension, in both LAN and WAN environments, and thus is essentially optimal with respect to the passive protocol.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Oblivious transfer (OT) is a fundamental primitive in cryptography, used in the construction of a range of protocols. In particular, OT is sufficient and necessary for secure multi-party computation [10, 15, 25], and is also often used in special-purpose protocols for tasks such as private set intersection [22]. Due to a result of Impagliazzo and Rudich [11] it is very unlikely that OT is possible without the use of public-key cryptography, so all OT constructions have quite a high cost when used in a practical context.

OT Extension. Since OT requires public key machinery, it is natural to wonder whether OT can be efficiently ‘extended’. That is, starting with a small number of ‘base OTs’, create many more OTs with only symmetric primitives, somewhat analogous to the use of hybrid encryption to extend public key encryption. Beaver [3] first showed how, starting with $\kappa$ base OTs, one could create $\mathsf {poly}(\kappa )$ additional OTs using only symmetric primitives, with computational security $\kappa$. Beaver’s protocol is very elegant, but requires evaluation of pseudo-random generators within Yao’s garbled circuits; therefore it is highly impractical. In 2003, Ishai, Kilian, Nissim and Petrank [12] presented a very efficient protocol for extending OTs, requiring only black-box use of symmetric primitives and $\kappa$ base OTs. Concretely, the main cost of their basic protocol is computing and sending just two hash function values per OT. Asharov et al. [1] gave several algorithmic optimizations to the IKNP protocol, reducing the communication down to one hash value for the random OT variant, where the sender’s messages are sampled at random, and using a cache-oblivious algorithm for matrix transposition, which turned out to be the computational bottleneck when implemented naively. By analysing an implementation, they suggest that the actual bottleneck of the IKNP protocol is communication, particularly in wide area networks (WANs) with high latency and low bandwidth.

The above protocols are only secure against passive adversaries, who are trusted to strictly follow the protocol. For the case of actively secure protocols, which remain secure against arbitrary deviations from the protocol, typically most cryptographic protocols have a much greater cost than their passive counterparts. The actively secure OT extension of Ishai et al. [12] uses an expensive cut-and-choose technique, where s runs of the protocol are done in parallel to achieve O(s) bits of statistical security. In recent years, the cost of actively secure OT extension has improved greatly, down to just constant overhead. The TinyOT protocol for secure two-party computation [20] is based on a very efficient OT extension where the total cost is roughly $\frac{8}{3}$ times the passively secure IKNP extension – this applies to communication and computation, as well as the number of base OTs required to run the protocol. Very recently, in an independent and concurrent work, Asharov et al. [2] gave a protocol reducing the overhead even further: their protocol requires roughly $\kappa + s$ base OTs for computational security $\kappa$ and statistical security s, which in practice reduces the constant from $\frac{8}{3}\approx 2.7$ down to $\approx 1.4$, plus an additive overhead in $O(\kappa )$.

Applications of OT Extension. As we mentioned before, OT extension has been getting a lot of attention recently, because the efficiency of this procedure plays a decisive role in the overall efficiency of a number of protocols for secure computations where the number of OTs needed is very large, for example in the two-party and multiparty TinyOT protocols [5, 18, 20], in the MiniMAC protocol of Damgard et al. [7] and in private set intersection protocols [8, 22].

Our Contributions. In this paper we give the first practical, actively secure OT extension protocol requiring only $\kappa$ base OTs, matching the efficiency of the passively secure IKNP extension in this respect. For communication and computation costs, the overhead on top of IKNP is negligible: our protocol requires 2 finite field (of size $\kappa$) operations per extended OT, plus a small communication overhead of $O(\kappa )$ bits in a constant number of rounds, independent of the number of OTs being performed, which amortizes away when creating many OTs. We give extensive benchmarks (in both LAN and WAN settings) showing that the practical cost of our protocol for performing 10 million OTs is less than 6 % more than the IKNP extension, and so is almost optimal. In contrast, the protocol of Asharov et al. [2] takes at least 80 % more time than the passive protocol in the WAN setting and over 20 % more in the LAN setting for $2^{23}$ OTs, according to their implementation figures.

The comparison table below shows the concrete efficiency of various other OT extension protocols, in terms of the number of base OTs required and the total communication and computation cost for creating $\ell$ OTs. Our protocol is more efficient than all previous protocols in all of these measures. Note that these comparisons are for OT extensions on strings of length at least $\kappa$ bits. For shorter strings, the passively secure protocol of Kolesnikov and Kumaresan [16] is more efficient, but it does not seem straightforward to apply our techniques to obtain an actively secure protocol in that setting. We also omit the protocol of Ishai et al. [13], since although asymptotically this has only a constant overhead, the protocol is based on the ‘MPC-in-the-head’ technique, which has not been shown to be practical.

Table 1. Concrete cost of OT extension protocols for producing $\ell$ OTs of 128-bit strings with 128-bit computational and 40-bit statistical security parameters.

Our protocol is similar in structure to previous protocols [2, 20], in that we carry out one run of the passively secure IKNP extension, and then use a correlation check to enforce correct behaviour. As in the previous protocols, it is possible that a cheating receiver may pass our check, in which case some information on the sender’s secret is leaked. However, the leakage is such that we still only need $\kappa$ base OTs, and then must sacrifice $\kappa + s$ of the extended OTs produced from the IKNP extension, where s is a statistical security parameter, to ensure security. The check itself is extremely simple and only requires a constant number of hash computations on a fixed input length, unlike previous checks where the amount of data being hashed increases with the number of extended OTs (Table 1).

Random Oracle Usage. We prove our OT extension protocol secure in the random oracle model, used for a functionality $\mathcal {F}_{\mathsf {Rand}}$, which securely generates random values, and the hash function H used to randomize the correlated OT outputs. For the function H, Ishai et al. [12] prove security of their protocol in the standard model, under the assumption that H is a correlation robust function. The protocol of Asharov et al. [2] is proven secure with the additional requirement that H satisfies some kind of leakage resilience, and it is conjectured that the protocol of Nielsen et al. [20] is also secure in this model.

Note that in the case of random OT, where the sender’s outputs are defined as randomly chosen by the functionality, the security of the protocol (using the optimization of Asharov et al. [1], which cuts the communication in half) has only ever been proven in the random oracle model, because of the need for the simulator to program the receiver’s outputs from H to be as defined by the functionality. Random OT can be used for an offline/online scenario where random OTs are generated in advance of the inputs being known, and is also often used in practical protocols (e.g. [20, 22]), so we take the pragmatic approach of using random oracles for our security proofs, which also simplifies the exposition. However, due to the similarities between our protocol and previous ones [2, 20], we believe it is likely that our (non-random) OT extension protocol can also be proven secure under a form of correlation robustness for H.

2 Preliminaries

2.1 Notation

We denote by $\kappa$ the computational security parameter and by s the statistical security parameter. We let ${\mathsf {negl}}({\kappa })$ denote some unspecified function $f(\kappa )$, such that $f=o(\kappa ^{-c})$ for every fixed constant c, saying that such a function is negligible in $\kappa$. We say that a probability is overwhelming in $\kappa$ if it is $1- {\mathsf {negl}}({\kappa })$. We denote by $a \mathop {\leftarrow }\limits ^{\small {\$}}A$ the random sampling of a from a distribution A, and by [d] the set of elements $\{1, \dots d\}$.

Throughout the proofs we will often identify $\mathbb {F}_2^\kappa$ with the finite field $\mathbb {F}_{2^\kappa }$. Addition is the same in both; we will use $``\cdot "$ for multiplication in $\mathbb {F}_{2^\kappa }$ and $``*"$ for the componentwise product in $\mathbb {F}_2^\kappa$. We use lower case letters to denote elements in $\mathbb {F}_2$ and bold lower case letters for vectors in $\mathbb {F}_2^\kappa$ and elements in $\mathbb {F}_{2^\kappa }$. We will use the notation $\mathbf {v}[i]$ to denote the i-th entry of $\mathbf {v}$.

Given a matrix A, we denote its rows by subindices $\mathbf {a}_i$ and its columns by superindices $\mathbf {a}^{k}$. Given a vector $\mathbf {v}\in \mathbb {F}_2^\kappa$, we denote by $\bar{\mathbf {v}}$ the vector in $\mathbb {F}_2^\kappa$ such that $\mathbf {v}+ \bar{\mathbf {v}}=\mathbf {1}$. We say that a vector $\mathbf {v}\in \mathbb {F}_2^\kappa$ is monochrome if $v[i]=v[j]$, for each $i,j \in [\kappa ]$; otherwise we say it is polychrome.

In our proofs we often use the notion of affine space. We recall that an affine space is a set X that admits a free transitive action of a vector space V.

2.2 Oblivious Transfer and OT Extension

Oblivious transfer (OT) [4, 9, 23, 24] is a two-party protocol between a sender S and a receiver R. The sender transmits part of its input to R, in such a way that S remains oblivious as what part of its input was transmitted and R does not obtain more information than it is entitled.

We use three main oblivious transfer functionalities. We denote by $\mathcal {F}_{\mathsf {OT}}$ the standard $\left( {\begin{array}{c}2\\ 1\end{array}}\right)$-OT functionality, where the sender S inputs two messages $\mathbf {v}_0, \mathbf {v}_1 \in \mathbb {F}_2^\kappa$, and the receiver inputs a choice bit x, and at the end of the protocol R learns only the selected message $\mathbf {v}_x$. We use the notation $\mathcal {F}_{\mathsf {OT}}^{\kappa ,\ell }$ to denote the functionality that provides $\ell$ $\left( {\begin{array}{c}2\\ 1\end{array}}\right)$-OTs of messages in $\mathbb {F}_2^\kappa$ (see Fig. 1 for a formal definition). Another variant of OT is correlated OT, where the sender’s messages are correlated, i.e. $\mathbf {v}_0+ \mathbf {v}_1 = \varDelta$ for a fixed $\varDelta \in \mathbb {F}_2^\kappa$; in Fig. 3 we give a version of this functionality which allows “errors”. Finally, in the random OT functionality, $\mathcal {F}_{\mathsf {ROT}}$, the messages $\mathbf {v}_0, \mathbf {v}_1$ are sampled uniformly at random by the functionality (Fig. 7).

Fig. 1.

The OT functionality

Fig. 2.

Correlated OT with errors functionality $\mathcal {F}_{\mathsf {COTe}}$

IKNP Protocol Augmented with Errors. In Fig. 2, we model the IKNP extension as a separate functionality, $\mathcal {F}_{\mathsf {COTe}}$ that incorporates a cheating receiver’s behavior, and call this correlated OT with errors. Figure 3 gives the implementation of this functionality: after the first phase and the local expansion of the seeds through a pseudorandom generator $\mathsf {PRG}$, R holds two $\ell \times \kappa$ matrices $\{\mathbf {t}_0^i\}_{i \in [\kappa ]}, \{\mathbf {t}_1^i\}_{i \in [\kappa ]}$, while S holds the vector $\varDelta \in \mathbb {F}_2^\kappa$ and the matrix $\{\mathbf {t}_{\varDelta _i}^i\}_{i \in [\kappa ]}$. In the extension phase, we allow a cheating receiver R to input vectors $\mathbf {x}_1, \dots , \mathbf {x}_\ell \in \mathbb {F}_2^\kappa$, instead of inputting bits $x_1, \dots , x_\ell$. To better understand this situation we can imagine R inputting an $\ell \times \kappa$ matrix X, having $\mathbf {x}_1, \dots , \mathbf {x}_\ell \in \mathbb {F}_2^\kappa$ as rows and $\mathbf {x}^1, \dots , \mathbf {x}^\kappa \in \mathbb {F}_2^\ell$ as columns. If R is honest then $\mathbf {x}^1= \cdots = \mathbf {x}^\kappa$ and the rows $\mathbf {x}_j$ are “monochrome” vectors, i.e. consisting either of all 0’s or all 1’s. At this point the receiver computes $\mathbf {u}^i = \mathbf {t}_0^i +\mathbf {t}_1^i + \mathbf {x}^i$, for each $i \in [\kappa ]$. Clearly, if R is honest, they send the same vector $\mathbf {x}^i$ for each i. After this step S computes $\mathbf {q}^i=\mathbf {t}_{\varDelta _i}^i + \mathbf {u}^i + \mathbf {u}^i \cdot \varDelta _i = \mathbf {t}_0^i + \mathbf {x}^i\cdot \varDelta _i$, obtaining the $\ell \times \kappa$ matrix Q, having $\mathbf {q}^i$ as columns and $\mathbf {q}_j= \mathbf {t}_{0,j} + \mathbf {x}_j * \varDelta$ as rows. If $\mathbf {x}_j$ is monochrome, i.e. $\mathbf {x}_j= x_j \cdot (1, \dots , 1)$, then $\mathbf {q}_j=\mathbf {t}_{0,j} +x_j \cdot \varDelta$, otherwise, rewriting $\mathbf {x}_j$ as $\mathbf {x}_j= x_j \cdot (1, \dots , 1) + \mathbf {e}_j$, we get $\mathbf {q}_j= \mathbf {t}_{0,j} + x_j \cdot \varDelta + \mathbf {e}_j * \varDelta$, where $\mathbf {e}_j$ is an “error” vector counting the number of positions in which R cheated.

Notice that, compared with the original IKNP protocol, the protocol ${\mathsf {COTe}}$ stops before hashing the output with the random oracle to break the correlation and performing the final round of communication. It is easy to see (and was shown e.g. by Nielsen [19]) that the protocol for ${\mathsf {COTe}}$ (given in Fig. 3) securely implements this functionality.

Fig. 3.

Protocol for correlated OT with errors between S and R.

3 Our Actively Secure OT Extension Protocol

In this section we describe our protocol for actively secure OT extension based on the passive IKNP functionality, $\mathcal {F}_{\mathsf {COTe}}$. We recall that to deal with malicious adversaries, all the known actively secure OT extension protocols add a consistency check to the passive secure IKNP protocol to ensure that R inputs consistent values.

For example, in previous works [2, 20] this check is added before the “extension” phase, i.e. before the sender S “reverses” the base OTs and breaks the correlation, effectively checking on the OT seeds. In our construction we check the correlation for consistency after the extension step, precisely after the execution of ${\mathsf {COTe}}$, actually checking the extended OTs.

Fig. 4.

Relationship between the different functionalities used to go from $\mathcal {F}_{\mathsf {OT}}^{\kappa ,\kappa }$ to $\mathcal {F}_{\mathsf {OT}}^{\kappa ,\ell }$.

Fig. 5.

Functionality $\mathcal {F}_{\mathsf {Rand}}^\mathbb {F}$

Fig. 6.

Functionality $\mathcal {F}^{\kappa , \ell }_{\mathsf {ROT}}$

The high level idea of our protocol in Fig. 7 is to perform a simple correlation check to ensure that the receiver used the same vector $\mathbf {x}^i$ for each $\mathbf {u}^i$ sent in Step 3 of the IKNP extension. If the check passes, then the correlated OTs are hashed to obtain random OTs. This check requires sacrificing $\kappa +s$ extended OTs to ensure security, so we obtain a reduction from $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$ to $\mathcal {F}_{\mathsf {COTe}}^{\kappa ,\ell '}$, with $\ell '=\ell +(\kappa +s)$.

The intuition in this reduction is that, if the check passes, the adversary can only learn few bits of the correlation vector $\varDelta$, and hence the values $H(\mathbf {q}_j + \varDelta )$ are actually random except with negligible probability. Finally, if required, the random OTs obtained from ${\mathsf {ROT}}$ can be derandomized with an additional set of messages from the sender, using the standard reduction from $\mathcal {F}_{\mathsf {OT}}^{\kappa , \ell }$ to $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$.

The relationship between all the functionalities used are described in Fig. 4. The first stage to $\mathcal {F}_{\mathsf {COTe}}$ essentially consists of the IKNP OT extension protocol (with some modifications from the protocol by Asharov et al. [1]) that we have seen in the previous section.

3.1 Protocol from ${\mathsf {COTe}}$ to ${\mathsf {ROT}}$

Here we describe the protocol implementing the $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$ functionality in Fig. 6. The main idea of our construction is to use a variant of the MAC check protocol from SPDZ [6], adapted for two parties where one party holds the MAC key, to check the correlation is consistent. The correlation check is performed on the $\ell '$ correlated OTs of length $\kappa$ output by $\mathcal {F}_{\mathsf {COTe}}^{\kappa ,\ell '}$, i.e. after the vectors have been transposed. Recall that after running $\mathcal {F}_{\mathsf {COTe}}$, the sender S has $\varDelta , \mathbf {q}_1, \dots , \mathbf {q}_{\ell '} \in \mathbb {F}_2^\kappa$ and the receiver R has $\mathbf {x}_1, \dots , \mathbf {x}_{\ell '}, \mathbf {t}_1,\dots , \mathbf {t}_{\ell '} \in \mathbb {F}_2^\kappa$ such that $\mathbf {q}_j = \mathbf {t}_j + \mathbf {x}_j * \varDelta$ for $j \in [\ell ']$. If R was honest then every $\mathbf {x}_j$ is monochrome, so $\mathbf {q}_j = \mathbf {t}_j + x_j \cdot \varDelta$ for bits $x_1, \dots , x_{\ell '}$.

To carry out the check, both parties first securely generate $\ell '$ random weights $\chi _1,\dots ,\chi _{\ell '} \in \mathbb {F}_2^\kappa$ (using Fig. 5), and then compute weighted sums of their outputs from $\mathcal {F}_{\mathsf {COTe}}$. Then R sends these values to S to check consistency with S’s output. So, R computes $x = \sum _{j=1}^{\ell '} x_j \cdot \chi _j, t = \sum _{j=1}^{\ell '} \mathbf {t}_j \cdot \chi _j$ and S computes $q = \sum _{j=1}^{\ell '} \mathbf {q}_j \cdot \chi _j$, where the vectors $\mathbf {t}_j,\mathbf {q}_j,\chi _j$ are viewed as elements of $\mathbb {F}_{2^\kappa }$ and multiplications are performed in this finite field. S then checks that $q = t + x \cdot \varDelta$.

Clearly, by linearity of the correlated OT output, the check will always pass for an honest receiver. If R is corrupted then it is possible they may pass the check despite having used polychromatic $\mathbf {x}_j$ vectors; in this case they will learn some information about $\varDelta$. We show that this leakage is optimal, in the sense that a cheating receiver can learn c bits of information on $\varDelta$ with at most probability $2^{-c}$, and the possible errors in the resulting OTs do not provide the adversary with any further useful information. Looking ahead to the proof, the success probability of a receiver who passes the check in breaking the resulting OTs with $q = \mathsf {poly}(\kappa )$ queries to H will therefore be $q/2^{\kappa -c}$, giving an overall success probability of $q/2^{\kappa }$. This implies that $\kappa$ base OTs suffice for computational security $\kappa$.

On the other hand, if the sender is corrupted, our correlation check introduces the possibility that the values of x and t could leak information about R’s input bits $x_1, \dots , x_\ell$. However, we show that it suffices to perform $\kappa +s$ additional OTs with random choice bits to counter against this leakage, for statistical security s. Overall, this means our protocol requires only $\kappa$ base OTs, which is optimal with respect to the IKNP extension, and an additive overhead of $s+\kappa$ extended OTs, regardless of the number $\ell$ of OTs required, as well as just $O(\kappa )$ additional communication in a constant number of rounds.

3.2 Analysis of the Correlation Check

Corrupt Sender. To ensure that the correlation check step is secure against a corrupt sender we must carefully choose the parameter $\ell '$, which determines the size of the batch each check is performed on. Recall that the elements in the field $\mathbb {F}$ are $\kappa$ bits long; if $\ell ' \le \kappa$ then it is likely that the secret bits $x_j$ will be uniquely determined given $\chi _j$ and x, so an adversary could attempt to solve the corresponding knapsack problem to recover these. As we will see in the proof in Theorem 1, to thwart this attack, we use a technical lemma giving a bound on the rank of a random binary matrix. This is also the reason why we do not let the sender sample $\{\chi _j\}_{j=1}^\ell$.

Corrupt Receiver. The case of a corrupt receiver is much more involved. We now investigate a cheating receiver’s success probability in the correlation check stage of the ${\mathsf {ROT}}$ protocol in Fig. 7. Let $\mathbf {x}_1, \dots , \mathbf {x}_{\ell '}$ be the vectors in $\mathbb {F}_2^\kappa$ input by R during the protocol. Taking these to be the rows of a $\ell ' \times \kappa$ matrix, let $\mathbf {x}^1, \dots , \mathbf {x}^\kappa$ be the columns of the same matrix, in $\mathbb {F}_2^{\ell '}$. If R was honest then $\{\mathbf {x}_j\}_{j \in [\ell ']}$ are all monochrome and $\{\mathbf {x}^i\}_{i \in [\kappa ]}$ are all equal. The following Lemma gives the main properties needed from our correlation check.

Fig. 7.

Random OT extension protocol from correlated OT with errors.

Lemma 1

Let $S_{\varDelta }\subseteq \mathbb {F}_2^\kappa$ be the set of all $\varDelta$ for which the correlation check passes, given the view of the receiver. Except with probability $2^{-\kappa }$, there exists $k \in \mathbb {N}$ such that

• 1. $|S_{\varDelta } | = 2^k$.

• 2. For every $\mathbf {s}\in \{\mathbf {x}^{i}\}_{i \in [\kappa ]}$, let $H_\mathbf {s}= \{i \in [\kappa ] \mid \mathbf {s}= \mathbf {x}^{i}\}$. Then one of the following holds:

  • For all $i \in H_\mathbf {s}$ and any $\varDelta ^{(1)}, \varDelta ^{(2)} \in S_{\varDelta }$, $\varDelta ^{(1)}_i = \varDelta ^{(2)}_i$.

  • $k \le |H_\mathbf {s}|$, and $|\{\varDelta _{H_\mathbf {s}}\}_{\varDelta \in S_{\varDelta }}| = 2^k$, where $\varDelta _{H_\mathbf {s}}$ denotes the vector consisting of the bits $\{\varDelta _i\}_{i \in H_\mathbf {s}}$. In other words, $S_{\varDelta }$ restricted to the bits corresponding to $H_{\mathbf {s}}$ has entropy at least k.

  Furthermore, there exists $\hat{\mathbf {s}}$ such that $k \le |H_{\hat{\mathbf {s}}}|$.

Proof

See full version [14].

We now give some intuition about the meaning of this statement. The set $S_\varDelta$ is the set of all possible values of $\varDelta$ with which the correlation check could pass – note that since $\varDelta$ is uniformly random to the receiver, their probability of passing the check is therefore $|S_{\varDelta } |/2^\kappa$. For some vector $\mathbf {s}\in \{\mathbf {x}^{i}\}_{i \in [\kappa ]}$, the set $H_\mathbf {s}$ represents indices of all of the vectors equal to $\mathbf {s}$. Clearly, for an honest receiver, $H_\mathbf {s}$ is always just the set $\{1, \dots , \kappa \}$, and so the size of $H_\mathbf {s}$ measures the amount of deviation in the protocol for a given $\mathbf {s}$. The precise indices in $H_\mathbf {s}$ are also important, as they correspond to a subset of the bits of the secret $\varDelta$, which could be learnt using $2^{|H_\mathbf {s} |}$ queries to the hash function (causing the simulation to abort in our security proof).

The second part of the lemma implies that for any $\mathbf {s}$, either the bits of $\varDelta$ corresponding to the indices in $H_\mathbf {s}$ are constant for all possible $\varDelta \in S_{\varDelta }$, or, the size of $H_\mathbf {s}$ is at least k, which means the corresponding abort in the simulation occurs with probability at least $1-2^{-k+\kappa }$. Clearly in the first case, the adversary gains no new information, but in the second case we have a bound on the amount of information an adversary can learn, which directly corresponds to the size of the set $S_{\varDelta }$, and hence also the success probability in the correlation check. The final part of the Lemma, concerning ${\hat{\mathbf {s}}}$, simply states that there is always a vector $\mathbf {s}$ that satisfies the second condition, so at least one block of k bits of $\varDelta$ remains hidden. A careful analysis of these possible deviations allows us to show that $\kappa$ base OTs suffice for our protocol.

3.3 Proof of Security

Theorem 1

The protocol in Fig. 7 securely implements the $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$ functionality in the ($\mathcal {F}_{\mathsf {COTe}},\mathcal {F}_{\mathsf {Rand}},\mathcal {F}_{\mathsf {RO}}$)-hybrid model with computational security parameter $\kappa$.

The computational security parameter $\kappa$ manifests itself in that the adversary is only allowed $\mathsf {poly}(\kappa )$ calls of the random oracle in the proof. Other than that, the simulation is statistically indistinguishable.

Proof

We construct a simulator $\mathcal {S}$ that has access to $\mathcal {F}_{\mathsf {ROT}}$, and show that no environment $\mathcal {Z}$ can distinguish between an interaction with $\mathcal {S}$ and $\mathcal {F}_{\mathsf {ROT}}$ and an interaction with the real adversary $\mathcal {A}$ and the real parties. To simulate a real world execution of the protocol, $\mathcal {S}$ starts an internal copy of $\mathcal {A}$ and runs an internal copy of the protocol with dummy parties $\pi _S$ and $\pi _R$, as shown in Fig. 8.

First we deal with the (simpler) case of a corrupt sender. Since the simulator gets the sender’s secret $\varDelta$, it is straightforward to construct x and t that will pass the check. All we need to do is argue indistinguishability from the real world execution. We need the following lemma.

Lemma 2

Let A be a random $(\kappa + m) \times \kappa$ matrix over $\mathbb {F}_2$, where $m > 0$. Then A has rank $\kappa$ except with probability less than $2^{-m}$.

Proof

See full version [14].

Fig. 8.

Simulator for random OT extension

Recall that in the real world the sender receives

$$ x = \sum _{j=1}^{\ell '} x_j \cdot \chi _j = \sum _{j=1}^{\ell } x_j \cdot \chi _j + \sum _{j=\ell +1}^{\ell '} x_j \cdot \chi _j. $$

The second summation corresponds to the image of a linear map from $\mathbb {F}_2^{\ell '-\ell } = \mathbb {F}_2^{\kappa +s}$ to $\mathbb {F}_2^\kappa$. From Lemma 2, it follows that this map has full rank with probability $1-2^{-s}$. In this case, the second summation is uniformly random in $\mathbb {F}_{2^\kappa }$ because $(x_{\ell +1}, \dots , x_{\ell '})$ were chosen uniformly at random by R, and so indistinguishable from the simulated random x. Finally, t has the same distribution in both worlds because there is only one t fulfilling the equation $q = t + x \cdot \varDelta$.

We now consider the case of R being corrupted. In steps 1–4, $\mathcal {S}$ simply emulates $\mathcal {F}_{\mathsf {COTe}}$ and the correlation check, choosing random values for the dummy sender’s input. Lemma 1 states that (except with negligible probability) $|S_{\varDelta } | = 2^k$ for some $k \in \mathbb {N}$. For every $\mathbf {s}\in \{\mathbf {x}^{i}\}_{i \in [\kappa ]}$, let $H_\mathbf {s}= \{i \in [\kappa ] \mid \mathbf {s}= \mathbf {x}^{i}\}$ and ${\hat{\mathbf {s}}}$ as in Lemma 1. Recall that the adversary knows $(\mathbf {t}_j, \mathbf {x}_j)$ such that $\mathbf {t}_j = \mathbf {q}_j + \mathbf {x}_j * \varDelta$. If $x_1, \dots , x_\ell$ are the bits of ${\hat{\mathbf {s}}}$ then this can be expressed as $\mathbf {t}_j = \mathbf {q}_j + x_j\cdot \varDelta + \mathbf {e}_j * \varDelta$, where $\mathbf {e}_j = (x_j,\dots ,x_j) + \mathbf {x}_j$ is an adversarially chosen error vector. By definition, $\mathbf {e}_j[i] = \mathbf {e}_j[i']$ for all $i,i' \in H_\mathbf {s}$, for any $\mathbf {s}\in \{\mathbf {x}^{i}\}_{i \in [\kappa ]}$ and $j \in [\ell ]$.

In step 7, the simulator responds to the adversary’s random oracle queries. Notice that it is the queries $\mathbf {q}_j = \mathbf {t}_j + \mathbf {x}_j*\varDelta$ and $\mathbf {q}_j + \varDelta = \mathbf {t}_j + \overline{\mathbf {x}_j}*\varDelta$ that require the reply conforming to the output of $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$. The simulator knows $\mathbf {v}_{x_j,j}$, which is the output of $H(j \Vert \mathbf {q}_j + x_j \cdot \varDelta )$ in the real-world protocol. On the other hand, if the adversary queries $(j \Vert \mathbf {q}_j + \overline{x_j} \cdot \varDelta )$, the simulator cannot give the right output and thus aborts.

We now investigate the probability that this happens, given that the correlation check has passed. It holds that

$$ \mathbf {q}_j + \overline{x_j} \cdot \varDelta = \mathbf {t}_j + \mathbf {x}_j * \varDelta + \overline{x_j} \cdot \varDelta = \mathbf {t}_j + (\mathbf {x}_j + (\overline{x_j},\dots ,\overline{x_j}) ) * \varDelta . $$

For $i \in H_{\hat{\mathbf {s}}}$, $\mathbf {x}_j[i] = x_j$ and thus $(\mathbf {x}_j + (\overline{x_j},\dots ,\overline{x_j})[i] = 1$. By Lemma 1, there are $|S_{\varDelta }| = 2^k$ possibilities for $(\mathbf {x}_j + (\overline{x_j},\dots ,\overline{x_j}) ) * \varDelta$ and hence $\mathbf {q}_j + \overline{x_j} \cdot \varDelta$, given $\varDelta \in S_{\varDelta }$. Therefore, the probability of one such query is $2^{-k}$.

However, we must also show that the environment cannot learn any additional information from previous queries. For example, when R queries $\mathbf {q}_j + x_j \cdot \varDelta$ to get their correct OT output, the environment (who sees the honest sender output so can verify this has occurred) can learn $\mathbf {e}_j * \varDelta$ by computing $\mathbf {q}_j + x_j\cdot \varDelta + \mathbf {t}_j$. By definition, the bits of $\mathbf {e}_j$ corresponding to any index set $H_\mathbf {s}$ are constant. Furthermore, Lemma 1 states that either $\varDelta ^{(1)}_i = \varDelta ^{(2)}_i$ for all $\varDelta ^{(1)}, \varDelta ^{(2)} \in S_{\varDelta }$ and $i \in H_\mathbf {s}$ or $|H_\mathbf {s}| \ge k$. In the first case, $e_j[i] \cdot \varDelta _i$ is known by the fact that $\varDelta \in S_{\varDelta }$. In the second case, consider that $e_j[i]$ is the same for all $i \in H_\mathbf {s}$. If $e_j[i] = 0$ for all $i \in H_\mathbf {s}$, then $e_j[i] \cdot \varDelta _i = 0$ for all $i \in H_\mathbf {s}$. On the other hand, if $e_j[i] = 1$, there are $2^k$ possibilities for $\mathbf {e}_j * \varDelta$ (given $\varDelta \in S_{\varDelta }$ as above) and thus for $\mathbf {q}_j + x_j \cdot \varDelta$. Hence, either the latter is known to the adversary already or the probability of querying it is $2^{-k}$ per query.

It follows that the probability the simulation aborts after the correlation check has passed is at most $q \cdot 2^{-k}$, where q is the number of queries made by the environment. Now taking into account the fact that the check passes with probability $|S_{\varDelta } | \cdot 2^{-\kappa } + 2^{-\kappa } = 2^{-\kappa } \cdot (2^k + 1)$, the overall success probability of distinguishing is at most $q \cdot 2^{-\kappa } \cdot (1 + 2^{-k})$, which is negligible in $\kappa$.   $\square$

3.4 From ${\mathsf {ROT}}$ to ${\mathsf {OT}}$

Finally we show how to reduce $\mathcal {F}_{\mathsf {OT}}^{\kappa ,\ell }$ to $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$.

Lemma 3

The protocol in Fig. 9 securely implements the $\mathcal {F}_{\mathsf {OT}}^{\kappa ,\ell }$ functionality in the $\mathcal {F}_{\mathsf {ROT}}^{\kappa ,\ell }$-hybrid model.

Proof

It is easy to describe a simulator for a corrupt R. $\mathcal {S}$ runs a copy of $\mathcal {A}$ setting dummy parties $\pi _R$ and $\pi _S$ and then simulates for them a real execution of $\mathsf {DeROT}$, running an internal copy of $\mathcal {F}_{\mathsf {ROT}}$.

We just need to show indistinguishablity of the transcripts and of the outputs. In both worlds, $\{\mathbf {d}_{x_i,i}\}_{i \in [\ell ]}$ and $\{\mathbf {v}_{x_i,i}\}_{i \in [\ell ]}$ are distributed uniformly subject to the condition $\mathbf {d}_{x_i,i} + \mathbf {v}_{x_i,i} = \mathbf {y}_{x_i,i}$ for all $i \in [\ell ]$, as the pads $\mathbf {v}_{0,i}$ and $\mathbf {v}_{1,i}$ provided by $\mathcal {F}_{\mathsf {ROT}}$ are random and independent of R’s view, except with negligible probability.

Fig. 9.

Derandomization protocol for random OT.

4 Implementation

In this section, we evaluate the efficiency of our random OT extension protocol. As was done in previous works [1, 2], we tested the protocol in a standard LAN setting and a simulated WAN environment, using the Linux tc tool to create an average round-trip-time of 100 ms (with standard deviation 1 ms) and limit bandwidth to 50 Mbps (comparable with the setting reported by Asharov et al. [2]). We used computational security parameter $\kappa =128$ and statistical security parameter $s=64$ throughout, and instantiated the PRG with AES-128 in counter mode (using Intel AES-NI) and the random oracle H with SHA-1. $\mathcal {F}_{\mathsf {Rand}}$ is implemented using a standard hash-based commitment scheme, where both parties commit to and then open a seed, then the XOR of the two values is used to seed a PRG, which is UC-secure in the random oracle model.

Our implementation was written in C++ using the Miracl libary for elliptic curve arithmetic in the base OTs, which were executed using the actively secure protocol of Peikert et al. [21]. All benchmarks were taken as an average of 20 runs on Intel Core i7-3770S 3.1 GHz processors with 8 cores and 32 GB of memory.

Implementation Optimizations. The correlation check stage of our protocol requires computing values of the form $\sum _i x_i \cdot y_i$ where $x_i, y_i \in \mathbb {F}_{2^\kappa }$. We used Intel PCLMUL instructions to efficiently compute carrlyess multiplications and then performed summations and the check itself in the polynomial ring (of length $2\kappa -1$) to avoid having to do expensive reduction by the finite field polynomial.

As was done by Asharov et al. [1], we use Eklundh’s algorithm for transposing the matrices T and Q during the ${\mathsf {COTe}}$ protocol in a cache-friendly manner, which makes the time spent in this stage less than 3 % of the total runtime. Our implementation also supports multi-threading, making use of the 8 cores available on our test machines.

4.1 Comparison of Protocols

Table 2 shows the time taken for our implementation to compute 10 million OT extensions (excluding the base OTs) in a variety of settings. The one-directional setting is a traditional OT between a sender and a receiver, whilst in the bi-directional times, both parties perform both roles simultaneously (for a total of 20 million OTs). The bi-directional variant is often required for secure two-party and multi-party computation protocols, and over a LAN is much more efficient than performing the one-directional protocol twice, but less so in the WAN setting where communication is the bottleneck.

Table 2. Random OT extension runtimes in seconds, using either 1 or 8 threads. The one-directional time is for 10 million OTs between a sender and receiver, whilst for the bi-directional time both parties are playing each role for a total of 20 million OTs.

The passive protocol is just the standard IKNP extension (with the random OT communication optimization of Asharov et al. [1]), which is essentially our protocol without the correlation check. In the LAN setting, the time difference between the active and passive protocols is less than 5 %. The WAN times for the passive and active protocols are very similar, however it should be noted that there was more variation in our WAN experiments – computing 95 % confidence intervals for these means in the table gives a variation of up to $\pm 3$ %. This is probably mostly due to network variation and can be taken as evidence that our protocol has roughly the same performance as the passive IKNP extension. The total amount of data sent (in all protocols) is almost identical, due to the very low overhead of our correlation check. Compared with the reported timings for the protocol of Asharov et al. [2], our runtimes are much improved: their actively secure times are between 40 % and 80 % higher than their passive implementation, whilst ours almost match the efficiency of the passive protocol. (We do not directly compare figures due to the different benchmarking environments involved.)

Figure 10 illustrates the performance of our protocol as the number of OTs computed varies, in both the WAN and LAN settings, tested in the one-directional and bi-directional modes of OT operation.

Fig. 10.

Performance of our OT extension protocol for various numbers of OTs. Times exclude the base OTs.

4.2 Profiling

Figure 11 presents profiling results for the main components of our protocol, run in a single thread creating 10 million OTs. It clearly demonstrates that the bottleneck of our protocol is communication from the IKNP extension phase, as was reported for the passive secure implementation of Asharov et al. [1]. The correlation check that we require for active security has a negligible impact on the runtime; the best way to further optimize our implementation in the LAN setting would be to target the hash function computations. The ‘Other’ section includes overhead from PRG computations, matrix transposition and allocating memory, which could also potentially be reduced a small amount.

Fig. 11.

Profiling results for running 10 million OTs in a single thread.