Extending Oblivious Transfer Efficiently

Abstract

On top of the passively secure extension protocol of [IKNP03] we build a new construction secure against active adversaries. We can replace the invocation of the hash function that is used to check the receiver is well-behaved with the XOR of bit strings. This is possible by applying a cut-and-choose technique on the length of the bit strings that the receiver sends in the reversed OT. We also improve on the number of seeds required for the extension, both asymptotically and practically. Moreover, the protocol used to test receiver’s behaviour enjoys unconditional security.

1 Introduction

Oblivious Transfer (OT), concurrently introduced by Rabin [Rab81] and Wiesner [Wie83] (the latter under the name of multiplexing) is a two-party protocol between a sender Alice and a receiver Bob. In its most useful version the sender has two secret bit strings, and the receiver wants to obtain one of the secrets at his choosing. After the interaction the receiver has not learnt anything about the secret string he has not chosen, and the sender has not learnt anything about the receiver’s choice. Several flavours have been considered and they turn out to be equivalent [EGL85, BCR86a, BCR86b, Cré87].

In the Universally Composable Framework [Can01], OT has been rigorously formalized and proved secure [CLOS02] under the assumption of trapdoor permutations (static adversaries) and non-committing encryption (adaptive adversaries). It was further realized [PVW08] under several hard assumptions (DDH, QR or worst-case lattice problems).

OT is a powerful cryptographic primitive that may be used to implement a wide range of other cryptographic primitives [Kil88, IPS08, Yao82, GMW86, GV87, EGL85]. Unfortunately, the results of Impagliazzo and Rudich [IR89] make it very unlikely that one can base OT on one-way functions (as a black-box).

As a second best solution, Beaver showed in its seminal paper [Bea96] that one can implement a large number of oblivious transfers assuming that only a small number of OTs are available. This problem is known as Extended Oblivious Transfer. The OTs that one starts with are sometimes called the seeds of the extension. Beaver showed that if one starts with say $n$ seeds, it is possible to obtain any polynomial number (in $n$) of extended OTs. His solution is very elegant and concerns feasibility, but it is inherently non-efficient. Later, Ishai et al. [IKNP03] showed a very efficient reduction for semi-honest adversaries. Since then other works have focused on extensions with active adversaries [IKNP03, HIKN08, IPS08, NNOB12]. This paper continues this line of research.

State of the Art. The approach initiated in [IKNP03] runs at his core a reversed OT to implement the extension. As already noted in [IKNP03], proving security against a cheating receiver Bob $^*$ is not trivial, as nothing refrains him from inputting whatever he likes in the reversed OT, allowing him to recover both secrets on Alice’s side.

In terms of efficiency, the passive version of [IKNP03] needs $O(s)$ OT seeds, where $s$ is a security parameter, with cut-and-choose techniques and the combiner of [CK88] active security comes at the cost of using $\varOmega (s)$ seed OTs¹. In [HIKN08] active security is achieved at no extra cost in terms of seed expansion (and communication), they apply OT-combiners worsening the computational cost. In [NNOB12] the expansion factor is $\frac{8}{3} \approx 2.66$, which is already quite good. Recently, it has been shown [LZ13] that meaningful extensions only exist if one starts with $\omega (\log {s})$ seeds, (for $\log {s}$ seeds one would have to construct an OT protocol from the scratch). The constructions of [Bea96, IKNP03] can be instantiated with superlogarithmic seeds, so are optimal in this respect.

The communication cost is not really an issue, due to known almost-free reductions of $\mathcal {OT}^{n}_{poly(n)}$ to $\mathcal {OT}^{n}_{n}$, using a pseudo random generator, and running the small OT on the seeds. The computational cost of [IKNP03] is extremely efficient (passive version), it needs $O(s)$ work, i.e. constant work per extended OT (precisely it needs three invocations of the cryptographic primitive). All active extensions need at least amortized $\varOmega (s)$ work.

Our Contributions. A technique that has proven to be quite useful [Nie07] is to split the extension protocol in two: an outer protocol $\rho$, and an inner protocol $\pi$. The former implements the actual extended transfers, whereas the latter wraps the reversed OT, ensuring at the same time that the receiver Bob is well-behaved in some sense. We follow the same idea, the novelty of our construction being in how the inner protocol $\pi$ is realized. More concretely, for a fixed security level $s$ we give a family of protocols $\pi _{m,n,t}$, where $n$ is the number of seeds, $m$ is the number of extended transfers, and $t \in [\frac{1}{n},1)$. Values of $t$ close to $\frac{1}{n}$ render less OT seeds, and values close to $1$ less computational and communication cost. We obtain

• The overall construction has amortized constant cost in terms of cryptographic computation. Active security is obtained at the cost of XORing $O((1-t)n^2)$ bits. The construction has similar communication complexity. The previous best [NNOB12] need to hash $O(n)$ bits per extended transfer.

• The seed expansion factor of the reduction, with respect to the passive version of [IKNP03] is asymptotically close to $2$, and this convergence is quite fast, for example for security level $s=128$ one needs about $n = 323$ seeds to produce about $1,00,000$ extended OTs. This means that our construction essentially suffers an overhead factor of $2$ in the security parameter, with respect to the passive protocol of [IKNP03].

• The reduction of $\pi$ to the inner OT is information-theoretic. Other constructions either required computational assumptions e.g. [IKNP03, HIKN08, IPS08], or were in the random oracle [Nie07, NNOB12]. The outer protocol $\rho$ is the standard protocol of [IKNP03], thus it uses a correlation robust function.

Our proof technique is, to some extent, similar to those of [Nie07, NNOB12] in the sense that it is combinatorial. Instead of working with permutations, we are able to connect security with set partitions. In [NNOB12] adversarial behaviour was quantified through what the authors called leakage functions. We take a different approach, and measure adversarial behaviour with the thickness of a partition. Details are in Sect. 4.3.

Paper Organization. Notation and basic background is introduced in Sect. 2. Section 3 discusses the approach of [IKNP03] and fits it in our context. In Sect. 4 we present the inner protocol $\pi$ and prove it secure. In Sect. 5 the final construction is concluded, we discuss complexity and further directions.

2 Preliminaries

2.1 Notation

We denote with $[n]$ the set of natural number less or equal than $n$. Let $\mathbb {F}_2$ be the field of telements, binary vectors $\mathbf {x}$ are written in bold lowercase and binary matrices $\mathbf {M}$ in bold uppercase. When $\mathbf {M}$ is understood from the context, its rows will be denoted with subindices $\mathbf {m}_i$, and its columns with superindices $\mathbf {m}^j$. The entry at position $(i,j)$ is denoted with $m_i^j$. Accordingly, the $j$th bit of a row vector $\mathbf {r}\in \mathbb {F}_2^n$ will be denoted with $r^j$, and the $i$th bit of a column vector $\mathbf {c}\in \mathbb {F}_2^m$ with $c_i$. For any two matrices $\mathbf {M}$, $\mathbf {N}$, of dimension $m \times n$, we let $[\mathbf {M}, \mathbf {N}]$ be the $m \times 2n$ matrix whose first $n$ columns are $\mathbf {m}^j$ and last $n$ columns are $\mathbf {n}^j$. The symbol $\mathbf {a}_{|J}$ stands for the vector obtained by restricting $\mathbf {a}$ at positions indexed by $J$.

2.2 Set Partitions

Given a finite set $X$ of $n$ objects, for any $p \le n$, a partition $\mathcal {P}$ of $X$ is a collection of $p$ pairwise disjoint subsets $\{ P_k \}_{k = 1}^p$ of $X$ whose union is $X$. Each $P_k$ is a part of $X$. We say that part $P_k$ is maximal if its size is the largest one. Let $\mathcal {ER}(X)$ denote the set of all possible equivalence relations in $X$. There is a one-to-one correspondence between partitions of $X$ and equivalence relations in $X$, given by the mapping $\mathcal {P}\mapsto \mathcal {R}$, where $x \mathcal {R} y$ iff $x \in P_k$ and $y \in P_k$. We write $\mathcal {P}^{X}$ to denote the set of all partitions of $X$. In this work we will be concerned with partitions of the set $[n]$, where $n$ is the number of OT seeds.

