Introduction

The exact round complexity of secure computation has been a focus of research in cryptography over the past two decades. This has been especially well-studied in the synchronous setting in the plain model, with up to all-but-one static malicious corruptions. It is known that general-purpose secure multiparty computation (MPC) protocols in this setting admitting a black-box simulator require at least 4 rounds of simultaneous exchange [GK96b, KO04,GMPP16]. 5 In this work we focus on MPC with black-box simulation. On the positive side, there has been a long sequence of works [GMPP16, BHP17, ACJ17, KS17, BGI + 17, BGJ + 18, CCG + 20] improving the round complexity, culminating in a round-optimal construction that relies on the minimal assumption that a 4-round malicious-secure OT protocol exists [CCG + 20].

Black-Box Use of Cryptography. Notably, all MPC protocols discussed above make non-black-box use of cryptography, which is typically associated with signiőcant overheads in efficiency. It is interesting, from both a theoretical and a practical perspective, to realize fully black-box protocols [RTV04] where not only does the simulator make black-box use of an adversary, but also the construction itself can be fully speciőed given just oracle access to the input-output relation of the underlying cryptographic primitives, and without being given any explicit representation of these primitives. In the following, we refer to this standard notion of fully black-box protocols as simply black-box protocols. The focus of this work is on the following natural question:

What is the round complexity of black-box MPC in the plain model?

It was only recently that the concrete round complexity of black-box MPC in the plain model was studied. Ishai et al. [IKSS21] obtained a őve-round MPC protocol making only black-box use of a public-key encryption scheme with pseudorandom public keys, along with any 2-message OT protocol satisfying semimalicious security. They also gave 4-round protocols for a restricted class of functionalities that consist of parallel copies of łsender-receiverž two-party functionalities. While signiőcantly improving over prior works, which required more than 15 rounds, it did not generally match the known 4-round lower bound. Indeed, round-optimal black-box protocols are not known even for the restricted case of two-sided 2PC, where both parties receive the output at the end of the protocol execution. Furthermore, [IKSS21] highlighted signiőcant barriers in extending their techniques to obtain a round-optimal construction.

Our Results. In this work, we overcome these barriers to obtain a 4-round blackbox MPC, thereby obtaining the őrst round-optimal fully-black-box MPC in the plain model for general functions. Our construction makes black-box use of any sub-exponential secure two-message OT, that satisőes a well-studied łstatistical sender privacyž (SSP-OT) property. This essentially requires that the sender input remain statistically hidden from an unbounded malicious receiver. Such an OT protocol can be instantiated based on (sub-exponential variants) of standard cryptographic assumptions such as DDH/QR/N th Residuosity/LWE [NP01, AIR01, Kal05, HK12, BD18, DGI + 19]. This covers most of the standard cryptographic assumptions known to imply public-key cryptography, with LPN being the most notable exceptionfoot_1

On the role of subexponentially secure OT. We stress that even though we rely on sub-exponentially secure OT, our őnal simulator still runs in expected polynomial time. This itself may seem counter-intuitive, and indeed we see it as a highlight of our technique and work. Very roughly, the reason why subexponentially secure OT is helpful to us for achieving polynomial-time simulation is that we design a protocol that admits two separate means for extracting the adversary's input. One is an łoptimisticž extraction that runs in expected polynomial time, and the other is a super-polynomial extraction that achieves stronger properties. We use the super-polynomial extraction to essentially łbootstrapž and allow the optimistic extraction to succeed for the purposes of simulation. (See Technical Overview below for more details.) We believe this technique is of independent interest and may inspire progress in other settings where standard polynomial simulation is desired, but there is a need to reduce round complexity beyond a barrier that arises from the need for some component of the protocol to achieve simulation security.

Finally, we note that the 4-round lower bound [GK96b, KO04, GMPP16] holds even when considering protocols that rely on sub-exponential hardness assumptions as long as the simulator runs in (expected) polynomial time.

Related Work

The black-box round-complexity of general purpose secure computation as well as for speciőc tasks such as oblivious transfer, zero-knowledge, non-malleable commitments etc., has a long and rich history.

General Purpose MPC. Haitner et al. [HIK + 11] gave the őrst construction of a malicious-secure black-box MPC protocol in the plain model based on any semihonest secure oblivious transfer. However, the round complexity of this construction grew linearly in the number of parties (denoted by n) even if one starts with a constant round semi-honest OT protocol. A later work of Wee [Wee10] gave a O(log * n) black-box protocol by relying on stronger cryptographic assumptions such as dense cryptosystems, or homomorphic encryption, or lossy encryption. This was later improved by Goyal [Goy11] to give a constant round protocol under similar assumptions. Unfortunately, this constant was more than 15 which is a far cry from the lower bound of 4. A recent work of Ishai et al. [IKSS21] gave a black-box őve-round protocol based on any PKE with pseudorandom public keys and any two-message OT protocol with semi-malicious security.

Special Secure Computation Tasks. For the case of oblivious transfer, Ostrovsky et al. [ORS15] gave a round-optimal (i.e., a four-round) construction that made black-box use of enhanced trapdoor permutations. Friolo et al. [FMV19] gave a round-optimal black-box construction of OT based on any public key encryption with pseudorandom public keys. Other black-box constructions of four-round OT from lower level primitives were given in [CCG + 21, MOSV22]. Ishai et al. [IKSS21] extended these results to the multiparty setting and gave a round-optimal protocol for pairwise oblivious transfer functionality. In the pairwise OT setting, each ordered pair of parties, namely, P i and P j execute an OT instance with P i acting as the sender and P j acting as the receiver. This can be extended to parallel instances of general two-party sender-receiver functionalities.

Hazay and Venkitasubramanian [HV18] and Khurana et al. [KOS18] gave round-optimal black-box constructions of zero-knowledge arguments based on injective one-way functions. Hazay et al. [HPV20] showed that unless the polynomial hierarchy collapses, all of NP cannot have a black-box zero-knowledge argument based on one-way functions. Goyal et al. [GLOV12] gave the őrst constant-round black-box construction of non-malleable commitments based on one-way functions. A latter work of Goyal et al. [GPR16] gave a three-round (which is round-optimal) black-box construction that is secure against a weaker class of synchronizing adversaries assuming the existence of injective one-way functions.

Technical Overview

In this section, we give an overview of the main techniques used in our construction of a round-optimal black-box secure multiparty computation protocol.

Starting Point. The starting point of our work is the recent result of Ishai et al. [IKSS21] who gave a construction of a őve-round MPC protocol that makes black-box use of any public-key encryption scheme with pseudorandom public keys and any two-message semi-malicious OT protocol.foot_2 Their protocol is obtained via a round-efficient implementation of the IPS compiler [IPS08] in the plain model.

We note a key component that was used in their instantiation: a four-round black-box protocol that securely implements the watchlist functionality. Informally speaking, the watchlist functionality is an n-party functionality where each ordered pair of parties (P i , P j ) where i, j ∈ [n] are involved in a k-out-of-m OT instance with P i acting as the sender and P j acting as the receiver. Using this four-round watchlist protocol, Ishai et al. [IKSS21] showed that with an additional round of interaction, it is possible to securely compute any multiparty functionality. Furthermore, the resulting protocol only made black-box use of cryptographic primitives.

