Taming Adaptivity in YOSO Protocols: The Modular Way

Abstract

YOSO-style MPC protocols (Gentry et al., Crypto’21), are a promising framework where the overall computation is partitioned into small, short-lived pieces, delegated to subsets of one-time stateless parties. Such protocols enable gaining from the security benefits provided by using a large community of participants where “mass corruption” of a large fraction of participants is considered unlikely, while keeping the computational and communication costs manageable. However, fully realizing and analyzing YOSO-style protocols has proven to be challenging: While different components have been defined and realized in various works, there is a dearth of protocols that have reasonable efficiency and enjoy full end to end security against adaptive adversaries.

The YOSO model separates the protocol design, specifying the short-lived responsibilities, from the mechanisms assigning these responsibilities to machines participating in the computation. These protocol designs must then be translated to run directly on the machines, while preserving security guarantees. We provide a versatile and modular framework for analyzing the security of YOSO-style protocols, and show how to use it to compile any protocol design that is secure against static corruptions of t out of c parties, into protocols that withstand adaptive corruption of T out of N machines (where T/N is closely related to t/c, specifically when $t/c<0.5$, we tolerate $T/N \le 0.29$) at overall communication cost that is comparable to that of the traditional protocol even when $c << N$.

Furthermore, we demonstrate how to minimize the use of costly non-committing encryption, thereby keeping the computational and communication overhead manageable even in practical terms, while still providing end to end security analysis. Combined with existing approaches for transforming stateful protocols into stateless ones while preserving static security (e.g. Gentry et al. 21, Kolby et al. 22), we obtain end to end security.

1 Introduction

Secure multiparty computation (MPC) allows data owners to outsource the processing of their sensitive data to a set of machines, with the guarantee that as long as fewer than a threshold $t$ of those machines are corrupt, no-one will learn more about the data than revealed by the computation output. YOSO MPC [GHK+21] is an emerging new style of MPC where participating machines have very short term roles: they receive messages, performing an internal computation, and send messages in a single communication round to the next set of participating machines. Before sending those messages, the machine erases all other state relevant to the protocol execution.

The advantage of YOSO MPC is that the communication complexity of the protocol can be sublinear in $N$ (the number of available machines), even if the corruption threshold $T$ is linear in $N$. This might appear impossible, since if the communication complexity is sublinear in $N$, the set of all machines ever to send a message fits within the adversary’s corruption budget; however, the crucial insight is that as long as an adversary cannot predict which machines will “speak”, she is unable to target them. One of the challenges of YOSO MPC is choosing participating machines in an unpredictable way, making it harder to locate and adaptively attack those machines while they are active and relevant to the protocol.

YOSO MPC protocols naturally decompose into two tasks. The first of these is role assignment, which entails determining which machines will have a role to play and handing them the secret keys they will need in order to do so, while keeping their identities hidden from the adversary. The second task is actually running the MPC by having the chosen machines play their assigned roles.

One can view YOSO MPC protocols through two lenses: In the natural world, a protocol must specify instructions for physical machines, including instructions for role assignment; i.e., how the machines should go about determining whether they have a role to play, and if so, which one. In the abstract world, a YOSO MPC protocol can be described in terms of the roles alone, without consideration for the machines running them.

Some previous YOSO protocols (e.g. the protocol of Benhamouda et al. [BGG+20]) are described in the natural world, running both role assignment and computation in an entwined way. Others (e.g. the protocols of Gentry et al. [GHK+21] and Acharya et al. [AHKP22]) are described in the abstract world, relying on behind-the-scenes machinery to take care of role assignment.

The second is a more modular approach, resulting in simpler protocol descriptions. However, these descriptions do not suffice for use in the real, natural world. We need a compiler to translate them into something machines can run; such a compiler might access an ideal role assignment functionality.

One such role assignment functionality and compiler were introduced by Gentry et al. [GHK+21]. However, the role assignment functionality presented by Gentry et al. was perhaps too strong, in that it did not allow the adversary to influence the role assignment, instead choosing all machines in an ideal, random way. This makes it impossible for the most efficient known role assignment mechanism (that of Benhamouda et al. [BGG+20]) to realize this functionality. Furthermore, the compiler of Gentry et al. [GHK+21] has two drawbacks: (a) it is inefficient, and (b) it is incompatible with some abstract protocols (e.g. the protocol of Braun et al. [BDO22] and Kolby et al. [KRY22]).

1.1 Our Contributions

In this paper, we fill the above gaps: we introduce a more realistic role assignment ideal functionality $\mathcal {F}_{\textsf{RA}}$, give a realization of $\mathcal {F}_{\textsf{RA}}$, and present a more efficient, more general compiler that relies on this new functionality. In particular, we use non-committing encryption only for implementing $\mathcal {F}_{\textsf{RA}}$. All the messages of the underlying (statically secure) protocol are encrypted using standard (CCA secure) encryption.

1.1.1 Ideal Role Assignment Functionality

In Sect. 3, we introduce our role assignment ideal functionality $\mathcal {F}_{\textsf{RA}}$. Our goal is to capture a more general and broad class of potential and existing role assignment protocols. Towards this, we give a comprehensive design of $\mathcal {F}_{\textsf{RA}}$ that supports modeling various assignment approaches.

At a very high-level $\mathcal {F}_{\textsf{RA}}$ supports two kinds of elections: assignment of a role to a random honest machine, and assignment influenced by the adversary, to a chosen, possibly corrupt machine. The machines are allowed to probe the $\mathcal {F}_{\textsf{RA}}$ to read the public keys of the roles assigned so far, deduce if they themselves have been assigned a role, and retrieve the secret keys in such a case. Furthermore, our design of $\mathcal {F}_{\textsf{RA}}$ supports modeling various scenarios that can occur during its execution, such as (a) when the adaptive adversary manages to corrupt a role that was assigned when it was uncorrupted (before the election of the committee was completed), (b) when a machine wishes to delete its state before it speaks on behalf of a role, and (c) when a machine is unavailable for nomination while it refreshes its secret state.¹ The formal details appear in Sect. 3.

1.1.2 Compiling Abstract Protocols

In Sect. 4, we describe how to leverage $\mathcal {F}_{\textsf{RA}}$ to compile an MPC protocol in the abstract world into one that can be run in the natural world. Unlike the compiler of Gentry et al. [GHK+21], we only use non-committing encryption within the realization of $\mathcal {F}_{\textsf{RA}}$ (and not within the compiler itself). This has a two-fold advantage: (a) it yields a significant efficiency gain, and (b) it gives compatibility with a broader class of abstract YOSO protocols (e.g. the protocol of Braun et al. [BDO22] and Kolby et al. [KRY22]).

At a high-level, in our compiled protocol in the natural world, each machine deduces if it has been selected for a role by invoking the $\mathcal {F}_{\textsf{RA}}$. If this is the case, it reads the bulletin board (in the natural world) to obtain ciphertexts encrypted using that role’s public key. It can decrypt these ciphertexts using the secret keys provided by $\mathcal {F}_{\textsf{RA}}$ and proceed to compute the outgoing messages of the role to other roles. These outgoing messages can be encrypted using the other roles’ public keys (provided by $\mathcal {F}_{\textsf{RA}}$) and posted on the bulletin board. Just before a machine speaks on behalf of a role, it instructs the $\mathcal {F}_{\textsf{RA}}$ to delete its state. After speaking, it instructs $\mathcal {F}_{\textsf{RA}}$ that it is ready for new nominations.

