A New Approach to Black-Box Concurrent Secure Computation

Secure multiparty computation (MPC) protocols enable mutually distrustful parties to compute a joint functionality on their private inputs without compromising the correctness of the outputs and the privacy of their inputs. They have been studied in both two-party and multi-party cases. General constructions of such protocols for computing any functionality even when a majority of players are adversarial have been long known [16, 49]. In this work, we are interested in MPC protocols that only make a black-box use of cryptographic primitives and maintain security in a concurrent environment with many simultaneous executions.

Black-box constructions. General purpose MPC protocols are often non-black-box in nature. They use the code of the underlying primitives at some stage of the computation, e.g., an NP reduction for general zero-knowledge proofs. Such non-black-use of the primitives is generally undesirable since not only it is computationally expensive, it also renders the protocol useless in situations where such code is not available (e.g., primitives based on hardware-tokens). One therefore seeks black-box constructions of such protocols which use the underlying primitives only in black-box way (i.e., only through their input/output interfaces).

Recently, a number of works have studied black-box constructions of general MPC protocols. Ishai et al. [26] presented the first black-box construction of general purpose MPC based on enhanced trapdoor permutations or homomorphic public-key encryption schemes. Combined with the subsequent work of Haitner [22] on black-box OT, this gives a black-box construction of general MPC based assuming only semi-honest OT [23]. Subsequently, Wee [48] reduced the round complexity of these constructions to \(O(\log ^*n)\), and Goyal [17] to only constant rounds. In the two-party setting, black-box construction were obtained by Pass and Wee [44] in constant-rounds and Ostrovsky et al. [39] in optimal 5-rounds.

Concurrent security. The standard notion of security for MPC, also called stand-alone security considers only a single execution of this protocol. While this is sufficient for many applications, other situations (such as protocol executions over the Internet) require stronger notions of security. Such a more demanding setting, where there may be many protocols executions at the same time, is called the concurrent setting. Unfortunately, it is known that stand-alone security does not necessarily imply security in the concurrent setting [12].

Secure computation in the concurrent setting is quite challenging to define. Canetti [4] proposed the notion of universally composable (UC) security where protocols maintain their strong simulation based security guarantees even in the presence of other arbitrary protocols. Achieving such strong notion of UC-security turned out to be impossible in the plain model [4, 5]. Moreover, Lindell [34, 35] proved that even in the special case where only instantiations of the same protocol are allowed, standard notion of polynomial-time simulation is impossible to achieve. (This is “self composition” and corresponds to the setting we are interested in.)

These strong negative results motivated the study of alternative notions of security; of these, most relevant to us are super-polynomial simulation (SPS) [41], angel-based security [6, 46], and security with shielded oracles [3].

• SPS Security. SPS security is similar to UC security except that the simulator is allowed to run in super-polynomial time. It guarantees that whatever an adversary can do in the real world can also be done in the ideal world in super-polynomial time. While SPS-security is a weaker guarantee, it is still meaningful security for many functionalities, and allows concurrent self-composition in the plain model. (In what follows, by SPS security we mean SPS-security under concurrent self-composition.) Prabhakaran and Sahai [46] provided the initial positive result for SPS security. Although, these early results [2, 33, 36, 46] relied on non-standard/sub-exponential assumptions, Canetti, Lin and Pass achieved this notion under standard polynomial-time assumptions [6] in polynomially many rounds. Soon after, Garg et al. [14] presented a constant round construction. The works of [6, 36, 46] actually get angel-based security, discussed below.

• Angel-Based Security. Angel-based UC security is the same as UC security except that the environment/adversary and the simulator have access to an additional entity—an angel—that allows some judicious use of super-polynomial resources. Angel-based UC security, though weaker than UC security, is meaningful for many settings and implies SPS security. Furthermore, like UC security, it also guarantees composability. As noted above, the works in [6, 36, 46] achieve angel-based security, though only [6] relies on standard polynomial hardness. Subsequently, Goyal et al. [20] presented a \(\widetilde{O}(\log n)\) round construction under the same assumptions.

  Black-box constructions of angel-based secure computation were first presented by Lin and Pass [31] assuming the existence of semi-honest OT, in \(O(\max (n^{\epsilon }, R_{\mathsf {OT}}))\) rounds, where \(\epsilon >0\) is an arbitrary constant and \(R_{\mathsf {OT}}\) is the round complexity of the underlying OT protocol. (Hence, if the underlying OT protocol has only constant round, the round complexity is \(O(n^{\epsilon })\).) Subsequently, Kiyoshima [28] provided a \(\tilde{O}(\log ^2n)\)-round construction under the same assumption.

• Security with Shielded Oracles. Security with shielded oracles, proposed very recently by Broadnax et al. [3], is similar to angel-based security where the environment and the simulator have access to an additional entity—a shielded oracle—that can perform some super-polynomial computation. However, unlike angel-based security, the results of super-polynomial time computation are “shielded away” from the simulator, in the sense that the shielded oracle directly interacts with the ideal functionality; the simulator cannot observe their communication. This notion lies strictly between SPS and angel-based security, and guarantees composability. A constant-round MPC protocol satisfying this notion were also presented in [3]; one of their protocol is black-box and relies on standard polynomial hardness. More specifically, it requires (verifiable perfectly binding) homomorphic commitment schemes and PKE with oblivious public-key generation.

State-of-the-art. All of the constructions of concurrently-secure MPC protocols we have discussed so far, rely on first constructing non-malleable commitment schemes with strong concurrent or UC-security properties; in particular (robust) “CCA-secure commitments” or “coin tossing” or UC-secure commitments. These schemes are then used to build higher level protocols such as OT and general secure computation. However, the concurrent security of these higher level protocols is proven indirectly, by relying on the strong concurrent security of the CCA-secure commitments. While this approach leads to (better) angel-based security, it is quite expensive in terms of rounds, requiring \(\tilde{O}(\log ^2n)\) in [28] for black-box constructions. The work of Broadnax et al. [3] significantly improves this situation by relaxing the angel-based security requirement to SPS with shielded-oracles, and obtains a constant round construction. However, it still needs stronger assumptions (see above) and represents the only approach so far for obtaining constant round black-box constructions. In contrast, much of the results that make non-black-box use of the primitives, can rely on the minimal assumption of semi-honest OT. The approach of Broadnax et al. [3] is still based on first constructing a sufficiently strong commitment scheme with UC properties and using it to obtain OT and general functionalities. It is highly desirable to find new approaches to construct such protocols which have the potential to rely on minimal assumptions in constant rounds.

1.1 Our Contribution

In this work, we seek new approaches for constructing concurrently-secure black-box MPC protocols which can lead to qualitative improvements over existing constructions, such as minimal underlying assumptions, a constant number of rounds, and so on. Towards this goal, we deviate from the existing approaches which focus on incorporating both concurrent security and non-malleability into a single primitive such as (CCA-secure) commitment schemes or coin-tossing. Instead, we take a different approach and focus on incorporating concurrent security into the oblivious transfer functionality. We present a black-box OT protocol satisfying the SPS notion of concurrent-security. We achieve this by using concurrent simulation techniques and non-malleable commitments in a somewhat modular way where (roughly speaking) the former is primarily used for trapdoor extraction/simulation and the latter for independence of committed values. The protocol has constant rounds and relies only on the existence of (constant round) semi-honest OT and standard collision-resistant hash functions (CRHFs).

Having obtained concurrent security for OT, we proceed to construct SPS-secure MPC protocols for all functionalities. Our method does not require any additional assumptions, and maintains the black-box and constant round properties of the original OT protocol. Consequently, we obtain SPS-secure constant-round black-box MPC under much weaker assumptions than [3]. On the flip side, our work achieves a weaker security notion than [3].

Theorem 1

(Informal). Assume the existence of constant-round semi-honest oblivious transfer protocols and collision-resistant hash functions. Then, there exists a constant-round black-box construction of concurrently secure MPC protocol that achieve SPS security.

The formal statement is given as Theorem 3 in Sect. 5.

1.2 Other Related Work

Other than the works mentioned above, there are several works that study SPS security/angel-based security. For SPS-security, Pass et al. [43] present a constant-round non-black-box construction of MPC from constant-round semi-honest OT. Dachman-Soled et al. and Venkitasubramaniam [11, 47] present a non-black-box construction that satisfies adaptive security. And very recently, Badrinarayanan et al. [1] present a non-black-box 3-round construction assuming sub-exponential hardness assumptions. For angel-based security, Kiyoshima et al. [29] present a constant-round black-box construction albeit under a sub-exponential hardness assumption, and Hazay and Venkitasubramaniam [25] present a non-black-box construction that achieves adaptive security.

We have not discussed several works that focus on other notions of concurrent security such as input-indistinguishable computation, bounded concurrent composition, and multiple ideal-query model [18, 37, 42].

Black-box constructions have been extensively explored for several other primitives such as non-malleable/CCA-secure encryption, non-malleable commitments, zero-knowledge proofs and so on (e.g., [9, 10, 19, 21, 40, 45]). For concurrent OT, Garay and MacKenzie [13] presented a protocols for independent inputs under the DDH assumption, and Garg et al. [15] showed the impossibility of this task for general input distributions.

We obtain our MPC protocol in two steps. First, we construct a constant-round black-box construction of a SPS-secure concurrent OT protocol. Second, we compose this OT protocol with an existing constant-round OT-hybrid UC-secure MPC protocol. We elaborate on each step below.

We remark that we consider concurrent security in the interchangeable-roles setting. So, in the case of OT, the adversary can participate a session as the sender while concurrently participating another session as the receiver.

2.1 Constant-Round Black-Box Concurrent OT

Our starting point is the (super-constant-round) black-box concurrent OT protocol of Lin and Pass [31], which is secure under angel-based security and makes only black-box use of semi-honest OT protocols. Our approach is to modify their protocol so that it has only constant number of rounds (while degrading security from angel-based security to SPS security).

Let us first recall the OT protocol of [31]. At a high level, it uses a semi-honest OT protocol in the black-box way in a similar manner to the stand-alone black-box OT of Haitner et al. [23] does. Specifically, the OT protocol of [31] proceeds roughly as follows.

1. 1.

   First, the sender S and the receiver R execute many instances of a semi-honest OT protocol in parallel, where in each instance S and R use the inputs and the randomness that are generated by a coin-tossing protocol. (S and R execute two instances of coin tossing for each instance of OT; the sender obtains random coin in the first coin tossing and the receiver obtains random coin in the second coin tossing.)

2. 2.

   Next, S and R do a simple trick called OT combiner, which allows them to execute an OT with their real inputs securely when most of the OT instances in the previous step are correctly executed. To check that most of the OT instances in the previous step were indeed correctly executed, S and R do the well-known cut-and-choose trick, where S (resp., R) chooses a constant fraction of the OT instances randomly and R (resp., S) reveals the input and randomness that it used in those instances so that S (resp., R) can verity whether R executed those instances correctly.

(Actually, the underlying OT protocol is required to be secure against malicious senders, but we ignore this requirement in this overview.)

The OT protocol of [31] has more than constant number of rounds because it uses CCA-secure commitment schemes [6, 7] in the coin-tossing part of the protocol and existing constructions of CCA-secure commitment schemes have more than constant number of rounds under standard assumptions.^{Footnote 1} Key observations by the authors of [31] are that CCA-secure commitment schemes can be used to obtain a “concurrently secure” coin tossing protocol,^{Footnote 2} and that their OT protocol is concurrently secure when its coin-tossing part is concurrently secure.

To obtain a constant-round protocol, we need to remove the CCA-secure commitments from the protocol of [31]. A naive approach is to simply replace the CCA-secure commitments with (concurrent) non-malleable commitments, which provide weaker security than CCA-secure ones but are known to have a constant-round black-box instantiation under the existence of one-way functions [19]. However, this approach does not work because, as mentioned by Lin and Pass [31], non-malleable commitment schemes only lead to “parallel secure” coin tossing protocols^{Footnote 3} and the parallel security of the coin tossing protocol is insufficient for proving the concurrent security of the OT protocol of [31].

At a high level, we remove the CCA-secure commitments from the protocol of [31] as follows. Our starting idea is to prove the concurrent security of the OT protocol of [31] without relying on the concurrent security of the coin tossing part (and therefore without using CCA-secure commitments there). To prove the concurrent security in this way, we modify the protocol of [31] so that it uses non-malleable commitments in a similar manner to the constant-round (non-black-box) SPS-secure concurrent MPC protocol of Garg et al. [14] does. Informally speaking, the protocol of Garg et al. [14] uses non-malleable commitments when each party commits to a witness for the fact that the “trapdoor statement” is false, where the trapdoor statement is a statement about the transcript and it is guaranteed that any adversary cannot “cheat” in the protocol when the trapdoor statement is false. With this use of non-malleable commitments, the concurrent security of the protocol of Garg et al. [14] is proven in two steps:

1. 1.

   First, it is shown that in the real experiment (where an adversary interacts with honest parties in multiple sessions of the protocol concurrently), the non-malleable commitment from the adversary in each session is indeed a commitment of a valid witness for the fact that the trapdoor statement is false. (This is guaranteed by a zero-knowledge proof in the protocol).

2. 2.

   Second, it is shown that if the non-malleable commitment in a session is indeed a commitment of a valid witness (which implies that the trapdoor statement is false in that session, which in turn implies that the adversary cannot “cheat” in that session), it is possible to switch the honest parties in that session with the simulator in an indistinguishable way, and furthermore this switch does not affect the non-malleable commitments in the other sessions (i.e., their committed values remain to be valid witnesses). (The latter is guaranteed by non-malleability of the non-malleable commitments^{Footnote 4}.)

3. 3.

   Now, the concurrent security follows from the above two since the honest parties can be switched to the simulator in all the sessions by repeatedly using what is shown in the second part.

Following this approach by Garg et al. [14], we first identify the trapdoor statement of the OT protocol of Lin and Pass [31] and then add non-malleable commitments to their protocol in such a way that the trapdoor statement is false whenever the committed values of the non-malleable commitments satisfy a specific condition. With this modification, we can prove the concurrent security of the OT protocol of [31] without relying on the concurrent security of coin tossing by following the approach of [14] outlined above.

Remark 1

It is not straightforward to use the approach of Garg et al. [14] in the OT protocol of Lin and Pass [31] since its trapdoor statement does not have a simple witness for the fact that the statement is false. Because of this difficulty, we do not use non-malleable commitments to commit to a witness; rather, we use them in such a way that there exists a condition on the committed values of the non-malleable commitments such that the trapdoor statement is false as long as this condition holds. For details, see Sect. 4 (in particular, Definitions 5 and 6 and Claims 3 and 4).

2.2 Composition of OT with OT-Hybrid MPC

We next compose our OT protocol with a OT-hybrid UC-secure MPC protocol (i.e., replace each invocation of the ideal OT functionality in the latter with an execution of the former), thereby obtaining a MPC protocol in the plain model. A problem is that the security of the resultant MPC protocol cannot be derived trivially from those of the components since SPS security does not guarantee composability. Hence, we prove the security by analyzing the MPC protocol directly. In essence, what we do is to observe that the security proof for our OT protocol (which consists of a hybrid argument from the real world to the ideal world) still works even after the OT protocol is composed with a OT-hybrid MPC protocol, and in particular we observe that the condition on the committed values of the non-malleable commitments (which is mentioned in Sect. 2.1) remains to hold in each session even after switching the OT-hybrid MPC protocol in any session to simulation. Fortunately, this can be observed easily thanks to the non-malleability of the non-malleable commitments, so we can prove the concurrent security of our MPC protocol under SPS security easily.

We denote the security parameter by \(n\). We assume familiarity with basic cryptographic protocols (e.g., commitment schemes and oblivious transfer protocols).

3.1 Non-malleable Commitment Schemes

We recall the definition of non-malleable commitment schemes from [30]. Let \(\langle C,R \rangle \) be a tag-based commitment scheme (i.e., a commitment scheme that takes a \(n\)-bit string—a tag—as an additional input). For any man-in-the-middle adversary \(\mathcal {M}\), consider the following experiment. On input security parameter \(1^n\) and auxiliary input \(z\in \{0,1 \}^*\), \(\mathcal {M}\) participates in one left and one right interactions simultaneously. In the left interaction, \(\mathcal {M}\) interacts with the committer of \(\langle C,R \rangle \) and receives a commitment to value v using identity \(\mathsf {id}\in \{0,1 \}^{n}\) of its choice. In the right interaction, \(\mathcal {M}\) interacts with the receiver of \(\langle C,R \rangle \) and gives a commitment using identity \(\widetilde{\mathsf {id}}\) of its choice. Let \(\widetilde{v}\) be the value that \(\mathcal {M}\) commits to on the right. If the right commitment is invalid or undefined, \(\widetilde{v}\) is defined to be \(\bot \). If \(\mathsf {id}= \widetilde{\mathsf {id}}\), value \(\widetilde{v}\) is also defined to be \(\bot \). Let \(\mathsf {mim}(\langle C,R \rangle , \mathcal {M}, v, z)\) be a random variable representing \(\widetilde{v}\) and the view of \(\mathcal {M}\) in the above experiment.

Definition 1

A commitment scheme \(\langle C,R \rangle \) is non-malleable if for any \(\textsc {ppt} \) adversary \(\mathcal {M}\), the following are computationally indistinguishable.

• \(\{\mathsf {mim}(\langle C,R \rangle , \mathcal {M}, v, z) \}_{n\in \mathbb {N}, v\in \{0,1 \}^{n},v'\in \{0,1 \}^{n},z\in \{0,1 \}^*}\)

• \(\{\mathsf {mim}(\langle C,R \rangle , \mathcal {M}, v',z) \}_{n\in \mathbb {N}, v\in \{0,1 \}^{n},v'\in \{0,1 \}^{n},z\in \{0,1 \}^*}\)

The above definition can be generalized naturally so that the adversary gives multiple commitments in parallel in the right interaction. The non-malleability in this generalized setting is called parallel non-malleability. (It is known that this “one-many” definition implies the “many-many” one, where the adversary receives multiple commitments in the left session [32].)

Robust Non-malleability. We next recall the definition of k-robust non-malleability (a.k.a. non-malleability w.r.t. k-round protocols) [30]. Consider a man-in-the-middle adversary \(\mathcal {M}\) that participates in one left interaction—communicating with a machine B—and one right interaction—communicating with a receiver a commitment scheme \(\langle C,R \rangle \). As in the standard definition of non-malleability, \(\mathcal {M}\) can choose the identity in the right interaction. We denote by \(\mathsf {mim}^{B,\mathcal {M}}_{\langle C,R \rangle }(y,z)\) the random variable consisting of the view of \(\mathcal {M}(z)\) in a man-in-the-middle execution when communicating with B(y) on the left and an honest receiver on the right, combined with the value \(\mathcal {M}(z)\) commits to on the right. Intuitively, \(\langle C,R \rangle \) is non-malleable w.r.t. B if \(\mathsf {mim}^{B,\mathcal {M}}_{\langle C,R \rangle }(y_1,z)\) and \(\mathsf {mim}^{B,\mathcal {M}}_{\langle C,R \rangle }(y_2,z)\) are indistinguishable whenever interactions with \(B(y_1)\) and \(B(y_2)\) are indistinguishable.

Definition 2

Let \(\langle C,R \rangle \) be a commitment scheme and B be a \(\textsc {ppt} \) ITM. We say that a commitment scheme \(\langle C,R \rangle \) is non-malleable w.r.t. B if the following holds: For every two sequences \(\{y_{n}^1 \}_{n\in \mathbb {N}}\) and \(\{y_{n}^2 \}_{n\in \mathbb {N}}\) such that \(y_{n}^1,y_{n}^2\in \{0,1 \}^{n}\), if it holds that for any \(\textsc {ppt} \) ITM \(\mathcal {A}\),

it also holds that for any \(\textsc {ppt} \) man-in-the-middle adversary \(\mathcal {M}\),

\(\langle C,R \rangle \) is k-robust if \(\langle C,R \rangle \) is non-malleable w.r.t. any machine that interacts with the adversary in k rounds. We define parallel k-robustness naturally.

Black-Box Instantiation. There exists a constant-round black-box construction of a parallel (actually, concurrent) non-malleable commitment scheme based on one-way functions [19]. In the full version of this paper, we show that any parallel non-malleable commitment can be transformed into a parallel k-robust non-malleable one in the black-box way by using collision-resistant hash functions (more precisely, by using statistically hiding commitment schemes, which can be constructed from collision-resistant hash functions). If k is constant, the round complexity increases only by a constant factor in this transformation.

3.2 UC Security and Its SPS Variant

We next recall the definition of UC security [4] and its SPS variant [2, 14, 46]. A part of the text below is taken from [14]. (We assume that the readers are familiar with the UC framework. A brief overview can be found in, e.g., [7].)

UC Security. Recall that in the UC framework, the model for protocol execution consists of the environment \(\mathcal {Z}\), the adversary \(\mathcal {A}\), and the parties running protocol \(\pi \). In this paper, we consider static adversaries and assume the existence of authenticated communication channels. Let \({\textsc {EXEC}}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z)\) denote a random variable for the output of \(\mathcal {Z}\) on security parameter \(n\in \mathbb {N}\) and input \(z\in \{0,1 \}^{*}\) with a uniformly chosen random tape. Let \({\textsc {EXEC}}_{\pi ,\mathcal {A},\mathcal {Z}}\) denote the ensemble \(\{{\textsc {EXEC}}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z) \}_{n\in \mathbb {N}, z\in \{0,1 \}^{*}}\).

The security of a protocol \(\pi \) is defined using the ideal protocol. In the ideal protocol, all the parties simply hand their inputs to the ideal functionality \(\mathcal {F}\), which carries out the desired task securely and gives outputs to the parties; the parties then forward these outputs to \(\mathcal {Z}\). The adversary \(\mathcal{S}im\) in the execution of the ideal protocol is often called the simulator. Let \(\pi (\mathcal {F})\) denote the ideal protocol for functionality \(\mathcal {F}\).

We say that a protocol \(\pi \) emulates protocol \(\phi \) if for any adversary \(\mathcal {A}\) there exists an adversary \(\mathcal{S}im\) such that no environment \(\mathcal {Z}\), on any input, can tell whether it is interacting with \(\mathcal {A}\) and parties running \(\pi \) or it is interacting with \(\mathcal{S}im\) and parties running \(\phi \). We say that \(\pi \) securely realizes an ideal functionality \(\mathcal {F}\) if it emulates the ideal protocol \(\varPi (\mathcal {F})\).

UC Security with Super-Polynomial Simulation. UC-SPS security is a relaxed notion of UC security where the simulator is given access to super-polynomial computational resources.

Definition 3

Let \(\pi \) and \(\phi \) be protocols. We say that \(\pi \) UC-SPS-emulates \(\phi \) if for any adversary \(\mathcal {A}\) there exists a super-polynomial-time adversary \(\mathcal{S}im\) such that for any environment \(\mathcal {Z}\) that obeys the rules of interaction for UC security, we have \({\textsc {EXEC}}_{\phi , \mathcal{S}im, \mathcal {Z}} \approx {\textsc {EXEC}}_{\pi , \mathcal {A}, \mathcal {Z}}\).

Definition 4

Let \(\mathcal {F}\) be an ideal functionality and let \(\pi \) be a protocol. We say that \(\pi \) UC-SPS-realizes \(\mathcal {F}\) if \(\pi \) UC-SPS-emulates the ideal process \(\varPi (\mathcal {F})\).

The multi-session extension of an ideal functionality. When showing concurrent security of a protocol \(\pi \) under SPS security, we need to construct a simulator in a setting where parties execute \(\pi \) concurrently. To consider the simulator in this setting, we use a multi-session extension of an ideal functionality [8]. Roughly speaking, the multi-session extension \(\hat{\mathcal {F}}\) of an ideal functionality \(\mathcal {F}\) is a functionally that internally runs multiple copies of \(\mathcal {F}\).

In this section, we prove the following theorem.

Theorem 2

Assume the existence of constant-round semi-honest oblivious transfer protocols and collision-resistant hash functions. Let \(\mathcal {F}_{\mathrm OT}\) be the ideal oblivious transfer functionality (Fig. 1) and \(\hat{\mathcal {F}}_{\mathrm OT}\) be its multi-session extension. Then, there exists a constant-round protocol that UC-SPS realizes \(\hat{\mathcal {F}}_{\mathrm OT}\), and it uses the underlying primitives in the black-box way.

4.1 Protocol Description

In our protocol, we use the following building blocks.

• A two-round statistically binding commitment \(\mathsf {Com}\) and a four-round statistically binding extractable commitment \(\mathsf {ExtCom}\), both of which can be constructed from one-way functions in the black-box way [24, 38, 44].

• A O(1)-round OT protocol \(\mathsf {mS}\hbox {-}\mathsf {OT}\) that is secure against malicious senders and semi-honest receivers.^{Footnote 5} As shown in [23], such a OT protocol can be obtained from any semi-honest one in the black-box way.

• A O(1)-round parallel non-malleable commitment \(\mathsf {NMCom}\) that is parallel k-robust for sufficiently large constant k. (Concretely, we require that k is larger than the round complexity of the above three building blocks.) As remarked in Sect. 3.1, we show in the full version of this paper that such a non-malleable commitment scheme can be constructed from collision-resistant hash functions in the black-box way.

Our OT protocol \(\varPi _{\mathrm {OT}}\) is described below. As explained in Sect. 2.1, (1) our protocol is based on the OT protocol of Lin and Pass [31], which roughly consists of coin-tossing, semi-honest OT, OT combiner, and cut-and-choose, and (2) our protocol additionally uses non-malleable commitments, which will be used in the security proof to argue that the adversary cannot make the “trapdoor statement” true even in the concurrent setting. Below, we give intuitive explanations in italic.

• Inputs: The input to the sender S is \(v_0, v_1 \in \{0,1 \}^{n}\). The input to the receiver R is \(u\in \{0,1 \}\).

• Stage 1: (Preprocess for cut-and-choose)

1. 1.

   S commits to a random subset \(\varGamma _S \subset [11n]\) of size \(n\) by using \(\mathsf {Com}\).

2. 2.

   R commits to a random subset \(\varGamma _R \subset [11n]\) of size \(n\) by using \(\mathsf {Com}\).

Comment:As in the OT protocol of Lin and Pass [31], the subsets that will be used in the cut-and-choose stages are committed in advance to prevent selective opening attacks.

• Stage 2:

1. 1.

   (Coin tossing for S) S commits to random strings \(\varvec{a}^S = (a_1^S, \ldots , a_{11n}^S)\) by using \(\mathsf {Com}\); let \(d_1^S, \ldots , d_{11n}^S\) be the decommitments. R then sends random strings \(\varvec{b}^S = (b_1^S, \ldots , b_{11n}^S)\) to S. S then defines \(\varvec{r}^S = (r_1^S, \ldots , r_{11n}^S)\) by \(r_i^S {\mathop {=}\limits ^\mathrm{def}}a_i^S \oplus b_i^S\) for each \(i\in [11n]\) and parses \(r_i^S\) as \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\) for each \(i\in [11n]\).