Going Below Five Rounds. In the same work, Ishai et al. [IKSS21] also observed that to get a four-round protocol (which is round-optimal) in the plain model by making use of the IPS compiler, one needs a three-round watchlist protocol. However, such a protocol cannot satisfy the standard simulation based security deőnition w.r.t. a simulator that only makes black-box use of the adversary. This is because such a simulation-secure watchlist protocol almost directly implies a three-round protocol for oblivious transfer that satisőes standard simulation security. We know that such a protocol is impossible to construct (even with non-black-box use of cryptography) if the simulator uses the adversary in a black-box manner [KO04]. Furthermore, to make matters more complicated, the proof of security of the overall compiler given in [IKSS21] crucially relied on the watchlist protocol to satisfy the standard simulation-style deőnition. Therefore, to go below őve rounds and obtain a round-optimal construction, we need to come up with a new set of techniques.

Our Approach in a Nutshell. In this work, we show how to instantiate the IPS compiler using a weaker notion of watchlists, that we call watchlists with promise security. As one of our main contributions, we give a construction of a threeround watchlist protocol that satisőes promise security. In Section 2.1, we motivate the deőnition of this weaker watchlist protocol and show how it can be used to instantiate the IPS compiler and in Section 2.2, we give the main ideas in constructing such a watchlist protocol.

Instantiating the IPS Compiler with Three-Round Watchlist

What Security can be achieved in Three Rounds? The work of Ishai et al. [IKSS21] gave a round-preserving compiler that transforms any two-party computation protocol that satisőes certain additional properties (which we will ignore for the moment) to a watchlist protocol. To understand what security properties can be achieved by a three-round watchlist protocol, let us őrst try to understand what type of security can be achieved by a three-round 2PC protocol.

Recall that in the standard two-party protocol setting, there is a receiver who holds an input x and there is a sender who holds an input y. At the end of the protocol, the receiver obtains the output of f (x, y) for some pre-determined functionality f . If we consider three-round protocols for the above task, then the őrst and the third round messages in the protocol are sent by the sender and the second round message is sent by the receiver.foot_3 As the sender is tasked with sending both the őrst and the third round message, a simulator could potentially rewind the second and the third round messages in the protocol and extract the effective private input from an adversarial sender. In other words, a three-round 2PC protocol could satisfy standard simulation-based security deőnition against malicious senders. However, the receiver in this protocol is only sending a single message, namely, the second round message. In fact, it is impossible to design a black-box PPT simulator that could extract the effective private input from an adversarial receiver.

The key observation is that if we allow the simulator against malicious receivers to run in super-polynomial time, then such a simulator can extract the effective receiver input and provide security against malicious receivers. Therefore, in the three-round setting, we can hope to construct a two-party protocol that satisőes standard simulation based security against malicious senders and super-polynomial time simulation security against malicious receivers. Indeed, as we explain later, we give a construction of such a three-round protocol that makes black-box use of a sub-exponentially hard two-message OT protocol with statistical sender security. Such an OT protocol is known from the (subexponential variant) of standard cryptographic hardness assumptions such as DDH/N th residuosity/LWE/QR [AIR01, NP01, Kal05, HK12, BD18, DGI + 19].

Instantiating the IPS Compiler with the Three-Round Watchlist. Given the twoparty protocol above, we could hope to obtain a three-round watchlist satisfying łsemi-SPSž security by following ideas in prior work [IKSS21]. If this were possible, could we directly get a four-round MPC protocol by instantiating the IPS compiler with this łsemi-SPSž three-round watchlist protocol? Unfortunately, this is not quite possible, as we now explain. To understand this better, we give a brief overview of the IPS compiler which is simpliőed and tailored to constructing a four-round protocol. The IPS compiler makes use of the following components:

-A two-round client-server MPC protocol that is secure against a malicious adversary that corrupts an arbitrary number of clients and a constant fraction of the servers. This is called as the outer protocol. Such an outer protocol was constructed by Ishai et al. [IKP10,Pas12] by making black-box use of any PRG. -A four-round inner protocol that satisőes the following robustness property.

Speciőcally, even if the adversary behaves maliciously and deviates arbitrarily from the protocol speciőcation in the őrst three rounds, it cannot learn any information about the inputs of the honest parties. Furthermore, if the adversary is able to produce an input, random tape that correctly explains that the messages sent by it in the őrst three rounds, then the last round message from the honest parties only reveals the output of the functionality.foot_4 -A three-round watchlist protocol that satisőes the standard extraction of the adversarial sender inputs and super-polynomial time extraction of the adversarial receiver inputs.

In the compiled protocol, each party plays the role of a client in the outer protocol and computation done by the servers are emulated by the inner protocol. To ensure that that the adversary only cheats in at most a small number of these inner protocol executions, we make use of the watchlist protocol. Speciőcally, each party acting as the receiver in the watchlist protocol chooses a random subset of k executions as part of its secret watchlist. Every other party acting as the sender uses the input, randomness used in each of the inner protocol executions as the sender inputs. This watchlist protocol is run in parallel with the őrst three rounds of the inner protocol. At the end of the third round, each party checks if the input, randomness pair provided by every other party corresponding to its watched executions are consistent. If it detects any inconsistency, then it aborts. Using standard probabilistic arguments, it is possible to show that if the honest parties have not aborted at the end of their watchlist check, then the adversary only deviates in a tiny constant fraction of the inner protocol executions. These deviations can be directly mapped to the corresponding server corruptions in the outer protocol. Since the outer protocol is secure against a constant fraction of the server corruptions, security of the overall protocol follows.

While the above intuition seems sound, we encounter a major issue while formalizing it. In particular, recall that we are aiming for standard polynomial security for our 4-round protocol, but we are relying on super-polynomial time extraction as an ingredient. Thus, we are only able to show that this protocol satisőes security via a super-polynomial time simulator. The łsuper-polynomialž part in this simulator is needed to extract the receiver inputs used by the adversarial parties in the watchlist protocol. Recall that in the watchlist protocol, the adversarial receiver inputs correspond to the set of watched executions of the corrupted parties. We need to extract this information in order to invoke the security of the outer protocol.foot_5 Further, the simulator also needs to additionally extract the adversarial sender inputs. As mentioned earlier, we cannot hope to simultaneously achieve efficient polynomial time extraction of both the sender and the receiver inputs.

Our Solution: łPromise-Stylež Extraction. In order to get around this issue, we use a łpromise-stylež extraction technique that is inspired by the notion of Promise Zero-Knowledge [BGJ + 18]. Speciőcally, we seek to devise an alternative polynomial-time extraction system that guarantees extraction of the adversarial receiver inputs only against those adversaries that send a valid third round message in the watchlist protocol (with non-negligible probability). For all other adversaries, we do not provide any guarantees. Let us now explain how this weaker extraction guarantee is sufficient to instantiate the IPS compiler.

The simulator of the compiled protocol starts generating the őrst-round messages of the outer protocol using some default inputs for the honest parties. Note that these őrst round messages correspond to the inputs to the inner protocol executions. The simulator uses these łdummyž inputs to the inner protocol and starts interacting with the adversary for the őrst three rounds. If the adversary aborts during this interaction, or fails to send a valid third round message in the watchlist protocol, then the simulator simply outputs the view of this adversary. On the other hand, if the adversary sends a valid third round message in the watchlist protocol, then the simulator uses the łpromise-stylež extractor to extract the set of watched executions. This information is then used by the simulator to simulate the messages in the main thread (using Goldreich-Kahan simulation technique [GK96a]).