The main challenge is proving adaptive security of the compiled protocol, assuming that the underlying abstract protocol is only statically secure. The crux of our proof is that the set of corrupt roles can be chosen statically, and then the $\mathcal {F}_{\textsf{RA}}$ may be suitably re-programmed so that adaptive corruption of machines are appropriately matched to the already chosen static corrupt roles. We refer to Sect. 5 for details on the technicalities in our proof.

Compiling Abstract Protocols that Require Message Verification. The above compiler supports abstract protocols that use only ideally private point-to-point and broadcast channels. This does not cover a large class of abstract YOSO protocols where parties are expected to accompany their messages with zero-knowledge proofs that relate their outgoing messages to their secret state and previously received messages. Indeed, in order to compile such protocols to natural ones, such proofs would need to involve both secret state from the abstract protocol and secret keys from the compiler itself. In Sect. 6, we show how our compiler can be extended to abstract protocols that contain such constructs. More specifically, we modify the above compiler to accommodate abstract protocols that leverage the functionality $\mathcal {F}_{\textsf{VeSPa}}$ [KRY22], which is used to enable parties to prove to others that the broadcast and peer-to-peer messages they send within a protocol were derived honestly.

In order to extend our compiler to abstract protocols using $\mathcal {F}_{\textsf{VeSPa}}$, we need to be able to emulate the verifiability of messages in the natural world. For this, we simply rely on augmenting the messages posted on the bulletin board in the compiled protocol with corresponding non-interactive zero-knowledge proofs proving that these messages were computed correctly.

1.1.3 Realizing the Role Assignment Functionality

In Sect. 7, we modify the role assignment protocol of Benhamouda et al. [BGG+20] to realize $\mathcal {F}_{\textsf{RA}}$. As shown in [HLH+22], their protocol had problems in addressing the adaptivity of the adversary when it came to realizing the necessary anonymity property. As in [BGG+20], our modified protocol $\varPi _{\textsf{RA}}$ uses a cryptographic sortition algorithm in order to ensure that an adversary is not able to increase the likelihood of corrupting a role of his choice. Furthermore, $\varPi _{\textsf{RA}}$ uses Key and Message Non-Commiting Encryption (KM-NCE). This enables the simulator to deal with the different problematic scenarios described above. That is, by creating “fake” ciphertexts, the simulator can deal with the case of honest parties sending messages to recipients who were a priori expected to be honest, but then became corrupted by the adversary.

Crucially, our protocol instructs nominated machines to erase their private decryption key before making themselves known. As soon as the machine completes its role as a committee member, it chooses a new key pair and registers the new public encryption key with the PKI server. The machine will keep a (truly) long-term signature key in order to authenticate itself to the PKI server.

The much less efficient role assignment protocol of Gentry et al. [GHM+21] (which uses any MPC protocol to run random-index PIR) may be modified to trivially realize $\mathcal {F}_{\textsf{RA}}$, by a similar application of KM-NCE.

2 Preliminaries

2.1 Key and Message Non-commiting Encryption

We recall the notion of a Key and Message Non-Commiting Encryption (KM-NCE) from [HLH+22], which is an extension of receiver non-commiting encryption. Informally, a KM-NCE is a public-key encryption scheme that allows to generate fake ciphertexts without any public key in such a way that those fake ciphertexts can later be decrypted to any plaintext for any public key, by generating an appropriate secret key on the fly. We briefly recall the syntax of a KM-NCE scheme, referring the reader to [HLH+22] for a more detailed motivation.

• $\textsf{Setup} (1^\kappa ) \rightarrow \textsf{pp}$ : Given security parameter $1^\kappa$, the setup algorithm generates public parameters $\textsf{pp}$.

• $\textsf{Gen} (\textsf{pp}) \rightarrow (pk, sk, tk)$ : Given public parameters $\textsf{pp}$, the key generation algorithm produces a public key $pk$ and secret key $sk$, as well as a trapdoor key $tk$. The trapdoor key is not used for encryption or decryption, but instead provides additional information for the purposes of opening simulated ciphertexts.

• $\textsf{Enc} (\textsf{pp}, pk, m) \rightarrow c$ : Given public parameters $\textsf{pp}$, public key $pk$ and a message m, the encryption algorithm produces a ciphertext c.

• $\textsf{Dec} (\textsf{pp}, sk, c) \rightarrow m$ : Given public parameters $\textsf{pp}$, public key $pk$ and a ciphertext c, the decryption algorithm outputs a plaintext m.

• $\textsf{Fake} (\textsf{pp}) \rightarrow (c, \tau )$ : Given only the public parameters $\textsf{pp}$, the fake algorithm produces a fake ciphertext c and additional trapdoor information $\tau$.

• $\textsf{Open} _{k} (\textsf{pp},tk,pk,sk,(c_\gamma ^*, \tau _\gamma ^*, m_\gamma ^*)_{\gamma \in [k]}) \rightarrow sk'$:] Given public parameters $\textsf{pp}$, keys $tk, pk, sk$, and k tuples, each containing a ciphertext $c_\gamma$, its trapdoor information $\tau _\gamma$ and a desired plaintext $m_\gamma$ the open algorithm produces a fresh secret key $sk'$ corresponding to $pk$, such that each ciphertext appropriately decrypts to the desired plaintext.

In the security experiments for KM-NCE the adversary is never given trapdoor keys, implicitly requiring secure erasure of these keys if we wish to achieve adaptive security.

Definition 1 (Security)

A KM-NCE scheme $\mathsf{{KM{-}NCE}} = (\textsf{Setup} , \textsf{Gen} ,\textsf{Enc} , \textsf{Dec} ,\textsf{Fake} ,\textsf{Open} _{k})$ in the k-challenge setting is $\mathsf {CCA -}$secure if for any $\textsf{PPT}$ adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2,\mathcal {A}_3)$, the advantage $\textbf{Adv}_{\mathsf{{KM{-}NCE}},\mathcal {A},k}^{\mathsf{{KM{-}NCE}}-\textsf{CCA}}(\lambda ) :=$

$$ |\Pr [\textbf{Exp}_{\mathsf{{KM-NCE}},\mathcal {A},k}^{\mathsf{{KM{-}NCE}}-\textsf{CCA} -\textsf{real}}(\lambda ) = 1] - \Pr [\textbf{Exp}_{\mathsf{{KM{-}NCE}},\mathcal {A},k}^{\mathsf{{KM{-}NCE}}-\textsf{CCA} -\textsf{ideal}}(\lambda ) = 1] |$$

is negligible, where $\textbf{Exp}_{\mathsf{{KM{-}NCE}},\mathcal {A},k}^{\mathsf{{KM{-}NCE}}-\textsf{CCA} -\textsf{real}}$ and $\textbf{Exp}_{{\textsf {KM-NCE}},\mathcal {A},k}^{\mathsf{{KM{-}NCE}}-\textsf{CCA} -\textsf{ideal}}$ are defined in Fig. 1.

Fig. 1.

The experiments for ${{KM-NCE}}-\textsf{CCA}$ security of a KM-NCE scheme.

Note, $\mathsf {KMNC_k- CCA}$ security implies conventional adaptive CCA security, as the fake algorithm does not take a message as input. By a hybrid argument, the encryption of any message $m_0$ must be indistinguishable from a faked ciphertext, which in turn is itself indistinguishable from the encryption of any other message $m_1$.

$\mathsf{{KM{-}NCE}}$ schemes can be constructed from hash proof systems, as shown in [HLH+22].

2.1.1 KM-NCE with a Unique Recipient

We need to define an additional property for $\mathsf{{KM{-}NCE}}$, which ensures that the adversary cannot produce (something that looks like) a ciphertext which decrypts under two different honest secret keys.