2.3 Universally Composable Framework

Due to lack of space we assume the reader is familiar with the UC Framework [Can01], especially with the notions of environment, ideal and real adversaries, indistinguishability, protocol emulation, and the composition theorem. Functionalities will be denoted with calligraphic $\mathcal {F}$. As an example $\mathcal {OT}^{m}_{n}$ denotes the OT functionality, in which the sender inputs $m$ pairs of secret strings $(\mathbf {l}_i, \mathbf {r}_i)_{i \in [m]}$, each string of length $n$. The receiver inputs vector $\varvec{\sigma }\in \mathbb {F}_2^m$, and as a result obtains the $i$th left secret $\mathbf {l}_i$ if $\sigma _i = 0$, or the $i$th right secret $\mathbf {r}_i$ if $\sigma _i =1$. We will also make use of a correlation robust function. We name the output of the $\mathsf {CRF}$ as the hash of the input. Some times we will write $H$ instead of $\mathsf {CRF}$. The definition can be found in [IKNP03].

3 The IKNP Approach

In $2003$, in their breakthrough, Ishai, Kilian, Nissim and Petrank [IKNP03] opened the door for practical OT extensions. They provided two protocols for this task. Throughout this paper we will sometimes refer to the passive version as the IKNP extension. We consider the standard OT functionality [CLOS02] in its multi session version, the only difference is that the adversary is allowed to abort the execution. This is necessary because of how we deal with a cheating sender (see Fig. 3).

3.1 IKNP in a Nutshell

For any $m = \text {poly}(n)$, the ideal functionality ${\mathcal {OT}^{m}_{n}}$ is realized making a single call to ${\mathcal {OT}^{n}_{m}}$, where the security parameter of the reduction depends on $n$. This in turn implies a reduction to $\mathcal {OT}^{n}_{n}$ using a pseudorandom generator. It works as follows: Let $\varvec{\sigma }\in \mathbb {F}_2^m$ be the input of $\mathsf {Bob}$ to $\mathcal {OT}^{m}_{n}$, he chooses a $m \times 2n$ binary matrix $[\mathbf {L},\mathbf {R}]$ for which it holds $\mathbf {l}^j \oplus \mathbf {r}^j = \varvec{\sigma }$, $j \in [n]$, but is otherwise random, and inputs it to an inner $\mathcal {OT}^{n}_{m}$ primitive. $\mathsf {Alice}$ inputs a random vector $\mathbf {a}\in \mathbb {F}_2^n$. As a result of the call $\mathsf {Alice}$ obtains (row) vectors $\{ \mathbf {q}_i\}_{i \in [m]}$, for which hold $\mathbf {q}_i = \mathbf {l}_i \oplus \sigma _i \cdot \mathbf {a}$. Now, if $\mathsf {Alice}$ wants to obliviously transfer one of her two $i$th secrets $(\mathbf {x}_i^{(0)},\mathbf {x}_i^{(1)})$, she XORs them with $\mathbf {p}_i^{(0)} = \mathbf {q}_i$ and $\mathbf {p}_i^{(1)} = \mathbf {q}_i \oplus \mathbf {a}$ respectively, and sends masks $\mathbf {y}_i^{(0)}$, $\mathbf {y}_i^{(1)}$ to $\mathsf {Bob}$, who can obtain $\mathbf {x}_i^{(b_i)}$ from $\mathbf {y}_i^{(b_i)}$ and $\mathbf {l}_i$. This can be used to implement one transfer out of the $m$ that $\mathsf {Bob}$ wishes to receive, but can not cope with more: the OTP used for the $i$th transfer, with pads $(\mathbf {p}_i^{(0)}, \mathbf {p}_i^{(1)})$, prohibits to use $(\mathbf {p}_j^{(0)}, \mathbf {p}_j^{(1)})$ in the $j$th transfer, because they are correlated (the same $\mathbf {a}$ is implicit in both pairs²). To move from a situation with correlated pads to a situation with uncorrelated ones, IKNP uses a $\mathsf {CRF}$; i.e. $\mathsf {Alice}$ masks $\mathbf {x}_i^{(c)}$ with the hash of $\mathbf {p}_i^{(c)}$. The construction is perfectly secure against a malicious sender $\mathsf {Alice}^*$, and statistically secure against a semi-honest receiver $\mathsf {Bob}^*$.

Intuitively, each input bit, $\sigma _i$, of $\mathsf {Bob}$ is protected by using $n$ independent additive sharings as inputs to the inner $\mathcal {OT}^{n}_{m}$. As for $\mathsf {Alice}$’s privacy, the crucial point being that as long as $\mathbf {a}$ is not known to $\mathsf {Bob}$, then $\mathbf {x}^{(1+b_i)}$ remains hidden from him; in that situation, one of the pads in each pair is independent of $\mathsf {Bob}$’s view. Unfortunately, the above crucially relies on $\mathsf {Bob}$ following the protocol specifications. In fact, it is shown in [IKNP03] how $\mathsf {Bob}^*$ can break privacy if he chooses carefully what he gives to the inner $\mathcal {OT}^{n}_{m}$.

3.2 Modularizing the Extension

We define an ideal functionality that acts as a wrapper of the inner call to the $\mathcal {OT}^{}_{}$ primitive.³ It behaves as follows: (1) On an honest input $\mathbf {B}= [\mathbf {L},\mathbf {R}]$ from $\mathsf {Bob}$ (i.e. $\mathbf {B}$ defines $n$ sharings of some vector $\varvec{\sigma }$), the functionality gives to $\mathsf {Alice}$ a pair $(\mathbf {a},\mathbf {Q})$ that she will use to implement the extended transfers. The secret $\mathbf {a}$ is randomly distributed in $\mathsf {Bob}$’s view. (2) An ideal adversary $\mathcal {S}$ can guess $d$ bits of $\mathbf {a}$, in this case the functionality takes the guesses with probability $2^{-d}$. The secret $\mathbf {a}$ has $n-d$ bits randomly distributed in $\mathsf {Bob}$’s view.

The functionality is denoted with $c\mathcal {PAD}_{m,n}$ to emphasize that it gives $m$ correlated pairs of pads, under the same $\mathbf {a}$ to $\mathsf {Alice}$ (of length $n$). See Fig. 1 for a formal description. We emphasize that $c\mathcal {PAD}$ without the malicious behaviour was implicit in [IKNP03], and with the malicious behaviour in [Nie07]. We have just made the probability of aborting more explicit. The novelty of our approaches lies in how is realized.

For completeness, we have included the IKNP extension protocol, see Fig. 2 for details. The only difference is that the pads $(\mathbf {p}_i^{(0)},\mathbf {p}_i^{(1)})_{i \in [m]}$ that $\mathsf {Alice}$ uses to generate uncorrelated ones via the $\mathsf {CRF}$ are assumed to be given by $c\mathcal {PAD}_{m,n}$.

Fig. 1.

Modeling creation of correlated pads

Fig. 2.

IKNP extension

3.3 The Reduction

The proof is on the same lines of the reduction of [IKNP03]. For the case the receiver is actively corrupted, with $c\mathcal {PAD}_{m.n}$ at play, $\mathsf {Bob}^*$ is forced to take a guess before the actual extended transfers are executed. He is not caught with probability $2^{-d}$, in which case $n-d$ bits of $\mathbf {a}$ are completely unknown to him. This correspondence between adversarial advantage and uncertainty (observed in [Nie07]) is the key to argue security in the active case. What we observe is that within the set $F$ that indexes the $n-d$ unknown bits, either $\mathbf {a}$ or the flipped vector $\mathbf {a}\oplus \mathbf {1}$ has at least $(n -d)/2$ bits set to one. Consequently, the same number of bits of one of the pads that $\mathsf {Alice}$ uses remains unknown to $\mathsf {Bob}^*$. Using bounding techniques borrowed from [Nie07] it is not difficult to simulate $\rho$ with security essentially half the security of the IKNP extension.