A subtle point to note here is that the third round message in the watchlist protocol is sent by the adversary only after it receives the third round message from the honest parties (as we are considering rushing adversaries). However, the third round message of the watchlist protocol delivers the input, randomness used by the honest parties corresponding to the adversarial watched executions. Recall that the simulator described above uses łdummyž inputs in the inner protocol executions and tries to extract the adversarial watched executions. This will succeed only if the distribution of the messages generated by the simulator is computationally indistinguishable to the messages in the real protocol. Specifically, to prove this indistinguishability, we need to make sure that the output of the watchlist protocol when using the real inputs is indistinguishable to the case when the simulator uses default inputs.

To argue this, we rely on the security of the outer protocol. Recall that the inputs given to the inner protocol executions correspond to the messages sent by the clients to the servers. By corrupting the servers corresponding to the adversarial watched executions, we are guaranteed that the őrst round message sent to these servers reveals no information about the inputs of the honest clients. To give a bit more details, this is realized by őrst relying on the SPS security of the watchlist protocol against adversarial receivers to extract the adversarial watched executions, and then switch the input to a default value by relying the security of the outer protocol, and then switch back to an honest watchlist execution using the default inputs.

Another point to note here is that we cannot guarantee perfect extraction of the adversarial receiver inputs even if it sends a valid third round message with non-negligible probability. Due to technical reasons, we can only guarantee łalmostž perfect extraction. By this, we mean that whenever the output received by the adversarial receiver is not ⊥, the output of the promise extractor is identical to the SPS extractor. In other cases, there are no guarantees about the extracted value. We show that this weaker property is sufficient to instantiate the IPS compiler. Roughly, this is because if the output of the watchlist protocol is provided to the adversary is ⊥, the adversary learns no information about the input, randomness for any inner protocol execution. Hence, if the promise extractor łover-extractsž the adversarial watched executions, this does not create any trouble with the simulation.

Constructing Three-Round Watchlists with Promise Extraction

A core ingredient of our black-box MPC protocol is a three-round łwatchlistž protocol with promise-style extraction guarantees. For every i ∈ [n], j ∈ [n] \ {i}, this functionality enables P i to choose a (private) subset K ⊆ [m] of protocol executions of size k, and obtain the input and randomness used by P j in all executions in the set K, while all other input and randomness values of P j remain hidden from P i .

Our őrst goal is to develop a three round protocol that realizes the watchlist functionality in the plain model in the presence of malicious corruptions, with super-polynomial simulation and (polynomial) promise-style extraction. Following [IKSS21], we observe that it would suffice to implement łsender nonmalleablež OTs with super-polynomial simulation-based łreal/idealž security and with promise-style polynomial extraction; where in the (i, j)-th execution for i ∈ [n], j ∈ [n] \ {i}, P i is the receiver and P j is the sender. P j 's input to the OT will be the input and randomness it used in each of the m instances of the inner protocol, and P i 's input is a random subset K of [m] of size k. By sender non-malleability, we mean that the adversarial parties cannot maul the sender messages in an OT execution with an honest party to obtain a łrelatedž sender inputs in an OT execution with an honest receiver.

The work of [IKSS21] showed how to implement such sender non-malleable OT in four rounds from any four-round simulation-secure two-party computation protocol with certain additional properties (which we ignore for the momemt). Since we need three-round watchlists, we would need to begin with three-round two-party computation, which is impossible to realize with black-box polynomialtime simulation security. Nevertheless, we show that it is possible to realize such two-party computation with super-polynomial simulation and promise-style extraction, which is one of our key technical contributions. We describe this in the next subsection; here we discuss how such a two-party protocol can be compiled into 3-round non-malleable OT.

Our overall approach builds on [IKSS21], but also diverges in some key technical aspects. Like [IKSS21], our construction relies on a secure two-party protocol between a sender and a receiver realizing a special functionality F (described in Figure 1). Unlike [IKSS21], we must develop a three-round compiler instead of a four round one.

In the [IKSS21] compiler, the sender S on input (m 0 , m 1 ) őrst encodes these messages using an appropriate 2-split-state non-malleable code (Enc, Dec).foot_6 For technical reasons pertaining to the use of watchlists in our őnal protocol, we require our watchlists to satisfy 1-rewinding security, i.e., no adversary should be able to distinguish the joint distribution of a main and a rewinding thread (with common preőx) from the real distribution, from those sampled according to the simulated distribution. This was not needed by [IKSS21], but this requirement in our setting necessitates deviating from the [IKSS21] template, relying on (a special type of) 3-split-state non-malleable code ś speciőcally one that is also a 3-out-of-3 secret sharing scheme ś instead of 2-split-state non-malleable codes.

Speciőcally, our sender encodes

The receiver obtains input a choice bit b ∈ {0, 1}, and additionally samples a uniformly random c ∈ {0, 1, 2}. S and R invoke a two-party secure protocol Π to compute functionality F, described in Figure 1.

Sender Inputs: m0, L0, M0, R0, m1, L1, M1, R1, Receiver Inputs: b, c The functionality F is deőned as follows.

Fig. 1: The functionality F

We note that the ideal functionality F only reveals m b to the receiver, and statistically hides m 1-b . This is because the receiver obtains only one of L 1-b , M 1-b and R 1-b , and secrecy follows from the security of the secret sharing scheme. Thus, given one of the states the message m 1-b is information-theoretically hidden. Further, even given two executions of the ideal functionality on the same sender inputs, same receiver input b, and different receiver challenges c, the receiver only obtains m b and two out of L 1-b , M 1-b and R 1-b . Given two out of these three shares, m 1-b is again statistically hidden. Indeed, when F is realized via a secure protocol Π, m 1-b continues to be computationally hidden even given a main and rewinding thread (with same inputs m 0 , m 1 , b). This protocol Π makes only black-box use of cryptography, and can be based on black-box access to our three-round two-party computation protocol that additionally satisőes certain amount of rewinding security, which we discuss in the next subsection.

Proving Sender Non-Malleability. We must prove that running this protocol Π between every pair of parties in parallel securely realizes the watchlist functionality. We model the adversary as a man-in-the-middle, which acts as a receiver in łleftž sessions and as sender in łrightž sessions. We require that there is a simulator-extractor Sim-Ext that given the inputs of all honest receivers (in all right sessions), is able to extract all the implicit inputs used by the man-in-themiddle in all its right sessions. Crucially, Sim-Ext does not have access to the inputs of honest senders. Since the underlying protocol Π may be susceptible to arbitrary mauling attacks, achieving this property is non-trivial, as we discuss next.

Similar to [IKSS21], we use the speciőc way that sender inputs are encoded to introduce an alternate extraction mechanism. Speciőcally, one could imagine rewinding the second and the third round message of Π twice, with őrst round message őxed, and using inputs c = 0, c = 1 and c = 2 on behalf of the honest receiver in the real and rewinding threads, respectively. Our two-party computation protocol will be developed in such a way that őxing the őrst round message will őx all other inputs m 0 , m 1 , b in all left and right sessions. Let us make the simplifying assumption that our adversary does not abort. Therefore, we expect to obtain outputs ( L 0 , L 1 ), ( M 0 , M 1 ) and ( R 0 , R 1 ) in the right session in the real and rewinding threads respectively. At this point, we can use the decoder of the non-malleable code to obtain ( m 0 , m 1 ), which, by correctness of the two-party protocol, should correspond to the implicit inputs of the MIM in the right session.