2. 2.

   (Coin tossing for R) R commits to random strings \(\varvec{a}^R = (a_1^R, \ldots , a_{11n}^R)\) by using \(\mathsf {Com}\); let \(d_1^R, \ldots , d_{11n}^R\) be the decommitments. S then sends random strings \(\varvec{b}^R = (b_1^R, \ldots , b_{11n}^R)\) to R. R then defines \(\varvec{r}^R = (r_1^R, \ldots , r_{11n}^R)\) by \(r_i^R {\mathop {=}\limits ^\mathrm{def}}a_i^R \oplus b_i^R\) for each \(i\in [11n]\) and parses \(r_i^R\) as \(c_i \!\parallel \!\tau _i^R\) for each \(i\in [11n]\).

• Stage 3: (mS-OTs with random inputs)

  S and R execute \(11n\) instances of \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in parallel. In the i-th instance, S uses \((s_{i,0}, s_{i,1})\) as the input and \(\tau _i^S\) as the randomness, and R uses \(c_i\) as the input and \(\tau _i^R\) as the randomness, where \(\{s_{i,0}, s_{i,1}, \tau _i^S \}_i\) and \(\{c_i, \tau _i^R \}_i\) are the random coins that were obtained in Stage 2. The output to R is denoted by \(\widetilde{s}_{1}, \ldots , \widetilde{s}_{11n}\), which are supposed to be equal to \(s_{1,c_1}, \ldots , s_{11n,c_{11n}}\).

• Stage 4: (NMCom and ExtCom for checking honesty of R )

1. 1.

   R commits to \((a_1^R, d_1^R), \ldots (a_{11n}^R, d_{11n}^R)\) using \(\mathsf {NMCom}\). Let \(e_1^R, \ldots , e_{11n}^R\) be the decommitments.

2. 2.

   R commits to \((a_1^R, d_1^R, e_1^R), \ldots (a_{11n}^R, d_{11n}^R, e_{11n}^R)\) using \(\mathsf {ExtCom}\).

Comment: Roughly, the commitments in this stage, along with the cut-and-choose in the next stage, will be used in the security proof to argue that even cheating  R  must behave honestly in most instances of \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in Stage 3. A key point is that given the values that are committed to in \(\mathsf {NMCom}\) or \(\mathsf {ExtCom}\) in this stage, one can obtain the random coins that R obtained in Stage 2 and thus can check whether R behaved honestly in Stage 3.

• Stage 5: (Cut-and-choose against R )

1. 1.

   S reveals \(\varGamma _S\) by decommitting the \(\mathsf {Com}\) commitment in Stage 1-1.

2. 2.

   For every \(i\in \varGamma _S\), R reveals \((a_i^R, d_i^R, e_i^R)\) by decommitting the i-th \(\mathsf {ExtCom}\) commitment in Stage 4.

3. 3.

   For every \(i\in \varGamma _S\), S checks the following.

• \(((a_i^R, d_i^R), e_i^R)\) is a valid decommitment of the i-th \(\mathsf {NMCom}\) commitment in Stage 4.

• \((a_i^R, d_i^R)\) is a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-2.

• R executed the i-th mS-OT in Stage 3 honestly using \(c_i \!\parallel \!\tau _i^R\), which is obtained from \(r_i^R = a_i^R \oplus b_i^R\) as specified by the protocol.

Comment: In other words, for each index that it randomly selected in Stage 1, Schecks whether R behaved honestly in Stages 3 and 4 on that index.

• Stage 6: (OT combiner) Let \(\varDelta := [11n]{\setminus }\varGamma _S\).

1. 1.

   R sends \(\alpha _i := u \oplus c_i\) to S for every \(i\in \varDelta \).

2. 2.

   S computes a \((6n+1)\)-out-of-\(10n\) secret sharing of \(v_0\), denoted by \(\varvec{\rho }_0 = (\rho _{0,i})_{i\in \varDelta }\), and computes a \((6n+1)\)-out-of-\(10n\) secret sharing of \(v_1\), denoted by \(\varvec{\rho }_1 = (\rho _{1,i})_{i\in \varDelta }\). Then, S sends \(\beta _{b,i} := \rho _{b,i} \oplus s_{i, b\oplus \alpha _i}\) to R for every \(i\in \varDelta \), \(b\in \{0,1 \}\).

3. 3.

   R computes \(\widetilde{\rho }_i := \beta _{u,i} \oplus \widetilde{s}_i\) for every \(i\in \varDelta \). Let \(\varvec{\widetilde{\rho }} := (\widetilde{\rho }_i)_{i\in \varDelta }\).

Comment: In this stage, S and R execute OT with their true inputs by using the outputs of \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in Stage 3. Roughly speaking, this stage is secure as long as most instances of \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in Stage 3 are correctly executed.

• Stage 7: (NMCom and ExtCom for checking honesty of S )

1. 1.

   S commits to \((a_1^S, d_1^S), \ldots (a_{11n}^S, d_{11n}^S)\) using \(\mathsf {NMCom}\). Let \(e_1^S, \ldots , e_{11n}^S\) be the decommitments.

2. 2.

   R commits to \((a_1^S, d_1^S, e_1^S), \ldots (a_{11n}^S, d_{11n}^S, e_{11n}^S)\) using \(\mathsf {ExtCom}\).

• Stage 8: (Cut-and-choose against S )

1. 1.

   R reveals \(\varGamma _R\) by decommitting the \(\mathsf {Com}\) commitment in Stage 1-2.

2. 2.

   For every \(i\in \varGamma _R\), S reveals \((a_i^S, d_i^S, e_i^S)\) by decommitting the i-th \(\mathsf {ExtCom}\) commitment in Stage 7.

3. 3.

   For every \(i\in \varGamma _R\), R checks the following.

• \(((a_i^S, d_i^S), e_i^S)\) is a valid decommitment of the i-th \(\mathsf {NMCom}\) commitment in Stage 7.

• \((a_i^S, d_i^S)\) is a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-1.

• S executed the i-th mS-OT in Stage 3 honestly using \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\), which is obtained from \(r_i^S = a_i^S \oplus b_i^S\) as specified by the protocol.

• Output: R outputs \(\mathsf {Value}(\varvec{\widetilde{\rho }}, \varGamma _R\cap \varDelta )\), where \(\mathsf {Value}(\cdot , \cdot )\) is the function that is defined in Fig. 2.

Comment: As in the OT protocol of Lin and Pass [31], a carefully designed reconstruction procedure \(\mathsf {Value}(\cdot , \cdot )\) is used here so that the simulator can extract correct implicit inputs from cheating S by obtaining sharing that is sufficiently “close” to \(\varvec{\widetilde{\rho }}\).

4.2 Simulator \(\mathcal{S}im_{\mathrm {OT}}\)

To prove the security of \(\varPi _{\mathrm {OT}}\), we consider the following simulator \(\mathcal{S}im_{\mathrm {OT}}\). Recall that our goal is to prove that \(\varPi _{\mathrm {OT}}\) US-SPS realizes the multi-session extension of \(\mathcal {F}_{\mathrm OT}\). We therefore consider a simulator that works against adversaries that participate in multiple sessions of \(\varPi _{\mathrm {OT}}\) both as senders and as receivers.

Let \(\mathcal {Z}\) be any environment, \(\mathcal {A}\) be any adversary that participates in multiple sessions of \(\varPi _{\mathrm {OT}}\). Our simulator \(\mathcal{S}im_{\mathrm {OT}}\) internally invokes \(\mathcal {A}\) and simulates each of the sessions for \(\mathcal {A}\) as follows.

When  R  is corrupted: In a session where the receiver R is corrupted, \(\mathcal{S}im_{\mathrm {OT}}\) simulates the sender S for \(\mathcal {A}\) by extracting the implicit input \(u^*\in \{0,1 \}\) from \(\mathcal {A}\). During the simulation, \(\mathcal{S}im_{\mathrm {OT}}\) extracts the committed subset and random coins in Stages 1 and 2 by brute force; the former extraction is needed to execute most instances \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in Stage 3 with true randomness (which is crucial to use their security in the analysis), and the latter extraction is needed to infer what information \(\mathcal {A}\) obtained in the \(\mathsf {mS}\hbox {-}\mathsf {OT}\) instances in Stage 3 (which is crucial to extract the implicit input \(u^*\in \{0,1 \}\) from \(\mathcal {A}\)).

Concretely, \(\mathcal{S}im_{\mathrm {OT}}\) simulates S for \(\mathcal {A}\) as follows. From Stage 1 to Stage 5, \(\mathcal{S}im_{\mathrm {OT}}\) interacts with \(\mathcal {A}\) in the same way as an honest S except for the following.

• From the \(\mathsf {Com}\) commitments from \(\mathcal {A}\) in Stages 1 and 2, the committed subset \(\varGamma _R\) and the committed strings \(\varvec{a}^R = (a_1^R, \ldots , a_{11n}^R)\) are extracted by brute force. \(\mathcal{S}im_{\mathrm {OT}}\) then defines \(\varvec{r}^R = (r_1^R, \ldots , r_{11n}^R)\) by \(r_i^R {\mathop {=}\limits ^\mathrm{def}}a_i^R \oplus b_i^R\) for each \(i\in [11n]\) and parses \(r_i^R\) as \(c_i \!\parallel \!\tau _i^R\) for each \(i\in [11n]\). (Notice that \(\varvec{r}^R\) is the outcome of the coin-tossing that \(\mathcal {A}\) must have obtained.)

• In Stage 3, the i-th mS-OT is executed with a random input and true randomness rather than with \((s_{i,0}, s_{i,1})\) and \(\tau _i^S\) for every \(i\not \in \varGamma _R\).

In Stage 6, \(\mathcal{S}im_{\mathrm {OT}}\) interacts with \(\mathcal {A}\) as follows.

1. 1.

   Receive \(\{\alpha _i \}_{i\in \varDelta }\) from \(\mathcal {A}\) in Stage 6-1.