Claim

(Restatement of ([IKNP03, Lemma1) for Active Adversaries). In the $c\mathcal {PAD}_{m,n}$-hybrid model, in the presence of $\mathsf {static}$ $\mathsf {active}$ adversaries, with access to at most $2^{o(n)}$ queries of a $\mathsf {CRF}$, the output of protocol $\rho$, and the output of the ideal process involving $\mathcal {OT}^{m}_{n}$, are $2^{-n/2 + o(n) +2}$-close.

For completeness it follows a proof sketch that combines the proofs of [IKNP03, Nie07]. Later, in Sect. 4.4 we will elaborate on an alternative idea for the simulation.

We focus on the case $\mathsf {Bob}^*$ is corrupted, simulating a malicious $\mathsf {Alice}^*$ is easy, and we refer the reader to [IKNP03] for details. To simulate a real execution of $\rho$, an ideal adversary $\mathcal {S}$ starts setting an internal copy of the real adversary $\mathcal {A}$, and runs the protocol between $\mathcal {A}$ and dummy parties $\rho _{\mathsf {A}}$ and $\rho _{\mathsf {B}}$. The communication with the environment $\mathcal {E}$ is delegated to $\mathcal {A}$. Recall t hat $\mathcal {S}$ is also interacting with the (augmented with aborts) ideal functionality $\mathcal {OT}^{m}_{n}$ (see Fig. 3). A description of $\mathcal {S}$ for a malicious $\mathsf {Bob}^*$ is in Fig. 4.

Fig. 3.

The functionality of [CLOS02] augmented with aborts

Fig. 4.

The ideal adversary for actively corrupted receivers

Let $\mathsf {Dist}$ be the event that $\mathcal {E}$ distinguishes between the ideal process and the real process, we examine the simulation conditioned on three disjoint events: $\mathsf {SH}$ is the event defined as “$\mathcal {A}$ sends $(\mathsf {deliver},sid)$ to $c\mathcal {PAD}$”, $\mathsf {Active}$ is the event “$\mathcal {A}$ sends $(\mathsf {corruptBob},sid)$ and $c\mathcal {PAD}$ does not abort”, and $\mathsf {Abort}$ is the event “$\mathcal {A}$ sends $(\mathsf {corruptBob},sid)$ and $c\mathcal {PAD}$ aborts”. It is clear that conditioned on $\mathsf {Abort}$ the simulation is perfect (with unbounded environments), because no transfers are actually done. Now, say that $|G| = d$, then $c\mathcal {PAD}_{m,n}$ does not abort with probability $2^{-d}$, so we write

$$\begin{aligned} Pr[\mathsf {Dist}] \le Pr[\mathsf {Dist}|\mathsf {SH}] + Pr[\mathsf {Dist}|\mathsf {Active}] \cdot 2^{-d} \end{aligned}$$

(1)

Conditioning on $\mathsf {Active}$ . In this case, the only difference between the ideal and the real process is that $\mathcal {S}$ fills with garbage the secret $\mathbf {x}_{i}^{(r_i+1)}$ of $\rho _{\mathsf {A}}$, thus, the transcripts are indistinguishable provided $\mathcal {E}$ (or $\mathcal {A}$) does not submit $Q = \mathbf {p}_{i}^{(r_i+1)}$ to the $\mathsf {CRF}$ (in that case, $\mathcal {E}$ sees the zero vector in the ideal process, and the actual input of $\mathsf {Alice}$ in the real process). It is enough to see that this happens with negligible probability: First, pad $\mathbf {p}_{i}^{(r_i+1)}$ restricted at positions indexed with $F_{r_i}$ can be expressed as

$$\begin{aligned} \mathbf {p}_{i|F_{r_i}}^{(r_i+1)}&= \mathbf {q}_{i|F_{r_i}} \oplus (r_i \oplus 1) \cdot \mathbf {a}_{|F_{r_i}} = (\tilde{\mathbf {l}}_i \oplus (\tilde{\mathbf {l}}_i \oplus \tilde{\mathbf {r}}_i) * \mathbf {a})_{|F_{r_i}}) \oplus (r_i \oplus 1) \cdot \mathbf {a}_{|F_{r_i}}\\&= \tilde{\mathbf {l}}_{i|F_{r_i}} \oplus r_i\cdot \mathbf {a}_{|F_{r_i}} \oplus (r_i \oplus 1) \cdot \mathbf {a}_{|F_{r_i}}\\&= \tilde{\mathbf {l}}_{i|F_{r_i}} \oplus \mathbf {a}_{|F_{r_i}}. \end{aligned}$$

Second, the size of $F_{r_i}$ is at least $(n -d)/2$, because $F = F_0 \vee F_1$ and $F_{r_i}$ is maximal. Third, $c\mathcal {PAD}_{m,n}$ generates $\mathbf {a}_{|F_{r_i}}$ using his own random bits. It follows that $\mathbf {p}_i^{(r_i+1)}$ has $(n - d)/2$ bits randomly distributed in $\mathcal {E}$’s view.

He may still guess such bits searching through the query space and using the $\mathsf {CRF}$ to compare. We next bound the probability of this happening. If $\mathcal {E}$ (or $\mathcal {A}$) guess correctly such bits, they would have handed to the $\mathsf {CRF}$ query $Q = \mathbf {p}_i^{(r_i+1)}$. As $(n-d)/2$ bits are unknown, the $\mathsf {CRF}$ returns random answers on $\mathcal {E}$’s view, the probability of hitting all the bits in $\mathbf {p}_i^{(r_i+1)}$ is bounded by $p_i \le h_{r_i+1}2^{(d - n)/2}$ where $h_{r_i+1}$ is the number of queries made to $H^{(r_i+1)}_{i}$. By the union bound, given $h$ denoting the total number of queries, $\mathcal {E}$ and $\mathcal {A}$ jointly hit query $Q = \mathbf {p}_i^{(r_i+1)}$ for some $i \in [m]$, with probability

$$\begin{aligned} Pr[\mathsf {Dist}|\mathsf {Active}] \le 2 (\sum _{i \in [m]} h_{r_i+1}2^{(d - n)/2}) \le h 2^{d/2+1-n/2}. \end{aligned}$$

(2)

Conditioning on $\mathsf {SH}$. This case corresponds to semi-honest adversaries. We refer the reader to the proof of [IKNP03] for details. The only difference is that now also $\mathcal {A}$ can submit arbitrary queries to the $\mathsf {CRF}$, hitting the offending one with the same probability than the environment would, thus

$$\begin{aligned} Pr[\mathsf {Dist}|\mathsf {SH}] \le h2^{-n+1}. \end{aligned}$$

(3)

Plugging inequalities 2 and 3 into 1, we obtain that the simulation fails with probability

$$\begin{aligned} Pr[\mathsf {Dist}] \le h 2^{-n+1} + h 2^{d/2+1-n/2} \cdot 2^{-d} \le h2^{-n/2 + 2}. \end{aligned}$$

The Claim follows setting $h = 2^{o(n)}$.   $\square$

4 Generating Correlated Pads

The result of Sect. 3.3 (and previous works) shows that the IKNP extension can be upgraded to active security assuming that any adversarial strategy, on the receiver’s side, amounts to guessing some of the bits of the sender’s secret $\mathbf {a}$ before the extended transfers are executed. In this section we realize the $c\mathcal {PAD}$ functionality in a way where the only computational cost involved, beyond the underlying OT primitive on which it builds, is XORing bit strings.

4.1 Warming Up: Committing $\mathsf {Bob}$ to His Input