The Need for 2-Rewinding Security. Before we can rely on non-malleable codes to formally argue security, we need to replace the two-party protocol Π with its simulated version. At the same time, we need to argue that the joint distribution of values extracted from the strategy above (via extracting ( L 0 , L 1 ), ( M 0 , M 1 ) and ( R 0 , R 1 )) from the simulated two-party protocol, matches the distribution in the real protocol. This requires the two-party protocol Π to satisfy a stronger security property, that we call 2-rewind sender security. This roughly means that any adversarial receiver/MIM that rewinds the honest sender one time in the third and fourth rounds, with its input c set to a possibly different value, does not learn more than the output of F on (őxed) inputs

). This can be formalized by demonstrating the existence of a simulator that simulates the receiver's view in the real and rewinding threads, given only (m b , L 0 , L 1 ) in the main thread, and (m b , M 0 , M 1 ), (m b , R 0 , R 1 ) respectively in each of the rewinding threads (w.l.o.g.). Now, it may seem like the sum total of this information could essentially allow the receiver to recover m 1-b . Yet, we show that if Π satisőes this property, it becomes possible to replace m 1-b with an arbitrary value (say 0 λ ).

Here we make use of the fact that the different states of the non-malleable code are available to the MIM in separate (i.e. real and rewinding) executions, which allows us to rely on the security guarantees provided by non-malleable codes, by arguing that each of these states are essentially tampered by independent functions.

Finally, we note that just as in [IKSS21], we require these codes to satisfy many-many non-malleability. At a high level, these are codes that are secure against multiple tamperings of a codeword [CGL16]. We note that a construction of 3-out-of-3 non-malleable secret sharing from [GSZ21] satisőes all the required properties (if instantiated with the CGL non-malleable code). Also following [IKSS21], to deal with adversaries who might abort, we will modify the protocol and functionality F so that instead of encoding (m 0 , m 1 ) a single time, the sender generates λ (where λ is the security parameter) fresh encodings

,b∈{0,1} of m 0 and m 1 . The receiver picks λ choice bits c 1 , . . . , c λ instead of a single bit c. The functionality F checks if for every i ∈

. We also recall that our watchlists need to satisfy super-polynomial simulation with łpromise-stylež extraction, but we note that these properties in fact carry over from the underlying special two-party computation protocol.

Constructing Three-Round 2PC with Special Extraction

In this subsection, we explain the key ideas behind our construction of a threeround 2PC that satisőes the łpromise-stylež extraction guarantee and ł2-rewindingž sender security.

3-Round OT Protocol. As a őrst step, we construct a three-round black-box OT protocol that satisőes standard simulation-based security against malicious senders and super-polynomial time simulation security against malicious receivers. For this purpose, we rely on a (sub-exponentially hard) two-round OT protocol that has super-polynomial time simulation security against malicious receivers. To enable polynomial time extraction of the malicious sender input, we additionally require the sender to generate an extractable commitment to its input. To ensure the consistency of inputs used in the extractable commitment and the ones used in the OT protocol, we rely on the IPS compiler. Speciőcally, we use the 1-out-of-2 SPS OT to construct a k-out-of-m SPS OT protocol (using Yao's garbled circuits) and use this as the watchlist protocol. We show that this watchlist protocol is sufficient to instantiate the IPS compiler when we only require SPS security against malicious receivers.

3-Round 2PC. As a next step, we use the above OT protocol to construct a threeround 2PC protocol that satisőes standard simulation security against malicious senders and SPS security against malicious receivers. This step involves standard tools and closely follows the construction given in [IKSS21]. Additionally, we also show how to add 2-rewinding sender security to this protocol. Speciőcally, we show that if the underlying 3-round OT is 2-rewinding sender secure and we also have a 2-rewinding secure extractable commitment scheme (which was constructed in [BGJ + 18]), we get a 2-rewinding sender secure 2PC protocol. Further, we note that 2-rewinding sender security of our 3-round OT protocol just boils down to instantiating the underling extractable commitment on the sender side (as explained earlier) with a 2-rewinding secure one, and we instantiate this with the construction given in [BGJ + 18].

3-Round 2PC with Special Extraction. We then use the above 3-round 2PC protocol to construct a protocol that additionally satisőes the łpromise-stylež extraction guarantee. To achieve this, we require the receiver to commit to its input (as well as the randomness) used in the 2PC protocol via a three-round extractable commitment. Again, as in the case of OT protocol, we need to make sure that the inputs committed via the extractable commitment is consistent with the inputs used in the 2PC protocol. As before, we rely on the IPS compiler but we observe that we do not need the łfull-blownž watchlist protocol. Instead, we require the sender in the second round to send a set of executions to be opened in the clear and the receiver in the őnal round opens the extractable commitment corresponding to these executions. The sender then checks whether the input, randomness committed via the extractable commitment is consistent with the messages sent in the 2PC protocol. If they are consistent for randomly opened set of executions, then by standard statistical argument, we can show that they are consistent for a majority of the executions with overwhelming probability. This allows us to rewind and extract the receiver's input via the extractable commitment. We note that we are only able to guarantee łalmostž perfect extraction due to the existence of a łsmallž set of inconsistent executions. Speciőcally, the łsmallž set of inconsistent executions could force the output of the watchlist protocol to be ⊥, but even in this case, our polynomial time extract could extract some receiver input. But as explained earlier, this is not problematic and is sufficient to instantiate the IPS compiler. We also note that if the underlying 2PC protocol is 2-rewinding sender secure then this property is inherited by the 2PC protocol with special extraction as well.

Organization. Due to lack of space, we only present the watchlist protocol and defer the other constructions and their proof of security to the full version.

Preliminaries

We recall some standard cryptographic deőnitions in this section.

Split-State Non-Malleable Codes

We will use non-malleable codes in the splitstate model that are one-many secure and satisfy a special augmented nonmalleability [AAG + 16] property, as discussed below.

Definition 1 (One-many augmented split-state non-malleable codes).

) and every set of permutations

there exists a random variable D f,g,h,σ,σ ′ on R×{{0, 1} p(λ) ∪same * } ℓ(λ) which is independent of the randomness in NM.Code such that for all messages m ∈ {0, 1} p(λ) it holds that the statistical distance between the distributions

and

is at most ϵ(λ), where the function replace : {0, 1} * ×{0, 1} * → {0, 1} replaces all occurrences of same * in its őrst input with its second input, and outputs the result.

We note that the construction of non-malleable secret sharing in [GSZ21] can be proven to satisfy this deőnition. This is already implicit in [GSZ21] for the case of single tampering but extension of their proof to the case of multiple tamperings follows directly if we use a strong two-source non-malleable extractors that is multi-tamperable [CGL16].Thus, we have the following: Lemma 1. [GSZ21] For every polynomial ℓ(•), there exists a polynomial q(•) such that for every λ ∈ N, there exists an explicit ℓ-augmented, split-state nonmalleable code satisfying Deőnition 1 with efficient encoding and decoding algorithms with code length q(λ), rate q(λ) -Ω(1) and error 2 -q(λ) Ω (1) .