Fig. 2.

The unique recipient experiment.

Definition 2 (Unique recipient)

A KM-NCE scheme $\mathsf{{KM{-}NCE}} = (\textsf{Setup} , \textsf{Gen} ,\textsf{Enc} , \textsf{Dec} ,\textsf{Fake} ,\textsf{Open} _{k})$ is unique recipients if for any $\textsf{PPT}$ adversary $\mathcal {A}$, $\Pr [\textbf{Exp}_{\mathsf{{KM{-}NCE}},\mathcal {A}}^{\mathsf{{KM{-}NCE}}-\textsf{UR}}(\lambda ) = 1]$ is negligible, where $\textbf{Exp}_{\mathsf{{KM{-}NCE}},\mathcal {A}}^{\mathsf{{KM{-}NCE}}-\textsf{UR}}$ is defined in Fig. 2.

2.1.2 A Unique Recipient KM-NCE Construction

We show how to build a unique recipient KM-NCE encryption scheme in the programmable random oracle model. Since this implies the notion of receiver non-committing encryption, we know that random oracles are necessary in order to avoid secret keys that are as long as the messages to be encrypted [Nie02].

Our construction is based on a simple variant of ElGamal, which makes it more efficient than the KM-NCE construction based on hash proof systems (HPS) from [HLH+22, Section 5.3], which relies on a matrix variant of DDH [EHK+13]. Furthermore, that construction does not have the unique recipient property that we need. The reason behind this is that, since the projected and unprojected hash need to coincide for elements x of the language, the adversary can use the unprojected hash (in their specific notation, $\widetilde{\texttt {Pub}}$) together with the public keys of honest parties in order to try and find a suitable witness that leads to a collision (in their notation, the same $\widetilde{\pi }$) with several secret keys. Once he has that, it is easy for him to come up with the rest of the elements of the ciphertext (given x, any d can be fixed by varying the message m. Hence, a whole range of values $\tau = H(x,d)$ can be explored by the adversary). It is very easy for the adversary to come up with elements of the language x and their witnesses w, since this is a necessary feature for the practical efficiency of the encryption algorithm. Thus, we cannot rule out maliciously created ciphertexts that decrypt to several recipients. In more detail, for the HPSs from [HLH+22, Section 6], each public key defines a hyperplane, and collisions happen at the intersection of any two such hyperplanes. This gives plenty of candidates for collisions.

Whereas the prior attack to the unique recipient property is specific to the instantiation of construction of [HLH+22, Section 5.3] with the HPSs from [HLH+22, Section 6], it is likely that similar attacks could be mounted for other natural constructions based on HPSs. The necessary relation between the public and private hash functions, together with any nice algebraic description of the public hashing algorithm (e.g. defining hyperplanes as in the attack above) would potentially lead to the same problem.

We define below our candidate construction based on a modification of ElGamal. The algorithms of our scheme are oracle algorithms with query access to the oracle $\texttt{RO}: \{0,1\}^* \rightarrow \{0,1\}^{2\kappa }$, we let this be implicit in our notation.

• $\textsf{pp} \ {\leftarrow }\$\ \textsf{Setup} (1^\kappa )$: Pick a cyclic group $\mathbb {G}$ of order q, where q is a $\kappa$-bit prime, and let g be a generator of $\mathbb {G}$. Let the message space of the encryption scheme be $\{0,1\}^\kappa$. Set public parameters $\textsf{pp} = (\mathbb {G}, g, q)$.

• $(pk,sk,\emptyset ) \ {\leftarrow }\$\ \textsf{Gen} (\textsf{pp})$: Sample $a \ {\leftarrow }\$\ \mathbb {Z}_q$, let $sk= a$. Compute the public key $pk\leftarrow g^a$ and output $(pk,sk, \emptyset )$.

• $c \ {\leftarrow }\$\ \textsf{Enc} (\textsf{pp}, pk, m)$: Sample $r \ {\leftarrow }\$\ \mathbb {Z}_q$ and compute $\beta \leftarrow g^r$. Query the oracle for a mask $k \leftarrow \texttt{RO}(pk^r)$ and a MAC $d \leftarrow \texttt{RO}(r,m)$. Let $e \leftarrow k \oplus (r,m)$, and output $c = (\beta , e, d)$.