The inner $\mathcal {OT}^{n}_{m}$ of the IKNP extension can be seen, in a way, as a commitment for $\mathsf {Bob}$’s input $\varvec{\sigma }$ to the outer $\mathcal {OT}^{m}_{n}$. The idea resembles the commitment scheme of [Cré89] generalized to $m$-bit strings. We split the protocol in two phases: A “commit” phase and a “prove” phase. To commit to $\varvec{\sigma }$, $\mathsf {Bob}$ chooses $n$ independent sharings $\mathbf {B}= [\mathbf {L}, \mathbf {R}]$ (i.e. $\mathbf {l}^j \oplus \mathbf {r}^j = \varvec{\sigma }$ for $j \in [n]$) and offers them to an $\mathcal {OT}^{n}_{m}$ primitive. For the $j$th sharing, $\mathsf {Alice}$ obliviously retrieves one of the shares using her secret bit $a^j$. She obtains a “witness” matrix $\mathbf {Q}=[\mathbf {q}^j]_{j \in [n]}$. To prove his input $\mathsf {Bob}$ reveals $(\varvec{\sigma }, \tilde{\mathbf {B}})$, and $\mathsf {Alice}$ checks she got the right share in the first place, (i.e. she checks $\mathbf {q}^j \mathop {=}\limits ^{\mathsf {?}}\tilde{\mathbf {l}}^j \oplus a^j \cdot (\tilde{\mathbf {l}}^j\oplus \tilde{\mathbf {r}}^j)$), and that $\tilde{\mathbf {B}}$ is consistent with $\varvec{\sigma }$ (i.e. $\tilde{\mathbf {l}}^j \oplus \tilde{\mathbf {r}}^j \mathop {=}\limits ^{\mathsf {?}}\varvec{\sigma }$).

Witnessing. The above protocol is of no use in our context, as for $\mathsf {Bob}$ to show he behaved correctly, he would have to reveal his input $\varvec{\sigma }$ to the outer $\mathcal {OT}^{m}_{n}$. Nevertheless, we retain the concept of $\mathsf {Alice}$ obtaining a “witness” of what $\mathsf {Bob}^*$ gave to the inner $\mathcal {OT}^{}_{}$. Such object is a pair $W = (\mathbf {a},\mathbf {Q})$ obtained as the output of an $\mathcal {OT}^{n}_{m}$ primitive. Two witnesses $W$, $W'$ are consistent if $\mathbf {a}= \mathbf {a}'$. Similarly, a “proof for witness $W$” is a pair $(\varvec{\sigma }, \tilde{\mathbf {B}})$ such that $\tilde{\mathbf {B}}$ defines $n$ sharings of $\varvec{\sigma }$. We say the proof is valid if it is consistent with $W$, in the sense $\mathsf {Alice}$ would accept in the above protocol, when she is presented the proof and uses $W$ to check it.

We emphasize that with this terminology, the output of $c\mathcal {PAD}_{m,n}$ is precisely a witness (see Fig. 1).

Fig. 5.

Realizing $c\mathcal {PAD}_{m,n}$

4.2 The Protocol

Suppose $\mathsf {Alice}$ has obtained a witness $W_0$ and she wants to use it to implement the extended transfers (as in protocol $\rho$). She is not sure if in order to give her the witness $\mathsf {Bob}$ used a good matrix $\mathbf {B}_0 = [\mathbf {L}_0,\mathbf {R}_0]$ or a bad one (loosely speaking a good matrix defines almost $n$ sharings of a fixed vector $\varvec{\sigma }$, whereas a bad matrix has many (left,right) pairs adding up to distinct vectors.). Now, say that $\mathsf {Alice}$ has not one but two witnesses $W_0$, $W_1$. If they are consistent it is not difficult to see that she also knows a witness for $\mathbf {B}_+ = \mathbf {B}_0 \oplus \mathbf {B}_1$. So what $\mathsf {Alice}$ can do is to ask $\mathsf {Bob}$ to “decommit” to $\mathbf {B}_+$ as explained in Sect. 4.1. Intuitively $\mathsf {Bob}^*$ is able to “decommit” if $\mathbf {B}_+$ is not a bad matrix. It is also intuitive that $\mathbf {B}_+$ is not a bad matrix provided $\mathbf {B}_0$ and $\mathbf {B}_1$ are both good, or both bad. To rule out the latter possibility, $\mathsf {Alice}$ flips a coin and asks $\mathsf {Bob}$ to either “decommit” to $\mathbf {B}_1$ or to $\mathbf {B}_+$ accordingly. The process is repeated $r$ times to achieve real soundness. Observe that a malicious $\mathsf {Alice}^*$ can not tell anything from $\varvec{\sigma }$, as an honest $\mathsf {Bob}$ always sends either $\varvec{\sigma }_1$ or masked $\varvec{\sigma }_0 \oplus \varvec{\sigma }_1$ when he is “decommitting”.

Generating $r$ consistent witnesses with $W_0$ can be done very efficiently⁴ using an $\mathcal {OT}^{n}_{r(m+1)}$ primitive. The details of the protocol are in Fig. 5.

Correctness. If the parties follow the protocol it is not difficult to see that $\pi _{m,n,t}$ outputs exactly the same as $c\mathcal {PAD}_{m,n}$. By the homomorphic property, $\mathsf {Alice}$ does not reject on honest inputs. Output correctness is due to the fundamental relation exploited in the IKNP extension.

4.3 Security Analysis

The rest of the section is dedicated to prove that the output of $\pi _{m,n,t}$ and the output of $c\mathcal {PAD}_{m,n}$ are statistically close. The road-map is as follows: we first explain why we can work with partitions of $[n]$, then we state some useful results, and lastly we use them to show indistinguishability.

Taxonomy of Receiver’s Input. Here we are after a classification of $\mathsf {Bob}$’s matrix $\mathbf {B}= [\mathbf {L},\mathbf {R}] \in \mathcal {M}_{m \times 2n}$. As an illustration consider an honest situation where $\mathsf {Bob}$ gives matrix $\mathbf {B}$ such that it defines $n$ additive sharings of some vector $\varvec{\sigma }$ of his choosing. This means that $\mathbf {l}^j \oplus \mathbf {r}^j = \varvec{\sigma }$ for all indices in $[n]$. Clearly, the relation $j_1 \mathcal {R} j_2$ iff $\mathbf {l}^{j_1} \oplus \mathbf {r}^{j_2} = \varvec{\sigma }$ is the trivial equivalence relation in $[n]$ where all indices are related to each other. In other words, the matrix $[\mathbf {L},\mathbf {R}]$ defines the trivial partition of $[n]$, i.e. $\mathcal {P}= \{ [n] \}$.

Underlying Partition. For any binary matrix $\varvec{\varDelta }$ in $\mathcal {M}_{m \times n}$, its underlying relation is the subset $\mathcal {R}_{\varvec{\varDelta }} \in [n] \times [n]$ defined as

$$ \mathcal {R}_{\varvec{\varDelta }} = \{ (i,j) \in [n] \times [n]\ |\ \varvec{\delta }^i = \varvec{\delta }^j \}. $$

As usual, we write $i \mathcal {R}_{\varvec{\varDelta }} j$ to mean $(i,j) \in \mathcal {R}_{\varvec{\varDelta }}$. It is not difficult to see that $\mathcal {R}_{\varvec{\varDelta }}$ is an equivalence relation⁵, in particular each $\varvec{\varDelta }$ defines a unique partition $\mathcal {P}_{\varvec{\varDelta }}$ of $[n]$. Also, for any partition of $[n]$, we say is $\ell$-thick if the size of its maximal parts are $\ell$. Now it becomes clear that any (possibly malicious) receiver’s input $\mathbf {B}= [\mathbf {L},\mathbf {R}]$ implicitly defines a partition of $[n]$, given by matrix $\varvec{\varDelta }= [\mathbf {l}^1 \oplus \mathbf {r}^1, \ldots , \mathbf {l}^n \oplus \mathbf {r}^n]$. The input is $\ell$-thick if its partition is $\ell$-thick.