Low-Depth Proofs Any computation performed by a family of polynomial sized ciruits can be transformed into a proof that is veriőable by a family of circuits in NC1. We refer to the transformation as a low-depth proof, and we require such a proof to satisfy the following deőnition.

Definition 2 (Low-Depth Non-Interactive Proofs). A low-depth non-interactive proof with perfect completeness and soundness for a relation R consists of an (efőcient) prover P and a veriőer V that satisfy:

-Perfect completeness. A proof system is perfectly complete if an honest provers can always convince an honest veriőer. For all x ∈ L we have

-Perfect soundness. A proof system is perfectly sound if it is infeasible to convince an honest veriőer when the statement is false. For all x ̸ ∈ L and all (even unbounded) adversaries A we have

-Low Depth. The veriőer V can be implemented in NC1.

It is shown in [IKSS21] building on [GGH + 13] how such a non-interactive proof can be constructed in a simple way. Looking ahead, our construction of watchlists makes use of a (malleable) two-party computation protocol for NC1 that must verify validity of a non-malleable code. We rely on low-depth proofs to ensure that the two-party computation protocol only performs NC1 computations.

3-Round Two-Party Computation Protocol with Special Extraction

The watchlist protocol requires a special two-party computation protocol. We give a construction of this protocol in the full version and present the deőnition here.

Syntax. A three-round protocol Π = (Π 1 , Π 2 , Π 3 , out Π ) between a sender and a receiver proceeds as follows. In each round r ∈ [3], the sender runs Π r on its identity, the transcript, its input and randomness to generate msg S r . Similarly, in round r, the receiver runs Π r on its identity, the transcript, its input and randomness to generate msg R r . The sender sends msg S r to the receiver and the receiver sends msg R r to the sender and these messages are then added to the transcript. At the end of the protocol, the receiver run out Π on its identity, transcript, its input and randomness to compute the output which is a string z or ⊥. The sender runs out Π on its identity and the őrst round message from the receiver, the second round message from the sender and third round message from the receiver and outputs either accept/reject. We note that while the output computation of the receiver requires access to its private random tape, the output of the sender is publicly computable. -Public Coin Second Round Messages. The second round messages from the sender and the receiver are both public coin.

-Security against Malicious Senders. There exists an expected PPT machine Sim S such that for every non-uniform A the corrupts the sender and for every receiver's input x ∈ {0, 1} n , we have:

In the above deőnition, we note that if y output by Sim S is the special symbol ⊥, then the output of f is also ⊥. We additionally need the existence of a straight-line SPS simulator SPSim S that has the same guarantees as Sim S . -Super-Polynomial Time Simulation Security against Malicious Receivers. There exists a super-polynomial time machine

) such that for every adversary A corrupting the receiver and for every sender's input y ∈ {0, 1} n , we have:

where the experiment Ideal R is described in Figure 2.

-2-Rewinding Sender Security against Sub-Exponential Adversaries.

We require that this protocol to be secure against any malicious sub-exponential time receiver that could rewind an honest sender twice by giving possibly different second round messages in each rewind. -Special Extraction of the Malicious Receiver Input. There exists a super-polynomial time extractor SPSpecExt R such that for any adversary A corrupting the receiver and for any sender input y ∈ {0, 1} n , the probability the following experiment outputs 1 is negligible: 1. Sample a transcript T from Ideal R (1 λ , y, A, SPSim R ).

2. If the output of the sender S in the transcript T is reject, then output of the experiment is 0.

output of the experiment is 0. 4. Else, run SPSpecExt(T) to obtain x ′ . 5. The output of the experiment is 1 if and only if x ̸ = x ′ .

-Existence of k accepting Transcript Extractor. There exists a polynomial time machine Ext R that on input any k transcripts T 1 , . . . , T k such that in each of the transcript the output of the sender is accept outputs x such that x = SPSpecExt(T 1 ) with overwhelming probability. -Delayed Function Selection. The function to be computed can be chosen by the sender in the third round.

The Watchlist Protocol

In this section, we formally construct and prove security of three-round watchlist protocol. Recall that in the watchlist protocol, each ordered pair of parties P i -Run SPSim and P j invoke a ℓ-out-of-m OT functionality where P i acts as the receiver and P j acts as the sender. Speciőcally, the private input of party P j in this OT instance consists of of x j which is the vector of sender inputs of dimension m and the private input of party P i is K i which is a subset of [m] of size ℓ. The output to party P i consists of {x j,k } k∈Ki . We note that in the watchlist protocol, every honest party P i uses the same K i in each instance of the OT functionality when acting as the receiver and same x i in each instance when acting as the sender. However, the corrupted party P i may choose different K i and x i for each instance when acting as the receiver and the sender respectively. For ease of notation, whenever we use K i as the receiver input of a corrupted party P i , we actually mean a set of subsets {K i,j } j∈H . Similarly, whenever we use x j as the sender input of a corrupted party P j , we actually mean set of vectors, one for each honest party.

Definitions

Before we proceed to the formal deőnition of the watchlist protocol, we give an informal overview of the various properties that the protocol needs to satisfy.

1. The őrst requirement is the existence of a straight-line super-polynomial time simulator Sim WL that has oracle access to the watchlist functionality and produces a view of the adversary that is computationally indistinguishable to the real world. This requirement is same as standard SPS security. Here, it is crucial that the simulator is straight-line i.e., it does not rewind the adversary. 2. The second property is about the existence of an łalternatež extraction mechanism of the malicious receiver inputs. Speciőcally, we require that if the output of all the honest parties when acting as the sender is not ⊥ in the protocol, then there exists an alternate super-polynomial time extractor SPExt WL,R that extracts the adversarial receiver inputs using the accepting transcript. Further, for each corrupted party, these inputs are the same as the ones extracted by Sim WL except in the case that it is ⊥.

3. The third property is about the existence of polynomial-time rewinding extractor (that rewinds the adversary until it obtains k accepting transcripts) and outputs the malicious receiver inputs that is identical to the one output by SPExt WL,R . For technical reasons, we need to separate out the existence of a polynomial time rewinding extractor and super-polynomial time extractor in the alternate extraction mechanism. 4. The fourth property is about the one-rewinding sender non-malleability.

Roughly speaking, it requires that adversarial sender inputs cannot depend on the honest party sender inputs even if the adversary is allowed to rewind the second and third round message of the protocol once.

Definition 4 (Extractable (n, m, ℓ)-Watchlists). Fix any polynomials n = n(λ), m = m(λ), ℓ = ℓ(λ). An extractable (n, m, ℓ)-watchlist is a protocol that achieves the simultaneous n-party m-choose-ℓ OT functionality with the following security guarantees:

1. Real-Ideal Security with Straight-line SPS simulator. There exists a (stateful) straight-line super-polynomial time simulator Sim WL such that for any (stateful) adversary A that is corrupting an arbitrary subset M of the parties and for any choice of honest party inputs {x j , K j } j∈H (where H denotes the set of honest parties, x j 's denote the sender inputs of party j, and K j 's denote the set of executions that player j watches), we have the following two distributions are computationally indistinguishable: (a) View of the adversary and the output of all the honest parties H in the real execution of the protocol. (b) Ideal SP S (1 λ , M, A, Sim WL ) where Ideal SP S is given in Figure 3. Furthermore, the distribution of the messages generated by Sim WL on behalf of honest receivers is identically distributed to the real receiver messages with dummy inputs. 2. Special Extraction of the Malicious Receiver Input. There exists a super-polynomial time extractor SPExt WL,R such that for any adversary A corrupting a subset M of the parties and for any choice of honest party inputs {x j , K j } j∈H , the probability that the following experiment outputs 1 is negligible: (a) Sample a transcript T from Ideal SP S experiment and let {σ j } j∈H be the output of the honest parties.