2. 2.

   Determine the implicit input \(u^*\) of \(\mathcal {A}\) as follows. Let \(I_0, I_1\) be the sets such that for \(b\in \{0,1 \}\) and \(i\in \varDelta \), we have \(i \in I_b\) if and only if:

   • \(i\in \varGamma _R\), or

   • \(\mathcal {A}\) did not execute the i-th mS-OT in Stage 3 honestly using \(c_i \!\parallel \!\tau _i^R\) as the input and randomness, or

   • \(c_i = b \oplus \alpha _i\), and \(\mathcal {A}\) executed the i-th mS-OT in Stage 3 honestly using \(c_i \!\parallel \!\tau _i^R\) as the input and randomness.

   Then, define \(u^*\) by \(u^* {\mathop {=}\limits ^\mathrm{def}}0\) if \(|I_0 | \ge 6n+1\) and \(u^* {\mathop {=}\limits ^\mathrm{def}}1\) otherwise. (Roughly, \(|I_b |\) is the number of strings that \(\mathcal {A}\) can obtain out of \(\{s_{i,b\oplus \alpha _i} \}_{i\in \varDelta }\) by requiring S to reveal them in Stage 8, by cheating in mS-OT, or by executing mS-OT honestly with input \(b\oplus \alpha _i\). We remind the readers that \(\{s_{i,b\oplus \alpha _i} \}_{i\in \varDelta }\) are the strings that are used to mask \(\varvec{\rho }_b = (\rho _{b,i})_{i\in \varDelta }\) in Stage 6.)

3. 3.

   Send \(u^*\) to the ideal functionality and obtains \(v^*\).

4. 4.

   Subsequently, interact with \(\mathcal {A}\) in the same way as an honest S assuming that the inputs to S are \(v_{u^*} = v^*\) and random \(v_{1-u^*}\).

From Stage 7 to Stage 8, \(\mathcal{S}im_{\mathrm {OT}}\) interacts with \(\mathcal {A}\) in the same way as an honest S except that in Stage 7, an all-zero string is committed in the i-th \(\mathsf {NMCom}\) rather than \((a_i^S, d_i^S)\) for every \(i\not \in \varGamma _R\), and an all-zero string is committed in the i-th \(\mathsf {ExtCom}\) rather than \((a_i^S, d_i^S, e_i^S)\) for every \(i\not \in \varGamma _R\).

When S is corrupted: In a session where the sender S is corrupted, \(\mathcal{S}im_{\mathrm {OT}}\) simulates the receiver R for \(\mathcal {A}\) by extracting the implicit input \(v_0^*, v_1^*\) from \(\mathcal {A}\). During the simulation, \(\mathcal{S}im_{\mathrm {OT}}\) extracts the committed subset and random coins in Stages 1 and 2 by brute force; the former extraction is needed to execute most instances \(\mathsf {mS}\hbox {-}\mathsf {OT}\) in Stage 3 with true randomness (which is crucial to use their security in the analysis), and the latter extraction is needed to learn what input \(\mathcal {A}\) used in the \(\mathsf {mS}\hbox {-}\mathsf {OT}\) instances in Stage 3 (which is crucial to extract the implicit input \(v_0^*, v_1^*\) from \(\mathcal {A}\)).

Concretely, \(\mathcal{S}im_{\mathrm {OT}}\) simulates R for \(\mathcal {A}\) as follows. \(\mathcal{S}im_{\mathrm {OT}}\) interacts with \(\mathcal {A}\) in the same way as an honest R in all the stages except for the following.

• From the \(\mathsf {Com}\) commitment from \(\mathcal {A}\) in Stage 1, the committed subset \(\varGamma _S\) is extracted by brute force.

• In Stage 3, the i-th mS-OT is executed with a random input and true randomness rather than with \(c_i\) and \(\tau _i^R\) for every \(i\not \in \varGamma _S\).

• In Stage 4, an all-zero string is committed in the i-th \(\mathsf {NMCom}\) rather than \((a_i^S, d_i^S)\) for every \(i\not \in \varGamma _S\), and an all-zero string is committed in the i-th \(\mathsf {ExtCom}\) rather than \((a_i^S, d_i^S, e_i^S)\) for every \(i\not \in \varGamma _S\).

• In Stage 6, \(\alpha _i\) is a random bit rather than \(\alpha _i = u \oplus c_i\) for every \(i\in \varDelta \), and \(\widetilde{\rho }_i\) is not computed for any \(i\in \varDelta \).

Then, \(\mathcal{S}im_{\mathrm {OT}}\) determines the implicit inputs \(v_0^*, v_1^*\) of \(\mathcal {A}\) as follows.

1. 1.

   From the \(\mathsf {Com}\) commitments from \(\mathcal {A}\) in Stage 2, extract the committed strings \(\varvec{a}^S = (a_1^S, \ldots , a_{11n}^S)\) by brute force.

2. 2.

   Define \(\varvec{r}^S = (r_1^S, \ldots , r_{11n}^S)\) by \(r_i^S {\mathop {=}\limits ^\mathrm{def}}a_i^S \oplus b_i^S\) for each \(i\in [11n]\) and parse \(r_i^S\) as \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\) for each \(i\in [11n]\). (Notice that \(\varvec{r}^S\) is the outcome of the coin-tossing that \(\mathcal {A}\) must have obtained.)

3. 3.

   Define \(\varvec{\rho }^{\mathsf {ext}}_b = (\rho ^{\mathsf {ext}}_{b,i})_{i\in \varDelta }\) for each \(b\in \{0,1 \}\) as follows: \(\rho ^{\mathsf {ext}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\beta _{b,i} \oplus s_{i,b\oplus \alpha _i}\) if \(\mathcal {A}\) executed the i-th mS-OT in stage 3 honestly using \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\), and \(\rho ^{\mathsf {ext}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\bot \) otherwise.

4. 4.

   For each \(b\in \{0,1 \}\), define \(v_b^* {\mathop {=}\limits ^\mathrm{def}}\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_b, \varGamma _R\cap \varDelta )\).

Then, \(\mathcal{S}im_{\mathrm {OT}}\) sends \(v_0^*, v_1^*\) to the ideal functionality.

4.3 Proof of Indistinguishability

We show the indistinguishability by using a hybrid argument. Before defining hybrid experiments, we define special messages, which we use in the definitions of the hybrid experiments. (Essentially, they are the messages on which the simulator applies brute-force extractions.)

• first special message is the \(\mathsf {Com}\) commitment in Stage 1-1.

• second special message is the \(\mathsf {Com}\) commitment in Stage 1-2.

• third special message is the \(\mathsf {Com}\) commitments in Stage 2-1.

• fourth special message is the \(\mathsf {Com}\) commitments in Stage 2-2.

Hybrid Experiments. Now, we define hybrid experiments. Let m denote an upper bound on the number of the sessions that \(\mathcal {A}\) starts. Note that the number of special messages among m sessions can be bounded by 4m. We order those 4m special messages by the order of their appearances; we use \(\textsf {SM} _k\) to denote the k-th special messages, and s(k) to denote the session that \(\textsf {SM} _k\) belongs to.

We define hybrids \(H_0\) and \(H_{k:1}, \ldots , H_{k:7}\) (\(k\in [4m]\)) as follows. (For convenience, in what follows we occasionally denote \(H_0\) as \(H_{0:7}\).)

Remark 2

(Rough idea of the hybrids). In the sequence of the hybrid experiments, we gradually modify the read-world experiment to the ideal-world one. All the experiments (except for \(H_0\)) involve super-polynomial-time brute-force extraction, but we make sure that \(H_{k:i}\) (\(i\in [7]\)) involves brute-force extraction only until \(\textsf {SM} _k\), and it deviates from the previous hybrid only after \(\textsf {SM} _k\). These properties help us prove the indistinguishability of each neighboring hybrids because we can think the results of brute-force extraction as non-uniform advice and use the non-uniform security of the underlying primitives to show the indistinguishability.^{Footnote 6} \(\Diamond \)

Hybrid \(H_0\). \(H_0\) is the same as the real experiment.