Parametrizing the Thickness. One can take a parametric definition, saying that $\mathcal {P}$ is $\ell$-thick if $\ell = \frac{M}{n}$, where $M$ is the size of a maximal part⁶. In the security analysis this notion will prove to be useful. For example, honest inputs have (high) thickness level $\ell = 1$. We will always adopt the parametric perspective.

Witnessing and Thickness. Let $W = (\mathbf {a},\mathbf {Q})$ be a witness that $\mathsf {Alice}$ has. If $\mathsf {Bob}^*$ used an $\ell$-thick $\mathbf {B}$ to give $W$ to $\mathsf {Alice}$, then $W$ is said to be $\ell$-thick.

Rejecting Thin Inputs. Now we formalize the intuition that $\mathsf {Bob}^*$ is caught with high probability if he inputs a matrix with their columns adding up to many distinct vectors.

The first lemma deals with rejections on a particular “proof” handed by $\mathsf {Bob}$. The second lemma upper bounds the thickness of a witness derived from the XOR operation. The proof of the rejection lemma exploits the correctness of the $\mathcal {OT}^{}_{}$ primitive. Both proofs make heavy use of the underlying partition defined in Sect. 4.3. The reader might want to skip them in the first lecture, and go directly to Proposition 1.

Lemma 1

Let $W = (\mathbf {a},\mathbf {Q})$ be a witness that is known to $\mathsf {Alice}$. Then, $\mathsf {Bob}$ knows a valid proof for $W$ only if he knows at least $n(1- \ell )$ bits of $\mathbf {a}$, where $\ell$ is the thickness of $W$. In particular, if $\mathsf {Alice}$ is honest this happens with probability $p \le 2^{-n(1-\ell )}$.

Proof

Let $\mathbf {B}=[\mathbf {L},\mathbf {R}]$ be the input of $\mathsf {Bob}$ to the $\mathcal {OT}^{}_{}$ from which $\mathsf {Alice}$ obtained witness $(\mathbf {a},\mathbf {Q})$, and let $(\varvec{\sigma }, \tilde{\mathbf {B}})$ be the proof held by $\mathsf {Bob}$. Also, let $\varvec{\varDelta }= [\mathbf {l}^1 \oplus \mathbf {r}^1, \ldots , \mathbf {l}^n \oplus \mathbf {r}^n]$, and say that $\varvec{\varDelta }$ defines partition $\mathcal {P}= \{ P_1, \ldots , P_p \}$ of $[n]$.

If the proof $(\varvec{\sigma }, \tilde{\mathbf {B}})$ is valid, then for all $j \in [n]$ we can derive the equations

$$\begin{aligned} (1)\ \mathbf {q}^j&= \mathbf {l}^j \oplus a^j \cdot (\mathbf {l}^j \oplus \mathbf {r}^j)\ ,\ (2)\ \varvec{\delta }^j = \mathbf {l}^j \oplus \mathbf {r}^j,\\ (3)\ \mathbf {q}^j&= \tilde{\mathbf {l}}^j \oplus a^j \cdot (\tilde{\mathbf {l}}^j \oplus \tilde{\mathbf {r}}^j)\ ,\ (4)\ \varvec{\sigma }= \tilde{\mathbf {l}}^j \oplus \tilde{\mathbf {r}}^j. \end{aligned}$$

where $(1)$ and $(2)$ are given by the correctness of the $\mathcal {OT}^{n}_{m}$ executed on $\mathsf {Bob}$’s input $\mathbf {B}= [\mathbf {L},\mathbf {R}]$, and $(3)$ and $(4)$ follow from assuming $(\varvec{\sigma }, \tilde{\mathbf {B}})$ is valid. Adding $(1)$ and $(3)$, and plugging $(2)$ and $(4)$ in the result, we write $\mathbf {l}^j \oplus \tilde{\mathbf {l}}^j = a^j \cdot (\varvec{\delta }^j \oplus \varvec{\sigma })$. Assume first there exist $j_0 \in [n]$, such that $\varvec{\sigma }= \varvec{\delta }^{j_0}$. Say wlog. that $j_0 \in P_1$. Now, by definition of $\mathcal {P}$, we have $\varvec{\sigma }= \varvec{\delta }^j$ iff $j \mathcal {R}_{\varvec{\varDelta }}j_0$. In other words, for $2 \le k \le p$ and $j \in P_k$ we have $\varvec{\sigma }\ne \varvec{\delta }^j$. It follows that there exists $i \in [m]$ such that $\delta _i^j \ne \sigma _i$, and therefore $a^j = l_i^j \oplus \tilde{l}_i^j$. The RHS of the last equation is known to $\mathsf {Bob}$, so is $a^j$. This is true for all $j \in P_k$, and all $k \ge 2$, therefore $\mathsf {Bob}$ knows $|P_2 \vee \ldots \vee P_p| = n - |P_1| \ge n(1-\ell )$ bits of $\mathbf {a}$, where the last inequality follows because $\mathcal {P}$ is $\ell$-thick. On the other hand, if $\varvec{\sigma }\ne \varvec{\delta }^j$ for all $j \in [n]$, then $\mathsf {Bob}$ knows the entire vector $\mathbf {a}$. Adding up, $\mathsf {Bob}^*$ knows at least $n(1-\ell )$ bits of $\mathbf {a}$.

Since $\mathbf {a}$ is secured via the $\mathcal {OT}^{n}_{m}$, $\mathsf {Bob}$ knows such bits by guessing them at random. We conclude that $\mathsf {Alice}$ accepts any $\varvec{\sigma }$ with probability $p < 2^{n(1-\ell )}$, provided $\mathsf {Alice}$ samples $\mathbf {a}$ at random, which is indeed the case.

Lemma 2

If $W = (\mathbf {a},\mathbf {Q})$ is $\ell$-thick and $\tilde{W} = (\mathbf {a},\tilde{\mathbf {Q}})$ is $\tilde{\ell }$-thick , then $W_+ = (\mathbf {a},\mathbf {Q}\oplus \tilde{\mathbf {Q}})$ is $\ell _+$-thick with $\ell _+ \le 1 - |\ell -\tilde{\ell }|$.

Proof

Say that $\epsilon = | \ell - \tilde{\ell }|$. and let $[\mathbf {L},\mathbf {R}]$, $[\tilde{\mathbf {L}},\tilde{\mathbf {R}}]$ be the $\mathsf {Bob}$’s inputs from which $\mathsf {Alice}$ obtained witnesses $W$ and $\tilde{W}$. Say that they define partitions $\mathcal {P}= \mathcal {P}_{[\mathbf {L},\mathbf {R}]}$, $\tilde{\mathcal {P}} = \mathcal {P}_{[\tilde{\mathbf {L}},\tilde{\mathbf {R}}]}$. Similarly one defines partition $\mathcal {P}_{\varvec{\varDelta }\oplus \tilde{\varvec{\varDelta }}}$ for witness $(\mathbf {a},\mathbf {Q}\oplus \tilde{\mathbf {Q}})$.

First, suppose $\ell \le \tilde{\ell }$, and let $\tilde{P}_{max}$ a maximal part of $\tilde{\mathcal {P}}$. Consider the refinement $\mathcal {P}^{\cap }_{max} = \tilde{P}_{max} \cap \mathcal {P}$. If $j_1$, $j_2$ lie in the same part of $\mathcal {P}^{\cap }_{max}$ then $j_1 \mathcal {R}_{\varvec{\varDelta }\oplus \tilde{\varvec{\varDelta }}} j_2$ iff $j_1 \mathcal {R}_{\varvec{\varDelta }} j_2$. This follows from the fact that if $j_1$ and $j_2$ are both in $\tilde{P}_{max}$, then $\tilde{\varvec{\delta }}^{j_1} = \tilde{\varvec{\delta }}^{j_2}$. In particular, each part of $\mathcal {P}^{\cap }_{max}$ lies in a different part of $\mathcal {P}_{\varvec{\varDelta }\oplus \tilde{\varvec{\varDelta }}}$.