The output of the experiment is 1 if and only if there exists an i ∈ H such that

Existence of k accepting Transcript

Extractor. There exists a polynomial time machine Ext WL,R such that on input any k transcripts T 1 , . . . , T k with common őrst message such that in each of the transcript the output of the honest parties is not ⊥ outputs {K j } j∈H such that {K j } j∈H = SPExt WL,R (T 1 ) with overwhelming probability.

4. One-Rewinding Sender Non-Malleability. We require the existence of an (expected) PPT algorithm Ext WL,S such that for any 1-rewinding adversary A corrupting any set M of the parties (by 1-rewinding, we refer to an adversary that is allowed to rewind the second and third round message of the protocol once) and for any choice of honest party inputs {x j , K j } j∈H such that the following two distributions are computationally indistinguishable against adversaries that run in time which is polynomial in the running time of SPSim WL,R : (a) Consider the Ideal SP S experiment in Figure 3 with the 1-rewinding adversary A (i.e., step-4 in the experiment is repeated once more). Let us denote the őrst execution with the adversary as the main thread and the rewinding execution with A as the rewind thread. After step-4, run Sim WL on the messages generated in the main thread to compute {x i } i∈M . Output the view of the adversary A and {x i } i∈M . (b) Sample uniform random tape {r j } j∈H and execute the protocol honestly with the 1-rewinding adversary A using the honest inputs {K j , x j } j∈H with the above random tape. Run Ext WL,S (1 λ , {K j , x j , r j } j∈H ) to obtain {x i } i∈M . Output view of the adversary in the above honest execution along with {x i } i∈M .

Construction

Our construction is described in Figure 4, and makes use of the following ingredients:

-A 3 round two-party secure computation protocol Π satisfying Deőnition 3 with delayed-function selection for NC 1 circuits and 2-rewinding sender security.

-An information-theoretic m(λ) • ℓ(λ) non-malleable coding scheme satisfying Deőnition 1. -A low-depth proof for P according to Deőnition 2.

-An existentially unforgeable signature scheme with algorithms denoted by Signature.Setup, Signature.Sign and Signature.Verify.

We describe our protocol formally in Figure 4. The correctness of this protocol follows from correctness of the underlying oblivious transfer, non-malleable codes and signature scheme. In what follows, we formally prove security according to Deőnition 4. Proof of Theorem 1. We observe that properties 2 and 3 carry over from the properties of the underlying two-party computation protocol, and 1 is implied by 4 together with SPS security of the two-party protocol against malicious adversaries (following [IKSS21]). Our key goal is to prove that the protocol satisőes property 4. To keep exposition simple, we prove this property against polynomial time distinguishers. We note that indistinguishability against distinguishers running in time which is polynomial in the running time of SPExt WL,R follows directly from the 2-rewinding sender security of the underlying 2PC protocol against such distinguishers. We now consider a man-in-the-middle adversary that participates as an OT receiver in upto ℓ(λ) executions of this protocol on the right, and participates as an OT sender in upto ℓ(λ) executions on the left. Towards proving that our protocol satisőes property 1, we will prove that there exists a PPT algorithm Sim-Ext, that with black-box access to the MIM, and to ℓ copies of the ideal OT functionality OT = {OT j ({m i,j } i∈[m] , •)} j∈[ℓ] and with input {K j } j∈[ℓ] , simulates an execution of the protocol with the MIM and extracts all the inputs

used by the MIM in the executions where the MIM is sender. We will prove that the 1-rewinding view output by Sim-Ext, that we denote by

) will be such that

where the expression on the left denotes the joint distribution of the view and messages committed by a 1-rewinding adversary in an interaction where honest senders S j have inputs {m i,j } i∈[m] , and honest receivers R j have inputs K j .

To prove indistinguishability, we deőne a sequence of hybrid experiments, where the őrst one outputs the distribution

Inputs: Sender S has inputs {mj}j∈m and receiver R has input a set K ⊆ [m] where |K| = k.

Protocol: S and R do the following.

1. S samples (vk, sk) ← Signature.Setup(1 λ ), then does the following.

-

, pick uniform randomness ri,j and compute (Li,j, Mi,j, Ri,j) = NM.Code((vk|mj); ri,j).

-Set instance x = (vk, {(Li,j, Mi,j, Ri,j, mj)} i∈[λ],j∈ [m] ) and language

NM.Decode(Li,j, Mi,j, Ri,j) = (vk|mj) .

Compute ldp = LDP.Prove(x, L).

For each

3. Both parties engage in the protocol Π to compute functionality F where:

-R plays the receiver with input K committed in round 1 and delayed function (c1, . . . , c λ ) chosen in round 2. -S plays the sender with input (x, ldp), where x is parsed as

generates an output as follows:

Additionally, S signs messages generated according to Π, denoted by (Π1, Π3). It sets σ1 = Signature.Sign(Π1, idS, sk), σ3 = Signature.Sign(Π3, idS, sk) where idS is the identity of the sender. It sends (σ1, σ3) to R. 4. R obtains output out and parses out = (vk, {mj}j∈K , •). It outputs {mj}j∈K iff Signature.Verify(σ1, Π1, idSvk) ∧ Signature.Verify(σ3, Π3, idS, vk) = 1, otherwise outputs ⊥.

Formally, these hybrids are deőned as follows:

Hyb 0 : This corresponds to an execution of the MIM with ℓ honest senders {S j } j∈[ℓ] on the left, each using inputs {m i,j } i∈[m] respectively and ℓ honest receivers on the right with inputs ({K j } j∈[ℓ] ) respectively. The output of this

Hyb 1 : This experiment modiőes Hyb 1 by introducing an additional abort condition. Speciőcally, the experiment őrst executes the complete protocol corresponding to the real execution of the MIM exactly as in Hyb 0 (including rewinding the MIM once) to obtain the distribution

Let p(λ) denote the probability that the MIM completes this execution without aborting. Set γ(λ) = max λ, p -2 (λ) . With the őrst two rounds of the transcript őxed, the rewind the right execution up to γ 2 (λ) times, picking inputs (c j 1 , . . . , c j λ ) for each of the ℓ receivers {R j } j∈ [ℓ] independently and uniformly at random in every run. If there exist two rewinding threads where the MIM completes the protocol execution, denote the inputs chosen by the challenger on behalf of the honest receiver in these rewinding threads by (c ′ j 1 , . . . , c ′ j λ ) and (c ′′ j 1 , . . . , c ′′ j λ ) respectively. For every j ∈

) obtained as output from the main and rewinding executions respectively to compute m j i = NM.Decode( L j αj ,i , M j αj ,i , R j αj ,i ). If no such rewinding thread exists, or if there exists j ∈ [ℓ] for which there does not exist α ∈

Lemma 2. For every unbounded distinguisher D and large enough λ ∈ N,

Proof. Since the MIM's inputs { m j i } j∈[ℓ] are committed in round 1 of the protocol, then conditioned on the adversary providing a non-aborting transcript in rewinding executions in Hyb 1 , by simulation security of the 2pc, {( m j i } j∈[ℓ] are correctly extracted.