Hybrid \(H_{k:1}\). \(H_{k:1}\) is the same as \(H_{k-1:7}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is first special message,

• the committed subset \(\varGamma _S\) is extracted by brute force in Stage 1-1,

• the value committed to in the i-th \(\mathsf {NMCom}\) commitment in Stage 4 is switched to an all-zero string for every \(i\not \in \varGamma _S\), and

• the value committed to in the i-th \(\mathsf {ExtCom}\) commitment in Stage 4 is switched to an all-zero string for every \(i\not \in \varGamma _S\).

Hybrid \(H_{k:2}\). \(H_{k:2}\) is the same as \(H_{k:1}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is first special message, the i-th mS-OT in Stage 3 is executed with a random input and true randomness for every \(i\not \in \varGamma _S\).

Hybrid \(H_{k:3}\). \(H_{k:3}\) is the same as \(H_{k:2}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is third special message, the following modifications are made.

1. 1.

   The committed strings \(\varvec{a}^S = (a_1^S, \ldots , a_{11n}^S)\) are extracted by brute force in Stage 2-1. Define \(\varvec{r}^S = (r_1^S, \ldots , r_{11n}^S)\) by \(r_i^S {\mathop {=}\limits ^\mathrm{def}}a_i^S \oplus b_i^S\) for each \(i\in [11n]\), and parse \(r_i^S\) as \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\) for each \(i\in [11n]\). Define \(\varvec{\rho }^{\mathsf {ext}}_b = (\rho ^{\mathsf {ext}}_{b,i})_{i\in \varDelta }\) for each \(b\in \{0,1 \}\) as follows: \(\rho ^{\mathsf {ext}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\beta _{b,i} \oplus s_{i,b\oplus \alpha _i}\) if \(\mathcal {A}\) executed the i-th mS-OT in stage 3 honestly using \(s_{i,0} \!\parallel \!s_{i,1} \!\parallel \!\tau _i^S\), and \(\rho ^{\mathsf {ext}}_{b,i} = \bot \) otherwise.

2. 2.

   R outputs \(\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_u, \varGamma _R\cap \varDelta )\) rather than \(\mathsf {Value}(\widetilde{\rho }, \varGamma _R\cap \varDelta )\). (Recall that u is the real input to R.)

Hybrid \(H_{k:4}\). \(H_{k:4}\) is the same as \(H_{k:3}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is third special message, \(\alpha _i\) is a random bit rather than \(\alpha _i = u \oplus c_i\) for every \(i\in \varDelta \) in Stage 6-1 and \(\widetilde{\rho }_i\) is no longer computed for any \(i\in \varDelta \) in Stage 6-3.

Hybrid \(H_{k:5}\). \(H_{k:5}\) is the same as \(H_{k:4}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is second special message,

• the committed subset \(\varGamma _R\) is extracted by brute force in Stage 1-2,

• the value committed in the i-th \(\mathsf {NMCom}\) commitment in Stage 7 is switched to an all-zero string for every \(i\not \in \varGamma _R\), and

• the value committed in the i-th \(\mathsf {ExtCom}\) commitment in Stage 7 is switched to an all-zero string for every \(i\not \in \varGamma _R\).

Hybrid \(H_{k:6}\). \(H_{k:6}\) is the same as \(H_{k:5}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is second special message, the i-th mS-OT in Stage 3 is executed with a random input and true randomness for every \(i\not \in \varGamma _R\).

Hybrid \(H_{k:7}\). \(H_{k:7}\) is the same as \(H_{k:6}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, the following modifications are made.

1. 1.

   The committed strings \(\varvec{a}^R = (a_1^R, \ldots , a_{11n}^R)\) are extracted by brute force in Stage 2-2. Define \(\varvec{r}^R = (r_1^R, \ldots , r_{11n}^R)\) by \(r_i^R {\mathop {=}\limits ^\mathrm{def}}a_i^R \oplus b_i^R\) for each \(i\in [11n]\), and parse \(r_i^R\) as \(c_{i} \!\parallel \!\tau _i^R\) for each \(i\in [11n]\). Define \(u^*\) as follows. Let \(I_0\) and \(I_1\) be the set such that for \(b\in \{0,1 \}\) and \(i\in \varDelta \), we have \(i \in I_b\) if and only if:

• \(i\in \varGamma _R\), or

• \(\mathcal {A}\) did not execute the i-th mS-OT in Stage 3 honestly using \(c_i \!\parallel \!\tau _i^R\) as the input and randomness, or

• \(c_i = b \oplus \alpha _i\), and \(\mathcal {A}\) executed the i-th mS-OT in Stage 3 honestly using \(c_i \!\parallel \!\tau _i^R\) as the input and randomness.

Then, define \(u^*\) by \(u^* {\mathop {=}\limits ^\mathrm{def}}0\) if \(|I_0 | \ge 6n+1\) and \(u^* {\mathop {=}\limits ^\mathrm{def}}1\) otherwise.

1. 2.

   In Stage 6, \(\varvec{\rho }_{1-u^*}\) is a secret sharing of a random bit rather than that of \(v_{1-u^*}\).

We remark that in \(H_{4m:7}\), all the messages from the honest parties and their output are computed as in \(\mathcal{S}im_{\mathrm {OT}}\).

Indistinguishability of Each Neighboring Hybrids. Below, we show that each neighboring hybrids are indistinguishable, and additionally show, for technical reasons, that an invariant condition holds in each session of every hybrid.

First, we define the invariant condition.

Definition 5

(Invariant Condition (when R is corrupted)). For any session in which R is corrupted, we say that the invariant condition holds in that session if the following holds when the cut-and-choose in Stage 5 is accepted.

1. 1.

   Let \((\hat{a}_1^R, \hat{d}_1^R), \ldots (\hat{a}_{11n}^R, \hat{d}_{11n}^R)\) be the values that are committed in \(\mathsf {NMCom}\) in Stage 4. Let \(I_{\mathrm {bad}}\subset [11n]\) be the set such that \(i\in I_{\mathrm {bad}}\) if and only if

   1. (a)

      \((\hat{a}_i^R, \hat{d}_i^R)\) is not a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-2, or

   2. (b)

      R does not execute the i-th mS-OT in Stage 3 honestly using \(\hat{c}_i \!\parallel \!\hat{\tau }_i^R\) as the input and randomness, where \(\hat{c}_i \!\parallel \!\hat{\tau }_i^R\) is obtained from \(\hat{r}_i^R = \hat{a}_i^R \oplus b_i^R\).

   Then, it holds that \(|I_{\mathrm {bad}} | < n\).

Remark 3

Roughly speaking, this condition guarantees that most of the mS-OTs in Stage 3 are honestly executed using the outcome of the coin tossing, which in turn guarantees that the cheating receiver’s input can be extracted by extracting the outcome of the coin tossing. \(\Diamond \)

Remark 4

When Stage 5 is accepted, we also have \(I_{\mathrm {bad}}\cap \varGamma _S = \emptyset \) from the definition of \(I_{\mathrm {bad}}\). \(\Diamond \)

Definition 6

(Invariant Condition (when S is corrupted)). For any session in which S is corrupted, we say that the invariant condition holds in that session if the following hold when the cut-and-choose in Stage 8 is accepted.

1. 1.

   Let \((\hat{a}_1^S, \hat{d}_1^S), \ldots (\hat{a}_{11n}^S, \hat{d}_{11n}^S)\) be the values that are committed in \(\mathsf {NMCom}\) in Stage 7. Let \(I_{\mathrm {bad}}\subset [11n]\) be the set such that \(i\in I_{\mathrm {bad}}\) if and only if

1. (a)

   \((\hat{a}_i^S, \hat{d}_i^S)\) is not a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-1, or

2. (b)

   S does not execute the i-th mS-OT in Stage 3 honestly using \(\hat{s}_{i,0} \!\parallel \!\hat{s}_{i,1} \!\parallel \!\hat{\tau }_i^S\) as the input and randomness, where \(\hat{s}_{i,0} \!\parallel \!\hat{s}_{i,1} \!\parallel \!\hat{\tau }_i^S\) is obtained from \(\hat{r}_i^S = \hat{a}_i^S \oplus b_i^S\).

Then, it holds that \(|I_{\mathrm {bad}} | < 0.1n\).

1. 2.

   For each \(b\in \{0,1 \}\), define \(\varvec{\rho }^{\mathsf {nm}}_b = (\rho ^{\mathsf {nm}}_{b,i})_{i\in \varDelta }\) as follows: \(\rho ^{\mathsf {nm}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\beta _{b,i} \oplus \hat{s}_{i,b\oplus \alpha _i}\) if \(i \not \in I_{\mathrm {bad}}\) and \(\rho ^{\mathsf {nm}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\bot \) otherwise. Then, for each \(b\in \{0,1 \}\), \(\rho ^{\mathsf {nm}}_b\) is either 0.9-close to a valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = \rho ^{\mathsf {nm}}_{b,i}\) for every \(i\in \varGamma _R\) or 0.15-far from any such valid codeword.

Remark 5

Roughly speaking, this condition guarantees that the cheating sender’s input can be extracted from the outcome of the coin tossing. In particular, it guarantees that the sharing that is computed from the outcome of mS-OTs (i.e., the sharing that is computed by the honest receiver) and the sharing that is computed from the outcome of the coin tossing (i.e., the sharing that is computed by the simulator) are very “close” (see Claim 3 below). \(\Diamond \)

Remark 6

When Stage 8 is accepted, we also have \(I_{\mathrm {bad}}\cap \varGamma _R = \emptyset \) from the definition of \(I_{\mathrm {bad}}\). \(\Diamond \)

Next, we show that the invariant condition holds in every session in \(H_0\) (i.e., the real experiment).

Definition 7

We say that \(\mathcal {A}\) cheats in a session if the invariant condition does not hold in that session.

Lemma 1

In \(H_0\), \(\mathcal {A}\) does not cheat in every session except with negligible probability.

Proof

Assume for contradiction that in \(H_0\), \(\mathcal {A}\) cheats in a session with non-negligible probability. Since the number of the sessions is bounded by a polynomial, there exists a function \(i^*(\cdot )\) and a polynomial \(p(\cdot )\) such that for infinitely many \(n\), \(\mathcal {A}\) cheats in the \(i^*(n)\)-th session with probability at least \(1/p(n)\); furthermore, since \(\mathcal {A}\) cheats only when either R or S is corrupted, in the \(i^*(n)\)-th session either R is corrupted for infinitely many such \(n\) or S is corrupted for infinitely many such \(n\). In both cases, we derive contradiction by using \(\mathcal {A}\) to break the hiding property of \(\mathsf {Com}\).

Case 1. R is corrupted in the \(i^*(n)\)-th session. We show that when \(\mathcal {A}\) cheats, we can break the hiding property of the \(\mathsf {Com}\) commitment in Stage 1-1 (i.e., the commitment by which \(\varGamma _S\) is committed to). From the definition of the invariant condition (Definition 5), when \(\mathcal {A}\) cheats, we have \(|I_{\mathrm {bad}} | \ge n\) even though the cut-and-choose in Stage 5 is accepting (and hence \(I_{\mathrm {bad}}\cap \varGamma _S = \emptyset \) as remarked in Remark 4), where \(I_{\mathrm {bad}}\subseteq [11n]\) is the set defined from the committed values of the \(\mathsf {NMCom}\) commitments in Stage 4. If we can compute \(I_{\mathrm {bad}}\) efficiently, we can use it to distinguish \(\varGamma _S\) from a random subset of size \(n\) (this is because a random subset \(\varGamma \) of size \(n\) satisfies \(I_{\mathrm {bad}}\cap \varGamma = \emptyset \) only with negligible probability when \(|I_{\mathrm {bad}} | \ge n\)), so we can use it to break the hiding property of the commitment to \(\varGamma _S\). However, \(I_{\mathrm {bad}}\) is not efficiently computable since the committed values of the \(\mathsf {NMCom}\) commitments are not efficiently computable. We thus first show that we can “approximate” \(I_{\mathrm {bad}}\) by extracting the committed values of the \(\mathsf {ExtCom}\) commitments in Stage 4. Details are given below.

First, we observe that if we extract the committed values of the \(\mathsf {ExtCom}\) commitments in Stage 4 of the \(i^*(n)\)-th session, the extracted values, \((\hat{a}_1^R, \hat{d}_1^R, \hat{e}_1^R), \ldots ,(\hat{a}_{11n}^R, \hat{d}_{11n}^R, \hat{e}_{11n}^R)\), satisfy the following condition.

• Let \(\hat{I}_{\mathrm {bad}}\subset [11n]\) be a set such that \(i\in \hat{I}_{\mathrm {bad}}\) if and only if

  1. 1.

     \(((\hat{a}_i^R, \hat{d}_i^R), \hat{e}_i^R)\) is not a valid decommitment of the i-th \(\mathsf {NMCom}\) commitment in Stage 4, or

  2. 2.

     \((\hat{a}_i^R, \hat{d}_i^R)\) is not a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-2, or

  3. 3.

     R does not execute the i-th mS-OT in Stage 3 honestly using \(\hat{c}_i \!\parallel \!\hat{\tau }_i^R\) as the input and randomness, where \(\hat{c}_i \!\parallel \!\hat{\tau }_i^R\) is obtained from \(\hat{r}_i^R = \hat{a}_i^R \oplus b_i^R\).

  Then, \(|\hat{I}_{\mathrm {bad}} | \ge n\) and \(\hat{I}_{\mathrm {bad}}\cap \varGamma _S = \emptyset \) with probability at least \(1/2p(n)\).

The extracted values satisfy this condition because when \(\mathcal {A}\) cheats, we have \(|\hat{I}_{\mathrm {bad}} | \ge n\) and \(\hat{I}_{\mathrm {bad}}\cap \varGamma _S = \emptyset \) except with negligible probability. (We have \(|\hat{I}_{\mathrm {bad}} | \ge n\) since we have \(I_{\mathrm {bad}}\subset \hat{I}_{\mathrm {bad}}\) from the definitions of \(I_{\mathrm {bad}}, \hat{I}_{\mathrm {bad}}\) and the binding property of \(\mathsf {NMCom}\). We have \(\hat{I}_{\mathrm {bad}}\cap \varGamma _S = \emptyset \) since when the cut-and-choose in Stage 5 is accepting, for every \(i\in \varGamma _S\) the i-th \(\mathsf {ExtCom}\) commitment is a valid decommitment of the i-th \(\mathsf {NMCom}\) commitment, and \(I_{\mathrm {bad}}\cap \varGamma _S = \emptyset \).)

Based on this observation, we derive contradiction by considering the following adversary \(\mathcal {A}_{\mathsf {Com}}\) against the hiding property of \(\mathsf {Com}\).

\(\mathcal {A}_{\mathsf {Com}}\) receives a \(\mathsf {Com}\) commitment \(c^*\) in which either \(\varGamma _S^0\) or \(\varGamma _S^1\) is committed, where \(\varGamma _S^0, \varGamma _S^1 \subset [11n]\) are random subsets of size \(n\).

Then, \(\mathcal {A}_{\mathsf {Com}}\) internally executes the experiment \(H_0\) honestly except that in the \(i^*(n)\)-th session, \(\mathcal {A}_{\mathsf {Com}}\) uses \(c^*\) as the commitment in Stage 1-1 (i.e., as the \(\mathsf {Com}\) commitment in which S commits to a subset \(\varGamma _S\)). When the experiment \(H_0\) reaches Stage 4 of the \(i^*(n)\)-th session, \(\mathcal {A}_{\mathsf {Com}}\) extracts the committed values of the \(\mathsf {ExtCom}\) commitments in this stage by using its extractability.^{Footnote 7} Let \(\hat{I}_{\mathrm {bad}}\subset [11n]\) be the set that is defined as above from the extracted values. Then, \(\mathcal {A}_{\mathsf {Com}}\) outputs 1 if and only if \(|\hat{I}_{\mathrm {bad}} | \ge n\) and \(\hat{I}_{\mathrm {bad}}\cap \varGamma _S^1 = \emptyset \).

If \(\mathcal {A}_{\mathsf {Com}}\) receives a commitment to \(\varGamma _S^1\), \(\mathcal {A}_{\mathsf {Com}}\) outputs 1 with probability at least \(1/2p(n)\) (this follows from the above observation). In contrast, if \(\mathcal {A}_{\mathsf {Com}}\) receives a commitment to \(\varGamma _S^0\), \(\mathcal {A}_{\mathsf {Com}}\) outputs 1 with exponentially small probability (this is because when no information about \(\varGamma _S^1\) is fed into \(H_0\), the probability that \(|\hat{I}_{\mathrm {bad}} | \ge n\) but \(\hat{I}_{\mathrm {bad}}\cap \varGamma _S^1 = \emptyset \) is exponentially small). Hence, \(\mathcal {A}_{\mathsf {Com}}\) breaks the hiding property of \(\mathsf {Com}\).

Case 2. S is corrupted in the  \(i^*(n)\)-th session. The proof for this case is similar to (but a little more complex than) the one for Case 1. Specifically, we show that if the invariant condition does not hold, we can break the hiding property of \(\mathsf {Com}\) in Stage 1-2 by approximating \(I_{\mathrm {bad}}\) using the extractability of \(\mathsf {ExtCom}\). We give a formal proof in the full version of this paper. (A somewhat similar proof is given as the proof of Claim 4 later.)    \(\square \)

Finally, we show the indistinguishability between each neighboring hybrids.

Lemma 2

Assume that in \(H_{k-1:7}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k-1:7}\) and \(H_{k:1}\) are indistinguishable, and

• in \(H_{k:1}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

We prove the lemma by using a hybrid argument. Specifically, we consider the following intermediate hybrid \(H'_{k-1:7}\).

Hybrid \(H'_{k-1:7}\). \(H'_{k-1:7}\) is the same as \(H_{k-1:7}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is first special message,

• the committed subset \(\varGamma _S\) is extracted by brute force in Stage 1-1, and

• the value committed to in the i-th \(\mathsf {ExtCom}\) commitment in Stage 4 is switched to an all-zero string for every \(i\not \in \varGamma _S\).

Claim 1

Assume that in \(H_{k-1:7}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k-1:7}\) and \(H'_{k-1:7}\) are indistinguishable, and

• in \(H'_{k-1:7}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

We first show the indistinguishability between \(H_{k-1:7}\) and \(H'_{k-1:7}\). Assume for contradiction that \(H_{k-1:7}\) and \(H'_{k-1:7}\) are distinguishable. From an average argument, we can fix the execution of the experiment up until \(\textsf {SM} _k\) (inclusive) in such a way that even after being fixed, \(H_{k-1:7}\) and \(H'_{k-1:7}\) are still distinguishable. As remarked in Remark 2, no brute-force extraction is performed after \(\textsf {SM} _k\) in \(H_{k-1:7}\) and \(H'_{k-1:7}\); hence, by considering the transcript (including the inputs and randomness of all the parties) and the extracted values up until \(\textsf {SM} _k\) as non-uniform advice, we can break the hiding property of \(\mathsf {ExtCom}\) as follows.

The adversary \(\mathcal {A}_{\mathsf {ExtCom}}\) internally executes \(H_{k-1:7}\) from \(\textsf {SM} _k\) using the non-uniform advice. In Stage 4 of session s(k), \(\mathcal {A}_{\mathsf {ExtCom}}\) sends \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\) and \((0, 0, 0)_{i\not \in \varGamma _S}\) to the external committer, receives back \(\mathsf {ExtCom}\) commitments (in which either \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\) or \((0, 0, 0)_{i\not \in \varGamma _S}\) are committed to), and feeds them into \(H_{k-1:7}\). After the execution of \(H_{k-1:7}\) finishes, \(\mathcal {A}_{\mathsf {ExtCom}}\) outputs whatever \(\mathcal {Z}\) outputs in the experiment.

When \(\mathcal {A}_{\mathsf {ExtCom}}\) receives commitments to \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\), the internally executed experiment is identical with \(H_{k-1:7}\), whereas when \(\mathcal {A}_{\mathsf {ExtCom}}\) receives a commitments to \((0, 0, 0)_{i\not \in \varGamma _S}\), the internally executed experiment is identical with \(H'_{k-1:7}\). Hence, from the assumption that \(H_{k-1:7}\) and \(H'_{k-1:7}\) are distinguishable (even after being fixed up until \(\textsf {SM} _k\)), \(\mathcal {A}_{\mathsf {ExtCom}}\) distinguishes \(\mathsf {ExtCom}\) commitments.

We next show that in \(H'_{k-1:7}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\). Assume for contradiction that in \(H'_{k-1:7}\), \(\mathcal {A}\) cheats in one of those sessions, say, session s(j), with non-negligible probability. Then, from an average argument, we can fix the execution of the experiment up until \(\textsf {SM} _k\) (inclusive) in such a way that even after being fixed, \(\mathcal {A}\) cheats in session s(j) only with negligible probability in \(H_{k-1:7}\) but with non-negligible probability in \(H'_{k-1:7}\). Then, by considering the transcript and the extracted values up until \(\textsf {SM} _k\) as non-uniform advice, we can break the robust non-malleability of \(\mathsf {NMCom}\) as follows. (Note that the \(\mathsf {ExtCom}\) commitments in sessions \(s(k), \ldots , s(4m)\) starts only after \(\textsf {SM} _k\).)

The man-in-the-middle adversary \(\mathcal {A}_{\mathsf {NMCom}}\) internally executes \(H_{k-1:7}\) from \(\textsf {SM} _k\) using the non-uniform advice. In Stage 4 of session s(k), \(\mathcal {A}_{\mathsf {NMCom}}\) sends \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\) and \((0, 0, 0)_{i\not \in \varGamma _S}\) to the external committer, receives back \(\mathsf {ExtCom}\) commitments (in which either \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\) or \((0, 0, 0)_{i\not \in \varGamma _S}\) are committed to), and feeds them into \(H_{k-1:7}\). Also, in session s(j), \(\mathcal {A}_{\mathsf {NMCom}}\) forwards the \(\mathsf {NMCom}\) commitments from \(\mathcal {A}\) to the external receiver (specifically, the \(\mathsf {NMCom}\) commitments in Stage 4 if R is corrupted and in Stage 7 if S is corrupted). After the execution of \(H_{k-1:7}\) finishes, \(\mathcal {A}_{\mathsf {NMCom}}\) outputs its view.

The distinguisher \(\mathcal {D}_{\mathsf {NMCom}}\) takes as input the view of \(\mathcal {A}_{\mathsf {NMCom}}\) and the values committed by \(\mathcal {A}_{\mathsf {NMCom}}\) (which are equal to the values committed to by \(\mathcal {A}\) in session s(j) in the internally executed experiment). \(\mathcal {D}_{\mathsf {NMCom}}\) then outputs 1 if and only if \(\mathcal {A}\) cheated in session s(j). (Notice that given the committed values of the \(\mathsf {NMCom}\) commitments, \(\mathcal {D}_{\mathsf {NMCom}}\) can check whether \(\mathcal {A}\) cheated or not in polynomial time.)

When \(\mathcal {A}_{\mathsf {NMCom}}\) receives commitments to \((a_i^R, d_i^R, e_i^R)_{i\not \in \varGamma _S}\), the internally executed experiment is identical with \(H_{k-1:7}\), whereas when \(\mathcal {A}_{\mathsf {NMCom}}\) receives a commitments to \((0, 0, 0)_{i\not \in \varGamma _S}\), the internally executed experiment is identical with \(H'_{k-1:7}\). Hence, from the assumption that \(\mathcal {A}\) cheats in session s(j) with negligible probability in \(H_{k-1:7}\) but with non-negligible probability in \(H'_{k-1:7}\), \(\mathcal {A}_{\mathsf {NMCom}}\) breaks the robust non-malleability of \(\mathsf {NMCom}\).

This completes the proof of Claim 1.    \(\square \)

Claim 2

Assume that in \(H'_{k-1:7}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H'_{k-1:7}\) and \(H_{k:1}\) are indistinguishable, and

• in \(H_{k:1}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

This claim can be proven very similarly to Claim 1 (the only difference is that we use the hiding property of \(\mathsf {NMCom}\) rather than that of \(\mathsf {ExtCom}\) in the first part, and use the non-malleability of \(\mathsf {NMCom}\) rather than its robust non-malleability in the second part). We give a proof in the full version of this paper.

This completes the proof of Lemma 2.    \(\square \)

Lemma 3

Assume that in \(H_{k:1}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:1}\) and \(H_{k:2}\) are indistinguishable, and

• in \(H_{k:2}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Recall that hybrids \(H_{k:1}, H_{k:2}\) differ only in the input and the randomness that are used in some of the mS-OTs in Stage 3, where those that are derived from the outcomes of the coin tossing is used in \(H_{k:1}\) and random inputs and true randomness are used in \(H_{k:2}\). Intuitively, we prove this lemma by using the security of the coin tossing (which is guaranteed by the hiding property of \(\mathsf {Com}\)) because it guarantees that the outcome of the coin tossing is pseudorandom. The proof is quite similar to the proof of Claim 1 (we use the hiding of \(\mathsf {Com}\) rather than that of \(\mathsf {ExtCom}\)), and given in the full version of this paper.

Lemma 4

Assume that in \(H_{k:2}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:2}\) and \(H_{k:3}\) are indistinguishable, and

• in \(H_{k:3}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

Recall that \(H_{k:2}\) and \(H_{k:3}\) differ only in that in session s(k) of \(H_{k:3}\), if S is corrupted and \(\textsf {SM} _k\) is third special message, R outputs \(\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_u, \varGamma _R\cap \varDelta )\) rather than \(\mathsf {Value}(\varvec{\widetilde{\rho }}, \varGamma _R\cap \varDelta )\).

For proving the lemma, it suffices to show that in \(H_{k:3}\), we have \(\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_u, \varGamma _R\cap \varDelta ) = \mathsf {Value}(\varvec{\widetilde{\rho }}, \varGamma _R\cap \varDelta )\) except with negligible probability. This is because if \(\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_u, \varGamma _R\cap \varDelta ) = \mathsf {Value}(\varvec{\widetilde{\rho }}, \varGamma _R\cap \varDelta )\) holds in \(H_{k:3}\) except with negligible probability, \(H_{k:2}\) and \(H_{k:3}\) are statistically close, which implies that in \(H_{k:3}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Hence, we show that in \(H_{k:3}\), we have \(\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_u, \varGamma _R\cap \varDelta ) = \mathsf {Value}(\varvec{\widetilde{\rho }}, \varGamma _R\cap \varDelta )\) except with negligible probability. Since \(H_{k:2}\) and \(H_{k:3}\) proceed identically until the end of session s(k), we have that in \(H_{k:3}\), \(\mathcal {A}\) does not cheat in sessions s(k) except with negligible probability. It thus suffices to show the following two claims.

Claim 3

For any \(\varvec{x} = (x_i)_{i\in \varDelta }, \varvec{y} = (y_i)_{i\in \varDelta }\) and a set \(\varTheta \), we have \(\mathsf {Value}(\varvec{x}, \varTheta ) = \mathsf {Value}(\varvec{y}, \varTheta )\) if the following conditions hold.

1. 1.

   \(\varvec{x}\) and \(\varvec{y}\) are 0.99-close, and \(x_i = y_i\) holds for every \(i\in \varTheta \).

2. 2.

   If \(x_i \ne \bot \), then \(x_i = y_i\).

3. 3.

   x is either 0.9-close to a valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = x_i\) for every \(i\in \varTheta \) or 0.14-far from any such valid codeword.

Claim 4

In \(H_{k:3}\), if in session s(k) the sender S is corrupted, \(\mathcal {A}\) does not cheat, and the session is accepting, the following hold.

1. 1.

   \(\varvec{\rho }^{\mathsf {ext}}_u\) and \(\varvec{\widetilde{\rho }}\) are 0.99-close, and \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\) holds for every \(i\in \varGamma _R\cap \varDelta \).

2. 2.

   If \(\rho ^{\mathsf {ext}}_{u,i} \ne \bot \), then \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\).

3. 3.

   \(\varvec{\rho }^{\mathsf {ext}}_u\) is either 0.9-close to a valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = \rho ^{\mathsf {ext}}_{u,i}\) for every \(i\in \varGamma _R\cap \varDelta \) or 0.14-far from any such valid codeword.