Now, look at the auxiliar partition $\{ [n] \backslash \tilde{P}_{max}, \mathcal {P}^{\cap }_{max} \}$. The maximum size we can hope for a part in $P_{\varvec{\varDelta }\oplus \tilde{\varvec{\varDelta }}}$ occurs when $[n] \backslash \tilde{P}_{max}$ collapses with a single maximal part of $\mathcal {P}^{\cap }_{max}$. Even in this case, the size of a maximal part of $\mathcal {P}_{\varvec{\varDelta }\oplus \tilde{\varvec{\varDelta }}}$ is upper bounded by

$$ n(1 - \tilde{\ell }) + n\ell = n(1 - (\ell + \epsilon ) + \ell ) = n(1- \epsilon ). $$

This follows from observing that $\tilde{P}_{max}$ is of size $n\tilde{\ell }$, and $\mathcal {P}^{\cap }_{max}$ have parts upper bounded by $n \ell$. The case $\tilde{\ell } \le \ell$ is analogous (using auxiliar partition $\{ [n] \backslash P_{max}, P_{max}\cap \tilde{\mathcal {P}} \}$).

Next, we estimate the acceptance probability of $\pi _{m,n,t}$ on any possible input of $\mathsf {Bob}$. Note that the first witness obtained in the commit phase is the output of $\pi _{m,n,t}$.

Proposition 1

Let $W = (\mathbf {a},\mathbf {Q})$ the first witness that $\mathsf {Alice}$ obtains in the commit phase of $\pi _{m,n,t}$. Then, if $W$ has thickness $\ell \le t$, $\mathsf {Alice}$ accepts any adversarial proof with probability $p \le 2^{-n(1-t)/2+2}$. In that case, $\mathsf {Bob}$ knows at least $n(1-t)/2$ bits of $\mathbf {a}$.

Proof

Recall that in the protocol $r = \lceil \frac{1-t}{2}n \rceil$, and let $E = (E_1, \ldots , E_r)$ be the random variable (uniformly distributed over $\mathbb {F}_2^r$) that $\mathsf {Alice}$ uses to challenge $\mathsf {Bob}^*$. For $i \in [r]$, let $B^*_i = (L^*_i,R^*_i)$ be the adversarial random variables that $\mathsf {Bob}^*$ uses to sample the $r$ matrices in the commit phase of $\pi$. Let $[\mathbf {L}_i, \mathbf {R}_i] = \mathbf {B}_i \leftarrow B^*_i$ the actual matrices. Denote with $\varvec{\varDelta }_i$ their correspondent underlying matrices. Each $\varvec{\varDelta }_i$ defines a unique partition $\mathcal {P}_i$ of $[n]$, with thickness $\ell _i \in [\frac{1}{n},1]$.

We want to upper bound the probability of $\mathsf {Alice}$ accepting in $\pi _{m,n,t}$ with $\ell \le t$. Denote with $\mathsf {Accept}$ this event. Consider the r.v. $E^* = (E^*_1, \ldots , \mathsf {E}^*_r)$, given by:

$$ E^*_i = {\left\{ \begin{array}{ll} 0 &{}i\text { if } \ell _i> t' + \ell \\ 1 &{}\text { if } \ell _i \le t' + \ell \end{array}\right. } $$

where $t' = \frac{1-t}{2}$ is positive if $t \in [\frac{1}{n},1)$. We first look at the probability of $\mathsf {Alice}$ accepting the $i$th proof,

$$\begin{aligned}&P[\mathsf {Accept}_i] = \frac{1}{2}(P[\mathsf {Accept}_i\ |\ E_i \rightarrow 0] + P[\mathsf {Accept}_i\ |\ E_i \rightarrow 1])\\&\le \frac{1}{2}(P[\mathsf {Accept}_i\ |\ E_i \rightarrow 0, E^*_i \rightarrow 0] + (P[\mathsf {Accept}_i\ |\ E_i \rightarrow 0, E^*_i \rightarrow 1] \\&+ P[\mathsf {Accept}_i\ |\ E_i \rightarrow 1, E^*_i \rightarrow 0] + P[\mathsf {Accept}_i\ |\ E_i \rightarrow 1, E^*_i \rightarrow 1])\\&= p_{0,0} +p_{0,1} +p_{1,0} + p_{1,1}. \end{aligned}$$

Consider the cases:

• $(e_i,e^*_i) = (0,1)$. If $\mathsf {Alice}$ uses $\tilde{W}_i = W_i$ and $\ell _i \le t'+\ell$ (i.e. $1 - \ell _i \ge 1- t' - \ell$), by Lemma 1 we bound $p_{0,1} \le 2^{-n(1-\ell _i)} \le 2^{-n(1-t'-\ell )}$.

• $(e_i,e^*_i) = (1,0)$. If $\mathsf {Alice}$ uses $\tilde{W}_i = W_+ = W_i + W$ and $\ell _i \ge t'+\ell$ (i.e. $\ell _i - \ell \ge t'$, with $t'\ge 0$ is equivalent to $| \ell _i - \ell | \ge t'$), by Lemma 2 we have $\ell _+ \le 1 - | \ell _i -\ell | \le 1- t'$, and Lemma 1 bounds $p_{1,0} \le 2^{-n(1-\ell _+)} \le 2^{-n(1 -(1-t'))} = 2^{-nt'}$.

Now, observe that by hypothesis $\ell \le t$, and therefore $\frac{1-t}{2} = t' = min\{1-t' -\ell ,t' \}$. From the above we deduce, (1) if $\mathsf {Bob}^*$ does not guess $\mathsf {Alice}$’s coin $E_i$ with his own coins $E^*_i$ then he has to guess at least $n(1-t)/2$ bits of $\mathbf {a}$, $(2)$ in that case we bound $p_{b,b+1} \le 2^{-nt'} = 2^{-n(1-t)/2}$.

We have to give up in bounding $p_{0,0}$ and $p_{1,1}$ as $\mathsf {Bob}^*$ can always choose $\ell _i$ appropriately to pass the test with high probability (e.g. $\ell _i=1$, $\ell _i=\ell$ respectively). As observed, in these cases $\mathsf {Bob}^*$ is guessing $\mathsf {Alice}$’s coin $e_i$ with his own coin $e^*_i$. It is now easy to finish the proof as follows:

Let $\mathsf {Guess}$ be the event $\{\mathbf {e}\leftarrow E\} \cap \{ \mathbf {e}\leftarrow E^*\}$, is clear that if $\lnot \mathsf {Guess}$, then exist $i_0$ s.t. $e_{i_0} \leftarrow E_{i_0}$ and $e_{i_0}\oplus 1 \leftarrow E^*_{i_0}$, we can write

$$\begin{aligned}&P[\mathsf {Accept}] = P[\cap _{i=1}^r \mathsf {Accept}_i] \\&\le P[(\cap _i^{r}\mathsf {Accept}_i) \cap \mathsf {Guess}] + P[(\cap _i^{r}\mathsf {Accept}_i)\ |\ \lnot \mathsf {Guess}] \\&\le P[\mathsf {Guess}] + P[\mathsf {Accept}_{i_0}\ |\ E_{i_0} \rightarrow e_i, E^*_{i_0} \rightarrow e_i+1]\\&\le 2^{-r} + 2^{-n\frac{1-t}{2}+1} \end{aligned}$$

Therefore $\mathsf {Alice}$ accepts and $\mathsf {Bob}^*$ knows $n(1-t)/2$ bits of $\mathbf {a}$ with probability at most $2^{-n(1-t)/2+2}$.