Therefore, to prove this lemma it suffices to show that two rewinding executions (with a non-aborting transcript) can be found within γ 2 (λ) attempts, except with probability negl(λ). To see this, we observe that the probability of a non-aborting transcript is p(λ), and therefore, the probability that γ 2 (λ) -1 out of the γ 2 (λ) trials abort is negl(λ).

Hyb 2 : This experiment modiőes Hyb 1 to execute the superpolynomial simulator of Π in all sessions where the MIM is a receiver. Speciőcally, in these executions, instead of the honest sender strategy with input

).

-A őrst creates receiver R ′ that interacts with the external challenger as follows.

• Obtain the őrst round sender message from the 2pc challenger, and forward this to the MIM as S j * 's message in the j * th left execution. In addition, generate the őrst round messages according to receiver strategy with inputs {K j } j∈ [ℓ] for the right execution. Obtain the őrst round message from the MIM, which includes a (malicious) sender message for the right execution and a (malicious) receiver message for the left execution. Output the MIM's receiver message in the j * th left execution to the challenger of the 2pc. • Generate the second round message for the right execution according to honest receiver strategy, and obtain the second round message for the left execution from the challenger. Forward the MIM's message in left session j * to the challenger. • Obtain the third round message for the left execution externally from the challenger, and forward this to the MIM as S's message in the j * th left execution. Generate messages for the right executions using honest receiver strategy. Obtain the third round message from the MIM for the right execution. -Next, A rewinds R ′ twice with őxed őrst round, and obtains MIM outputs as follows.

• Run the second round with honest receiver strategy on the right, and obtain challenger messages on the left. Obtain the second round message from the MIM, and output the MIM's message in session j * to the challenger. • Obtain the third round message for the left execution externally from the challenger, and forward this to the MIM as S's message in the j * th left execution. Obtain the third round messages from the MIM. -If none of the executions abort, for every j ∈ [ℓ], őnd α j ∈ [λ] such that c j αj = 0, c ′ j αj = 1, c ′′ j αj = 2. If these do not exist, abort. Otherwise use the outputs of the two-party computation protocol to compute m j i = NM.Decode( L j αj ,i , M j αj ,i , R j αj ,i )

. If the challenger used honest sender messages, we denote the distribution output by A in this experiment by Dist 1 and if the challenger used simulated messages, we denote the distribution output by A in this experiment by Dist 2 .

If the challenger's messages correspond to the real sender S, then the distribution output by A conditioned on not aborting corresponds to Hyb 1 , and if the challenger's messages correspond to Sim-2PC Sen , then the distribution output by A conditioned on not aborting corresponds to Hyb 2 .

By assumption, for inőnitely many λ ∈ N,

Since the MIM completes any run of the protocol without aborting with probability at least p(λ), and because aborts are independent of the distinguishing advantage, for inőnitely many λ ∈ N:

where ¬abort denotes the event that an execution that is completed in the main thread, is also completed without aborting in one rewinding execution.

This implies that for inőnitely many λ ∈ N:

where Dist 1 and Dist 2 denote the real and ideal distributions of the underlying 2-party computation protocol under 2-rewinding security. This implies that D contradicts 2-rewinding security of the two party computation protocol.

Hyb 3 : This hybrid is the same as Hyb 2 except whenever the challenger obtains as output a veriőcation key in one of the right sessions that is identical to a veriőcation key used in one of the left sessions, the hybrid outputs ⊥. By existential unforgeability of the signature scheme, given any PPT adversary MIM, Hyb 2 and Hyb 3 are computationally indistinguishable.

Hyb 4 : This hybrid is the same as Hyb 3 except that inp S j is set differently. Speciőcally, for every j ∈ [ℓ], i ∈ [m] and α ∈ [λ], we set (L j α,i , M j α,i , R j α,i ) ← NM.Sim (1 p(λ) ), and set inp S j = ({m j i , L j 1,i , . . . , L j λ,i , M j 1,i , . . . , M j λ,i , R j 1,i , . . . , R j λ,i } i∈[m] ).

We note that at this point, the functionality {F(inp S j , •)} j∈[ℓ] can be perfectly simulated with access to the ideal functionality {OT j (m j i , m j i , •)} j∈ [ℓ] . Moreover, this hybrid runs the super-polynomial simulator of the two-party computation protocol, which can be split into a straight-line simulator that extracts adversarial receiver input from the őrst round, and then a rewinding-based expected polynomial-time simulator that extracts adversarial sender input. The latter can also be replaced by a straight-line superpolynomial simulator that extracts the adversarial sender-input by running the straight-line superpolynomial simulator of the two-party computation protocol. Finally, as long as the underlying two-party computation protocol has its ideal distribution be identical to an honest execution with dummy inputs, the same is true for our protocol. Therefore, the output of this hybrid is identical to the ideal distribution Proof. We prove indistinguishability between Hyb 3 and Hyb 4 by considering a sequence of sub-hybrids, {Hyb 3,i,j,k } i∈ [1,m],j∈ [1,ℓ],k∈ [0,λ] where:

-Hyb 3 = Hyb 3,0,ℓ,λ , Hyb 4 = Hyb 3,m,ℓ,λ , -for i ∈ [m], Hyb 3,i-1,ℓ,λ = Hyb 3,i,1,0 -for j ∈ [ℓ], Hyb 3,i,j-1,λ = Hyb 3,i,j,0 , -

Suppose the lemma is not true. Then there exists i

an unbounded distinguisher D and a polynomial p(•) such that for large enough λ ∈ N,

We now deőne a set of tampering functions (f MIM , g MIM , h MIM ), and a set of additional functions (w MIM , y MIM , z MIM ). Before deőning them, we deőne a shared state for these functions, that is generated as follows:

-Execute Sim-2PC MIM Sen , using honest R strategy in the right executions with input {K j } j∈[ℓ] and uniformly chosen {c j 1 , . . . c j λ } j∈[ℓ] , until Sim-2PC Sen generates a query to the ideal functionality F at the end of round 2.

-At this point, Sim-2PC MIM Sen outputs a view and transcript of the MIM until the third round, as well as { K j } j∈[ℓ] that correspond to the receiver's inputs in the left execution.

-Rewind the second round twice with uniformly and independently chosen {c ′ j 1 , . . . , c ′ j λ } j∈[ℓ] and {c ′′ j 1 , . . . , c ′′ j λ } j∈[ℓ] respectively in each rewind. If for every j ∈ [ℓ(λ)], there exists α j ∈ [λ] such that c j αj = 0, c ′ j αj = 1, c ′′ j αj = 2, continue, otherwise abort.

-Obtain the rewinding message of the adversary in the second round (with the same őrst round preőx), as well as (c 1 , . . . , c n ) and ( c 1 , . . . , c n ) that correspond to the receiver's chosen functions in the j * th left session in this rewinding execution.

-Output the view of the MIM until round 2 in the main the rewinding threads, and also output (i * , j * , k * ), and the values

-Additionally, output the receiver's inputs { K j , c j 1 , . . . , c j λ } j∈[ℓ] and also output the sender's inputs {sk j , vk j , {m j i } i∈[m] } j∈[ℓ] , along with randomness r.

The functions f MIM,i,j , g MIM,i,j and h MIM,i,j correspond to tampering functions, and are deőned as follows.