We prove each of the claims below.

Proof

(of Claim 3). We consider the following two cases.  

Case 1. :

\(\varvec{x}\)  is 0.9-close to a valid codeword  \(\varvec{w} = (w_i)_{i\in \varDelta }\)  that satisfies  \(w_i = x_i\)  for every  \(i\in \varTheta \): First, we observe that \(\varvec{y}\) is 0.9-close to \(\varvec{w}\). Since \(\varvec{w}\) is a valid codeword, we have \(w_i \ne \bot \) for every \(i\in \varDelta \); thus, for every i such that \(x_i = w_i\), we have \(x_i \ne \bot \). Recall that from the assumed conditions, for every i such that \(x_i \ne \bot \), we have \(x_i = y_i\). Therefore, for every i such that \(x_i = w_i\), we have \(y_i = w_i\), which implies that \(\varvec{y}\) is 0.9-close to \(\varvec{w}\). Next, we observe that \(\varvec{w}\) satisfies \(w_i = y_i\) for every \(i\in \varTheta \). From the assumed conditions, we have \(x_i = y_i\) for every \(i\in \varTheta \). Also, from the condition of this case, \(\varvec{w}\) satisfies \(w_i = x_i\) for every \(i\in \varTheta \). From these two, we have that \(\varvec{w}\) satisfies \(w_i = y_i\) for every \(i\in \varTheta \).