Remark on Proposition 1 . The above result ensures two things: First, if $\mathsf {Bob}$ inputs a matrix whose columns do not add to the same constant value he is forced to take a guess on some bits of $\mathbf {a}$. As we saw in Sect. 3.3 this is enough to implement the extended transfers securely. Second, setting the thick parameter $t$ appropriately we can rule out a wide range of adversarial inputs with overwhelming probability in $n$. For example, the adversarial input $\mathbf {I}_{IKNP} = [\mathbf {L},\mathbf {R}]$ of the attack in the IKNP extension has all its columns adding up to distinct elements, i.e. its underlying partition is the thinnest possible partition of $[n]$, $\mathcal {P}_{IKNP} = \{ \{1\}, \ldots , \{n\}\}$. Since $t \ge \frac{1}{n}$, this input is rejected with overwhelming probability.

Putting the Pieces in the UC Framework. We have not yet captured the notion of having blocks of $\mathbf {a}$ randomly distributed in $\mathsf {Bob}$’s view, it is resolved with a simulation argument. More concretely, we show a reduction to $\mathcal {OT}^{n}_{m(r+1)}$ with perfect security against $\mathsf {Alice}^*$, and statistical security against $\mathsf {Bob}^*$.

Theorem 1

In the ${\mathcal {OT}^{n}_{m(r+1)}}$-hybrid, in the presence of $\mathsf {static}$ $\mathsf {active}$ $\mathsf {adversaries}$, the output of protocol $\pi _{m,n,t}$ and the output of the ideal process involving ${c\mathcal {PAD}_{m,n}}$ are $2^{-n(1-t)/2+2}$ close.

Proof

Let $\mathcal {E}$ denote the environment, and $\mathcal {S}$ be the ideal world adversary. $\mathcal {S}$ starts invoking an internal copy of $\mathcal {A}$ and setting dummy parties $\pi _{\mathsf {A}}$ and $\pi _{\mathsf {B}}$. It then runs an internal execution of $\pi$ between $\mathcal {A}$, $\pi _{\mathsf {A}}$, $\pi _{\mathsf {B}}$, where every incoming communication from $\mathcal {E}$ is forwarded to $\mathcal {A}$ as if it were coming from $\mathcal {A}$’s environment, and any outgoing communication from $\mathcal {A}$ is forwarded to $\mathcal {E}$. The description of $\mathcal {S}$ is in Fig. 6.

Fig. 6.

The ideal adversary for $c\mathcal {PAD}$

We now argue indistinguishability. Let $\mathsf {Dist}$ be the event of having $\mathcal {E}$ distinguishing between the ideal and real process. We bound the probability of $\mathsf {Dist}$ occurring conditioned on corrupting at most one of the parties.

Perfect security for $\mathsf {Bob}$ ($\mathsf {EXEC}_{\pi ,\mathcal {E},\mathcal {A}}\equiv \mathsf {EXEC}_{\phi ,\mathcal {E},\mathcal {S}}$). If $\mathsf {Alice}$ is malicious, then what $\mathcal {E}$ gets to see from $\mathsf {Bob}$’s ideal transcript is $(\mathbf {B}, [\tilde{\mathbf {Q}}_0,\mathbf {Q}_1 \ldots , \mathbf {Q}_r]), (\tilde{\varvec{\sigma }}_i, [\tilde{\mathbf {L}}_i, \tilde{\mathbf {R}}_i])_{i \in [r]})$, where $\mathbf {B}= [\mathbf {L},\mathbf {R}]$ is the input, i.e. $n$ sharings of, say, $\varvec{\sigma }_0$. Matrix $\tilde{\mathbf {Q}}_0$ is consistent with $\mathbf {B}$ and with adversarial choice $\tilde{\mathbf {a}}$ (see Fig. 1), hence by definition of $\mathcal {S}$ and the robustness of $\mathcal {OT}^{n}_{m(r+1)}$, matrix $[\tilde{\mathbf {Q}}_0, \mathbf {Q}_1,\ldots ,\mathbf {Q}_r]$ is exactly distributed as in the real process. Furthermore, if $\tilde{e}_i =1$, then $\tilde{\varvec{\sigma }}_i = \varvec{\sigma }_{i,+}$ is randomly sampled, whereas in the real process $\tilde{\varvec{\sigma }}_i = \varvec{\sigma }_0 \oplus \varvec{\sigma }_i$, with $\varvec{\sigma }_i$ being in the private part of $\mathsf {Bob}$’s transcript. Therefore the proofs of the ideal and real process are identically distributed. We conclude that real and ideal transcripts are identically distributed, and therefore $Pr[\mathsf {Dist}|\mathsf {corruptAlice}] = 0$.

Statistical security for $\mathsf {Alice}$ ($\mathsf {EXEC}_{\pi ,\mathcal {E},\mathcal {A}}\mathop {\approx }\limits ^{s} \mathsf {EXEC}_{\phi ,\mathcal {E},\mathcal {S}}$). For the case $\mathsf {Bob}$ is corrupted, we first note that up to step 5, both processes are identically distributed because $\mathcal {S}$ runs an internal copy of $\pi _{m,n,t}$ using input $[\mathbf {L}_{\mathcal {E}},\mathbf {R}_{\mathcal {E}}]$ specified by $\mathcal {E}$. Next, say $[\mathbf {L}_0, \mathbf {R}_0]$ is $\ell$-thick. Then, if $\ell \le t$, by Proposition 1, the size of $G$ is at least $n(1-t)/2$ with overwhelming probability (in $n$), thus $c\mathcal {PAD}_{m,n}$ does not abort with probability $p \le 2^{-n(1-t)/2}$. By Proposition 1 again the ideal and the real processes abort on thin inputs except with probability $p \le 2^{-n(1-t)/2+2}$ (i.e. we do not care if $\mathcal {E}$ distinguishes in this case). On the other hand, if $\ell > t$ and the internal copy of $\pi _{m,n,t}$ did not abort (if aborts, so does $c\mathcal {PAD}_{m,n}$ by definition of $\mathcal {S}$), then we claim that the output of both processes are identically distributed. This follows from (1) the output matrix $[\mathbf {L}_0,\mathbf {R}_0]$ is extracted by $\mathcal {S}$, and looking closely at the proof of Lemma 1, we deduce (2) if $j \in G$, then for some $i \in [r]$, $\mathsf {Bob}^*$ “decommits” to $\tilde{\varvec{\sigma }}_i \ne \varvec{\delta }_i^j \oplus e_i \cdot \varvec{\delta }_0^j$, the real bit $a^j$ is exactly as the one extracted by $\mathcal {S}$; (3) if $j \notin G$, then $j$ is such that for each $i \in [r]$, $\mathsf {Bob}^*$ is decommitting to $\tilde{\varvec{\sigma }}_i = \varvec{\delta }_i^j \oplus e_i \cdot \varvec{\delta }_0^j$. In this case, the system of equations given in the proof of Lemma 1 collapses to $\mathbf {l}^j = \tilde{\mathbf {l}}^j \ ; \ \mathbf {r}^j = \tilde{\mathbf {r}}^j$. One sees that if $\mathcal {E}$ could tell anything from $\mathbf {a}_{|[n] \backslash G}$, he could equally tell the same before the prove phase, contradicting the security of the underlying $\mathcal {OT}^{n}_{m(r+1)}$.

We have argued $Pr[\mathsf {Dist}| \mathsf {corruptBob}] \le 2^{-n(1-t)/2 +2}$.

Completeness. For the case none of the parties are corrupted, indistinguishability follows from the security of the underlying $\mathcal {OT}^{n}_{m(r+1)}$.

Adding up, $\mathcal {E}$ distinguishes with probability $Pr[\mathsf {Dist}] \le 2^{-n(1-t)/2 + 2}$. This concludes the proof.

4.4 Another Look at the Outer Reduction

Here we take a different perspective for the IKNP reduction that fits better with our partition point of view (as defined in Sect. 4.3). We aim to give some intuition of the underlying ideas, and the reader should by no means take the following discussion as formal arguments.