-The deterministic function f MIM,i,j on input L, sets L

It then invokes Sim-2PC Sen using randomness r on out to generate the third round message of the protocol transcript in the thread corresponding to the receiver challenge being 0. It outputs the value

It then invokes Sim-2PC Sen using randomness r on out to generate the third round message of the protocol transcript in the thread corresponding to the receiver challenge being 1. It outputs the value

It then invokes Sim-2PC Sen using randomness r on out to generate the third round message of the protocol transcript in the thread corresponding to the receiver challenge being 2. It outputs the value L j αj ,i or M j αj ,i or R j αj ,i obtained from the MIM.

The functions w MIM , y MIM , z MIM generate the threads themselves and are deőned as follows.

-Next, the function

It then invokes Sim-2PC Sen on out to generate the third round message of the protocol transcript in the thread corresponding to receiver left challenge being 0. It outputs the resulting transcript as one thread in the view of the MIM.

-Next, the function y

. It then invokes Sim-2PC Sen on out to generate the third round message of the protocol transcript in the thread corresponding to receiver left challenge being 1. It outputs the resulting transcript as another thread in the view of the MIM.

-Next, the function

. It then invokes Sim-2PC Sen on out to generate the third round message of the protocol transcript in the thread corresponding to receiver left challenge being 2. It outputs the resulting transcript as another thread in the view of the MIM.

Note that there is a őxed set of permutations σ i,j such that f MIM,i,j , g MIM,i,j , h MIM,i,j can be relabeled as functions F i,j , G i,j , H i,j such that F i,j outputs L values, G i,j outputs M values, and H i,j outputs R values.

By Deőnition 1 of ℓ augmented non-malleable codes, we have that for every permutation σ and σ ′ on L, M, R, and every F i,j , G i,j and H i,j , σ ′ (L), σ ′ (M), {NM.Decode F i,j (σ i,j (L)), G i,j (σ i,j (M)), H i,j (σ i,j (R)) } i,j L, M, R ← NM.Code(m j * i * ) ≈ ϵ σ ′ (L), σ ′ (M), {NM.Decode F i,j (σ i,j (L)), G i,j (σ i,j (M)), H i,j (σ i,j (R)) } i,j L, M, R ← NM.Code(0)

But these distributions upon post-processing (via the functions w MIM , y MIM , z MIM ) exactly correspond to the outputs of Hyb 3,i * ,j * ,k * -1 and Hyb 3,i * ,j * ,k * respectively, whenever c j * k * , c j * k * and c j * k * are all different. On the other hand, when any two of the three values c j * k * , c j * k * and c j * k * are identical, the distributions Hyb 3,i * ,j * ,k * -1 and Hyb 3,i * ,j * ,k * are statistically indistinguishable because of the two-out-ofthree secret sharing property of the code, i.e. they jointly do not depend on all three of the shares, L, R and M. Since ϵ(λ) = negl(λ), this contradicts Equation (1), as desired.

Finally, this proof also extends to show that security of the watchlist protocol holds against sub-exponential adversaries that run in time less than or equal to T , where T denotes the running time of adversaries against which the underlying two-party computation protocol is 2-rewinding sender secure.

4-Round Black-Box MPC Protocol

In this section, we give our construction of a four-round black-box MPC protocol from any two-message OT protocol that has super-polynomial time security against malicious receivers and sub-exponential indistinguishability-based security against malicious senders. Speciőcally, we prove the following theorem.

Theorem 2. For some ϵ > 0, assume black-box access to a two-round oblivious transfer protocol with super-polynomial time simulation security against malicious receivers and (2 λ ϵ , 2 -λ ϵ )-indistinguishability-based security against malicious senders. Then, there exists a four-round protocol for computing general functions.

Building Blocks

The construction makes use of the following building blocks:

1. A three-round watchlist protocol WL = (WL 1 , WL 2 , WL 3 , out WL ) satisfying Deőnition 4. Let T 1 (λ) (abbreviated as T 1 ) be the running time of Sim WL (which is the SPS simulator for the watchlist protocol). Let T 2 (λ) (abbreviated as T 2 ) to be the running time of Sim WL,R (which is the special SPS extractor that over extracts the receiver inputs). 2. A two-round n-client, m-server MPC protocol Φ = (Φ 1 , Φ 2 , out Φ ) that satisőes ((T 1 + T 2 ) • poly(•), negl)-privacy with knowledge of outputs property against any adversary corrupting upto t servers and an arbitrary number of clients. By (T, ϵ)-security, we require ϵ distinguishing advantage against any adversary that runs in time T . By privacy with knowledge of outputs [IKP10], we consider a weaker notion of security (when compared to standard malicious security in the real/ideal paradigm), wherein the adversary has the additional power to determine the outputs of the honest parties. This is modelled by the ideal functionality getting an output to be delivered to the honest parties from the adversary. We call this protocol as the outer protocol. We set t = 2λn 2 and m = 3t + 1. We need this protocol to additionally satisfy the property that the őrst round message generated by the simulator on behalf of the honest clients to the corrupted servers is identically distributed to the őrst round messages generated by honest clients on some default input. We note that [IKP10, Pas12] constructed such a protocol making black-box use of a ((T 1 + T 2 ) • poly(•), negl)-secure PRG. As noted in [IKSS21], we can delegate the PRG computations done by the servers to the clients and ensure that the computations done by the servers are information-theoretic. 3. For each h ∈ [m], a three-round inner protocol Π h = (Π h,1 , Π h,2 , Π h,3 , out Π h )

for computing the functionality of the h-th server in the outer protocol. We require this protocol to satisfy Deőnition 5 (discussed below) against adversaries running in time (T 1 + T 2 ) • poly(λ) and the distinguishing advantage being negl(λ).

Syntax. The three-round inner protocol computing a function f is given by a tuple of algorithms (Π 1 , Π 2 , Π 3 , out Π ) with the following syntax. For each round r ∈ [3], the i-th party in the protocol runs Π r on 1 λ , the index i, the private input x i and the transcript of the protocol in the őrst (r -1) rounds to obtain π i r . It sends π i r to every other party via a broadcast channel. We use π(r) to denote the transcript of Π in the őrst r rounds. At the end of the interaction, parties run the public decoder out Π (π(3)) to compute the output.

Definition 5 ([IKSS21]

). The protocol Π is said to be an inner protocol for computing a funtion f if it satisőes the following properties.

-Correctness. The protocol Π correctly computes a function f if for every choice of inputs x i for party P i ,

where π(3) denotes the transcript of the protocol Π when the input of P i is x i . -Security. Let A be an adversary corrupting a subset of the parties indexed by the set M and let H be the set of indices denoting the honest parties. We require the existence of a simulator Sim Π such that for any choice of honest parties inputs {x i } i∈H , we have:

where the real and ideal experiments are described as in [IKSS21] (details deferred to the full version due to lack of space).

Given these building blocks, our construction is described in Figure 5. Due to space constraints, the full proof of security of this construction is deferred to the full version.

-Round-1: In the őrst round, the party Pi with input χi does the following:

1. It chooses a random MAC key ki ← {0, 1} * and sets zi := (χi, ki). Prabhanjan Ananth, Arka Rai Choudhuri, and Abhishek Jain. A new approach to round-optimal secure multiparty computation. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 468ś499, Santa Barbara, CA, USA, August 20ś24, 2017. Springer, Heidelberg, Germany.