Hello, I'm Rohit Chatterjee and I'll be talking about improved black-box constructions of composable secure computation. My co-authors are Zhao Lian and Omkad Pandey.

Let's begin. We will be talking about secure multiparty computation where we have several parties participating in an interactive protocol. Each party has their own private inputs and wants to compute a joint function on these inputs. We expect correctness, meaning the parties compute the correct output value while maintaining security, namely that no party learns any more information about the other party's inputs

apart from that which is given away by the function output. Security in MPC settings is defined using the real-ideal paradigm, wherein the real execution involves the parties communicating with each other and an adversary corrupting some subset of these parties. And the ideal execution involves all the parties talking to a trusted third party which

simply takes in their inputs and announces the correct outputs. The ideal execution involves a simulator which is a counterpart of the real-world adversary. Security is defined as follows. Any scenario the adversary can enact in the real execution, the simulator can also cause in the ideal execution, up to computation and indistinguishability in the view.

Classical treatments consider a single execution of the protocol. This is not enough for current day requirements, for example, on the internet. Common use cases in modern settings are likely to involve several concurrent and asynchronous executions of different protocols. We want security during multiple concurrent executions of the protocol.

We also want security for cases where one instance of the protocol is executed within another. The various executions of the protocol may be computing different functions. The specific model of security we use is called Angel-based security. This describes a model where the simulator may have access to certain oracles called angels.

These angels perform some pre-specified super-polynomial computation. The angels can be seen as helpers to the simulator in simulating the adversary's view. We can develop protocols in this model that are secure in concurrent settings. This model also affords a composition theorem. It is important to note that these features are not available in the standard model under

polynomial-time simulation-based security. The efficiency notion we will be concerned with is round complexity. Simply put, it is the number of rounds or distinct stages in which parties can communicate with each other. This is key in both theoretical and practical considerations for interactive protocols.

We can now discuss our result and compare it with previous work. In the non-blackbox regime, Conetti-Lin and Pass gave the first protocol in this setting which had polynomial rounds. The best-known result in this setting is by Goel et al. which hired a logarithmic number of rounds. In the blackbox setting, the first result was given by Lin and Pass which also had

polynomial rounds. Kiyoshima in 2014 improved this to give a protocol with order log square in rounds. As you can see, there is a multiplicative gap of log and rounds between these two settings. We wanted to understand if this gap was inherent or if we could compress it. Our answer is that yes, this gap can be removed and become a blackbox MPC protocol with only

order log and rounds. To outline the roadmap to our result, we need to consider CC's secure commitments. CCA here stands for Chosen Commitment Attacks. This notion involves a man-in-the-middle adversary A which participates in several sessions,

acting as a receiver in the left side commitment sessions and a committer in the right side sessions. There is a challenger on the left and a de-commitment to Oracle on the right, with the Oracle returning committed values immediately after the end of each session. It's important to note that the Oracle need not be efficient and can run in possibly exponential time. Security requirement roughly states that the adversary cannot tell apart committed values

on the left if it doesn't blindly copy over messages to the right. This notion is similar to CC encryption schemes and non-malleable commitments. This is important to us because the work of Kanetti, Lin, and Paz gives a transformation from K-round CC commitment schemes to order K-round MPC protocols in the Angel-based model,

and all the future results rely on this transformation. Let us take a look at previous constructions of this primitive and the associated round complexities. The non-blackbox result by Goel et al. construct this using a concurrency-renowned scheme and a non-malleable commitment scheme in a manner that the component round complexities

are multiplied, and we obtain an order log and round CCA commitment. Kiyoshima's result instead combines a concurrent zero-knowledge scheme with a 1-1 CCA commitment scheme. We will explain this shortly. And both these schemes have round complexity of order log n, yielding an order log squared and round CCA commitment scheme. It's important to note that the concurrent zero-knowledge protocol round complexity is

essentially tight, and it cannot be improved further. 1-1 CCA commitment schemes are a limited variant of CCA commitments, with the adversary only participates in one session each with the challenger and the org. The security guarantee is the same, namely that the adversary can't tell apart which value the challenger commits, unless it copies all the messages over to the org.

The core of our work is in constructing a constant round 1-1 CCA commitment scheme that makes blackbox use of its components. Kiyoshima's transform then directly gives us an ordered log n round blackbox MPC protocol in the Angel-based setting. We now explain how to construct such a scheme.

We have the following requirements in mind. First, we want to make use of standard polynomial time-hardness assumptions, as opposed to exponential time ones. This necessitates that we can find a method to replace the oracle during our proofs by a procedure that can return the decommitted value efficiently.

Finally, we want to of course use components that have constant round constructions and use them in a blackbox manner. Let us consider the following initial template. The committer first commits to its value using a non-malleable commitment scheme. It then proves that it knows the value it committed using a zero-knowledge argument

of knowledge. Intuitively, this works. Adversaries cannot prove they know the committed value if they simply maul the left commitment. Further, we can provide decommitments by running the extractor for the zk-aok scheme. Thus, the argument of knowledge property is crucial. But when we try to implement this template, there are problems.

Specifically, there are no known constant round blackbox constructions of a non-malleable commit-and-prove scheme. In fact, this seems to be a fundamental difficulty. Instead, our approach is to use a standard commit-and-prove scheme and add CCA security a little more indirectly.

The protocol works as follows. First, the committer sends a standard one-round commitment to the receiver. The receiver now makes an extractable non-malleable commitment to a value alpha sampled at random. We use a specific three-round commitment from the work of Koel-Pande-Richelson that is non-malleable against synchronous adversities.