For an illustrative example let us first look at the attack of the protocol in the IKNP extension. A malicious $\mathsf {Bob}^*$ was giving input matrix $\mathbf {B}$ with all the columns adding up to distinct elements. Consequently its underlying partition is $\mathcal {P}_{IKNP} = \{ \{1\}, \ldots , \{n\}\}$. This structure on $\mathbf {B}$ is such that all but one of the bits of both pads are known to $\mathsf {Bob}^*$. One can see this as splitting the query space $\mathbb {F}_2^n$ as $n$ copies of $\mathbb {F}_2$, namely $Q = \bigoplus _{i=1}^n \mathbb {F}_2$. To search for the secret vector $\mathbf {a}$, one just have to brute-force each summand separately and use the $\mathsf {CRF}$ to compare. After $n \cdot |\mathbb {F}_2| = 2n$ calls the query space is exhausted, i.e. even computationally bounded environments would distinguish between the ideal and the real process.

We want to assign to each possible matrix input $\mathbf {B}= [\mathbf {L},\mathbf {R}]]$ a unique structure of the query space that the environment is forced to use towards distinguishing. In other words, we want to establish a correspondence between the partition implicitly defined in $\mathbf {B}$, and the possible ways to split the query space $Q = \mathbb {F}_2^n$.

Let $\mathcal {P}$ be any partition of $[n]$, express it as $\mathcal {P}= \{ P_{1,1}, \ldots , P_{q_1,1}, \ldots , P_{1,n}, \ldots , P_{q_n,n} \}$ where for $i \in [n]$, $j \in [q_i]$, part $P_{j,i}$ is either empty or is of size $i$ (i.e. there are $q_i$ parts of size $i$ in $\mathcal {P}$). The type of $\mathcal {P}$ is the vector $\mathbf {q}= (q_1, \ldots , q_n) \in \{[n] \cup \{0\}\}^n$. The $\mathbf {q}$-type query space, is the vectorial space $Q_{\mathbf {q}} = \bigoplus _{i =1}^n Q_{\mathbf {q},i}$, where $Q_{\mathbf {q},i}$ is the $i$th block of $Q_{\mathbf {q}}$, and stands for $q_i$ copies of an $\mathbb {F}_2$-vectorial space of dimension $i$.

Thus, the type of $\mathcal {P}_{IKNP}$ corresponds to vector $\mathbf {q}= n \cdot \mathbf {e}_1$, and the query space the environment was using to brute-force $\mathsf {Alice}$’s secret $\mathbf {a}$ is precisely $Q_{n \cdot \mathbf {e}_1}$. On the other hand, honest inputs always define the trivial partition $\mathcal {P}_{H} = \{ [n] \}$ with type $\mathbf {q}= \mathbf {e}_n$, the reduction against a semi-honest receiver in [IKNP03], based security arguing that the environment would have to brute-force $\mathbb {F}_2^n$, which is the query space $Q_{\mathbf {e}_n}$.

Now, the map $f: \mathbf {B}\mapsto Q_{\mathbf {q}}$, where $\mathcal {P}_{\mathbf {B}}$ is $\mathbf {q}$-type, is well defined. To see this, just observe that the relation in $\mathcal {P}^{[n]}$ defined as $\mathcal {P}\sim \mathcal {P}'$ iff “both partitions are of same type” is an equivalence relation, and look at the chain

$$\begin{aligned}&\mathcal {M}_{m \times n} \mathop {\longrightarrow }\limits ^{g_1} \mathcal {P}^{[n]} \mathop {\longrightarrow }\limits ^{g_2} ( \mathcal {P}^{[n]} / \sim ) \mathop {\longrightarrow }\limits ^{g_3} \mathcal {V} \\&\varvec{\varDelta }\mapsto \mathcal {P}_{\varvec{\varDelta }} \mapsto [\mathcal {P}_{\varvec{\varDelta }}]_{\sim } = \mathbf {q}\mapsto Q_{\mathbf {q}} \end{aligned}$$

We see that $f = g_3 \circ g_2 \circ g_1$ is well defined.

From this one can imagine how the reduction would work. $c\mathcal {PAD}$ could check the thickness of the adversarial $\mathbf {B}$, and reject if is less than a fixed parameter $t$. This ensures that the structure of the query space contains at least one block of size big enough, wasting the chances of the environment to search through it in reasonable time. Unfortunately, with this reduction the composition of the inner and outer protocols renders worst choices of parameters.

5 Concluding the Construction

In this section we prove the main result of the paper. For a given security parameter $n$ recall that $t$ is a parameter lying in interval $[\frac{1}{n},1)$, and $r = \lceil \frac{1-t}{2}n \rceil$. Observe that the results of Sect. 4 break down for $t = 1$. This corresponds to a superfluous $\pi _{m,n,1}$ (no checks at all). In other words, a malicious $\mathsf {Bob}^*$ can input any possible bad-formed matrix $\mathbf {B}$ to the IKNP extension, in which case there is no security.

Corollary 1

In the $\mathcal {OT}^{n}_{m(r+1)}$-hybrid, for any $t \in [\frac{1}{n},1)$ protocol $\rho ^{\pi _{m,n,t} / c\mathcal {PAD}_{m,n}}$ $\mathsf {UC}$-$\mathsf {realizes}$ $\mathcal {OT}^{m}_{n}$ in the presence of $\mathsf {static}$ $\mathsf {active}$ $\mathsf {adversaries}$, provided the environment is given access to at most $2^{o(n)}$ queries to a $\mathsf {CRF}$.

Proof

The result follows applying the Composition Theorem of [Can01]. By Claim the error simulation for $\rho$ is $e_{\rho } = 2^{-n/2+ o(n)+2}$, and by Theorem 1 the error simulation for $\pi _{m,n,t}$ is $e_{\pi } = 2^{-n(1-t)/2 +2}$. Using that $(1-t)/2 < 1/2$ if $t>0$, and the transitivity of the composition operation, the error simulation for $\rho ^{\pi _{m,n,t} / c\mathcal {PAD}_{m,n}}$ is $e = e_{\rho } + e_{\pi } \le 2^{-n(1-t)/2 + o(n) +3}$.

5.1 Complexity and Choice of Parameters

For the computational overhead, we emphasize that a cryptographic primitive is still needed to implement the actual extended transfers (we are using the IKNP extension). To implement $m = poly(n)$ transfers, in the test $\mathsf {Alice}$ and $\mathsf {Bob}$ have to XOR $rm(2n+1)$ bits. Thus, per extended OT each participant needs to XOR $O((1-t)n^2)$ bits. The communication complexity (number of bits transferred per OT) turns out to be equivalent. The test adds a constant number of rounds to the overall construction, concretely $2$ extra rounds.

In terms of the seed expansion we can do it better. For a security level of $s$ bits in the reduction, one need roughly $n \approx \frac{2}{1-t}(s+o(n) +3)$ OT seeds. One can measure the quality of the reduction looking at the seed expansion factor $exp(t) = \frac{2}{1-t}$. It is clear that $exp(t)$ tends to $2$, when $t \rightarrow \frac{1}{n}$ and $n \rightarrow \infty$. One only need to halve the security parameter of the IKNP reduction (asymptotically).

Practical choice of parameters are also very efficient. For example, to implement about $1,000,000$ transfers, with security of $s = 64$ bits, setting $t = \frac{1}{16}$, one needs roughly $n \approx 186$ OT seeds. For security level $s=128$, one would need roughly $323$ OT seeds.

5.2 Open Problems

In the reductions for $\rho$ and $\pi$ the security parameter suffers an expansion factor of $2$. We ask whether one can remove this overhead whilst still maintaining security against computational unbounded receivers in the inner protocol.

In the area of secure function evaluation, recently OT has been used to boost the efficiency of two-party protocols [NNOB12] and their counterparts in the multiparty case [LOS14]. A key part on the design of such protocols was the generation of authenticated bits, which in turn borrows techniques from the IKNP extension. It would be interesting to see whether (a suitable modification of) our protocol $\pi$ can be used to generate such authenticated bits. This would immediately give unconditional security (currently both constructions need a random oracle), in terms of efficiency we do not know if this replacement would bring any improvement at all.