Now, from the definition of \(\mathsf {Value}(\cdot , \cdot )\), we have \(\mathsf {Value}(\varvec{x}, \varTheta ) = \mathsf {Value}(\varvec{y}, \varTheta ) = \mathsf {Decode}(\varvec{w})\).

Case 2. :

\(\varvec{x}\)  is 0.14-far from any valid codeword  \(\varvec{w} = (w_i)_{i\in \varDelta }\)  that satisfies  \(w_i = x_i\)  for every  \(i\in \varTheta \): For any valid codeword \(\varvec{w'} = (w'_i)_{i\in \varDelta }\) that satisfies \(w'_i = y_i\) for every \(i\in \varTheta \), we observe that \(\varvec{y}\) is 0.1-far from \(\varvec{w'}\). Since we assume that \(x_i = y_i\) holds for every \(i\in \varTheta \), we have \(w'_i = x_i\) for every \(i\in \varTheta \). Therefore, from the assumption of this case, \(\varvec{x}\) is 0.14-far from \(\varvec{w'}\). Now, since we assume that \(\varvec{x}\) and \(\varvec{y}\) are 0.99-close, \(\varvec{y}\) is 0.1-far from \(\varvec{w'}\). Now, from the definition of \(\mathsf {Value}(\cdot , \cdot )\), we conclude that \(\mathsf {Value}(\varvec{x}, \varTheta ) = \mathsf {Value}(\varvec{y}, \varTheta ) = \bot \).

  Notice that from the assumed conditions, either Case 1 or Case 2 is true. This concludes the proof of Claim 3.    \(\square \)

Proof

(of Claim 4). Recall that if \(\mathcal {A}\) does not cheat in an accepting session in which S is corrupted, we have the following.

1. 1.

   Let \((\hat{a}_1^S, \hat{d}_1^S), \ldots (\hat{a}_{11n}^S, \hat{d}_{11n}^S)\) be the values committed in \(\mathsf {NMCom}\) in Stage 7. Let \(I_{\mathrm {bad}}\subset [11n]\) be the set that is defined as follows: \(i\in I_{\mathrm {bad}}\) if and only if

1. (a)

   \((\hat{a}_i^S, \hat{d}_i^S)\) is not a valid decommitment of the i-th \(\mathsf {Com}\) commitment in Stage 2-1, or

2. (b)

   S does not execute the i-th mS-OT in Stage 3 honestly using \(\hat{s}_{i,0} \!\parallel \!\hat{s}_{i,1} \!\parallel \!\hat{\tau }_i^S\) as the input and randomness, where \(\hat{s}_{i,0} \!\parallel \!\hat{s}_{i,1} \!\parallel \!\hat{\tau }_i^S\) is obtained from \(\hat{r}_i^S = \hat{a}_i^S \oplus b_i^S\).

Then, it holds that \(|I_{\mathrm {bad}} | < 0.1n\).

1. 2.

   For each \(b\in \{0,1 \}\), define \(\varvec{\rho }^{\mathsf {nm}}_b = (\rho ^{\mathsf {nm}}_{b,i})_{i\in \varDelta }\) as follows: \(\rho ^{\mathsf {nm}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\beta _{b,i} \oplus \hat{s}_{i,b\oplus \alpha _i}\) if \(i \not \in I_{\mathrm {bad}}\) and \(\rho ^{\mathsf {nm}}_{b,i} {\mathop {=}\limits ^\mathrm{def}}\bot \) otherwise. Then, for each \(b\in \{0,1 \}\), \(\rho ^{\mathsf {nm}}_b\) is either 0.9-close to a valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = \rho ^{\mathsf {nm}}_{b,i}\) for every \(i\in \varGamma _R\) or 0.15-far from any such valid codeword.

We show that the above two imply all the three conditions in the claim statement.

First, we show that \(\varvec{\rho }^{\mathsf {ext}}_u\) and \(\varvec{\widetilde{\rho }}\) are 0.99-close and that \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\) holds for every \(i\in \varGamma _R\cap \varDelta \). From the definition of \(I_{\mathrm {bad}}\), we have \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\) for every \(i\not \in I_{\mathrm {bad}}\) (this is because for every \(i\not \in I_{\mathrm {bad}}\), \(\mathcal {A}\) executed the i-th mS-OT in Stage 3 honestly using the coin obtained in Stage 2-1, which implies that the value \(\widetilde{s}_i\) that was obtained from the i-th mS-OT is equal to the value \(s_{i,c_i}\) that was obtained by extracting the coin in Stage 2-1 by brute-force). Then, since \(|I_{\mathrm {bad}} | < 0.1n\) and \(I_{\mathrm {bad}}\cap \varGamma _R = \emptyset \) (the latter holds since the session would be rejected otherwise), we have that \(\varvec{\rho }^{\mathsf {ext}}_u\) and \(\varvec{\widetilde{\rho }}\) are 0.99-close and that \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\) holds for every \(i\in \varGamma _R\cap \varDelta \).

Next, we show that if \(\rho ^{\mathsf {ext}}_{u,i} \ne \bot \) then \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\). From the definition of \(\varvec{\rho }^{\mathsf {ext}}_u\), if \(\rho ^{\mathsf {ext}}_{u,i} \ne \bot \), \(\mathcal {A}\) executed the i-th mS-OT in Stage 3 honestly using the coin obtained in Stage 2-1, so we have \(\rho ^{\mathsf {ext}}_{u,i} = \tilde{\rho }_i\) from the argument same as above.

Finally, we show that \(\varvec{\rho }^{\mathsf {ext}}_u\) is either 0.9-close to a valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = \rho ^{\mathsf {ext}}_{u,i}\) for every \(i\in \varGamma _R\cap \varDelta \) or 0.14-far from any such valid codeword. From the assumption that \(\mathcal {A}\) does not cheat, it suffices to consider the following two cases.

• Case 1. \(\varvec{\rho }^{\mathsf {nm}}_u\)  is 0.9-close to a valid codeword  \(\varvec{w} = (w_i)_{i\in \varDelta }\)  that satisfies \(w_i = \rho ^{\mathsf {nm}}_{b,i}\)  for every \(i\in \varGamma _R\cap \varDelta \): In this case, \(\varvec{\rho }^{\mathsf {ext}}_u\) is 0.9-close to \(\varvec{w}\), and \(w_i = \rho ^{\mathsf {ext}}_{b,i}\) holds for every \(i\in \varGamma _R\). This is because for every i such that \(\rho ^{\mathsf {nm}}_{u,i} = w_i\), we have \(\rho ^{\mathsf {nm}}_{u,i} \ne \bot \) and thus we have \(\rho ^{\mathsf {nm}}_{u,i} = \rho ^{\mathsf {ext}}_{u,i}\) from the definition of \(\varvec{\rho }^{\mathsf {nm}}_u\).