The committer follows this with an extractable commitment to a value beta also sampled at random. The receiver now discloses alpha with the pertinent decommitment information. Finally, the committer proves that it either knows v or that beta equals alpha. An honest committer simply proves the former statement, while the latter statement is called

the trapped-o statement, and its role will be explained later. The proof is done by showing that the committer can switch to proving different values on the left by using a hybrid argument. The first step is to replace the oracle so that our hybrids are polynomial time. And we do this by running the zk-ok extractor on the right.

We will show that the adversary cannot use the trapped-o, and thus we provide a valid decommitment. We then ourselves set the trapped-o condition on the left by first extracting alpha and changing beta to equal it. Finally, we can switch to proving the trapped-o statement. At this point, we can switch the initial commitment to one to any value, and reverse

our steps to show the desired indistinguishability. The details of the proof will depend on the kind of scheduling the adversary deploys. The adversary may be synchronous, meaning that it executes both left and right sessions in lockstep, or asynchronous, which can refer to any other ordering or scheduling of the left and right sessions the adversary may use.

Let us first consider the synchronous case. We want to ensure that the decommitment returned to the adversary is valid. For this, the adversary must not be able to set the trapped-o on the right. Now unless the adversary can break hiding of the right ENMC, it must be modeling the subsequent extractable commitment on the right to set the trapped-o.

In turn, it must also be modifying the ENMC on the left, since alpha-tilde must equal beta-tilde for the trapped-o condition on the right. We can now move to a slightly modified hybrid experiment where we a. Extract beta-tilde on the right, and b. Stop extracting alpha on the left.

With this hybrid, we can use a reduction to the non-malleability game to show that if the adversary sets beta-tilde to be alpha-tilde with high probability, that the synchronous non-malleability of ENMC is violated. We conclude that the adversary cannot use the trapped-o condition on the right.

Our approach runs into a problem in the asynchronous case. Consider an adversary that follows the depicted scheduling. Since the left ENMC execution finishes before the right, we cannot argue that the right ENMC influences the left one. Thus, the previous reduction does not go through. This necessitates a modification of our current protocol.

Our solution is to prevent the receiver's ENMC with a compatible extractable commitment to alpha. The extractable commitment scheme must allow for extraction from any two-round challenge-response sequence that we call a slot. And the standard extractable commitment scheme we used initially has this property.

In fact, our ENMC scheme has this property as well. The rest of the protocol is the same as before. We can now view both the receiver's commitments together as an extractable commitment with the slot-based extraction property.

Our revised protocol is now secure against asynchronous adversaries. The proof uses separate arguments for different kinds of schedulings. We show that in any scheduling, for example the one indicated above, we can either find a slot on the left where there is no interaction on the right, allowing us to safely extract alpha.

This uses the slot-based extractability of the receiver-side commitments. Or the receiver-side commitments are perfectly aligned, in which case we can default to a synchronous case argument. We consider one final issue with our protocol. Recall that we extract the witness from the right zkok to provide the d-commitment to a.

Also, we must switch to proving the trapdoor statement to the left zkok. In the course of our proof, ordinarily, we can argue that the adversary cannot detect this change by the zero-knowledge property. But note that we extract from the right zkok, which involves rewinding this execution,

and this can cause the left zkok execution to be rewound as well. Ordinary zero-knowledge does not apply to such a scenario, and our initial proof does not go through. We resolve this by simply using repeated proofs in our protocol. Namely, the protocol now has sequential zkok executions for the same statement.

Now we can alternately switch to proving the trapdoor in the same zkok instances on the left and moving to a different extraction site on the right till we switch statements in all the proofs in the left.

Our amended protocol looks like this. It is still constant rounds and has k copies of the zero-knowledge proof at the end. Two proofs suffice for synchronous adversaries, but k are needed for the general case. The only thing left is to ensure that our protocol is blackbox,

and we observe that all the components are already so apart from the zero-knowledge protocol. We therefore need a blackbox zkok scheme and a compatible extractable commitment scheme. In our work, we construct a constant round blackbox commit and proof protocol.

Our construction is based on previous approaches and specifically involves the MPC in the head paradigm for constructing zero-knowledge arguments and proofs. This involves the prover or committer running an MPC protocol with virtual parties then committing to the views of those parties. The verifier then asks the prover to open some of the views, which it does.

This approach allows for making the commitment extractable in the proof and argument of knowledge, properties which we require. The commitment part involves the prover invoking virtual parties that execute a verifiable secret sharing scheme over the commitment value, with the committed value as the secret. In the proof phase, the prover has these parties further compute

phi using their previous shares. We discussed some features of this protocol that are crucial to a commitment scheme. The proofs in this protocol can be based on multiple commitments that may or may not be related. Further, we can support multiple proofs that refer to the same commitment.

There are several other constructions of such schemes that have very low round complexity that have come out recently, but they do not explicitly offer these properties and these are crucial to our overall construction. Our final protocol then has this form with the proofs and extractable commitments replaced

by the black box commit and prove counterparts. We emphasize that the new extractable commitment scheme still satisfies the slot-based extractability property and therefore is still compatible with the ENMC scheme. This protocol is constant round, black box, and satisfies 11CCA security.

To wrap up, what we have shown is a construction of an order login round black box MPC protocol in the angel-based security model by constructing a constant round, black box, 11CCA commitment scheme. Thank you for listening.