• $m \leftarrow \textsf{Dec} (\textsf{pp}, sk, c)$: Parse $c = (\beta , e, d)$. Query the oracle $k' \leftarrow \texttt{RO}(\beta ^{sk})$, compute $(r',m') \leftarrow e \oplus k'$. Check if $g^{r'} = \beta$ and $d = \texttt{RO}(r', m')$, output $m'$ if both conditions are satisfied, otherwise output $\bot$.

• $(c,\tau ) \ {\leftarrow }\$\ \textsf{Fake} (\textsf{pp})$: Sample $r \ {\leftarrow }\$\ \mathbb {Z}_q$ and compute $\beta \leftarrow g^r$. Let $\tau = r$. Sample uniformly random strings $e,d \in \{0,1\}^{2\kappa }$ and let the fake ciphertext be $c = (\beta , e, d)$. Output $(c, \tau )$.

• $sk' \leftarrow \textsf{Open} _{k} (\textsf{pp},pk,sk,(c_\gamma ^*,\tau _\gamma ^*, m_\gamma ^*)_{\gamma \in [k]})$: To open a fake ciphertext $c_\gamma ^* = (\beta , e, d)$ as an encryption a message $m_\gamma ^*$ to a chosen $pk$. Let $r = \tau _\gamma ^*$, program the random oracle such that $\texttt{RO}(r, m_\gamma ^*) = d$ and $\texttt{RO}(pk^r) = e \oplus (r, m_\gamma ^*)$. Output $sk' = sk$.

Intuitively it is possible to replace ciphertexts by fakes as long as the adversary is unable to query either $pk^r$ or (r, m) to the random oracle. We observe that an adversary querying these values it may be used to solve the computational Diffie-Hellman problem. Including $d = \texttt{RO}(r,m)$ allows the decryption oracle to extract the plaintext and verify the integrity of the ciphertext without use of the secret key. We now formally prove the security of our KM-NCE scheme.

Theorem 1

The construction above is $\mathsf{{KM{-}NCE}}_k-\textsf{CCA}$ and unique recipient secure, in the pROM under the CDH assumption in group $\mathbb {G}$.

Proof

First, we consider unique recipient security. Assume for contradiction there have been no collisions in random oracle, for a sufficiently large range and bounded adversary this holds with overwhelming probability. A winning adversary outputs a ciphertext $c = (\beta , e, d)$ such that for some $sk_i$, $sk_j$: $\textsf{Dec} (\textsf{pp}, sk_i, c) \ne \bot$ and $\textsf{Dec} (\textsf{pp}, sk_j, c) \ne \bot$. We subscript intermediate values in each decryption with the index of the secret key. For honestly generated keys $sk_i \ne sk_j$ with overwhelming probability, implying $\beta ^{sk_i} \ne \beta ^{sk_j}$. As a result, $k'_i \ne k'_j$ if there have been no collisions in the random oracle. This in turn implies that $(r'_i,n'_i) \ne (r'_j,n'_j)$. For both outputs to be different from $\bot$, it must be the case that $d = \texttt{RO}(r'_i,n'_i) = \texttt{RO}(r'_j,n'_j)$ raising a contradiction.

Now consider $\mathsf{{KM{-}NCE}}_k-\textsf{CCA}$ security. Through a series of hybrids we will replace $c_\gamma ^* = (\beta , e, d)$ with a fake ciphertext for each $\gamma \in [k]$. Faking a ciphertext is only different in how c and d are chosen. These two cases are only different in the oracle output on inputs $pk^r$ and (r, m) prior to $\mathcal {A}_3$ receiving the secret key $sk$.

In the real and ideal worlds the adversary receives the same secret key $sk$ and has access to an identically distributed random oracle. The only input which may differ is $\textsf{state}_2$, produced by $\mathcal {A}_2$. The views of Adversaries $\mathcal {A}_1$ and $\mathcal {A}_2$ only differ between the real and ideal game when querying $pk^r$ or (r, m) to the random oracle. Thus, if $\mathcal {A}_3$ distinguishes the real and ideal worlds with non-negligible advantage then one of $\mathcal {A}_1, \mathcal {A}_2$ must query $pk^r$ or (r, m) with probability greater than or equal to the advantage. We will argue that such a pair $(\mathcal {A}_1,\mathcal {A}_2)$ may be reduced to an adversary solving the computational Diffie-Hellman problem.

Consider an adversary which queries either $pk^r$ or (r, m) with probability $\epsilon$, while making at most t random oracle queries. Given a computational Diffie-Hellman instance $(g, x= g^a, y= g^r)$, we set $pk= x$ and $\beta = y$. Note, the solution to this instance is $pk^r = \beta ^a$. We will address how to provide a decryption oracle without knowing the secret key a later. The reduction chooses a query index $i \ {\leftarrow }\$\ [t]$. When the adversary makes the ith query, if the input is of the form (r, m), the reduction outputs $pk^r$, if the input only consists of a single element z the reduction outputs this directly. The reduction aborts before providing $\mathcal {A}_3$ the secret key. Note, the reduction needs $\tau = r$, which it does not have, to open the ciphertexts to $\mathcal {A}_3$, preventing the use of $\mathcal {A}_3$ in the reduction. The reduction yields an adversary solving the Diffie-Hellman problem with probability $\epsilon /t$.

We now return to the issue of providing a suitable decryption oracle during our hybrids. Consider a ciphertext $c^* = (\beta ^*, e^*, d^*)$ queried to the decryption oracle, which is not equal to any of the challenge ciphertexts. If $d^*$ is not a random oracle output on an input of the form (r, m) output $\bot$, this includes any d for faked ciphertexts. A ciphertext using d from a challenge with $\beta ^* \ne \beta$ or $e^* \ne e$, real decryption would result in $\bot$ with overwhelming probability.

For a given ciphertext, e and $k' = \texttt{RO}(\beta ^{sk})$ uniquely determine (r, m); if this has not yet been queried the probability $\texttt{RO}(r,m) = d$ is $2^{-2\kappa }$, and we may safely return $\bot$. If d is an output of the random oracle the reduction may retrieve the corresponding input (r, m). We check if $\beta = g^r$, returning $\bot$ if this is not the case. Given r the oracle then computes $k' \leftarrow \texttt{RO}(pk^r)$; $(r',m') \leftarrow e \oplus k'$. If $(r',m') = (r,m)$ output m, otherwise output $\bot$.

2.2 Cryptographic Sortition

A cryptographic sortition protocol [CM19] allows to provably select a random subset of parties according to some timely and truthful randomness through the use of a Verifiable Random Function (VRF) [MRV99]. Importantly, a party can find out whether it was selected through local computation, given the output from the VRF.

Usual VRF definitions guarantee output unpredictability for adversarially chosen inputs, provided that the keys were honestly generated. In our setting this is insufficient, as it does not preclude an adversary choosing malformed keys which bias its output distribution, causing it to be selected more frequently. To ensure security against rogue key attacks of this form we will use the functionality $\mathcal {F}_\textsf{VRF}$ from [DGKR18], which explicitly allows malicious key generation and VRF evaluation. The key property on which we will rely is “unpredictability under malicious key generation”. This property is captured by the functionality always sampling the VRF output regardless of whether the specified key was maliciously generated. For a complete description of $\mathcal {F}_\textsf{VRF}$ with a corresponding realisation we refer the reader to [DGKR18].

2.3 The You-Only-Speak-Once Model

The YOSO model introduced by Gentry et al. [GHK+21] formalised a variant of the UC framework enabling the design of protocols focusing only on role execution, and not the mechanisms for role assignment or receiver anonymous communication. We will refer to protocols in this model as abstract YOSO protocols. The YOSO model builds on top of the plain UC model. In particular, it uses the following constructs:

• Parties in the UC framework represent roles, namely abstract responsibilities. In an actual execution of a YOSO protocol, the roles will would be carried out by machine to which they are assigned to on the fly. The design of a YOSO protocol is indifferent to which actual machines would be executing the role.

• Idealised communication functionalities are provided to the roles executing a protocol, allowing point-to-point messages between roles. This corresponds to the availability of receiver anonymous communication channels, but ignores their realisation.

• Security is proven for “yosoified” versions of the protocol, where all roles are placed within a YOSO wrapper. This wrapper enforces that roles only speak once by killing them once they use a communication functionality. This is modelled by a $\textsc {Spoke}$ token which the ideal communication functionalities return upon the sending of messages. When receiving $\textsc {Spoke}$ the wrapper additionally forwards this to any sub-routines and its environment. Killing a role represents the machine running a role erasing any associated state, preventing the adversary from later corrupting the role.

• While we want natural YOSO protocols to be secure against an adaptive adversary, allowing the adversary this power in the abstract world would make protocol design significantly more difficult. Gentry et al. [GHK+21] make the observation that an adversary does not know which roles are assigned to a machine before it is corrupted. As a result the adversary may be restricted in the abstract world, while still being able to achieve adaptive security when translated to the natural world. This is enforced through a new “corruption controller” entity which dictates the types of corruptions the environment is allowed to make.

As in [GHK+21], (and following [KMTZ13]) we use a bounded-delay broadcast functionality, along with a global clock, to capture synchronous communication. We recall the ideal functionality allowing point-to-point and broadcast communication as in [GHK+21].

The central paradigm of synchronous abstract YOSO protocols is that executions proceeds by a sequence of committees, each permitting a certain corruption threshold. These committees may potentially receive messages concurrently, or even speak in the same round.

2.4 Compiling Abstract YOSO Protocols

By their nature, protocols designed in the abstract YOSO model cannot be run directly on machines, they first have to undergo translation, or compilation, to the natural world.

This compilation reraises the issues of role assignment and receiver anonymous communication. Any compiler must provide equivalent guarantees of secure communication between roles in the protocol.

In their presentation of the YOSO model Gentry et al. [GHK+21] provide an example of compilation from the abstract to natural world. Their approach used a simplified toy timed ledger with role assignment functionality as a building block. This functionality provided the necessary keys for roles, which were then used to wrap messages in the underlying protocol in encryption. The compiler allowed the compilation of an abstract protocol secure against random adaptive point corruptions (i.e. an adversary only allowed to corrupt random roles), to a natural protocol secure against chosen adaptive point corruptions.

The focus of the compiler of Gentry et al. [GHK+21] was demonstrating the feasibility of compilation. As a result the compiler has a number of limitations, such as the role assignment functionality not being realised. Additionally, to achieve adaptive security the compiler uses non-committing encryption for all messages in the underlying protocol, incurring a significant overhead.

3 Role Assignment

In this section we present the ideal functionality $\mathcal {F}_{\textsf{RA}}$², which assigns machines to computation roles while keeping this assignment hidden. (Note that which machines provide input to the computation—and receive output from the computation—could be determined in some fixed, external way, depending on the application; therefore we consider only the assignment of machines to computation roles, and not input and output roles.)

At a high-level, let us consider committee $C$ consisting of $c$ roles. There are two possible ways in which our $\mathcal {F}_{\textsf{RA}}$ chooses a machine for a role in $C$: (a) choosing a machine at random from among the set of honest machines (i.e. among the machines not corrupted so far), or (b) allowing the adversary to choose the machine, as long as the number of machines chosen by the adversary in $C$ so far is within the allowed corruption bound (which is determined as a function $\mathcal {T}$ on the fraction of corrupt machines). In the former case, $\mathcal {F}_{\textsf{RA}}$ samples fresh keys, gives the (public) encryption and verification keys to everyone, and gives the corresponding (secret) decryption and signing keys only to the chosen machine. In the latter case, all keys are chosen by the adversary. The commands $\textsc {Nom{-}Honest}$ and $\textsc {Nom{-}Corrupt}$ capture the above kinds of nominations.

We need to ensure that the fraction of corruptions in a committee remains within the allowed bound until the nomination is completed. Looking ahead, to capture adaptive corruptions after the adversary has seen public keys generated via $\textsc {Nom{-}Honest}$ but before $\textsc {Finish}$ (which finalises the keys for a committee), we introduce an additional command $\textsc {Corrupt{-}Nominee}$. This command allows accounting for the corruptions performed during the nomination process as needed, rather than always having to generate corrupt keys in proportional to the worst case threshold.

Once a set of $c$ machines are chosen for the committee $C$, $\mathcal {F}_{\textsf{RA}}$ picks a random permutation on $[c]$ to determine which machine plays which role in $C$. Allowing $\mathcal {F}_{\textsf{RA}}$ to map nominated machines to roles, instead of having machines assigned to specific roles in $C$ a priori, prevents the adversary from targeting a specific role for corruption.

Further, there is a provision for each machine M to:

• 1. ‘Read’: this allows it to retrieve public keys corresponding to the roles that have been assigned, as well as to obtain secret keys if it has been assigned a role.

• 2. ‘Delete’: this command revokes M’s ability to perform future reads until the point where it inputs ‘Ready’. (This revocation will also enable the implementation protocol to erase any secret keys that allow M to read information related to already assigned roles.)

• 3. ‘Ready’: this allows it to signal that it is available to be assigned a new role. We maintain both a global set of ready machines (“ready set”), and a committee-specific ready set. The latter keeps track of machines that have been ready throughout the nomination process for that committee.

If a machine that has been assigned a role gets corrupted after it has retrieved its secret keys (which it learns when it inputs ‘read’) but before it inputs ‘delete’, its secret keys are leaked to the adversary. However, if it gets corrupted after it inputs ‘delete’, its secret keys remain hidden. As we will see later, this is crucial for adaptive security, as it allows us to argue that an adversary gets no advantage in corrupting a role after its execution.

The formal description of this ideal functionality $\mathcal {F}_{\textsf{RA}}$ appears below. We assume $\mathcal {F}_{\textsf{RA}}$ to be synchronous, with round switches occurring at the same time as the protocols using it. We present $\mathcal {F}_{\textsf{RA}}$ as a functionality which is reused for multiple committees rather than the perhaps simpler approach of a one time functionality for each committee. We justify this choice by considering how existing constructions update their PKI. Specifically, whenever a machine has held a role and subsequently revealed itself, said machine must refresh its long term keys. This renders the machine unable to decrypt earlier messages pertaining to the revealed role. These key erasures and updates to the PKI impede treating it as a global setup (see [CDPW07]), which would allow consolidating these to just a single PKI. Using a single $\mathcal {F}_{\textsf{RA}}$ for multiple committees thus forces any realisation to deal with this challenge of updates directly.

We divide our role assignment functionality into two parts. The first describes the general setup and commands provided by parties for establishing new committees and reading generated keys. The second describes the powers allowed to the simulator, when populating committees under nomination with keys and the leakage in the case of corruption.

The simulator must perform nominations for each committee, but is restricted by the number of nominations it may bias relative to the current fraction of corrupt machines.

4 Compiling Abstract to Natural YOSO

Consider an abstract YOSO-protocol in the $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$-hybrid model which is maliciously secure against a static adversary. This protocol is run by a set of committees, where each committee is associated with a set of roles. We may assume the execution of any honest role is completed by inputting at most one $\textsc {Send}$ command to an instance of $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$, this is enforced by the $\textsc {Spoke}$ token which kills the role.

The goal of our compiler is to transform such a statically-secure YOSO abstract protocol in the $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$-hybrid model into an adaptively-secure natural-world protocol in the $\mathcal {F}_{\textsf{RA}}$-hybrid model, where $\mathcal {F}_{\textsf{RA}}$ denotes the ideal functionality for role assignment defined in Sect. 3. We also assume that the natural protocol has access to a bulletin board (formalized as an ideal functionality below) which can be used by anyone to broadcast a message.

Overview of the Compiler. Suppose we wish to compile an abstract protocol $\varPi$. At a high-level, the compiled protocol in the natural world involves the following stages: First, the machines initiate role assignment for committees that need to be nominated, which is determined based on the current round and the public state. Once the nomination process is completed, the machines can retrieve public keys corresponding to all roles in these committees and secret keys for the roles they were chosen for (if any). This can be done by machines inputting $\textsc {read}$ to $\mathcal {F}_{\textsf{RA}}$.

Consider a machine $M$ who has been assigned a role for some round of the abstract protocol. Recall that in this case, $\mathcal {F}_{\textsf{RA}}$ provides $M$ with a decryption key and a signing key. $M$ obtains from $\mathcal {F}_{\textsf{RA}}$ the signature verification keys of all the roles that are supposed to send messages to the role that’s assigned to $M$, as well as the public encryption keys of the roles that its assigned role is supposed to send messages to. (Note that the latter key may not be available yet.) In this case $M$ keeps asking $\mathcal {F}_{\textsf{RA}}$ for these keys in each round. As soon as $\mathcal {F}_{\textsf{RA}}$ provides these keys, the $M$ is ready to execute the role $\textsf{R}$ based on the specifications of the abstract protocol $\varPi$. Suppose this role $\textsf{R}$ invokes $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$ in $\varPi$ with a set of point-to-point and broadcast messages, then the machine does the following to emulate this step on behalf of the role:

• Read the bulletin board to retrieve messages posted by machines emulating sender roles. This includes broadcast messages and ciphertexts encrypting point-to-point messages intended for $\textsf{R}$ as a receiver, accompanied by signatures. Accept the messages only if the signatures are valid (note that the verification key of all roles are made public by $\mathcal {F}_{\textsf{RA}}$).

• To retrieve the point-to-point message, uses the decryption key to decrypt the relevant ciphertexts.

• Proceed to compute the outgoing broadcast and point-to-point messages on behalf of the role $\textsf{R}$ (Note that at this point, the machine has all the information a role holds in $\varPi$). Prepare a one-shot message comprising of the following (a) Broadcast messages (b) Ciphertexts encrypting the point-to-point messages using the encryption key of the relevant receiver roles in future committees (made public by $\mathcal {F}_{\textsf{RA}}$) (c) Signature on these messages, computed using the signing key of $\textsf{R}$ received from $\mathcal {F}_{\textsf{RA}}$.

• Once the above one-shot message is computed, invoke $\mathcal {F}_{\textsf{RA}}$ with input $\textsc {delete}$ and delete its own entire state, except the one-shot message to be posted. In particular, delete the secret keys, received messages and randomness used on behalf of the role $\textsf{R}$.

• Post this message to the bulletin board (as an atomic action).

Once the machine $M$ has finished executing the role $\textsf{R}$, it notifies $\mathcal {F}_{\textsf{RA}}$ that it is $\textsc {ready}$ i.e. available to be assigned a new role.

We point out that in the above informal description, we focused on machines that were assigned computation roles. The compiler easily accommodates actions by input and output roles in $\varPi$ as well – the only difference is that these roles are carried out by fixed machines and their identity is not secret. Therefore, the public keys of these roles can be established via a PKI and need not be handled by $\mathcal {F}_{\textsf{RA}}$. Further, the messages posted on the bulletin board by machines executing these roles need not be signed.

5 Security of the Compiler

In this section, we prove the security of the compiler presented in Sect. 4 which transforms a static, abstract YOSO protocol to an adaptively-secure natural protocol. The security of our compiled natural protocol fundamentally relies on the security of the original abstract protocol. The primary challenge arises due to the difference in the adversary’s corruption powers between the abstract and natural world. In order to rely on the static security of our abstract protocol, we must be able to translate the adaptive adversary in the natural world to an appropriate static adversary in the abstract world (against which a simulator must exist, due to security of the abstract protocol).

To rely on the static simulator of our abstract protocol it is essential that the natural world adversary cannot influence which roles are revealed through its chosen corruptions of machines. As a starting point, let us consider what goes wrong if a natural simulator is forced to commit to a mapping from roles to machines. An adaptive adversary might then subsequently choose which machines to corrupt based on this commitment. The simulator is essentially forced to guess which machines the adversary will corrupt making it overwhelmingly likely to fail.

To circumvent this issue we may instead consider the possible simulation strategy if our simulator were not committed to this role to machine mapping. Our static abstract simulator must always fix a choice of corrupt roles. The state of these corrupt roles may be simulated, making it acceptable to assign them to corrupt machines. Conversely, we have no way to simulate the state of honest roles, so these must never be revealed to the adversary. During simulation, the simulator presents a role assignment functionality to the natural world adversary. The natural world adversary expects the roles to be assigned to the machines it has corrupted in proportion to its expended corruptions. This may easily be accounted for by sampling a mapping where an appropriate number of statically corrupt roles are assigned to these machines. Things get more challenging when we start to consider adaptive corruptions, in the real world the adversary will sometimes get lucky and corrupt a machine which has been assigned a role. If we simply fix the mapping from roles to machines at the time of nomination this could cause simulation to fail if the newly corrupted machine had been assigned an honest role. However, if our role assignment functionality does not leak anything to the adversary about the mapping of honest roles we may simply change the assignment of this honest role to a machine which remains honest. This will of course affect the number of roles revealed to the adversary, to account for this we must additionally maintain some budget of statically corrupt roles, which we reveal in place of the honest roles.

As the simulator now controls which roles are revealed to the adversary it may be sure that it never has to open a ciphertext sent between the holders of two honest roles. As a result these ciphertexts need not be non-committing, allowing the use of the much more efficient CCA secure encryption.

We define the class of protocols which are compatible with our compiler.

Definition 3 (Compiler compatible protocol)

We call a protocol $\varPi$ a compiler compatible secure implementation of $\mathcal {F}$ with threshold $c/w$, if the following conditions are satisfied:³

• Let $c= \varOmega (\kappa )$ denote the committee size. Then, $\varPi$ must YOSO securely implement the ideal functionality $\mathcal {F}$ in the presence of $c/w$ static corruptions in the computation committees and an arbitrary number of static corruptions in the input and output roles.

• All honest roles in the same committee speak in the same round.

• There exists a positive constant $\texttt{delay}$, such that it is publicly computable which committees need to be nominated at least $\texttt{delay}$ round(s) in advance.

• There exists a constant $R_{max} \ge \kappa$, denoting the upper bound on the concurrently active roles at any point (which refers to roles that are able to receive messages, or currently being nominated).

Theorem 2

Consider an abstract protocol $\varPi$ in the $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$-hybrid model, which is a compiler compatible secure implementation of $\mathcal {F}$ with threshold $c/w$ (Definition 3). Let $\mathcal {F}_\textsf{RA}$ be shorthand for $\mathcal {F}_\textsf{RA}(\mathcal {P}, c, \mathcal {T}, \mathcal {U}, 2)$ where $\mathcal {U}$ samples the uniform distribution and a function $\mathcal {T}(f)$. Further, assume the schemes $\textsf{PKE}$ and $\textsf{SIG}$ used by $\mathcal {F}_{\textsf{RA}}$ are adaptive IND-CCA and EUF-CMA secure respectively.

Then, assuming a PKI setup, the protocol $\textsf{Compile} (\varPi )$ UC implements the ideal functionality $\mathcal {F}$ in the $(\mathcal {F}_\textsf{BB}, \mathcal {F}_\textsf{RA}, \mathcal {F}_\textsf{VRF} )$-hybrid model, under the presence of $T< Nf_t$ adaptive corruptions of the computation machines and any number of static corruptions in the input and output roles, where $N=(R_{max})^{2+\delta }$ for a constant $1 \le \delta$ and $f_t$ is fixed such that there exists a constant $\epsilon > 0$ where for all $0<f< f_t$ it holds that $\mathcal {T}(f) + (1+\epsilon ) (f_t- f)c< c/w$.

If we apply Theorem 2 to the threshold function achieved by our role assignment protocol in Sect. 7 we obtain the following corollary.

Corollary 1

For $\mathcal {T}(f) = c\left( 1 - (1- \epsilon ) (1-f)^2 \right)$ a protocol tolerating $c/w$ corruptions may be compiled to a protocol tolerating $T< Nf_t$ adaptive corruptions, where $f_t$ satisfies $0 < 1 - 2 w f_t+ w f_t^2$.⁴

We refer the reader to the full version of this paper for a proof of Theorem 2.

6 Compiling Abstract Protocols Requiring Verification

Our compiler in Sect. 4 supports the class of YOSO protocols in the $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$-hybrid model, such as the information-theoretic protocol of [GHK+21]. However, this notably excludes protocols which assume explicit access to keys for the roles to allow zero-knowledge proofs or any other types of public verifiability for point-to-point messages. A large part of the existing YOSO protocol literature falls under this umbrella, including the protocols presented in [BDO22, KRY22] and the computationally secure protocol of [GHK+21].

Kolby et al. [KRY22] introduced the verifiable state propagation ($\textsf{VeSPa}$) functionality $\mathcal {F}_{\textsf{VeSPa}}$ to capture verifiability of point-to-point messages and designed protocols in the $(\mathcal {F}_{\textsf{VeSPa}},\mathcal {F}_{\textsf{BC} \& \textsf{SPP}})$-hybrid model instead. We show how our compiler may be extended to accommodate the compilation of protocols in the $(\mathcal {F}_{\textsf{VeSPa}},\mathcal {F}_{\textsf{BC} \& \textsf{SPP}})$-hybrid model.

Before showing how our compiler may be extended to protocols in the $(\mathcal {F}_{\textsf{VeSPa}},\mathcal {F}_{\textsf{BC} \& \textsf{SPP}})$-hybrid model we will first reflect on the broader role of message verifiability within YOSO protocols. When using $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$ all point-to-point messaging is ideal, making it impossible to directly provide verifiability guarantees for any single message in a single round. Works studying information theoretic YOSO MPC [GHK+21, DKI+23] achieve verifiability by constructing verifiable secret sharing (VSS) protocols in the abstract world. They then make use of VSS to construct their desired MPC protocols. These protocols explicitly handle their need for verifiable message passing in the abstract world, and thus inherit these same guarantees when compiled to the natural world. There are drawbacks to this approach of explicit abstract world verifiability, as existing VSS constructions all introduce an overhead in both rounds and a number of intermediate roles.

An alternative approach follows from the ideas within computationally secure protocols, where verifiability may come from non-interactive zero-knowledge proofs, rather than additional interaction. In the context of YOSO the restriction to $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$ means that we only consider black box communication, and thus cannot directly prove statements about point-to-point messages. To resolve the limitation Kolby et al. [KRY22] introduced a new verifiable state propagation functionality which enabled enforcing statements for point-to-point messages, giving verifiability. A natural question to consider is whether it is possible to realise $\mathcal {F}_{\textsf{VeSPa}}$ in the abstract world given $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$. However, if we recall the cost of achieving VSS in the $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$-hybrid model, our hopes of verifying more complex relations, without a significant round and communication complexity overhead are quickly dampened. Conversely, if we do not realise $\mathcal {F}_{\textsf{VeSPa}}$ we are left with a protocol which remains incompatible with compilation. This leaves us with a choice of either realising $\mathcal {F}_{\textsf{VeSPa}}$ in the abstract world, or adapting our compiler to produce protocols which enforce the guarantees of $\mathcal {F}_{\textsf{VeSPa}}$, essentially making verifiability explicit during the translation to the natural world.

We observe that our compiler is actually well suited to the addition of message verifiability, making this a desirable choice. Recall, our modifications have eliminated the need for non-committing encryption for protocol messages, instead simply requiring CCA security. If we extend the few requirements we make of our encryption scheme to additionally permitting efficient proofs of knowledge of plaintext, we may use non-interactive zero-knowledge to prove that the encrypted messages between roles satisfy whatever relations we require.

6.1 Verifiable State Propagation

In this section, we recall the verifiable state propagation ($\textsf{VeSPa}$) functionality $\mathcal {F}_{\textsf{VeSPa}}$ introduced in Kolby et al. [KRY22]. Informally, this functionality enables both point-to-point and broadcast communication, while allowing the sender to prove that she correctly computed these messages (based on messages she received and possibly other additional inputs).

In more detail, a sender role $\textsf{S}$ in the abstract protocol invokes $\mathcal {F}_{\textsf{VeSPa}}$ with the following information: (a) the point-to-point messages $\textsf{S}$ intends to send to a set of recipient roles (b) the messages $\textsf{S}$ intends to broadcast (c) witness (comprising of the internal state of $\textsf{S}$ such as its private randomness used to compute its outgoing messages).

Consider the statement comprising of these outgoing point-to-point (say, $\phi _{send}$) and broadcast messages (say, $\phi _{broadcast}$), the incoming messages that were received by $\textsf{S}$ (say, $\phi _{receive}$) and the public state (containing all the messages broadcast so far, denoted by $\phi _{public}$). The role $\textsf{S}$ is associated with a relation $\mathcal {R}(\textsf{S})$ which basically specifies the correct behaviour of $\textsf{S}$ as per the abstract protocol specifications. The functionality $\mathcal {F}_{\textsf{VeSPa}}$ verifies this relation i.e. checks if the outgoing point-to-point and broadcast messages sent by $\textsf{S}$ are computed correctly based on the incoming messages it received previously, the current public state and its private randomness (given as part of the witness). The messages that are verified are subsequently communicated. The formal description of $\mathcal {F}_{\textsf{VeSPa}}$ appears below.

6.2 Extending to Verifiable State Propagation

In our extension of the compiler we use the NIZK functionality $\mathcal {F}_\textsf{NIZK}$ introduced by [GOS12]. Looking ahead, the ability to extract witnesses through $\mathcal {F}_{\textsf{VeSPa}}$ means that we no longer require CCA security for our encryption scheme and may relax this to CPA security.

At a high-level, in order to emulate the invocation of $\mathcal {F}_{\textsf{VeSPa}}$ by a role $\textsf{R}$ in the abstract protocol, the machine assigned to execute role $\textsf{R}$ does the following (1) first reads the bulletin board to obtain the broadcast messages and incoming point-to-point messages sent to $\textsf{R}$ (by decrypting the relevant ciphertexts). (2) Then, according to the specifications of the underlying abstract protocol (i.e. as per the relation $\mathcal {R}(\textsf{R})$ required by $\mathcal {F}_{\textsf{VeSPa}}$ in the underlying protocol), it computes its outgoing point-to-point and broadcast messages based on the incoming messages and internal state. (3) prepares encryptions of these outgoing point-to-point messages using the encryption keys of the recipient roles. (4) Finally, the machine then invokes the $\mathcal {F}_\textsf{NIZK}$ functionality with respect to a relation $\mathcal {R}_{\textsf{VeSPa}}$ (described below) which essentially checks that the machine did the above actions (1), (2) and (3) correctly.

Accordingly, we define the relation $\mathcal {R}_{\textsf{VeSPa}}$ which describes what we require of the messages sent by our machines. The requirements may be divided into two categories:

• Encryption and decryption is performed correctly.

• The incoming and outgoing plaintexts, and the public state satisfy the relation $\mathcal {R}(\textsf{R})$ required by $\mathcal {F}_{\textsf{VeSPa}}$ in the underlying protocol.

For a message $\textsf{msg}= (\textsf{R}, \textsf{sid},(\textsf{R}_1, \overline{x}_1), \dots , (\textsf{R}_k, \overline{x}_k), x)$, incoming message set $\textsf{R}.\textsf{Rec}_\textsf{sid}$, with elements of the form $(\textsf{S}, \overline{x}_i)$, and past broadcast messages $\textsf{Broadcast}_\textsf{sid}$, with elements of the form $(\textsf{R}, x)$, we define our relation,⁵

$$\mathcal {R}_{\textsf{VeSPa}} = \left\{ \begin{array}{l} \phi = \left( \begin{array}{l} \textsf{R}, \textsf{sid}, \textsf{R}.ek,\\ \mathcal {R}_\textsf{sid}(\textsf{R}), \\ (\textsf{R}_j.ek)_{j\in [k]},\\ \textsf{R}.\textsf{Rec}_\textsf{sid},\\ \textsf{msg}, \\ \textsf{Broadcast}_\textsf{sid}\end{array} \right) \\ \\ w= \left( \begin{array}{l} \textsf{R}.dk,\\ (x_j, \rho _j)_{j\in [k]},\\ w' \end{array} \right) \end{array} \begin{array}{|l} \top = \textsf{KeyMatch}(\textsf{R}.dk, \textsf{R}.ek) \\ \text {For } j\in [k]: \\ \quad \quad \overline{x}_j= \textsf{PKE} .\textsf{Enc} (\textsf{R}_j.ek, x_j; \rho _j) \\ \text {For } (\textsf{S}, \overline{y}_j) \in \textsf{R}.\textsf{Rec}_\textsf{sid}: \\ \quad \quad y_j= \textsf{PKE} .\textsf{Dec} (\textsf{R}.dk, \overline{y}_j) \\ \phi _{send} = ((\textsf{R}_j, x_j))_{j\in [k]}\\ \phi _{rec} = ((\textsf{R}_j,y_j))_{(\textsf{S}, \overline{y}_j) \in \textsf{R}.\textsf{Rec}_\textsf{sid}}\\ \phi _{bc} = x\\ \phi _{pub} = \textsf{Broadcast}_\textsf{sid}\\ ((\phi _{send},\phi _{rec}, \phi _{bc}, \phi _{pub}), w') \in \mathcal {R}_\textsf{sid}(\textsf{R}) \end{array} \right\} . $$

The only changes we need to allow for this functionality are when dealing with messages sent via $\mathcal {F}_{\textsf{VeSPa}}$, the role assignment process remains unchanged.

6.3 Security of the Extended Compiler

We prove the security of our extended compiler, stated in the formal theorem below.

Theorem 3

Consider an abstract protocol $\varPi$ in the $(\mathcal {F}_{\textsf{VeSPa}},\mathcal {F}_{\textsf{BC} \& \textsf{SPP}})$-hybrid model, which is a compiler compatible secure implementation of $\mathcal {F}$ with threshold $c/w$ (Definition 3). Let $\mathcal {F}_\textsf{RA}$ be shorthand for $\mathcal {F}_\textsf{RA}(\mathcal {P}, c, \mathcal {T}, \mathcal {U}, 2)$ where $\mathcal {U}$ samples the uniform distribution and $\mathcal {T}(f) = c\left( 1 - (1- \epsilon ) (1-f)^2 \right)$, for $\epsilon >0$. Further, assume the schemes $\textsf{PKE}$ and $\textsf{SIG}$ used by $\mathcal {F}_{\textsf{RA}}$ are IND-CPA and EUF-CMA secure respectively.

Then, assuming a PKI setup, the protocol $\textsf{Compile} (\varPi )$ UC implements the ideal functionality $\mathcal {F}$ in the $(\mathcal {F}_\textsf{NIZK}, \mathcal {F}_\textsf{BB}, \mathcal {F}_\textsf{RA})$-hybrid model, under the presence of $T< Nf_t$ adaptive corruptions of the computation machines and any number of static corruptions in the input and output roles, where $N= (R_{max})^{2+\delta }$ for a constant $\delta \ge 1$ and $0 < 1 - 2 w f_t+ w f_t^2$.⁶

The proof of Theorem 3 appears in the full version of this paper.

7 Realising Role Assignment

In compilation, we crucially relied on the ability to program the nominations of our role assignment functionality on the fly to mitigate the adaptive corruption powers of the adversary. We will now show how to realise $\mathcal {F}_{\textsf{RA}}$ by modifying the committee selection protocol of Benhamouda et al. [BGG+20] to allow equivocation of the mapping betweeen roles and machines.

We begin by recalling the high level approach of their construction. The task of choosing committee members is delegated to a nomination committee; nominators in this committee do not need to receive any private input and may therefore be self-selecting through cryptographic sortition. For a sufficiently large nomination committee the fraction of corrupt nominators will be close to the fraction of corruptions in the entire system. When a machine is chosen as a nominator it samples fresh ephemeral keys for the role it is nominating, the public key may be broadcast along with an encryption of the secret key under a special form of anonymous PKE. As we consider an adaptive adversary with the capacity to corrupt all members of the nomination committee, were they identified, each nominator must make sure to delete its secret state prior to sending their message. All machines may then observe the broadcast channel, and attempt to decrypt each nomination ciphertext, if the decryption succeeds the machine has been nominated and can decrypt ciphertexts messages sent to the role.

To satisfy our role-assignment functionality we must make some modifications. Recall, in our simulation we want to choose the static corruptions in each committee ahead of time, only ever revealing those chosen corrupt roles. If the role assignment mechanism commits to a mapping between roles and machines a simulator may be forced to corrupt machines which have been assigned honest roles, for which it cannot equivocate. However, if the role assignment mechanism does not commit to the mapping between roles and machines this could conceivably be chosen on the fly to avoid revealing any statically honest roles. To make the approach compatible with the approach of Benhamouda et al. [BGG+20] we replace the encryption scheme used for nomination ciphertexts with key and message non-committing encryption (KM-NCE) [HLH+22]. We additionally introduce the use of a randomness beacon, which provides fresh uniform randomness each round, which we use to ensure the mapping from roles to nominations is uniformly random and not biased by the adversary.

Note, while KM-NCE allows equivocating for both key and message, we will only ever change the key under which ciphertexts decrypt. The committee size must not exceed some fixed size c, to ensure this we must fix the winning probability p such that the expected committee size is smaller than c allowing the application of a tail bound. To this end we let $p= c/((1+\epsilon ') N)$ for some $\epsilon ' >0$.

We now prove the security of our role assignment mechanism. The protocol ensures at most $\mathcal {T}(f) = c\left( 1 - (1- \epsilon ) (1-f)^2 \right)$ of the $c$ roles in a committee are assigned to corrupt machines when the committee is finished being nominated. Here $f$ is the fraction of corruptions at the point where the committee finishes being nominated. Intuitively this corresponds to guaranteeing that the remaining $(1-f) N$ honest machines have nominated other machines which have remained honest at least a fraction $(1-f)$ of the time. The proof of Theorem 4 appears in the full version of this paper.

Theorem 4

For threshold function $\mathcal {T}(f) = c\left( 1 - (1- \epsilon ) (1-f)^2 \right)$ and the uniform distribution $\mathcal {U}$. If the $\mathsf{{KM{-}NCE}}$ scheme used has $\mathsf {KMNC_k- CCA}$ (for $\textsf{k} = \textsf{poly}(\kappa )$⁷ ) and $\mathsf{{KM{-}NCE}}-\textsf{UR}$ security and the sortition has winning probability $c/((1+\epsilon ') N)$ for $\epsilon ' > 0$. Then, assuming a bare PKI setup, the protocol $\varPi _\textsf{RA}$ UC realises the functionality $\mathcal {F}_\textsf{RA}(\mathcal {P}, c, \mathcal {T}, \mathcal {U}, 2)$ in the presence of $T\le N$ adaptive corruptions in the $(\mathcal {F}_\textsf{Beacon}, \mathcal {F}_\textsf{BB}, \mathcal {F}_\textsf{VRF} )$-hybrid model.

8 The Versatility of Our Compiler

The compiler we present allows the compilation of YOSO protocols using both $\mathcal {F}_{\textsf{BC} \& \textsf{SPP}}$ and $\mathcal {F}_{\textsf{VeSPa}}$. Of the existing literature only Kolby et al. present computationally secure protocols in the $\mathcal {F}_{\textsf{VeSPa}}$-hybrid model [KRY22], having introduced the functionality. However, existing works which make non-black-box use of the communication between roles may be recast into the $\mathcal {F}_{\textsf{VeSPa}}$-hybrid model allowing for their efficient compilation. We provide one such example. Braun et al. construct a YOSO MPC protocol from class groups, following the circuit based CDN paradigm of [CDN01]. Their protocol proceeds by first performing a distributed key generation to obtain a key for a threshold linearly homomorphic encryption scheme, which is then used for the circuit evaluation.

In the construction of their protocol they assume access to explicit public keys allowing them to prove statements about the ciphertexts and public messages with NIZK. The NIZK proofs are used in three of their functionalities, $\textsf{CreateVSS}, \textsf{CreateTriple}$ and $\mathsf {YOSO-ABB}$. Proving the exact same relations about the messages sent through $\mathcal {F}_{\textsf{VeSPa}}$ would clearly preserve security, giving the simulator access to the same witnesses it could extract from explicit proofs.

Braun et al. [BDO22] specifically tailor their statements to have efficient proofs for the class group encryption scheme they use [CCL+19]. As our extended compiler is secure for any PKE scheme with CPA security, it could in particular be instantiated with the same class group scheme preserving their efficiency.