• Case 2. \(\varvec{\rho }^{\mathsf {nm}}_u\)  is 0.15-far from any valid codeword \(\varvec{w} = (w_i)_{i\in \varDelta }\) that satisfies \(w_i = \rho ^{\mathsf {nm}}_{b,i}\)  for every  \(i\in \varGamma _R\cap \varDelta \): In this case, \(\varvec{\rho }^{\mathsf {ext}}_u\) is 0.14-far from any valid codeword \(\varvec{w'}\) that satisfies \(w'_i = \rho ^{\mathsf {ext}}_{b,i}\) for every \(i\in \varGamma _R\cap \varDelta \). This can be seen by observing the following: (1) for every \(i\in \varGamma _R\cap \varDelta \), we have \(i\not \in I_{\mathrm {bad}}\) (this is because the session is accepting) and hence \(\rho ^{\mathsf {ext}}_{u,i} = \rho ^{\mathsf {nm}}_{u,i}\); (2) therefore, for any valid codeword \(\varvec{w'}\) that satisfies \(w'_i = \rho ^{\mathsf {ext}}_{b,i}\) for every \(i\in \varGamma _R\cap \varDelta \), we have that \(\varvec{w'}\) also satisfies \(w'_i = \rho ^{\mathsf {nm}}_{b,i}\) for every \(i\in \varGamma _R\cap \varDelta \); (3) then, from the assumption of this case, \(\varvec{\rho }^{\mathsf {nm}}_u\) is 0.15-far from \(\varvec{w'}\); (4) now, since \(\varvec{\rho }^{\mathsf {nm}}_u\) and \(\varvec{\rho }^{\mathsf {ext}}_u\) are 0.99-close, \(\varvec{\rho }^{\mathsf {ext}}_u\) is 0.14-far from \(\varvec{w'}\).

This concludes the proof of Claim 4.    \(\square \)

This concludes the proof of Lemma 4.    \(\square \)

Lemma 5

Assume that in \(H_{k:3}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:3}\) and \(H_{k:4}\) are indistinguishable, and

• in \(H_{k:4}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Recall that \(H_{k:3}\) and \(H_{k:4}\) differ only in that in session s(k) of \(H_{k:4}\), if S is corrupted and \(\textsf {SM} _k\) is third special message, \(\alpha _i\) is a random bit rather than \(\alpha _i = u \oplus c_i\) for every \(i\in \varDelta \) in Stage 6-1. Intuitively, we can prove this lemma by using the security of \(\mathsf {mS}\hbox {-}\mathsf {OT}\): For every \(i\not \in \varGamma _S\), the choice bit \(c_i\) of the i-th mS-OT in Stage 3 is hidden from \(\mathcal {A}\) and hence \(\alpha _i = u \oplus c_i\) in \(H_{k:3}\) is indistinguishable from a random bit. Formally, we prove this Lemma in the same way as we do for Claim 1 (we use the security of \(\mathsf {mS}\hbox {-}\mathsf {OT}\) rather than the hiding of \(\mathsf {ExtCom}\)); the proof is given in the full version of this paper.

Lemma 6

Assume that in \(H_{k:4}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:4}\) and \(H_{k:5}\) are indistinguishable, and

• in \(H_{k:5}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Since hybrids \(H_{k:4}, H_{k:5}\) differ only in the values committed to in \(\mathsf {NMCom}\) and \(\mathsf {ExtCom}\) for the indices outside of \(\varGamma _R\), this lemma can be proven identically with Lemma 2. We give a prof in the full version of this paper.

Lemma 7

Assume that in \(H_{k:5}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:5}\) and \(H_{k:6}\) are indistinguishable, and

• in \(H_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Since hybrids \(H_{k:5}, H_{k:6}\) differ only in the inputs and the randomness that are used in some of the mS-OTs in Stage 3, this lemma can be proven identically with Lemma 3 (which in turn can be proven quite similarly to Lemma 2). We give a prof in the full version of this paper.

Lemma 8

Assume that in \(H_{k:6}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:6}\) and \(H_{k:7}\) are indistinguishable, and

• in \(H_{k:7}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

We prove the lemma by considering the following intermediate hybrids \(H'_{k:6}\), \(H''_{k:6}\), and \(H'''_{k:6}\).

Hybrid \(H'_{k:6}\). \(H'_{k:6}\) is the same as \(H_{k:6}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, the following modifications are made.

1. 1.

   As in \(H_{k:7}\), the committed strings \(\varvec{a}^R = (a_1^R, \ldots , a_{11n}^R)\) are extracted by brute force in Stage 2-2, \(\varvec{r}^R = (r_1^R, \ldots , r_{11n}^R)\) is defined by \(r_i^R {\mathop {=}\limits ^\mathrm{def}}a_i^R \oplus b_i^R\) for each \(i\in [11n]\), and \(r_i^R\) is parsed as \(c_{i} \!\parallel \!\tau _i^R\) for each \(i\in [11n]\). Also, \(I_0\), \(I_1\), and \(u^*\) are defined as in \(H_{k:7}\).

2. 2.

   In Stage 6, \(\beta _{b,i}\) is a random bit rather than \(\beta _{b,i} = \rho _{b,i} \oplus s_{i, b\oplus \alpha _i}\) for every \(b\in \{0,1 \}\) and \(i \in \varDelta {\setminus } I_b\). (Recall that, roughly, \(I_b\subset \varDelta \) is the set of indices on which \(\mathcal {A}\) could have obtained \(s_{i,b\oplus \alpha _i}\).)

Hybrid \(H''_{k:6}\). \(H''_{k:6}\) is the same as \(H'_{k:6}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, the following modification is made.

1. 1.

   In Stage 6, \(\varvec{\rho }_{1-u^*} = \{\rho _{1-u^*, i} \}_{i\in \varDelta }\) is a secret sharing of a random bit rather than that of \(v_{1-u^*}\).

Hybrid \(H'''_{k:6}\). \(H'''_{k:6}\) is the same as \(H''_{k:6}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, the following modification is made.

1. 1.

   In Stage 6, \(\beta _{b,i}\) is \(\beta _{b,i} = \rho _{b,i} \oplus s_{i, b\oplus \alpha _i}\) rather than a random bit for every \(b\in \{0,1 \}\) and \(i \in \varDelta {\setminus } I_b\).

Notice that \(H'''_{k:6}\) is identical with \(H_{k:7}\).

Claim 5

Assume that in \(H_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:6}\) and \(H'_{k:6}\) are indistinguishable, and

• in \(H'_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Recall that \(H_{k:6}\) and \(H'_{k:6}\) differ only in that in session s(k) of \(H'_{k:6}\), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, \(\beta _{b,i}\) is a random bit rather than \(\beta _{b,i} = \rho _{b,i} \oplus s_{i, b\oplus \alpha _i}\) for every \(b\in \{0,1 \}\) and \(i \in \varDelta {\setminus } I_b\). Intuitively, we can prove this claim by using the security of mS-OT: For every \(i \in \varDelta {\setminus } I_b\), \(\mathcal {A}\) executed the i-th mS-OT honestly with choice bit \((1-b)\oplus \alpha _i\), and the sender’s input and randomness of this mS-OT are not revealed in Stage 8; therefore, the value of \(s_{i, b\oplus \alpha _i}\) is hidden from \(\mathcal {A}\) and thus \(\beta _{b,i} = \rho _{b,i} \oplus s_{i, b\oplus \alpha _i}\) is indistinguishable from a random bit. Formally, we prove this claim in the same way as we do for Claim 1 (we use the security of mS-OT rather than the hiding of ExtCom); a formal proof is given in the full version of this paper.

Claim 6

Assume that in \(H'_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H'_{k:6}\) and \(H''_{k:6}\) are indistinguishable, and

• in \(H''_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

Recall that hybrids \(H'_{k:6}, H''_{k:6}\) differ only in that in Stage 6, \(\varvec{\rho }_{1-u^*} = \{\rho _{1-u^*, i} \}_{i\in \varDelta }\) is a secret sharing of a random bit rather than that of \(v_{1-u^*}\).

For proving the lemma, it suffices to show that we have \(|I_{1-u^*} | \le 6n\) in \(H'_{k:6}\) except with negligible probability. This is because if \(|I_{1-u^*} | \le 6n\) in \(H'_{k:6}\), then \(\beta _{1-u^*, i}\) is a random bit on at least \(4n\) indices and thus \(\rho _{1-u^*,i}\) is hidden on at least \(4n\) indices, which implies that \(H'_{k:6}\) and \(H''_{k:6}\) are statistically indistinguishable. (Statistical indistinguishability between \(H'_{k:6}\) and \(H''_{k:6}\) implies that in \(H''_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.)

Hence, we show that we have \(|I_{1-u^*} | \le 6n\) in \(H'_{k:6}\) except with negligible probability. Since we assume that \(\mathcal {A}\) does not cheat in session s(k) except with negligible probability, it suffices to show that we have either \(|I_0 | \le 6n\) or \(|I_1 | \le 6n\) whenever \(\mathcal {A}\) does not cheat in session s(k). Assume that \(\mathcal {A}\) does not cheat in session s(k). Then, since \(|\varGamma _R | = n\) and the number of indices on which \(\mathcal {A}\) does not execute mS-OT using the outcome of coin-tossing is at most \(n\), we have \(|I_0 \cap I_1 | \le 2n\). Now, since \(I_0, I_1 \subset \varDelta \) and thus \(|I_0 \cup I_1 | \le |\varDelta | = 10n\), we have \(|I_0 | + |I_1 | \le 12n\), and hence, we have either \(|I_0 | \le 6n\) or \(|I_1 | \le 6n\).    \(\square \)

Claim 7

Assume that in \(H''_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H''_{k:6}\) and \(H'''_{k:6}\) are indistinguishable, and

• in \(H'''_{k:6}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Proof

This claim can be proven identically with Claim 5.    \(\square \)

This completes the proof of Lemma 8.    \(\square \)

From Lemmas 2–8, we conclude that the output of \(H_0\) and that of \(H_{4m:7}\) are indistinguishable, i.e., the output of the real world and that of the ideal world are indistinguishable. This concludes the proof of Theorem 2.

In this section, we prove the following theorem.

Theorem 3

Assume the existence of constant-round semi-honest oblivious transfer protocols and collision-resistant hash functions. Let \(\mathcal {F}\) be any well-formed functionality and \(\hat{\mathcal {F}}\) be its multi-session extension. Then, there exists a constant-round protocol that UC-SPS realizes \(\hat{\mathcal {F}}\), and it uses the underlying primitives in the black-box way.

We focus on the two-party case below (the MPC case is analogues).

Protocol Description. Roughly speaking, we obtain our SPS 2PC protocol by composing our SPS OT protocol in Sect. 4 with a UC-secure OT-hybrid 2PC protocol. Concretely, let \(\varPi _{\mathrm {OT}}\) be our SPS OT protocol in Sect. 4, and \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) be a UC-secure OT-hybrid 2PC protocol with the following property: The two parties use the OT functionality \(\mathcal {F}_{\mathrm OT}\) only at the beginning of the protocol, and they send only randomly chosen inputs to \(\mathcal {F}_{\mathrm OT}\). Then, we obtain our SPS 2PC protocol \(\varPi _{\mathrm {2PC}}\) by replacing each invocation of \(\mathcal {F}_{\mathrm OT}\) in \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) with an execution of \(\varPi _{\mathrm {OT}}\) (i.e., the two parties execute \(\varPi _{\mathrm {OT}}\) instead of calling to \(\mathcal {F}_{\mathrm OT}\)), where all the executions of \(\varPi _{\mathrm {OT}}\) are carried out in a synchronous manner, i.e., in a manner that the first message of all the executions are sent before the second message of any execution is sent etc.

As the UC-secure OT-hybrid 2PC protocol, we use the constant-round 2PC (actually, MPC) protocol of Ishai et al. [27], which makes only black-box use of pseudorandom generators (which in turn can be obtained in the black-box way from any semi-honest OT protocol). (The protocol of Ishai et al. [27] itself does not satisfy the above property, but it can be modified easily to satisfy them; see the full version of this paper.) Since the OT-hybrid protocol of Ishai et al. [27] is a black-box construction and has only constant number of rounds, our protocol \(\varPi _{\mathrm {2PC}}\) is also a black-box construction and has only constant number of rounds.

Simulator \(\varvec{\mathcal{S}im}\). As in Sect. 4.2, we consider a simulator that works against adversaries that participate in multiple sessions of \(\varPi _{\mathrm {2PC}}\). Let \(\mathcal {Z}\) be any environment, \(\mathcal {A}\) be any adversary that participates in multiple sessions of \(\varPi _{\mathrm {2PC}}\). Our simulator \(\mathcal{S}im_{\mathrm {OT}}\) internally invokes the adversary \(\mathcal {A}\), and simulates each of the sessions by using the simulator of \(\varPi _{\mathrm {OT}}\) (Sect. 4.2) and that of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) as follows.

1. 1.

   In each execution of \(\varPi _{\mathrm {OT}}\) at the beginning of \(\varPi _{\mathrm {2PC}}\), \(\mathcal{S}im\) simulates the honest party’s messages for \(\mathcal {A}\) in the same way as \(\mathcal{S}im_{\mathrm {OT}}\). Recall that \(\mathcal{S}im_{\mathrm {OT}}\) makes a query to \(\mathcal {F}_{\mathrm OT}\) during the simulation. When \(\mathcal{S}im_{\mathrm {OT}}\) makes a query to \(\mathcal {F}_{\mathrm OT}\), \(\mathcal{S}im\) sends those queries to the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) in order to simulate the answer from \(\mathcal {F}_{\mathrm OT}\). (Recall that the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) simulates \(\mathcal {F}_{\mathrm OT}\) for the adversary.)

2. 2.

   In the execution of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) during \(\varPi _{\mathrm {2PC}}\), \(\mathcal{S}im\) simulates the honest party’s messages for \(\mathcal {A}\) by using the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\), who obtained the queries to \(\mathcal {F}_{\mathrm OT}\) as above.

We remark that here we use the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) in the setting where multiple sessions of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) are concurrently executed and some super-polynomial-time computation is performed. However, the use of it in this setting does not cause any problem because it runs in the black-box straight-line manner.

Proof of Indistinguishability. We show that the output of the environment in the real world and that in the ideal world are indistinguishable. The proof proceeds very similarly to the proof for our SPS OT protocol (Sect. 4). To simplify the exposition, below we assume that \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) makes only a single call to \(\mathcal {F}_{\mathrm OT}\). (The proof can be modified straightforwardly when \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) makes multiple calls to \(\mathcal {F}_{\mathrm OT}\).)

Recall that \(\varPi _{\mathrm {2PC}}\) is obtained by composing our OT protocol \(\varPi _{\mathrm {OT}}\) with a OT-hybrid 2PC protocol \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\). Roughly, we consider a sequence of hybrid experiments in which:

• Each execution of \(\varPi _{\mathrm {OT}}\) is gradually changed to simulation as in the sequence of hybrid experiments that we considered in the proof of \(\varPi _{\mathrm {OT}}\) (Sect. 4.3).

• Once the execution of \(\varPi _{\mathrm {OT}}\) in a session of \(\varPi _{\mathrm {2PC}}\) is changed to simulation completely, the execution of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) in that session is changed to simulation.

More concretely, we consider hybrids \(H_0\) and \(H_{k:1}, \ldots , H_{k:9}\) (\(k\in [4m]\)), where \(H_0\) and \(H_{k:1}, \ldots , H_{k:7}\) are defined as in Sect. 4.3, and \(H_{k:8}\) and \(H_{k:9}\) are defined as follows.

Hybrid \(H_{k:8}\). \(H_{k:8}\) is the same as \(H_{k:7}\) except that in session s(k), if S is corrupted and \(\textsf {SM} _k\) is third special message, all the messages of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) from R are generated by the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\). More concretely, the messages of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) from R are generated as follows. Recall that from the definition of Hybrid \(H_{k:3}\), the implicit input \(v_b^* {\mathop {=}\limits ^\mathrm{def}}\mathsf {Value}(\varvec{\rho }^{\mathsf {ext}}_b, \varGamma _R\cap \varDelta )\) (\(b\in \{0,1 \}\)) to \(\varPi _{\mathrm {OT}}\) is extracted from the adversary in session s(k) (as \(\varvec{\rho }^{\mathsf {ext}}_b\) are computed for both \(b\in \{0,1 \}\)). Now, the messages of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) from R are simulated by feeding those extracted implicit input and the subsequent messages to the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\).

Hybrid \(H_{k:9}\). \(H_{k:9}\) is the same as \(H_{k:8}\) except that in session s(k), if R is corrupted and \(\textsf {SM} _k\) is fourth special message, all the messages of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) from S are generated by the simulator of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\).

Lemma 9

Assume that in \(H_{k:7}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:7}\) and \(H_{k:8}\) are indistinguishable, and

• in \(H_{k:8}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Lemma 10

Assume that in \(H_{k:8}\) (\(k\in [4m]\)), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability. Then,

• \(H_{k:8}\) and \(H_{k:9}\) are indistinguishable, and

• in \(H_{k:9}\), \(\mathcal {A}\) does not cheat in sessions \(s(k), \ldots , s(4m)\) except with negligible probability.

Lemma 10 can be proven identically with Lemma 9, and Lemma 9 can be proven quite similarly to Claim 1 (Sect. 4.3); the only difference is that we use the security of \(\varPi _{\mathrm {2PC}}^{\mathcal {F}_{\mathrm {OT}}}\) rather than the hiding of \(\mathsf {ExtCom}\). We give a proof of Lemma 9 in the full version of this paper.

By combining Lemmas 9 and 10 with Lemmas 2–8 in Sect. 4.3, we conclude that the output of \(H_0\) and that of \(H_{4m:9}\) are indistinguishable, i.e., the output of the real world and that of the ideal world are indistinguishable. This concludes the proof of Theorem 3.