Single Secret Leader Election

;2 Dan Boneh¹, Saba Eskandarian¹, Lucjan Hanzlik¹, and Nicola Greco³

¹ Stanford University

² CISPA Helmholtz Center for Information Security ³ Protocol Labs

Abstract. In a Single Secret Leader Election (SSLE), a group of participants aim to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she has won the election. The election process itself should work properly even if many registered users are passive and do not send any messages. Among the many applications of SSLEs, their potential for enabling more ecient proof-of-stake based cryptocurrencies have recently received increased attention.

This paper formally denes SSLE schemes and presents three constructions that provide varying security and performance properties. First, as an existence argument, we show how to realize an ideal SSLE using indistinguishability obfuscation. Next, we show how to build SSLE from low-depth threshold fully homomorphic encryption (TFHE) via a construction which can be instantiated with a circuit of multiplicative depth as low as 10, for realistically-sized secret leader elections. Finally, we show a practical scheme relying on DDH that achieves a slightly relaxed notion of security but which boasts extremely lightweight computational requirements.

1 Introduction

Leader election is a question of fundamental importance in the distributed consensus literature and has for decades been the subject of academic study. The meteoric rise of blockchains in both academic and industry settings [41], however, has motivated a host of new research questions and motivated renewed enthusiasm for combining privacy with consensus applications. For example, a number of recent works have studied secret leader election in the context of Proof of Stake (PoS) blockchains [7, 9, 43], where the identity of a randomly chosen leader remains secret until she reveals herself as the leader [3,26,29,35]. The added secrecy guarantee defends against several attacks that could otherwise compromise liveness of the blockchain. For example, once a leader is selected, an attacker could mount a Denial of Service (DoS) attack on the chosen leader and prevent her for publishing a block. The system would then need to select an alternate leader, who might also get attacked before publishing a block, and so on, thereby halting the system. Secret leader election solves this issue by ensuring that the identity of the leader remains hidden until the leader publishes a new block.

Existing proposals for secret leader election work by electing a few potential leaders in expectation and describing a simple run-o procedure such that one of the potential leaders can be recognized as the absolute winner of the election after all potential leaders have revealed themselves. The possibility of several potential leaders, however, can lead to wasted eort and potentially even forks in the blockchain in case of attacks on the run-o procedure.

This situation has led to a desire for a new approach to secret leader election that guarantees that one, and only one, leader obtains a valid proof that it won the election [38]. In response, this paper formally denes and constructs a Single Secret Leader Election (SSLE). In a SSLE scheme, a group of users register to participate in a series of elections. Each election chooses exactly one leader; the leader knows that she was selected, but all other users only learn her identity once she reveals herself as the leader, along with a proof that she was indeed selected by the protocol. A variant of the basic scheme may ask for an ordered list of leaders, say 10 chosen leaders, to learn their position in the chosen list along with a proof of that position, but learn nothing else about the list. Practical deployments additionally require restrictions on computation, communication, and (most importantly) storage costs of such a protocol.

1.1 Our Contributions

This paper formally denes and constructs SSLE schemes. We begin by describing both the practical and theoretical requirements of an SSLE scheme before developing a syntax and a set of security denitions that formally capture these requirements, the paper’s rst core contribution. Along the way, we describe an important \straw man" solution that does not satisfy our full security denitions, but may suce for some applications.

It is not dicult to see that SSLE can be constructed from general multiparty computation. However, an MPC protocol where all parties must send one or more messages can easily be disrupted by an attacker who can take a single participant oine. For protection against denial of service as well as to minimize communication and storage costs, elections must take place even if a large subset of users send no messages for each election. We wish to construct schemes where users only send a single message to register as participants for many consecutive elections. As we shall see, two of our schemes require mostly zero messages per-election, once a user has registered.

Our second core contribution consists of SSLE constructions from three dierent classes of cryptographic assumptions and an exploration of the security and performance tradeos associated with each approach. We begin by showing feasibility of constructing an ideal SSLE scheme through a construction relying on indistinguishability obfuscation [5, 27]. Next, we show how to build an SSLE scheme from LWE [44] using threshold FHE [11] with a very low-depth leader election circuit. Finally, we give a construction relying on the Decision Die-Hellman (DDH) assumption and random shues [33,34] whose security and performance properties may suce for practical use-cases. The latter two constructions are proven secure in the random oracle model [6, 25]. In addition to proving the security of each construction, we discuss practical considerations associated with deploying them and cover a number of variations to tailor them to applications with a range of requirements and constraints. We briey summarize each approach below.

SSLE from indistinguishability obfuscation. Our rst and simplest solution from indistinguishability obfuscation [5, 27] serves to show the feasibility of constructing an SSLE scheme as we dene it and gives an example of a scheme that demonstrates all the qualitative properties one could want from an SSLE scheme. The construction involves obfuscating a program that takes as input all the participants’ public keys and outputs a commitment to each user indicating whether that user is the leader as well as a ciphertext encrypted to each user that holds the randomness used for that user’s commitment. The winner is chosen by evaluating a puncturable PRF [15, 17, 36] on public randomness, with the PRF key hidden inside the obfuscated program.

SSLE from threshold FHE. Next, we construct an SSLE scheme based on threshold FHE [11]. The core idea is for each user to post an encryption of a secret s_iwhen they register to participate and use computation under the FHE with the public randomness as input to select one string s_ifrom the registered set. Since only the user who generated s_iknows her secret, only she learns that she is the leader. As long as a threshold number of users are available to publish a partial decryption, the election will succeed even if some users are oine due to an active DoS attack. Given this high-level approach, the main technical challenge lies in choosing s_iwith a circuit that has low multiplicative depth in order to save on computational costs and ciphertext size. We show how to achieve depth of as little at 10 AND gates by combining low-depth block ciphers with a technique for eciently expanding log N bits of randomness to a length N vector with zeros in every position except for a single 1.

$$ s_{i} $$

$$ s_{i} $$

$$ s_{i} $$

$$ s_{i} $$

SSLE from DDH and shues. Our nal and most lightweight construction assumes only the hardness of DDH in some group. Instead of encrypting each user’s string s_ias we do with the FHE-based solution, we hide the link between each user and his or her s_iby shuing s_iinto the database of secrets at registration time. A Nave approach requires shuing a set of size N, the number of participants, whenever a new user joins and also posting proofs that the shue was carried out correctly. We show how to eliminate the need for a proof p and reduce the shue to a set of size N at the cost of some degradation of the resulting security property. The resulting balance of performance and security oers a tradeo well-suited to real-world applications.

$$ s_{i} $$

$$ s_{i} $$

$$ N $$

$$ \sqrt{N} $$

1.2 Related Work

An RFP published by Protocol Labs [38] informally describes SSLE and gives a sketch of a solution from functional encryption [13, 42] that roughly satises their requirements. Unfortunately, this scheme requires a new trusted setup phase each time the set of participants in an election changes. Although we are the rst to formally consider single secret leader election, secret leader election in the case without the strict requirement of electing a single leader has been studied extensively in prior work, especially in the context of Proof of Stake [7, 9, 43] blockchain applications. These approaches potentially elect multiple leaders and then suggest ways to pick one leader from among the set once the set has been made public.

Ganesh et al. [26] and Ouroboros Crypsinous [35] extend previous proof of stake systems in the Ouroboros family [4,22,37] to consider privacy-preserving proof of stake. Algorand [29] and Fantomette [3] both introduce secret leader election protocols as part of their overall proof of stake systems as well. Their approaches center around evaluating a VRF and checking if the output for each user falls near or below a target threshold. This mechanism lters out most potential leaders. Then the few remaining potential leaders reveal themselves and choose the nal leader with a simple tie-breaker, e.g. lowest VRF output. The downside of this approach is that the leader does not know that she was selected, until everyone else reveals their values. Moreover, if the nal leader’s messages do not reach all nodes in the network, those nodes may incorrectly conclude that a dierent leader was elected, causing the chain to fork. This cannot happen in an election scheme that guarantees electing exactly one leader. In Section 3 we will present a similar scheme that does not rely on VRFs on our way to formalizing security requirements for SSLE.

Finally, Zether [18] proposes a privacy-preserving proof of stake that hides both the winner(s) of an election and each user’s stake as an application of their techniques.

2 Preliminaries

R Notation. Let x F (y) denote the assignment of the output of F (y) to x, and let x S denote assignment to x of an element sampled uniformly random from set S. We use to refer to a security parameter and sometimes omit it if its presence is implicit. The notation [k] represents the set of integers 1*;* 2*;:::;k*, and*;* H denotes the empty set. We use A to denote that A has oracle access to some function H. A function negl(x) 1 is negligible if for all c > 0, there is a x₀ such that for all x > x₀, negl(x) <c. We omit x if the parameter is x implicit. PPT stands for probabilistic polynomial time. Finally, we allow algorithms to output*?* to indicate failure. When referring to a function with some input xed, we use in the place of other parameters, e.g. f (x;).

$$ F(y) $$

$$ x. $$

$$ x\leftarrow F(y) $$

$$ x\xleftarrow{\operatorname R S} $$

$$ \lambda $$

$$ [k] $$

$$ 1,2,...,k. $$

$$ \emptyset $$

$$ \mathcal{A}^{H} $$

$$ c>0 $$

$$ x_{0} $$

$$ \textstyle x>x_{0},\mathsf{n e g l}\big(x\big)<\frac{1}{r^{c}} $$

$$ \perp $$

$$ f(x,\cdot) $$

Standard Primitives. We use a number of standard cryptographic tools throughout the paper, including PRFs, weak PRFs, CPA-secure PKE, commitment schemes, and the DDH assumption. Denitions of these tools appear in Appendix A.

Randomness Beacons. Each election in all our constructions uses a fresh public randomness R generated for that election. A number of works study how to generate such randomness, with approaches ranging from harnessing randomness from nancial data (e.g. markets, cryptocurrencies) [8,16,21] to cryptographic delay functions [10,39], and a number of systems have been built to provide reliable public randomness [20,31,46]. The chosen source of public randomness for a particular instantiation of our schemes is orthogonal to our work, so we do not specify a particular means to generate the random input R used in our elections.

Indistinguishability obfuscation. Our rst construction, intended to show the feasibility of satisfying our denitions of SSLE, makes use of indistinguishability obfuscation [5, 27], dened as follows.

Denition 1(Indistinguishability obfuscator (iO)). A uniform PPT machine iO is called an indistinguishability obfuscator for a circuit class fC g if the following conditions are satised:

$$ i \mathcal {O} $$

$$ \left{\mathcal{C}_{\lambda}\right} $$

{ For all security parameters 2 N*, for all C 2C, for all inputs x, we have that Pr[C⁰*(x) = C(x) : C⁰ iO(;C)]= 1*.*

$$ \lambda\in\mathbb{N} $$

$$ C\in{\mathcal{C}}_{\lambda} $$

$$ x, $$

$$ P r \left[ C ^ {\prime} (x) = C (x): C ^ {\prime} \leftarrow \right. $$

$$ i\mathcal{O}(\lambda,C)=1 $$

{ For any (not necessarily uniform) PPT distinguisher D, there exists a negligible function such that the following holds: for all security parameters 2 N*, for all pairs of circuits C₀;C₁ 2C, we have that* if C₀(x) = C₁(x) for all inputs x, then jPr[D(iO(;C₀)) = 1*] Pr[D*(iO(;C₁)) = 1*]j* ().

$$ \lambda\in\mathbb{N} $$

$$ C_{0},C_{1}\in\mathcal{C}_{\lambda} $$

$$ f,C_{0}(x)=C_{1}(x) $$

$$ |\mathit{P r/}D(i\mathcal{O}(\lambda,C_{0}))=1/\mathit{P r/}D(i\mathcal{O}(\lambda,C_{1}))=1/|\leq\alpha(\lambda) $$

Puncturable PRFs. Our obfuscation-based construction in Section 4 also relies on puncturable PRFs [15, 17, 36], dened below. Puncturable PRFs behave as regular PRFs, except their keys can be punctured such that a punctured key cannot be evaluated at one point in the PRF’s domain.

Denition 2. A puncturable family of PRFs F is given by a triple of algorithms (Key_F, Puncture_F, Eval_F), and a pair of computable functions n( ) and m( ) satisfying the following conditions:

{ Functionality preserved under puncturing. For every PPT adversary A such that A(1) outputs a set n() n() S f0*;* 1g, for all x 2f0*;* 1g where x =2 S, we have that

$$ S\subseteq{0,1}^{n(\lambda)} $$

$$ \mathcal{A}(1^{\lambda}) $$

$$ x\in{0,1}^{n(\lambda)} $$

$$ x\notin S, $$

$$ \Pr \left[ E v a l _ {F} (K, x) = E v a l _ {F} \left(K _ {S}, x\right): K \leftarrow K e y _ {F} \left(1 ^ {\lambda}\right), K _ {S} = P u n c t u r e _ {F} (K, S)\right] = 1. $$

{ Pseudorandom at punctured points. For every PPT adversary (A₁; A₂) such that A₁(1) outputs a set n() S f0*;* 1g and state, consider an experiment where K Key_F(1) and K_SPuncture_F(K;S). Then we have

$$ (\mathcal{A}{1},\mathcal{A}{2}) $$

$$ \mathcal{A}_{1}(1^{\lambda}) $$

$$ S\subseteq{0,1}^{n(\lambda)} $$

$$ K\leftarrow K\mathsf{e}y_{F}(1^{\lambda}) $$

$$ K_{S}\gets P u n c t u r{_{F}}(K,S) $$

$$ \left| P r \left[ \mathcal {A} _ {2} \left(\sigma , K _ {S}, S, E v a l _ {F} (K, S)\right) = 1 \right] - P r \left[ \mathcal {A} _ {2} \left(\sigma , K _ {S}, S, U _ {m (\lambda) \cdot | S |}\right) = 1 \right] \right| = n e g l (\lambda) $$

where Eval_F(K;S) denotes the concatenation of Eval_F(K;x₁);:::;Eval_F(K;x_k) where S = fx₁;:::;x_kg is the enumeration of the elements of S in lexicographic order and U_ldenotes the uniform distribution over l bits.

$$ E v a I_{F}(K,S) $$

$$ E v a l_{F}(K,x_{1}),...E v a l_{F}(K,x_{k}) $$

$$ S={x_{1},...,x_{k}} $$

$$ U_{l} $$

For ease of notation, we write F (K;x) to represent Eval_F(K;x). We also represent the punctured key Puncture_F(K;S) by K(S).

$$ E v a I_{F}(K,x) $$

$$ F(K,x) $$

$$ K(S) $$

Threshold FHE. In Section 5 we present an SSLE construction relying on a low-depth threshold FHE (TFHE) [11]. A threshold FHE allows computation on encrypted data as well as threshold decryption of ciphertexts, where a threshold number of key holders must come together to decrypt any ciphertext. We modify the standard syntax and security denitions of TFHE to allow the encryption algorithm to additionally output a proof of knowledge of the encrypted plaintext. This can be done by combining a traditional TFHE scheme with standard NIZK techniques (e.g. in the random oracle model).

Denition 3(Threshold fully homomorphic encryption (TFHE) [11]). Let P = fP₁;:::;P_Ng be a set of parties and let S be a class of ecient access structure on P. A threshold fully homomorphic encryption scheme for S is a tuple of PPT algorithms TFHE = (TFHE.Setup, TFHE.Encrypt, TFHE.Eval, TFHE.PartDec, TFHE.FinDEec) with the following properties:

$$ P={P_{1},...,P_{N}} $$

$$ T!F H E=(T F H E.S e t u p) $$

d { TFHE.Setup(1; 1*; A) ! (pk, sk₁,...,sk*_N): On input the security parameter, a depth bound d, and an access structure A, output a public key pk, and a set of secret key shares sk₁,...,sk_N.

$$ -;;T F H E.S e t u p(1^{\lambda},1^{d},\mathcal{A})\to;(p k,;s k_{1},...,s k_{N}). $$

$$ \lambda_{e} $$

$$ \mathfrak k_{1},\ldots,\mathfrak s k_{N} $$

n { TFHE.Encrypt(pk,) ! (ct,): On input a public key pk, and a plaintext 2 F₂for n = poly(), the encryption algorithm outputs a ciphertext ct and a proof. Encrypt can optionally take a third parameter r, the randomness to be used for encryption.

$$ \mu)\to\left(c t,\pi\right) $$

$$ \mu\in\mathbb{F}_{2}^{n} $$

$$ n=p o l y(\lambda) $$

^n k n { TFHE.Eval(pk, C, ct₁,...,ct^k) ! ct*: On input a public key pk, circuit C* : F²! F²of depth at most d, and a set of ciphertexts ct₁,...,ct, the evaluation algorithm outputs a ciphertext ct^. k

$$ c t_{1},...,c t_{k}\big)\to\hat{\mathsf{c t}}. $$

$$ C:\mathbb{F}{2}^{n\times k}\to\mathbb{F}{2}^{n} $$

$$ c t_{1},...,c t_{k} $$

$$ d, $$

{ TFHE.PartDec(pk, ct, sk_i) ! p_i: On input a public key pk, a ciphertext ct, and a secret key share sk_i, the partial decryption algorithm outputs a partial decryption p_irelated to the party P_i.

$$ c t $$

$$ c t,,s k_{i}\big)\rightarrow\mathsf{p}_{\mathsf{i}} $$

{ TFHE.FinDec(pk, ct, B) ! ^: On input a public key pk, ciphertext ct, and a set B = fp_ig_i2Sfor some n S fP₁;:::;P_Ng the nal decryption algorithm outputs a plaintext ^ 2 F₂[?.

$$ s k_{i} $$

$$ P_{i} $$

$$ B={p_{i}}_{i\in S} $$

$$ B)\to{\hat{\mu}}. $$

$$ S\subseteq{P_{1},...,P_{N}} $$

$$ \ \hat{\mu}\in\mathbb{F}_{2}^{n}\cup\bot $$

{ TFHE.Verify(pk, ct,) ! 1/0: On input a public key pk, ciphertext ct, and proof this algorithm accepts or rejects the proof for the given ciphertext.

$$ \cdot F F H.V e r f/p(p,c,\pi)\to1/0. $$

{ TFHE.VerifyDec(pk, p_i, ct) ! 1/0: On input a public key pk, a partial decryption p_i, and a ciphertext ct, this algorithm accepts or rejects the partial decryption.

$$ -T F H E.V e r i n y D e c(p k,p_{1},c t)\to1/0. $$

$$ p k, $$

In order for a TFHE to be considered secure for our purposes, it must satisfy the compactness, correctness, robustness, semantic security, plaintext extractability, and simulation security denitions below.

$$ c t, $$

Denition 4(Compactness [11]). We say that a TFHE scheme is compact if there exists polynomials n k n poly₁( ) and poly₂( ) such that for all, depth bound d, circuit C : F₂*!* F²of depth at most d, access n d structure A*, and 2* F₂, the following holds. For (pk, sk₁,...,sk_N) TFHE.Setup(1; 1*;* A*),* ct_iTFHE.Encrypt(pk,_i) for i 2 [k], ct^ TFHE.Eval(pk, C; ct₁;:::; ct_k),

$$ p o l y_{1}(\cdot) $$

$$ p o l y_{2}(\cdot) $$

$$ C:\mathbb{F}{2}^{n\times k}\to\mathbb{F}{2}^{n} $$

$$ d, $$

$$ \ \mathrm{A}, $$

$$ \mu\in\mathbb{F}_{2}^{n} $$

$$ c t _ {i} \leftarrow T F H E. E n c r y p t (p k, \mu_ {i}) f o r i \in [ k ], \hat {c t} \leftarrow T F H E. E v a l (p k, C, c t _ {1}, \dots , c t _ {k}), $$

$$ s k_{1},...,s k_{N}){\leftarrow}\ T T H E.S e t u p(1^{\lambda},1^{d},\mathbb{A}) $$

p_jTFHE.PartDec(pk,ct,sk_j) for j 2 [N], we have that jct^j poly(;d) and jp j poly(;d;N). j

$$ p_{j}\gets\mathit{T F H E.P a r t D e c}(p k,c t,s k_{j})\mathit\ f{o r};j\in[N]. $$

$$ \left|\hat{c}t\right|\leq p o l y(\lambda,d) $$

$$ |p_{j}|\leq p o l y(\lambda,d,N). $$

Denition 5(Correctness [11]). We say that a TFHE scheme satises evaluation correctness if for all, n k n n depth bound d, access structure A*, circuit C* : F₂! F²of depth at most d, S 2 A*, and*ⁱ2 F²for i 2 [k], d the following condition holds. For (pk, sk₁,...,sk_N) TFHE.Setup(1; 1*;* A*), (ct*_i;_i) TFHE.Encrypt(pk,_i) and TFHE.Verify(pk, ct_i,_i)=1 for i 2 [k], ct^ TFHE.Eval(pk, C, ct₁,...,ct_k), h i

$$ \lambda, $$

$$ d, $$

$$ d,,\beta\in\mathbb{A}. $$

$$ \dot{C}:\mathbb{F}{2}^{n\times k}\to\mathbb{F}{2}^{n} $$

$$ i\in[k] $$

$$ \mu_{i}\in\mathbb{F}_{2}^{n} $$

$$ (p k,;s k_{1},...,s k_{N})\leftarrow;T F H E.S e t u p(1^{\lambda},1^{d},\mathbb{A}),;(c t_{i},\pi_{i}){\leftarrow} $$

$$ c t_{1},\ldots,c t_{k}) $$

$$ \operatorname*{P r}\Big[\mathit{T F H E.F i n D e c}(p k,\ \hat{c t},{\mathit{T F H E.P a r t D c c}(\rho k,c t,s k_{i})}{i\in S})=C(\mu{1},...,\mu_{k})\Big]\geq1-\mathsf{n e g l}(\lambda). $$

$$ i\in[k] $$

$$ V e r i f y(p k,,c t_{i},,\pi_{i}){=}{} $$

$$ E n c r y p t(p k,\mu_{i}) $$

Moreover, we additionally require that h

$$ \operatorname*{P r}\left[D\leftarrow{\mathit{T F H E.P a r t D e c}(p k,c t,s k_{i})}{i\in S}:{\mathit{T F H E.V e r t f y o e c}(p k,,D{i},,c t)=1}_{i\in S}\right]=1. $$

Denition 6(Robustness [11]). We say that a TFHE scheme satises robustness if for all, and depth d bound d, the following holds. For all PPT adversaries A, the following experiment ExptA;TFHE.rob(1*;* 1) outputs 1 with negligible probability:

$$ {lambda}, $$

$$ d, $$

$$ E x p t_{\mathcal{A},T F H E.r o b}(1^{\lambda},1^{d}) $$

A;TFHE.rob d 1.On input the security parameter 1 and a circuit depth 1*, the adversary A outputs messages*¹;:::;^k, n k n a circuit C : F₂! F₂of depth at most d and an access structure A*.*

$$ 1^{\lambda} $$

$$ 1^{d} $$

$$ \mu_{1},\ldots,\mu_{k} $$

$$ C:\mathbb{F}{2}^{n\times k}\to\mathbb{F}{2}^{n} $$

d 2.The challenger runs (pk,sk₁,...,sk_N) TFHE.Setup(1; 1*;* A*) and provides (pk,sk₁,...,sk*_N) and ciphertext ct TFHE.Eval(pk,C,ct₁,...,ct) to A, where (ct,) TFHE.Encrypt(pk,) for each i 2 [k].

$$ (p\bar{k,,}s k_{1},...,s k_{N})\gets\mathit{T F H E.S e t u p}(1^{\lambda},1^{d},\mathbb{A}) $$

$$ (p k,s k_{1},...,s k_{N}) $$

$$ t\gets T F H E.E v a l(p k,C,c t_{1},...,c t_{k}) $$

$$ (left(c t_{i},\pi_{i})\leftarrow $$

$$ i\in[k] $$

$$ \mu_{i}) $$

k i i i 3. A outputs a two sets S₁ = fp₁*;:::;p_tg and S₂ = fp⁰₁;:::;* p⁰_tg of partial decryptions.

$$ S_{1}=\left{\mathsf{p}{1},...,\mathsf{p}{\mathsf{t}}\right} $$

4.The experiment outputs 1 i:

$$ S_{2}=\left{\mathsf{p}{1}^{\prime},...,\mathsf{p}{\mathsf{t}}^{\prime}\right} $$

{ TFHE.VerifyDec(pk, p, ct) = 1 for all p 2fS₁;S₂g, and { TFHE.FinDec(pk, ct, S₁) 6=TFHE.FinDec(pk, ct, S₂).

$$ \mathsf{p}\in{S_{1},S_{2}} $$

$$ -\ T!{\cal F}E.{\cal F}{\cal F}n{\cal D}{{\cal D}}((p k,;c t,;S_{1})\neq{\cal}{\cal F}{\cal H}{\cal E}.{\cal F}{\ \ \cal}i{{\cal D}}{{\cal D}}({p k,,;c t,;S_{2}}). $$

Denition 7(Semantic security [11]). We say that a TFHE scheme satises semantic security if for all, d and depth bound d, the following holds. For any PPT adversary A, the following experiment ExptA;TFHE.sem(1*;* 1) outputs 1 with negligible probability:

$$ \lambda, $$

$$ E x p t_{\mathcal{A},\mathit{T F H E.s e m}}(1^{\lambda},1^{d}) $$

d ExptA;TFHE.sem(1*;* 1):

$$ {_\ }1^{\lambda},1^{d}) $$

d 1.On input the security parameter 1 and a circuit depth 1*, the adversary A outputs* A 2 S.

$$ 1^{\lambda} $$

$$ 1^{d} $$

$$ \mathbb {A} \in S. $$

d 2.The challenger runs (pk,sk₁,...,sk^N) TFHE.Setup(1; 1*;* A*) and provides pk to A.*

$$ (p k,{s k_{1},...,s k_{N}})\leftarrow\mathit F F H E.S e t u p(1^{\lambda},1^{d},\mathbb A) $$

n 3. A outputs a set S fP₁;:::;P_Ng such that S =2 A as well as messages m₀;m₁ 2 F².

$$ S\subseteq{P_{1},...,P_{N}} $$

$$ m_{0},m_{1}\in\mathbb{F}_{2}^{n} $$

R 4.The challenger provides fsk_ig_i2Salong with TFHE.Encrypt(pk,m) for m fm₀;m₁g to A.

$$ S\notin\mathbb{A} $$

$$ {{\mathfrak{s}}k_{i}}_{i\in S} $$

$$ m\xleftarrow{\mathbb{R}}{m_{0},m_{1}} $$

$$ m=m^{\prime}. $$

5. A outputs a guess m⁰. The experiment outputs 1 if m = m⁰.

Denition 8(Plaintext Extractability). We say that a TFHE scheme is plaintext extractable if for all , depth bound d, and access structure A the following holds. There exists a PPT extraction algorithm E such that for all PPT adversaries A, algorithm E interacts with A (e.g., emulating its random oracle) so that: h

$$ \begin{array}{l} \Pr \left[ (p k, s k _ {1}, \dots , s k _ {N}) \leftarrow T F H E. S e t u p \left(1 ^ {\lambda}, 1 ^ {d}, \mathbb {A}\right); (c t, \pi) \leftarrow \mathcal {A} (p k); (\mu , r) \leftarrow \mathcal {E} (p k, c t, \pi): \right. \ T F H E. E n c r y p t (p k, \mu ; r) \neq c t, a n d \ \left. T F H E. V e r i f y (p k, c t, \pi) = 1\right) \Bigg ] \leq n e g l (\lambda). \ \end{array} $$

Denition 9(Simulation security [11]). We say that a TFHE scheme satises simulation security if for all, depth bound d, and access structure A*, the following holds. There exists a PPT algorithm S* = (S₁; S₂) d d such that for all PPT adversaries A, the following experiments Expt_A;Real(1*;* 1) and Expt_A;Ideal(1*;* 1) are indistinguishable:

$$ d, $$

$$ \lambda, $$

$$ \mathcal{S}=(\mathcal{S}{1},\mathcal{S}{2}) $$

$$ E x p t_{\mathcal{A},R e a l}(1^{\lambda},1^{d}) $$

$$ E x p t_{\mathcal{A},I d e a l}(1^{\lambda},1^{d}) $$

$$ E x p t_{\mathcal{A},R e a l}(1^{\lambda},1^{d}) $$

A;Real d 1.On input the security parameter 1 and a circuit depth 1*, the adversary A outputs* A 2 S*.*

$$ 1^{\lambda} $$

$$ 1^{d} $$

$$ \mathbb{A}\in\mathbb{S} $$

d 2.The challenger runs (pk,sk₁,...,sk_N) TFHE.Setup(1; 1*;* A*) and provides pk to A.*

$$ (p k,{s k_{1},...,s k_{N}})\gets\mathit F F H E.S e t u p(1^{\lambda},1^{d},\mathbb A) $$

n 3. A outputs a maximal invalid party set S fP₁;:::;P_Ng, messages₁;:::;_k2 F₂and randomness r₁;:::;r_k.

$$ S^{*},\subseteq,{P_{1},...,P_{N}} $$

$$ \mu_{1},...,\mu_{k},\in,\mathbb{F}_{2}^{n} $$

$$ r_{1},...,r_{k} $$

4.The challenger provides the keys fsk_ig_i2Sand fTFHE.Encrypt(pk,_i;r_i)g_i2[k]to A.

$$ {s k_{i}}_{i\in S^{*}} $$

$$ \mathcal{A}. $$

5. A issues a polynomial number of adaptive queries of the form (S fP₁;:::;P^Ng;C) for circuits C : n _{k n}^ F₂! F₂of depth at most d. For each query, the challenger computes ct TFHE.Eval(pk,C,ct₁,...,ct_k) and provides the set fTFHE.PartDec(pk,ct,sk ^_i)g_i2Sto A.

$$ (S\subseteq{P_{1},...,P_{N}},\mathcal{C}) $$

$$ C $$

$$ \mathbb{F}{2}^{n\times k}\rightarrow\mathbb{F}{2}^{n} $$

$$ \dot{c t}\leftarrow T F H E.E v a l(p k,C,c t_{1},...,c t_{k}) $$

$$ \left{T F H E. P a r t D e c \left(p k, \hat {c} t, s k _ {i}\right) \right} _ {i \in S} t o \mathcal {A} $$

6.At the end of the experiment, A outputs the set of sets it received from the challenger.

$$ E x p t_{\mathcal{A},I d e a I}(1^{\lambda},1^{d}) $$

ExptA;Ideal(1; 1): d 1.On input the security parameter 1 and a circuit depth 1*, the adversary A outputs* A 2 S*.*

$$ 1^{\lambda} $$

$$ 1^{d} $$

$$ \mathbb{A}\in\mathbb{S}. $$

d 2.The challenger runs (pk,sk₁,...,sk_N,st) S₁(1; 1*;* A*) and provides pk to A.*

$$ (p k, s k _ {1}, \dots , s k _ {N}, s t) \leftarrow \mathcal {S} _ {1} \left(1 ^ {\lambda}, 1 ^ {d}, \mathbb {A}\right) $$

$$ {\mathcal A}. $$

$$ S^{*}\dot{;\subseteq;}P_{1},...,P_{N}}; $$

$$ \mu_{1},...,\mu_{k},\in,\mathbb{F}_{2}^{n} $$

$$ r_{1},...,r_{k} $$

5. A issues a polynomial number of adaptive queries of the form (S fP₁;:::;P^Ng;C) for circuits C : n _{k n} F₂! F₂of depth at most d. For each query, the challenger runs the simulator fpⁱgi2S S₂(C; fct₁;:::; ctkg; C(₁;:::;_k);S; st) and sends fp_ig_i2Sto A.

$$ {\mathfrak{s k}{i}}{i\in S^{*}} $$

$$ \scriptstyle\ {l,}\mu_{i};r_{i})}_{i\in[k]} $$

$$ (S\subseteq{P_{1},..,,P_{N}},\mathcal{C}) $$

$$ C $$

$$ \mathbb{F}{2}^{n\times k}\rightarrow\mathbb{F}{2}^{n} $$

$$ \left{p _ {i} \right} _ {i \in S} \leftarrow \mathcal {S} _ {2} \left(C, \left{c t _ {1},..., c t _ {k} \right}\right) $$

$$ C(\mu_{1},...,\mu_{k}),S,\mathsf{s t}) $$

$$ {p_{i}}_{i\in S} $$

6.At the end of the experiment, A outputs the set of sets it received from the challenger.

3 Dening Single Secret Leader Election

This section denes single secret leader election (SSLE) and its security properties as well as a number of practical restrictions on performance and resilience that an SSLE scheme should satisfy.

SSLE requirements. Informally, an SSLE scheme involves N users U₁;:::; U_Nwith access to each other’s public keys, a shared public ledger, and an unbiased randomness beacon. This group of users needs to repeatedly select exactly one leader U_isuch that only U_iknows who she is and other users remain oblivious to the leader’s identity, until she reveals herself. That is, each participant learns whether she is the leader and nothing else. The selected leader can provide a proof that she was selected.

$$ \mathcal{U}{1},\ldots,\mathcal{U}{N} $$

$$ U_{i}, $$

$$ U_{i}, $$

The scheme must satisfy a number of properties: (1) uniqueness means that exactly one leader is chosen 1 in each election; (2) fairness means that each user has a probability of becoming the leader, and as long N as there is at least one honest user, a set of malicious users cannot inuence the result of an election; and (3) unpredictability means that an adversary who does not control the leader cannot learn which user has been elected.

$$ \frac{1}{N} $$

Ultimately, an SSLE protocol should satisfy a robustness property requiring that a denial of service attack against an fraction of users succeeds in disrupting the election with probability at most. This is the best-possible security because an attack against a random fraction of the network hits the randomly-chosen leader with probability, and the election fails if the chosen leader is unable to perform its leadership role. Robustness is in fact implied by the combination of uniqueness, fairness, and unpredictability because so long as there is exactly one leader chosen uniformly at random from the set of participants such that no adversary can guess who the leader will be, an attacker can do no better than guess who to attack.

We would like to minimize the amount of data posted to the public ledger and the computational cost for users in each election. Since blockchain applications involve running elections on a continuing basis, we can allow for communication costs to be amortized over many elections, with participants registering once to participate in all elections until they decide to exit.

3.1 A \straw man" non-example

Before presenting formal denitions and constructions for SSLE schemes, we describe a simple scheme that does not satisfy the requirements for an SSLE. This construction bears a resemblance to prior solutions that rely on VRFs (e.g. [3, 29]) but uses only commitments and no global secret keys. It serves to illustrate the kind of approach used in prior work and highlight the new requirements that motivate SSLE. Since some use cases do not strictly require that exactly one leader be elected, it is possible that this scheme suces for some use-cases.

Our straw man scheme proceeds as follows. Users can register to participate in elections by posting a commitment com(v_id) to the ledger, where id is a user’s public identity and v_idis a random element in F_p, where p is a-bit prime that is a public parameter shared by all participants. Each election begins when a R public randomness beacon publishes a random value R F_p. The winner of the election is the participant who has the minimal value of jR v_idj. Unfortunately, no user can determine alone if she is the winner, so any user who has a good chance of being the winner reveals herself as a potential winner. That is, all users 2 for whom jR vidj < 10 open their commitments to vid, so that the ultimate winner becomes apparent N as the one whose choice of v_idresults in the smallest value of jR v_idj among those who post.

$$ \cos(v_{\mathsf{i d}}) $$

$$ v_{\mathrm{i d}} $$

$$ p $$

$$ \mathbb{F}_{p}, $$

$$ R\xleftarrow{\mathbb R}_{p p} $$

$$ |R-v_{\mathsf{i d}}| $$

$$ \left| R - v _ {\mathrm {i d}} \right| < 1 0 \cdot \frac {2 ^ {\lambda}}{N} $$

$$ v_{\mathrm{i d}}. $$

$$ |R-v_{\mathsf{i d}}| $$

It is clear that the above protocol will elect one leader with high probability and that the leader will be chosen uniformly at random from among the list of participants. The leader’s identity is totally unpredictable until the small group of candidate leaders is revealed, but once that list is revealed the leader’s identity is known to everyone. This means that if the leader is to privately do some expensive task before revealing herself, all potential leaders must do this task before revealing that they might be leaders, resulting in a great deal of duplication of work. Another problem with this scheme happens if a participant realizes that she was selected as the leader, but chooses not to reveal herself, allowing another participant with a higher value of jR v_idj to claim leadership. Later, the true leader who remained secret can make her claim to winning the election public and throw into doubt the result of any work done in the intervening time, e.g. any blocks published in a proof of stake blockchain system. Yet another problem happens in case the nal leader’s post of v_iddoes not reach all the users (nodes) in the system. In this case, users will have dierent views of who was elected, causing a fork. This cannot happen if the election protocol ensures that only a single user can prove that it won the election, no matter what the other users do.

$$ |R-v_{\mathsf{i d}}| $$

$$ v_{\mathrm{i d}} $$

In general, solutions based on selecting a small group of potential leaders by ipping a biased coin will not meet the requirement that the unique leader must learn she was elected before her identity becomes public. Ensuring that there is a canonical leader whose identity remains hidden until she chooses to reveal herself { and never sooner { is the problem that an SSLE must solve.

3.2 Formalizing SSLE denitions

We now formally dene the syntax and security properties of SSLE. In order to accommodate our diverse approaches to solving this problem, the syntax includes parameters and outputs which may be left empty if not required by a given scheme. For blockchain applications, we use the state st to record data that will be stored on the blockchain by the elected leader in each election, and by changes made after a user registers for elections.

Denition 10(Single secret leader election (SSLE)). A single secret leader election scheme is a tuple of PPT algorithms SSLE = (SSLE.Setup, SSLE.Register, SSLE.RegisterVerify, SSLE.Elect₁, SSLE.Elect₂, SSLE.Verify) with the following behavior:

{ SSLE.Setup(1;‘;N) ! pp, sk₁,...,sk_N, st₀: The setup process generates public parameters pp, a number of secrets to be used later, and an initial state st₀. Here N is an upper bound on the number of participants supported by the scheme, and ‘ an optional lower bound on the number of required users per election. SSLE.Setup is a one-time setup process intended to be run a single time before initiating a series of elections.

$$ -;S S L E.S e t u p(1^{\lambda},\ell,N)\rightarrow p p,,s k_{1},...,s k_{N},,s t_{0}. $$

$$ s t_{0} $$

{ SSLE.Register(i, pp, st) ! k_i, rt_i, st’: Each user registers with a unique public identity i 2 [N], the public parameters pp, and the current state st. Registration outputs a secret k_i, gives a user a registration token

$$ (i,,p p,,s t)\to k_{i},,r t_{i} $$

$$ i\in[N]. $$

$$ k_{i}. $$

rt_i, and modies the state to st’. SSLE.Register is run by each participant when that participant wants to begin taking part in elections. The participant registers once and stays registered unless she decides to leave. Some schemes will require an elected leader to re-register after having been elected.

$$ r t_{i}, $$

$$ s t^{\prime} $$

{ SSLE.RegisterVerify(i, k_i, rt_i, pp, st) ! 0*=1: SSLE.RegisterVerify is run by previously registered users after* a new user registers to verify that the registration was carried out correctly. Verication can use the verifying user’s secret k_i, registration token rt_i, the public parameters pp and current state st.

$$ k_{i},,r t_{i},,p p,,s t\ )\to0/1 $$

{ SSLE.Elect₁(pp, st, R, i, sk_i) ! p_i;l_i: Leader election begins by taking public parameters, current state, a random R 2 R (generated by a randomness beacon), and user U_i’s secret key sk_i, and outputting intermediate values p_iand l_i.

$$ k_{i} $$

$$ r t_{i} $$

$$ R,,i,,s k_{i})\rightarrow p_{i},l_{i}. $$

$$ R,\in,\mathcal{R} $$

$$ s k_{i}, $$

$$ p_{i} $$

$$ l_{i} $$

{ SSLE.Elect₂(pp, st, l₁,...,l_m, i, k_i, sk_i, rt_i, p_i) ! 1*=0;=?: Leader election concludes by taking outputs* of Elect₁ as well as U_i’s secrets k_i, sk_i, and rt_iand outputting whether user U_ihas been chosen as the leader, and potentially a proof of leadership. For schemes that do not require an intermediate output from an election, we use the shorthand notation Elect(pp, st, R, i, k_i, sk_i, rt_i) ! 1*=0;=? to combine Elect₁* and Elect₂, omitting unused inputs. The algorithms making up SSLE.Elect dene the actual protocol to be executed between participants in an election each time they wish to elect a leader.

$$ k_{i},;s k_{i}. $$

$$ \mathcal{U}_{i} $$

$$ m t_{i} $$

$$ k_{i},,s k_{i},,r t_{i})\rightarrow1/0,\pi/\bot $$

{ SSLE.Verify(i, pp, st, R,_i; p_i) ! 1/0: Given an index i, the state st, the election randomness R 2R, a proof_iclaiming that a particular user was elected leader, and optionally an intermediate value p_ifrom the election, the verication algorithm accepts or rejects the proof that user U_ihas been elected leader. SSLE.Verify is used to check the authenticity of a participant who claims to be the leader when it is time for the leader to reveal herself.

$$ R,,\pi_{i};,p_{i}\ )\to1/0. $$

$$ R\in\mathcal{R} $$

$$ \pi_{i} $$

$$ p_{i} $$

We could also include a Revoke algorithm for users to indicate that they no longer wish to participate. We refrain from formalizing this algorithm as it does not signicantly impact the security properties we wish to achieve, but our schemes can be modied to include a Revoke algorithm.

We now formalize our security denitions. All our elections account for the repeated nature of elections in real deployments of SSLE, allowing the adversary to choose which users register for each election and how many elections occur. While our denitions have all previously registered users run SSLE*:* RegisterVerify after each registration, our Obfuscation and TFHE-based SSLE schemes (see Sections 4 and 5) will retain all their security properties so long as any single honest user runs SSLE*:* RegisterVerify.

Uniqueness requires that exactly one participant in an election can prove that she is the elected leader. Our denition allows an adversary to corrupt as many users as it wants and still requires that at most one leader be elected in any given election. We do allow for zero leaders to be elected because if a corrupted participant is elected leader, it may choose not to announce that it is the leader. We also allow the adversary to produce proofs of leadership after seeing honest parties’ messages to account for an attacker who will use this information to produce fake proofs.

Denition 11(Uniqueness). We denote the uniqueness experiment with security parameter using UNIQUE[A;;‘;N]. The experiment is played between an adversary A and a challenger C as follows:

Setup Phase. Adversary A picks a number c < N as well as a set of indexes M [N], jM j = c of users to corrupt. The challenger C runs pp, sk₁,...,sk_N, st₀ SSLE.Setup(1;‘;N) and gives A the parameters pp, state st₀, and secrets sk_ifor i 2 M.

$$ c<N $$

$$ M\subset[N],,|M|=c $$

$$ s k_{1},...,s k_{N},;s t_{0}\gets S S L E.S e t u p(1^{\lambda},\ell,N) $$

$$ i\in M $$

Elections Phase. Adversary A can choose any set of users to register for elections and for any number of elections to occur, where A plays the role of users U_ifor i 2 M and C plays the role of the rest of the users. The challenger C also generates the election randomness R 2R.

$$ i\in M $$

$$ \ _{i} $$

$$ R\in\mathcal{R} $$

To register an uncorrupted user, A sends the index i of the user to C, and C runs k_i;rt_i;st⁰ SSLE: Register(i; pp*;st) To register a corrupted user, A sends the index i of the user to C along with an updated state st⁰. In ei-* ther case, C then runs SSLE*:* RegisterVerify(j;k_j;rt_j;pp;st) for any previously regisered user U_jwhere j 2 [N] n M. If any call to SSLE: RegisterVerify returns 0, the game immediately ends with output 0. Otherwise the state is updated to st⁰*.*

$$ k_{i},\mathsf{r t}_{i} $$

$$ {\mathfrak(i,\mathfrak{p p},\mathfrak{s t})} $$

$$ \mathsf{y}(j,k_{j},\mathsf{r t}_{j},\mathsf{p p},\mathsf{s t}) $$

$$ s mathbf t{{'}} $$

$$ j,\in,[N],\backslash,M $$

$$ U_{j} $$

$$ )\mathrm{~s t^{\prime}} $$

Each election begins with C generating p_i;l_iSSLE*:* Elect₁(pp*;st;R;i;* sk_i) on behalf of each uncorrupted registered user and A sending values l_ifor any subset of corrupted registered users. Let l₁;:::;l_tbe the

$$ p_{i},l_{i}\leftarrow\mathtt{S S L E E e E t_{l}}(\mathfrak{p p},\mathfrak{s t},R,i,\mathtt{S k}_{i}) $$

$$ l_{i} $$

$$ l_{1},...,l_{t} $$

set of intermediate values l_igenerated in this step. Then, for all uncorrupted users, C sets (b_j;_j) SSLE.Elect₂(pp;l₁;:::;l_t;j;k_j; sk_j; rk_j) if user j has registered for that election or (0*; ?) otherwise. C sends (b_j;*_j) for each uncorrupted user to A.

$$ (b_{j},\pi_{j}),\leftarrow $$

$$ l_{i} $$

$$ \mathit S S L E.E l e c t_{2}(p p,l_{1},...,l_{t},j,k_{j},s k_{j},r k_{j}) $$

Output Phase. For each election in the elections phase, A outputs values (b_i;_i) for each i 2 M.

$$ (b_{j},\pi_{j}) $$

$$ (b_{i},\pi_{i}) $$

The experiment outputs 0 if for each election with randomness R 2R and state st, there is at most one user Uⁱ(either corrupted or uncorrupted) who outputs b_i= 1 and_isuch that Verify(i ; pp; st;R;_i)) = 1*. Otherwise the experiment outputs 1.*

$$ i\in M $$

$$ R\in\mathcal{R} $$

$$ b_{i^{*}}=1 $$

$$ \pi_{i^{*}} $$

$$ V e r i f y(i^{},p p,s t,R,\pi_{i^{}})= $$

We say an SSLE scheme is unique if no PPT adversary A can win the uniqueness game except with negligible probability. That is, for all PPT A and for any ‘ < N, the quantity h i

$$ \operatorname*{P r}[U\ \ ! $$

If uniqueness only holds so long as there are at least t uncorrupted users participating in each election, we say that S is t-threshold unique. We say user U_iwins an election if it outputs a tuple (1*;_i) such that Verify(i ; pp; st;R;_i) = 1.*

$$ \mathcal{U}_{i}, $$

$$ \ 1,\pi_{i^{*}}, $$

$$ V e r i f y(i^{},p p,s t,R,\pi_{i^{}})=1 $$

We dene unpredictability with a security game where an adversary can control any number of participants in an election and, after participating in several elections, must guess which honest user won a challenge election. Our game captures the intuition that if an adversary does not control the winner, it can do no better than guess which of the honest users won the election.

Denition 12(Unpredictability). We denote the unpredictability experiment with security parameter by UNPRED[A;;‘;N;n;c]. The experiment is played between an adversary A and challenger C as follows:

$$ \Re E D!\ \ {mathcal A A},\lambda,\ell,N,n,c J $$

Setup Phase. Adversary A picks a set of indexes M [N], jM j = c of users to corrupt. The challenger C runs pp, sk₁,...,sk_N, st₀ SSLE.Setup(1;‘;N) and gives A the parameters pp, state st₀, and secrets sk_i for i 2 M.

$$ M\subset[N],,|M|=c $$

$$ s k_{1},...,s k_{N},;s t_{0}\gets S S L E.S e t u p(1^{\lambda},\ell,N) $$

$$ S t_{0}. $$

$$ i\in M $$

$$ \mathcal{U}_{i} $$

$$ i\in M $$

$$ R\in\mathcal{R} $$

To register an uncorrupted user, A sends the index i of the user to C, and C runs k_i;rt_i;st⁰ SSLE: Register(i; To register a corrupted user, A sends the index i of the user to C along with an updated state st⁰*. In ei-* ther case, C then runs SSLE*:* RegisterVerify(j;k_j;rt_j;pp;st) for any previously regisered user U_jwhere j 2 [N] n M. If any call to SSLE: RegisterVerify returns 0, the game immediately ends with output 0. Otherwise the state is updated to st⁰*.*

$$ k_{i},\mathsf{t_{i}},\mathsf{s t^{\prime}}\leftarrow\mathsf{S S L E.R e g i s e r}(i,\mathsf{p p}t, $$

$$ s!{\ }bf{t}^{\prime} $$

$$ \mathsf{g i s t e r V e r i f y}(j,k_{j},\mathsf{r t}_{j},\mathsf{p p},\mathsf{s t}) $$

$$ j,\in,[N],\backslash,M $$

$$ U_{j} $$

$$ \ {sf s}{\sf t}^{\prime} $$

Each election begins with C generating p_i;l_iSSLE*:* Elect₁(pp*;st;R;i;* sk_i) on behalf of each uncorrupted registered user and A sending values l_ifor any subset of corrupted registered users. Let l₁;:::;l_tbe the set of intermediate values l_igenerated in this step. Then, for all uncorrupted users, C sets (b_j;_j) SSLE.Elect₂(pp;l₁;:::;l_t;j;k_j; sk_j; rk_j) if user j has registered for that election or (0*; ?) otherwise. Finally, C sends (b_j;*_j) for each uncorrupted user to A.

$$ p _ {i}, l _ {i} \leftarrow \mathrm {S S L E . E l e c t} _ {1} (\mathrm {p p}, \mathrm {s t}, R, i, \mathrm {s k} _ {i}) $$

$$ l_{i} $$

$$ l_{1},...,l_{t} $$

$$ l_{i} $$

$$ \mathit S S L E.E e c t_{2}(p p,l_{1},...,l_{t},j,k_{j},s k_{j},r k_{j}) $$

$$ (b_{j},\pi_{j})\leftarrow $$

$$ (b_{j},\pi_{j}) $$

Challenge Phase. At some point after all users U_jfor j 2 [n] have registered, A indicates that it wishes to receive a challenge, and one more election occurs. In this election, C does not send (b_j;_j) for each uncorrupted user to A. Let U_ibe the winner of this election. The game ends with A outputting an index i⁰ 2 [N]. If, for U_ielected in the challenge phase, i 2 M, then the output of UNPRED[A;;‘;N;n;c] is set to 0*. Otherwise, UNPRED[A;;‘;N;n;c] outputs* 1 i i = i⁰.

$$ j\in[n] $$

$$ \ _{j} $$

$$ i^{\prime}\in[N] $$

$$ (b_{j},\pi_{j}) $$

$$ \ {cal U}_{i} $$

$$ \mathcal {U} _ {i} $$

$$ i\in M $$

$$ \ N P R E D(\mathcal{A},\lambda,\ell,N,n,c J $$

We say that an SSLE scheme S is unpredictable if no PPT adversary A can win the unpredictability game with greater than negligible advantage when the winner of the election is uncorrupted. That is, if for all PPT A, for any c n 2, n N, and for any ‘ < N the quantity

$$ {\ }R E D({\mathcal A},\lambda,\ell,N,n,c J $$

$$ c\leq n-2,,n\leq N $$

$$ \operatorname*{P r}\Big[\mathsf{U N P R E D}(\mathcal{A},\lambda,\ell,N,n,c]=1\ |\ i\in[N]\setminus M\Big]\leq\frac{1}{n-c}+\mathsf{n e g l}(\lambda). $$

1 If A wins with advantage + negl() for >, with potentially depending on c, n, or N, we say n c that S is-unpredictable. If the value of depends on N, then we require that n = N. If unpredictability

$$ \alpha+n e g I(\lambda) $$

$$ \alpha>\textstyle\frac{1}{n-c} $$

$$ c,,n, $$

$$ N_{\parallel} $$

$$ n=N $$ only holds for c < t for some t > 0, we say that S is t-threshold unpredictable. We can also dene a selectively secure version of the unpredictability game where the adversary registers all the users who wish to participate in the challenge phase during the setup and sends the list to the challenger before the challenger runs SSLE.Setup.

$$ c,=,t $$

$$ t,>,0 $$

Note that a trivial election scheme that never elects a leader does satisfy this notion of unpredictability because it will never be the case that i 2 [N] n M. However, this is ne because such a trivial scheme does not satisfy fairness (dened below), and a viable SSLE scheme must sastisfy all our denitions.

$$ i\in[N]\setminus M $$

It might seem that any unpredictable scheme must also be fair or else the unpredictability adversary could gain a non-negligible advantage by guessing the index of a user more likely to win an election. However, observe that the denition of unpredictability only considers the case where the adversary does not control the winner of the challenge election. If the adversary can manipulate an SSLE protocol so that it always controls the winner, our unpredictability denition becomes vacuous.

We require fairness to protect against such an adversary. The key idea behind our denition of fairness is that a scheme is fair if the best the adversary can do to be elected is to actually win the election honestly, i.e. with probability equal to the fraction of adversary-controlled participants. Moreover, fairness also requires that an honest user wins the election with probability equal to the fraction of honest users.

Denition 13(Fairness). We denote the fairness experiment with security parameter using FAIR[A;;‘;N;c;n]. The experiment is played between an adversary A and challenger C as follows:

Setup Phase. Adversary A picks a set of indexes M [N], jM j = c, of users to corrupt. The challenger C runs pp, sk₁,...,sk_N, st₀ SSLE.Setup(1;‘;N) and gives A the parameters pp, state st₀, and secrets sk_ifor i 2 M.

$$ \ \mathit A I I\ !A\ !\ $$

$$ M\subset|N|,,|M|=c, $$

$$ s k_{1},...,s k_{N},;s t_{0},\leftarrow,S S L E.S e t u p(1^{\lambda},\ell,N) $$

$$ s k_{i} $$

$$ s t_{0} $$

$$ i\in M $$

$$ \mathcal{U}_{i} $$

$$ i\in M $$

$$ R\in\mathcal{R} $$

$$ k_{i},\mathsf{t_{i}},\mathsf{t^{\prime}}\leftarrow\mathsf{S S L E.R e g i s t r}(i,p\mathsf{p,}\mathsf{S t}) $$

$$ \mathrm {s t} ^ {\prime} $$

$$ \ S S L\ R e g i s t r V i i!f(j,k_{j},\mathsf{t t}{}_{j},\mathsf{p p},\mathsf{s t}) $$

$$ U_{j} $$

$$ j,\in,[N],\backslash,M $$

$$ s mathsf{t}^{\prime} $$

$$ p_{i},l_{i}\leftarrow\mathsf{S S L E E e E t}{}{1}(\mathfrak{p p},\mathfrak{s t},R,i,\mathfrak{s k}{i}) $$

$$ l_{i} $$

$$ l_{1},...,l_{t} $$

$$ (b_{j},\pi_{j})\leftarrow $$

$$ \mathit{S S L E.E l e c t_{2}}(p p,l_{1},...,l_{t},j,k_{j},s k_{j},k_{j}) $$

$$ (b_{j},\pi_{j}) $$

Challenge Phase. At some point after all users U_ifor i 2 [n] have registered, A indicates it wishes to receive a challenge, and one more election occurs. FAIR[A;;‘;N;c;n] outputs 1 if there is no i 2 [n]n M for which Verify(i, pp, st,_i) = 1 in the challenge election.

$$ \mathcal{U}_{i} $$

$$ i,\in,[n] $$

$$ F A I R \left[ \mathcal {A}, \lambda , \ell , N, c, n \right] $$

$$ \pi_{i}\ \ =1 $$

$$ i\in[n]\setminus M $$

We say that an SSLE scheme S is fair if no PPT adversary A can win the fairness game with greater than negligible advantage. That is, if for all PPT A, n N, c < n, and for any ‘ < N, h i

$$ P P T,\mathcal{A},,n\leq N,,c<n $$

$$ \ell<N $$

$$ \Bigl|\operatorname*{P r}\Bigl[\mathsf{F A I R}[\mathcal{A},\lambda,\ell,N,c,n]=1\Bigr]-c/n\Bigr|\leq\mathsf{n e g l}(\lambda). $$

If fairness only holds for c < t for some t > 0, we say S is t-threshold fair. We can dene a selectively secure version of the fairness game where the adversary registers all users who wish to participate in the challenge phase during setup and sends the list to the challenger before it runs SSLE.Setup.

$$ c<t,f o r $$

$$ t>0. $$

Requirements and variations for real-world use cases. Our goal in constructing SSLE schemes is to build protocols that satisfy the above security denitions while achieving performance characteristics acceptable for use in applications of SSLE. Restrictions imposed by applications include limitations on ledger growth as a result of each election, limitations on the computation required of each party, and scalability requirements to large numbers of users.

Some use cases of SSLE [38] require that users’ chances of winning an election be weighted, e.g. according to their stake in a proof of stake system as recorded in a public power table. Each of our constructions will be accompanied by a discussion of how to adapt the scheme to handle this requirement.

Another common use case requires picking multiple leaders in an ordered list, such that each leader learns her own position in the list (and a proof for that fact), but nothing about the other leaders. Any SSLE scheme can trivially achieve a similar property by repeating the protocol several times, once for each leader, before having any leader reveal herself. Note that it might happen that the same leader appears several times on the ordered list, which may or may not be acceptable. However, it may also be possible for a scheme to natively support such a functionality without incurring the cost of running several elections in parallel. Our obfuscation and DDH-based solutions (in Sections 4 and 6, respectively) will natively support ecient selection of multiple leaders.

4 SSLE from Obfuscation

The rst question to answer after stating the requirements of a SSLE is whether a protocol with all the requisite security properties can be achieved. In this section, we answer the question armitively by presenting an SSLE protocol built from indistinguishability obfuscation (iO) [5,27] that satises all the requirements set forth in Section 3, albeit with selective unpredictability and fairness. Note that the goal of this construction is not to present a candidate that can be realized in practice, but to showcase the behavior we would expect of an ideal SSLE scheme as a rst step toward practical constructions. Subsequent sections will describe practical protocols targeted at real-world use cases.

In this solution, a one-time distributed setup protocol will choose a puncturable PRF [15, 17, 36] key k and embed it in an obfuscated program. The program, given a list of public keys, an index, and some public randomness, uses the PRF to choose one key from the list of public keys to be the winner and outputs a commitment to 0 or 1. If the index matches the winning public key, it outputs a commitment to 1. Otherwise, it outputs a commitment to 0. Moreover, the randomness used in the commitment is encrypted to the public key of the input index as a second output.

In order to register to participate in this scheme, a user just needs to generate a key pair and publish the public key. In each round, users run the obfuscated program with the list of participating public keys, their own indexes, and randomness from a public randomness beacon. After decrypting their respective commitment randomnesses, the leader will nd a commitment to 1 whereas all other users will receive a zero. To prove leadership, the leader publishes the randomness used to commit to the output it received.

More precisely, the scheme would begin with a trusted setup phase in which, rst, a random key k is chosen from K, the distribution of keys for a puncturable PRF. Let F be a puncturable PRF, (COM*:* com*;COM:* verify) a commitment scheme, and (PKE.Encrypt,PKE.Decrypt) a CPA-secure public-key encryption scheme. The output of the setup phase is an obfuscated circuit Pe O (P) that is posted to the ledger, where O is an indistinguishability obfuscator and P implements the following function. P((pk₀,...,pk);i;n;R):

$$ \widetilde{P}\gets\mathcal{O}(P) $$

$$ P(({\mathsf{p k}}{0},...,{\mathsf{p k}}{n-1}),i,n,R){\mathrm{:}} $$

$$ 1.\ s\gets R,\mathfrak{p k}{0},...,\mathfrak{p k}{n-1} $$

2.(w;r;r⁰) F (k;s)

$$ (w,r,r^{\prime})\leftarrow F(k,s) $$

3. b 1 if i = w mod n, b 0 otherwise

$$ b\gets1;\ \mathrm{i f};i=w;\mathsf{m o d};n,b\gets0 $$

4. c COM.com(b; r)

$$ c\leftarrow\sf{C O M.c o m}(b;r) $$

$$ \ :mathsf P P\ \ !mathsf E E E n n\ !mathsf p p p(\mathsf{p k}_{i},r;r^{\prime}) $$

6.Output c*;*ct.

For each election with n participants, user U sets (c*;ct) Pe((pk₁;:::;* pk);i;n;R) and runs COM*:* verify(c*;* 1*;* i n PKE*:* Dec(sk_i*;*ct)) with the output R of the randomness beacon to recover a bit 1 or 0. By construction, all users will receive a 0 except the leader, who receives a 1. Moreover, the choice of leader is determined by the

$$ ({\mathfrak{c}},{\mathfrak{c t}})\leftarrow{\tilde{P}}(({\mathfrak{p k}}{1},...,{\mathfrak{p k}}{n}),i,n,R) $$

$$ \mathsf{P K E.D e c}(\mathsf{s k}_{i},\mathsf{c t})) $$ output of the PRF on the list of participant keys and the public randomness, ensuring fairness. Uniqueness comes from the binding property of the commitment scheme. Unpredictability comes from the security of the punctured PRF, commitment scheme, encryption scheme, and obfuscator, which together ensure that users can only read their own output from Pe. We formalize the protocol below.

Construction 14 (Obfuscation-based SSLE). Our Obfuscation-based SSLE scheme OSSLE = (OSSLE.Setup, OSSLE.Register, OSSLE.RegisterVerify, OSSLE.Elect, SSSLE.Verify) with security parameter uses a punc- turable PRF F, a commitment scheme COM = (COM*:* com*;COM:* verify), a public-key encryption scheme PKE=(PKE.Setup, PKE.Encrypt, PKE.Decrypt), and an indistinguishability obfuscator O.

$$ {\mathcal O.} $$

R { OSSLE.Setup(1;‘;N): Choose k f0*;* 1g and use it to create the leader picking circuit P described above. Then Let Pe O (P). Output pp=(; Pe*) and st=fg. Inputs ‘ and N are unused.*

$$ -\ S S S L!E.\ !{\sf S e t u p}(1^{\lambda},\ell,N) $$

$$ k;\xleftarrow{\mathrm{~}tiny{}!0,1}^{\lambda}} $$

$$ \dot{P}\gets\mathcal{O}(P) $$

$$ \scriptstyle{p p=}(\lambda,\ {widetilde P))} $$

$$ s t{\mathrm{=}}{} $$

{ OSSLE.Register(i, pp, st): Recover from pp. Let (pk_i,sk_i) PKE.Setup(1). Append pk_ito st and output (pk_i,sk_i) as rt_i. Output k_iis left empty.

$$ (p k_{i},s k_{i})\gets P K E.S e t u p(1^{\lambda}) $$

$$ p k_{i} $$

$$ (p!!!\ k_{i},!!!k_{i}) $$

{ OSSLE.RegisterVerify(i, k_i, rt_i, pp, st): Output 1 i pk_i2 st and there are no duplicate public keys in st. Input k_iis unused.

$$ k_{i} $$

$$ m_{i} $$

$$ p k_{i}\in s t $$

$$ k_{i},,r t_{i},,p p,,s t) $$

$$ k_{i} $$

{ OSSLE.Elect(pp, st, R, i, rt): Interpret st as pk₁,...,pk, rt as sk, and recover Pe from pp. Then run c*,* i n i i ct Pe(pk₁,...,pk;i;n;R). If COM*:* verify(c*;* 1*;PKE:* Dec(sk;ct)) = 0, output 0*. Otherwise, output* 1 and n i (i; PKE.Decrypt(sk_i, ct)).

$$ R,,i,,r t_{i}, $$

$$ p k_{1},...,p k_{n},;r t_{i} $$

$$ \tilde{P} $$

$$ S k_{i}, $$

$$ \mathsf{c t}{\leftarrow}\tilde{P}(p k_{1},...,p k_{n},i,n,R) $$

$$ \pi\gets(i,P K E.D e c r y p t(s k_{i},c t)) $$

{ OSSLE.Verify(i, pp, st, R,): Interpret st as pk₁,...,pk, as (i;r), and recover Pe from pp. Then run c, i n i ct Pe(pk₁,...,pk;i;n;R). Output COM*:* verify*(c;* 1*;r).* n

$$ R,,\pi_{i}) $$

$$ p k_{1},...,p k_{n},,\pi_{i} $$

$$ \tilde{P} $$

$$ (i,r) $$

$$ C, $$

$$ \leftarrow\tilde{P}(p k_{1},...,p k_{n},i,n,R) $$

Extensions. The obfuscation-based approach outlined above can easily accommodate a power table that determines each user’s probability of election by taking an additional input T representing the power table and giving each user U_ia range of values of w mod n for which they would be elected whose size corresponds to their stake. The scheme could also be extended to output multiple encryptions instead of only one in order to elect more than one leader in each election.

$$ \mathcal{U}_{i} $$

We prove the following security theorem in Appendix B.

Theorem 15. Assuming that F is a puncturable PRF, that COM is a correct, binding, and hiding com- mitment scheme, that PKE is a correct and CPA-secure public-key encryption scheme, and that O is an indistinguishability obfuscator, then OSSLE is a unique, selectively unpredictable, and selectively fair SSLE scheme.

5 SSLE from TFHE

This section shows how to build an SSLE scheme based on threshold fully homomorphic encryption (TFHE) [11] for a shallow circuit. This scheme will require t users to post partial decryptions of a ciphertext in each election, for a threshold t chosen as a parameter to the scheme. However, we maintain resistance against disruption by using threshold encryption so that as long as any t of the participants remain online, the election will succeed. One caveat of this scheme compared to the previous scheme is a more expensive user registration process.

Setup requires a group of ‘ = t users to set up a TFHE scheme and generate a TFHE encryption of a PRF key k. When a user joins, she needs approval from t existing participants who can generate a new threshold decryption key for that user. Additionally, users register by uploading a TFHE ciphertext containing a random secret k_i2f0*;* 1g, which is appended to a vector of secrets. To elect a leader, users (loosely speaking) generate randomness inside the TFHE and then use it to randomly select a value of k_i from the vector of secrets. The user whose secret is chosen knows she has been elected, but nobody else knows that the revealed secret is hers. To participate in future elections, she re-registers with a new secret kⁱ⁰. To realize this scheme, we need to show, rst, how to get secret randomness in the TFHE and, second, how to use it to select a leader.

$$ k_{i},\in,{0,1}^{\lambda} $$

$$ k_{i} $$

$$ k_{i}^{\prime}. $$

Generating randomness inside the TFHE. One way to easily generate randomness inside the TFHE is to have many users upload encryptions of random bit vectors and then to xor together users’ contributions and use the result. This approach requires no FHE multiplications, but requires a great deal of communication. We reduce communication by taking advantage of a randomness beacon which outputs public randomness log ^N R 2 F²each election. We would like to interpret the public randomness R as an FHE encryption of a secret randomness R⁰. Unfortunately, we know of no dense FHE scheme where any R can be directly interpreted as a ciphertext. We get around this by treating R as an input to a PRF keyed with k (which we have encrypted under the TFHE). The computation to generate randomness for each election consists of running R⁰ through a block cipher under the TFHE to get a TFHE ciphertext of PRF(k;R⁰). In practice, we could use a low-depth block cipher designed for use in FHE schemes [2, 19, 24, 40] to keep multiplicative depth as low as 5. Moreover, since the output of most block ciphers produces more bits than we will need in each election, the block cipher could be evaluated once every several elections, and elections in between could simply use subsequent chunks of the block cipher output, only xoring them with new randomness beacon outputs instead of running a new block cipher evaluation. We discuss choice of PRF as well as other optimizations and practical considerations in more detail after formalizing our construction.

$$ R\in\mathbb{F}_{2}^{\log N} $$

$$ R^{\prime} $$

Selecting a leader. Once we have generated a TFHE ciphertext containing log N random bits, we can use them to select a leader. First, we will expand the random bits to a vector of length N with only one randomly chosen entry set to 1 and all other entries set to 0. We begin by expanding each random bit b into a vector (b;1 b), so that each vector has one 0 and one 1. Then we pair o the vectors produced, take the outer products between them, and reinterpret the output matrices as longer vectors, resulting in vectors of length 4 which will still have 1 in exactly one index and zero elsewhere. We repeat this process until we are left with a single vector v of length N, which will be set to 1 at exactly one index and zero everywhere else. This requires only logN multiplications and has multiplicative depth log log N, making it extremely ecient 16 (e.g. depth 4 for N = 2 participants). Having computed v under the TFHE, we take the inner product between v and s to get the value s_iwhich determines the leader. This step has a multiplicative depth of 1, 16 bringing the total depth of the entire leader election circuit to as little as 10 for N = 2 participants.

$$ N=2^{16} $$

$$ s_{i} $$

$$ N=2^{16} $$

Defending against duplication and modication attacks. The scheme as described thus far remins vulnerable to two attacks that we call duplication and modication attacks.

A duplication attack compromises uniqueness. Two malicious users who choose the same secret k_ican both legitimately claim to be the winner of the election if k_iis chosen as the winning key. To avoid such an attack, we must ensure that no two users can share the same k_i. We achieve this by splitting each user’s key into private and public components k_iLand k_iR. The private component plays the same role that k_i has played thus far, and the public component is posted publicly to ensure that duplicate keys are detected at registration time. Using a random oracle, the public and private components of each user’s key can be generated from a single master key such that it is hard to nd a master key that results in collisions in the private components of the output. In practice, we only require it to be hard to nd collisions in the private component of the hash function’s output, so we can instantiate such a random oracle for = 128 using one call to the SHA384 hash function, setting the rst 256 bits as the private output and the last 128 bits as the public output.

$$ k_{i} $$

$$ k_{i} $$

$$ k_{i} $$

$$ k_{i L} $$

$$ k_{i} $$

$$ k_{i R} $$

$$ \lambda=128 $$

A modication attack targets unpredictability. A malicious user U_jregisters by uploading a value of s_j that corresponds to the plaintext of s_iplus one for some honest user U_i(and uploading a random value for k_jR). This ciphertext s_jcan easily be obtained because the encryption is homomorphic. Then if U_j\wins" an election, the value k_i+ 1 will be revealed. U_jcannot prove that he has won this election, but note that in the denition of unpredictability, malicious users are not required to prove they have won an election. Later, if U_iwins an election, the malicious user can recognize that that the decrypted value k_imatches the one copied from U_iand predict that U_iis the winner before she reveals herself. We defend against this attack by having each user U_iupload a proof of knowledge_sof the plaintext corresponding to s_iat registration time, thus ruling out attackers that register by modifying another user’s secrets.

$$ U_{j} $$

$$ s_{i} $$

$$ s_{j} $$

$$ k_{j R}) $$

$$ \mathcal{U}_{i} $$

$$ s_{j} $$

$$ U_{j} $$

$$ k_{i}+1 $$

$$ U_{j} $$

$$ k_{i} $$

$$ U_{i} $$

$$ \mathcal{U}_{i} $$

$$ \mathcal {U} _ {i} $$

$$ \pi_{s} $$

$$ s_{i} $$

5.1 Construction

We now formalize the construction of our TFHE-Based SSLE. After describing the construction itself, we discuss some practical considerations related to the instantiation of the protocol and its applicability ot real log N use cases. Our construction makes use of a subroutine v Expand(r) that takes a random vector r 2 F² th ^N th and returns _the r standard basis vector v 2 F₂, that is zero in all positions except a 1 in _the r position. We show how to instantiate Expand with multiplicative depth log logN after presenting the main construction.

$$ v\leftarrow\mathsf{E x p a n d}(r) $$

$$ r^{\mathrm{t h}} $$

$$ \boldsymbol{v}\in\mathbb{F}_{2}^{N} $$

$$ r^{\mathrm{t h}} $$

Construction 16 (TFHE-based SSLE). Our TFHE-based SSLE scheme TSSLE = (TSSLE.Setup, TSSLE.Register, n log N TSSLE.RegisterVerify, TSSLE.Elect₁, TSSLE.Elect₂, TSSLE.Verify) uses a weak PRF f : F₂ F₂! F₂ of multiplicative depth d, a threshold FHE scheme TFHE = (TFHE.Setup, TFHE.Encrypt, TFHE.Eval, TFHE.PartDec, TFHE.FinDEec), and a random oracle H.

$$ f:\mathbb{F}{2}^{\lambda}\times\mathbb{F}{2}^{n}\to\mathbb{F}_{2}^{\log N} $$

{ TSSLE.Setup(1;‘;N): The setup algorithm prepares an access structure A_tfor t (= ‘) out of N secret d+dlog log(N)e+1 sharing. It then executes the setup algorithm (pk, sk₁,...,sk_N) TFHE.Setup(1; 1*;* A_t). Choose random r₁;:::;r^N2 F₂ and let cⁱTFHE.Encrypt(pk, r_i) for i 2 [N]. Compute the encrypted N PRF key rk TFHE.Eval(pk;C_s;c₁;:::;c_N) for circuit C_s: F₂*!* F₂ which computes the function C^s(r₁;:::;r^N) =^iN=1rⁱ= r. Output pp=(pk,rk), sk₁,...,sk^N. Note that because rk is computed using ciphertexts c₁,...,c_N, the generation of the PRF key can be easily distributed.

$$ -\ T{\sf S S L E.S e t u p}(1^{\lambda},\ell,N) $$

$$ \mathrm{A}_{t} $$

$$ t\ (=\ell) $$

$$ (p k, s k _ {1}, \dots , s k _ {N}) \leftarrow T F H E. S e t u p \left(1 ^ {\lambda}, 1 ^ {d + \lceil \log \log (N)} \right. $$

$$ c_{i}\leftarrow,F F H E $$

$$ l(p k,C_{s},c_{1},...,c_{N}) $$

$$ i\in[N] $$

$$ C_{s}:\mathbb{F}{2}^{\lambda\times N},\rightarrow,\mathbb{F}{2}^{\lambda} $$

$$ \mathcal{C}{s}(r{1},...,r_{N}),=,\Sigma_{i=1}^{N}r_{i},=,r $$

$$ c_{1},...,c_{N} $$

R { TSSLE.Register(i, pp, st): Interpret pp as (pk, rk) and sample k_iF₂*. Compute k*_iL;k_iRH(k_i), set s_i;_si=TFHE.Encrypt(pk, k_iL), and append (s_i;k_iR;_si) to st. Output k_iand rt_i, the randomness used to encrypt k_iL.

$$ k_{i}\xleftarrow{\mathtt{R}}\mathbb{F}_{2}^{\lambda} $$

$$ k_{i L},k_{i R}\leftarrow H(k_{i}) $$

$$ s_{i},\pi_{s i}=\ \mathit{T F H E.E n c r y p t}(p k,,k_{i L}) $$

$$ (s_{i},k_{i R},\pi_{s i}) $$

$$ k_{i} $$

$$ r t_{i}, $$

$$ k_{i L} $$

{ TSSLE.RegisterVerify(i, k_i, rt_i, pp, st): Interpret st as a list of values (s₁;k₁_R;_s1);:::;(s_n;k_nR;_sn). Output 1 if TFHE.Verify(pk, s_n,_sn) = 1 and if there are no duplicate values among s₁;:::;s_nand among k₁_R;:::;k_nR.

$$ (s_{1},k_{1R},\pi_{s1}),...,(s_{n},k_{n R},\pi_{s n}) $$

$$ 1;i f;T F H E.V e r i f f/p k,,s_{n},,\pi_{s n}\Big)=1 $$

$$ s_{1},...,s_{n} $$

$$ k_{1R},...,k_{n R} $$

{ TSSLE.Elect₁(pp, st, R, i, sk_i): Begin by interpreting pp as (pk, rk), st as (s₁;k₁_R;_s1);:::;(s_n;k_nR;_sn), log N and R as a vector in F². Compute pⁱTFHE.Eval(pk, C^e, rk, s₁,...,sⁿ) for circuit C^e(described below) with the value of R hard-coded inside of it. Output p_iand l_iTFHE.PartDec(pk, p_i, sk_i). C (r;k₁;:::;k):

$$ (p k,,k) $$

$$ (s_{1},k_{1R},\pi_{s1}),...,(s_{n},k_{n R},\pi_{s n}) $$

$$ \mathbb{E}_{2}^{\mathrm{l o g}\ N} $$

$$ p_{i};\leftarrow;F F H E.E v a I(p k,;C_{e},;r k,;s_{1},...,s_{n}) $$

$$ C_{e} $$

$$ p_{i} $$

$$ l_{i}\leftarrow T F H E.P a r\ D e c(p k,p_{i},s k_{i}) $$

$$ C_{e}(r,k_{1L},...,k_{n L}) $$

1. u f (r;R). Drop all but the rst log n entries of u.

$$ u\gets f(r,R).\ D r o p $$

2. v Expand(u)

$$ v\leftarrow E x p a n d(u) $$

$$ p_{i}=\varSigma_{j=1}^{N}\ v_{j}\cdot k_{j L}\big) $$

4.Output p_i.

$$ p_{i} $$

{ TSSLE.Elect₂(pp, st, l₁,...,l_m, i, k_iL, sk_i, rt_i, p_i): Begin by interpreting pp as (pk, rk) and st as (s₁;k₁_R;_s1) 0 ;:::;(sⁿ;k^nR;^sn). Produce a new list l₁;:::;l^t0of elements from l₁;:::;l^msuch that TFHE.VerifyDec(pk, lⁱ, 0 p_i) = 1. Compute the plaintext l TFHE.FinDec(pk,(l₁;:::;l_t0)). If l 6= k_iLoutput (0*; ?). Otherwise,* 0 remove (s_i;k_iR) from st and output 1*;* = (k_i; rt_i;l₁;:::;l_t0).

$$ l_{1},...,l_{m},i,k_{i L},s k_{i},r t_{i},p_{i}) $$

$$ (s_{1},k_{1R},\pi_{s1}) $$

$$ ,...,(s_{n},k_{n R},\pi_{s n}) $$

$$ l_{1}^{\prime},...,l_{t}^{\prime} $$

$$ l_{1},...,l_{m} $$

$$ p_{i})= $$

$$ I E.F i n D e c(p k,(l_{1}^{\prime},...,l_{t}^{\prime})) $$

$$ l\neq k_{i L} $$

$$ \left(s_{i},k_{i R}\right) $$

$$ 1,\pi=\left(k_{i},r t_{i},l_{1}^{\prime},...,l_{t}^{\prime}\right) $$

{ TSSLE.Verify(i, pp, st, R,; p_i): Begin by interpreting pp as (pk, rk), st as (s₁;k₁_R;_s1);:::;(s_n;k_nR;_sn), and as (k_i; rt_i;l₁;:::;l_t). Next, check TFHE.VerifyDec(pk, l_i, p_i)= 1 for i 2 [t] (output 0 if any check fails), 0 0 0 compute the plaintext l⁰ TFHE.FinDec(pk,(l₁;:::;l^t)), and set k_iL;k_iRH(k_i). If s_i= TFHE.Encrypt(pk, k_iL; rt_i), 0 0 l⁰ = k_iL, and k_iR= k_iR, output 1. Otherwise, output 0.

$$ (s_{1},k_{1R},\pi_{s1}),...,(s_{n},k_{n R},\pi_{s n}) $$

$$ R,\pi;p_{i}, $$

$$ (p k,r k), $$

$$ (k_{i},r t_{i},l_{1},...,l_{t}) $$

$$ l^{\prime}=k_{i L}^{\prime} $$

$$ l^{\prime}\gets T F H E.F i n D e c(p k,(l_{1},...,l_{t})) $$

$$ k _ {i L} ^ {\prime}, k _ {i R} ^ {\prime} \leftarrow H \left(k _ {i}\right). I f s _ {i} = T F H E. E n c r y p t \left(p k, k _ {i L} ^ {\prime}; r t _ {i}\right), $$

$$ k_{i R}^{\prime}=k_{i R} $$

$$ v\in\mathbb{F}_{2}^{n} $$

$$ \boldsymbol{u{}\ in\mathbb{{}F}_{2}^{m} $$

m n m n We implement the function Expand(r) as follows. For u 2 F₂aⁿd v 2 F₂, we use w = u v 2 F₂ to represent the outer product between two vectors u and v, dened as w_ij= u_iv_j. Expand(u):

$$ \boldsymbol=\boldsymbol u\otimes\boldsymbol v\in\mathbb F_{2}^{m\times n} $$

$$ w_{i j}=u_{i}v_{j} $$

$$ \ \mathsf{E x p a n d}(u)\colon $$

juj 1.Let N = 2.

$$ N=2||boldsymbol|u| $$

0 2.Let vector v_i(u_i; 1 u_i) for each value u_i2 F₂ in u. Let *N⁰ N=*2

$$ v_{i}^{0}\leftarrow\left(u_{i},1-u_{i}\right) $$

$$ u_{i}\in\mathbb{F}_{2} $$

$$ N^{\prime}\leftarrow N/2 $$

3.For i from 1 to log logN : (i) (i 1) (i 1)

$$ -;v_{j}^{(i)}\leftarrow v_{j}^{(i-1)}\otimes v_{j+2^{N^{\prime}}/2}^{(i-1)};\mathrm{f o r};j\in[N^{\prime}/2] $$

2i (i) 2 { Reinterpret v_jas a vector ⁱn F₂ formed by concatenating the rows of the matrix.

$$ \mathbb{F}_{2}^{2^{i}} $$

$$ v_{j}^{(i)} $$

$$ -\ N^{\prime}\leftarrow N/2^{2^{i}} $$

$$ v_{0}^{(\log\log N)} $$

(log log N) 4.Output v₀.

5.2 Practical Considerations

Adding users after setup. Our scheme, as written, requires the list of all users of the system to be known at the time TSSLE.Setup runs, but it can easily be extended to allow growth in the number of users after initial setup, so long as t users are available at setup time. In this case, the original t users run TSSLE.Setup with a t out of t access structure. Whenever a new user with identity i arrives, some subset of t existing users generate a new key share sk_ifor user i. Using the TFHE scheme of [11], this share generation be easily accomplished via a simple protocol among the t existing users.

Maintaining security over time. Consider an attacker that waits for users to become inactive in the leader election protocol. Once they withdraw from the system, the attacker purchases their threshold key shares, thereby gradually accruing t key shares. This lets the attacker break the security of the system by decrypting ciphertexts on its own. This attack is outside of the security model of our system because we only claim security against an attacker who controls fewer parties than the threshold t, but should be considered in practice nonetheless. To defend against this risk, the active parties can periodically refresh the TFHE key using a distributed key generation (DKG) protocol. The DKG protocol generates a new FHE key with new key shares every several elections, thereby making old key shares obsolete. All users must stop using the old TFHE public key every time the TFHE key changes, lest an attacker use an old TFHE secret key to learn the secrets corresponding to users who may be elected in future elections. We note that a protocol analogous to the DKG protocol for public key encryption schemes (e.g., [28]) can also be used to refresh the TFHE key of [11].

Unequal election probabilities. This scheme can easily be extended to accommodate a power table T that allocates dierent likelihoods for each user being elected. Users who have higher likelihood of being elected are simply allowed to run TSSLE.Register multiple times corresponding to their allotted likelihood of winning an election. The table T is public, so all users know how many times to allow each other to register. Since in practice, dierences in election probabilities are typically not extreme, the scheme’s eciency does not degrade signicantly by having some users register multiple times. Moreover, extra registrations have no impact on the multiplicative depth of the C_ecircuit, meaning they do not cause ciphertexts to get larger except through a limited number of additional ciphertexts added to the state st.

$$ C_{e} $$

PRF instantiation and optimization. The construction relies on a weak PRF f whose multiplicative depth d forms a signicant portion of the d + dlog log N e + 1 depth parameter to the underlying TFHE construction. As such, it is important to choose a PRF with low multiplicative depth. Fortunately, recent years have seen the development of a number of low-depth block ciphers optimized for the MPC and FHE settings, including MiMC [1], LowMC [2], Kreyvium [19], FLIP [40], and Rasta [24]. For one parameter setting, Rasta has a multiplicative depth of 6, with the tradeo that the block size is 351 bits. The variant of Rasta with more aggressive parameter settings, Agrasta, oers a multiplicative depth of 5 with 127 bit blocks, 15 meaning our construction could be instantiated for N = 2 users with a depth of only 10 multiplications.

$$ N=2^{15} $$

Note that although all the block ciphers we have considered thus far aim to act as strong PRFs, our scheme only requires a weak PRF, so it is possible that a low-depth weak PRF of signicantly lower depth exists. The Dark Matter weak PRF [12] is a promising rst step in this direction, but, despite its depth 2 circuit, it assumes mod operations can be carried out for free, which is not the case for the TFHE construction we use. Computing those mod operations under an FHE would cause the depth to become worse than some of the block ciphers we consider.

Since the computation of a block cipher under the TFHE constitutes the most computationally costly component of our scheme, we propose the following practical optimization to minimize the number of elections in which the PRF actually needs to be evaluated. Note that each election requires only log N bits of randomness inside the TFHE, but the block sizes for the ciphers we use to instantiate the PRF are much larger than typical values of logN. We can take advantage of all the random bits output by each evaluation of the PRF by splitting its output into chunks of size log N and using the next available chunk for each election, only evaluating the PRF again if the supply of random bits has run out. This could reduce the 15 amortized running time of PRF evaluation in the TFHE by 8 or more for realistic group sizes of 2 or less. In order to ensure that it is impossible to compute the leader for a future election ahead of time, the next chunk of PRF-generated randomness could be xored with the plaintext randomness R for each election, ensuring that the exact value of the randomness for each election remains unknown until the randomness has become available.

$$ 2^{15} $$

Reducing on-chain costs. We can reduce the nal storage costs for each election in a blockchain usecase by making a trade-o where we increase communication and computation for each election. In the scheme described above the proof contains a threshold number of partial decryptions, which are stored in perpetuity so that elections can be veried after the fact. Instead of publicly posting and perpetually storing partial decryptions of the nal threshold FHE ciphertext, users can communicate the decryptions to each other o-chain. When the leader reveals herself, she posts a short proof that the partial decryptions communicated during the election successfully decrypted her secret.

This corresponds to a generic transformation of any SSLE scheme with proof that depends polynomially on the number of participants to an SSLE scheme with a shorter proof. The idea is that, given partial intermediate outputs l₁;:::;l_Nof users U₁;:::;U_Nto create, the leader creates a succinct ZK proof (e.g. using ZK-SNARK [32]) that she knows l₁;:::;l_N, an index i, secrets k_i*;*sk_i, and registration token rt_ifor which SSLE.Elect₂(pp, l₁,...,l_N, i, k_i, sk_i, rt_i) outputs 1.

$$ l_{1},\ldots,l_{N} $$

$$ U_{1},\ldots,U_{N} $$

$$ l_{1},\ldots,l_{N} $$

$$ {\mathfrak{r}}_{i} $$

$$ i, $$

$$ k_{i},\mathsf{s k}_{i} $$

$$ \mathsf{S S L E.E I e c t}{2}(\mathsf{p p},;l{1},...,l_{N},;i,;k_{i},;\mathsf{s k}{i},;\mathsf{r t}{i}) $$

5.3 Security

We now state our security theorem for the TFHE-based SSLE construction. A full proof appears in Appendix C.

Theorem 17. Assuming that f is a weak PRF and that TFHE is a secure t out of N threshold FHE that satises the denitions of correctness, compactness, semantic security, robustness, simulation security, and plaintext extractability, then TSSLE is a t-threshold unique, t-threshold unpredictable, and t-threshold fair SSLE scheme in the random oracle model.

6 SSLE from DDH and Shuing

Our nal scheme uses only the simplest of cryptographic tools and exhibits costs satisfactory for deployment in practical systems today. In return, it achieves weaker security properties than the preceding constructions. As a step toward our actual scheme, we will consider a simplication that incurs more communication and computation. Then we will show how to drastically reduce communication and computation costs while maintaining much of the security of the simplied scheme.

A high-communication scheme. In this scheme, the setup operation initializes an empty list l on a public ledger, eectively requiring users to do nothing at all. Registration will involve a user choosing a secret value k_i2 Z_qfor some-bit prime q, uploading a special commitment to k_ito the list, and shuing/re-randomizing all elements of l. Moreover, we require each user who shues l to post a NIZK proof that they have honestly shued l. To elect a leader, the output of a randomness beacon, R, is used to select a row from l. The user to whom the chosen row belongs reveals her commitment as proof of leadership and re-registers with a new secret for future rounds. A user can leave the pool of participants by revealing its row so it can be excluded from future elections.

$$ k_{i}\in\mathbb{Z}_{q} $$

$$ k_{i} $$

$$ q\cdot $$

In order for this scheme to work, we need a commitment scheme for random strings that can be rerandomized such that the new version is unlinkable to any previous version, yet the owner of the secret k_ican identify a re-randomized commitment as her own after it has been shued. We will now describe such a scheme. The scheme xes a group element g 2 G for a group G of prime order q. The commitment

$$ k_{i} $$

$$ g\in\mathbb{G} $$

$$ \mathbb{G} $$

$$ q. $$ r ki r is computed as com(k_i;r) = (g;g) 2 G G for k_i;r 2 Z_q. To reveal, a user outputs k_i, and the ki commitment (u;v) can be veried by checking that v = u. To rerandomize a commitment, anyone can 0 r⁰ r⁰ compute Rerand((u;v);r) = (u;v).

$$ 1!(k_{i},r),=,(\varrho^{r},g^{k_{i}r})\in\ \ \mathbb{G}\times\mathbb{G} $$

$$ k_{i},r;\in;\mathbb{Z}_{q} $$

$$ k_{i}, $$

$$ (u,v) $$

$$ v=u^{k_{i}} $$

$$ \ \mathsf{I}((u,v),r^{\prime})=\bigl(u^{r^{\prime}},v^{r^{\prime}}\bigr) $$

Reducing communication. As described, the high-communication scheme above requires each user who registers to compute a shue over N list items, re-randomize each, and post the new list along with a proof of honest shuing and re-randomization. We can reduce communication costs by shuing new entries into only a part of the list l instead of shuing the entire list each time a new participant joins, resulting in a linear tradeo between communication costs and security. More specically, we assign each row liin l p p to one of N buckets, placing l_iin bucket j if i = j(mod N). As we shall see, this saves costs both by reducing communication for each registration and by removing the need for NIZK proofs. Unfortunately, the performance savings come at a cost in security. While still satisfying uniqueness and fairness, this scheme p 1 only provides-un^predi^ctability, where c is the number of corrupted users. This is the case because the N c adversary must make its guess as to the winner of the election among all the honest users in the chosen p bucket, not the total number of users in that bucket. While we use N buckets as an example, the same idea can easily be instantiated with a larger number of buckets and a correspondingly weaker security guarantee (and vice versa).

$$ l_{i} $$

$$ i=j({\mathsf{m o d}}{\sqrt{N}}) $$

$$ l_{i} $$

$$ \sqrt{N} $$

$$ \frac{1}{\sqrt{N-c}}. $$

$$ \sqrt{N} $$

Improving the communication/security tradeo. We can further improve the unpredictability of our scheme by, instead of deterministically allocating each user to a bucket, assigning new users to a bucket at random when they register. This prevents the adversary from corrupting a disproportionate number of users in one bucket, but introduces the possibility of buckets of dierent sizes. Using the same reasoning as above, this variation has 1*=h*^-unpredictability, where h^ is the minimum number of honest users in a bucket. Using a Cherno bound on the minimum number of honest users in a bucket, we nd that this scheme =4 N¹p gives p-unpredi_ctability (with security parameter). This is a signicant improvement N3=2c N 2 (N c) because the adversary now needs to corrupt O(N) users to guarantee breaking unpredictability instead of p just O( N).

$$ 1/\hat{h} $$

$$ \hat{h} $$

$$ \frac{N^{1/4}}{N^{3/2}{-}c\sqrt{N}{-}\sqrt{2\lambda(N{-}c)}} $$

$$ \lambda) $$

$$ O(N) $$

$$ O({sqrt{N}}) $$

Registration in this improved scheme requires unbiased public randomness to assign users to buckets. This randomness can be generated at the cost of introducing a one-election delay to registration: users publicly declare intent to register, and then the next randomness beacon output to be released determines bucket assignments. If the required amount of randomness gets too large to simultaneously support the election and many registrations, the beacon output can be used as a seed to a PRG instead. The one-election delay after a user declares intent to register is necessary because otherwise a user could wait until the beacon outputs favorable randomness before registering, biasing the bucket assignments.

It may be possible to instantiate our approach with a more involved shuing procedure to get even stronger security guarantees. For example, consider the square shue, analyzed by Hastad [33, 34], where a table is laid out as a square grid and shues are applied to an interleaved pattern of the rows and columns. Using a square shue instead of a bucketing approach would allow for a user’s row to move anywhere in the p table within 2 N shue steps. We leave the analysis of our protocol instantiated with alternative shues for future work.

$$ 2\sqrt{N} $$

Removing NIZKs. We can also remove the need for NIZK proofs that shues were carried out honestly, p saving even more space and time. Since each shue only operates on N entries, users whose entries were p included in a shue can check every shued entry, requiring only N exponentiations, to ensure that their entry still appears after the shue. Proving that a shue was not honest simply requires posting the secret that does not appear after the shue, allowing others to verify that it did appear before the shue and did not appear after. This approach requires several users to verify every new registration but does not signicantly increase demands on users who already need to check if they have won each election. It is of course also possible have users publish NIZKs to prove that they have performed an honest shue at registration time. One or the other approach may be more suitable depending on the application.

$$ \sqrt{N} $$

$$ \sqrt{N} $$

Defending against duplication attacks. Similar to the rst sketch of the tfhe-based scheme in Section 5, the scheme described thus far remains vulnerable to a duplication attack where two malicious users register with the same secret so that they can both be elected leader at the same time. The solution in this scheme is identical to that of the Section 5.

It is also possible for a malicious user to upload a commitment to a rerandomization of another user’s secret without knowing how to open the commitment, in hopes of disrupting fairness by increasing that user’s chances of winning the election. We have each user check new registrations to ensure that a new registrant has not uploaded a rerandomized commitment to that user’s own secret.

The modication attacks described in the previous section do not apply here because users’ secrets are never revealed before a user proves she is the leader.

6.1 Construction

We formalize the variant of our scheme with deterministically allocated buckets. A very similar construction in a model where public randomness is available at registration time would yield the construction with randomly assigned buckets. We will prove the security of both constructions below because the analysis is almost identical.

Construction 18 (Shuing-based SSLE). Our shuing-based SSLE scheme SSSLE = (SSSLE.Setup, SSSLE.Register, SSSLE.RegisterVerify, SSSLE.Elect, SSSLE.Verify) for up to N users with security parameter uses a group G of prime order q where DDH is hard and a random oracle H.

R { SSSLE.Setup(1;‘;N): Create an empty vector l = fg and choose g G*. Output st*= (l;g;N). Input ‘ is unused.

$$ -S S S L E.S e t u p(1^{\lambda},\ell,N) $$

$$ g\xleftarrow{\mathbb{R}}\ \mathbb{G} $$

R { SSSLE.Register(i, pp, st): Interpret st as (l;g;N;k₁_R;:::;k_nR). Sample k_if0*;* 1g and compute k_iL;k_iR R ri ri kiL H(k_i), append k_iRto st, sample r_iZ_q, and append (g;g) to l. If there is any entry in l whose ri ri kiL value isp?, put (g;g) in place of ? pinstead of appending it to l. Next, sample a random permutation on d N e elements and set b jljmod N. Finally, update l such that each l^{j b}= (u^{j b};v^{j b}) is replaced rj rj R by l_{j b(}u;v₎ for r_jZ_q. Output k_i, the new value of st, and p_i, the index where the user’s (j) b (j) b new entry has been moved by.

$$ \ l,g,N,k_{1R},...,k_{n R}\big) $$

$$ k_{i R} $$

$$ k_{i}\xleftarrow{\ {}^{\mathrm R}}{{{{0,1}}}^{\lambda}} $$

$$ H(k_{i}) $$

$$ k_{i L},k_{i R}\leftarrow $$

$$ r_{i}\xleftarrow{\mathbb{R}}{\mathbb{Z}}_{q}; $$

$$ (g^{r_{i}},g^{r_{i}k_{i L}}) $$

$$ (g^{r_{i}},g^{r_{i}k_{i L}}) $$

$$ [\sqrt{N}] $$

$$ \dot{b}\gets|l|m o d\sqrt{N} $$

$$ l_{j\cdot b}=\left(u_{j\cdot b},v_{j\cdot b}\right) $$

$$ l_{j\cdot b}\gets(u_{\mathit{\Pi}(j)\cdot b}^{r_{j}},v_{\mathit{\Pi}(j)\cdot b}^{r_{j}}) $$

$$ r_{j}\xleftarrow{\mathbb{R}}{\mathbb{Z}}_{q} $$

$$ k_{i} $$

$$ p_{i} $$

{ SSSLE.RegisterVerify(i, k_iL, rt_i, pp, st): Interpret rt_ias p_iand st as (l;g;N;k₁_R;:::;k_nR). Then run the following checks: p p

$$ m_{i} $$

$$ p_{i} $$

$$ (l,g,N,k_{1R},...,k_{n R}) $$

$$ -,f f_p i(m o d\sqrt{N})=|l|m d o\sqrt{N} $$

{If pi(mod N) = jljmod N (the newly registered user is in the same bucket as Ui*), check that there is* p kiL exactly one entry l_j= (u_j;v_j) in the bucket (where j is a multiple of p_imod N) such that u_j= v_j, and update p_ij for that entry. p p

$$ l{}{j}=(u{j},v_{j}) $$

$$ j $$

$$ p_{i}m o d\sqrt{N}) $$

$$ u_{j}^{k_{i L}}=v_{j}. $$

$$ p_{i}\gets j $$

{If pimod N 6= jljmod N (the newly registered user is not in the same bucket as Ui*), check that there* p kiL is no entry l_j= (u_j;v_j) in the bucket (where j is a multiple of p_imod N) such that u_j= v_j.

$$ I f p_{i}m o d\sqrt{N}\neq|l|m o d\sqrt{N} $$

$$ \ {cal U}_{i}) $$

$$ l{}{j}=(u{j},v_{j}) $$

$$ j $$

$$ p_{i}m o d\sqrt{N}) $$

$$ u_{j}^{k_{i L}}=v_{j} $$

{Check that there are no duplicates among k₁_R;:::;k_nR.

$$ k_{1R},...,k_{n R}. $$

If the checks above pass, output 1. Otherwise, output 0.

$$ O. $$

{ SSSLE.Elect(pp, st, R, i, k_i, sk_i, rt_i): Interpret st as (l;g;N;k₁_R;:::;k_nR) and rt_ias p_i. Let z be the th number of times ? appears in l, and let z⁰ be the number of times ? appears before the i entry of l. If p_{i z}0 6= R mod (N z), output 0. Otherwise, remove entry l_pifrom l (putting ? in its position) and k_iR from st, set = (i;p_i;k_i), and output 1. Input sk_iis unused.

$$ k_{i},\ s k_{i},\ r t_{i},) $$

$$ (l,g,N,k_{1R},...,k_{n R}) $$

$$ r t_{i} $$

$$ p_{i} $$

$$ z^{\prime} $$

$$ p_{i-z^{\prime}}\neq R $$

$$ (N-z) $$

$$ i^{\mathrm{t h}} $$

$$ l_{p_{i}} $$

$$ \pi=(i,p_{i},k_{i}) $$

$$ k_{i R} $$

{ SSSLE.Verify(i, pp, st, R,): Interpret st as (l;g;N;k₁^R;:::;k^nR), as (i;pⁱ;kⁱ), and l^pias (u;v). Compute 0 0 0 k_iL0 kiL*;k*_iRH(k_i). If p_i= R mod N, u = v, and k_iR= k_iR, output 1*. Otherwise, output 0. If* SSSLE.Verify outputs 1, user U_iis no longer registered.

$$ :(l,g,N,k_{1R},...,k_{n R}) $$

$$ (i,p_{i},k_{i}) $$

$$ k_{i L}^{\prime},k_{i R}^{\prime},\leftarrow,H(k_{i}) $$

$$ p_{i};=;R $$

$$ k_{i R}^{\prime}\ =\ k_{i R}. $$

$$ l _ {p _ {i}} $$

$$ u^{k_{i L}^{\prime}}\ =\ v. $$

$$ (u,v) $$

$$ \ 2_{i} $$

Extensions. This construction can support unequal election probabilities by allowing users with more power to register multiple times. It can also support election of multiple leaders by picking multiple values of R, one for each leader.

6.2 Security

We analyze the security of our shuing-based SSLE construction in Appendix D. We prove the rst theorem below for the scheme with deterministically allocated buckets before describing how to extend the analysis to the construction which assigns buckets randomly with access to public randomness at registration time.

Theorem 19. Assuming that G is a group in which the DDH problem is hard, then for any adversary A, p 1 SSSLE is a unique, fair, and-unpredictable SSLE scheme in the random oracle model. N c

$$ \frac{1}{\sqrt{N-c}} $$

Theorem 20(Informal). Assuming that G is a group in which the DDH problem is hard, then for any adversary A, SSSLE modied to assign buckets randomly at user registration time is a unique, fair, and ^{1=4 N}p p-unpredictable SSLE scheme in the random oracle model. N3=2c N 2 (N c)

$$ \overline {{N ^ {3 / 2} - c \sqrt {N} - \sqrt {2 \lambda (N - c)}}} $$

7 Conclusion

Ecient constructions for SSLE are an important tool in the blockchain space. This paper formally denes SSLE and constructs three SSLE schemes. Our protocols based on obfuscation, FHE, and DDH oer a range of tradeos between security and performance, with the last construction providing levels of security and performance that may satisfy practical requirements. Although our work explores a range of tradeos, it remains an open problem to construct an SSLE scheme that simultaneously provides both optimal security and performance. One promising direction to explore would be to improve the security/performance tradeo of our DDH-based construction by instantiating it with more complex shuing schemes. We leave this as a compelling problem for future work to address.

References

1.Martin R. Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. Mimc: Ecient encryption and cryptographic hashing with minimal multiplicative complexity. In ASIACRYPT, 2016. 2.Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. IACR Cryptology ePrint Archive, 2016. 3.Sarah Azouvi, Patrick McCorry, and Sarah Meiklejohn. Betting on blockchain consensus with fantomette. CoRR, abs/1805.06786, 2018. 4.Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas. Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. In CCS, 2018. 5.Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology-CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, pages 1{18, 2001. 6.Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing ecient protocols. In CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3-5, 1993., pages 62{73, 1993. 7.Iddo Bentov, Ariel Gabizon, and Alex Mizrahi. Cryptocurrencies without proof of work. In Financial Cryptog- raphy, 2016. 8.Iddo Bentov, Ariel Gabizon, and David Zuckerman. Bitcoin beacon. CoRR, abs/1605.04559, 2016. 9.Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Provably secure proofs of stake. IACR Cryptology ePrint Archive, 2016. 10.Dan Boneh, Joseph Bonneau, Benedikt Bunz, and Ben Fisch. Veriable delay functions. In CRYPTO, 2018. 11.Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In CRYPTO, 2018. 12.Dan Boneh, Yuval Ishai, Alain Passelegue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: - new simple PRF candidates and their applications. In TCC, 2018. 13.Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: Denitions and challenges. In TCC, 2011. 14.Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography (version 0.4). 2017. https:// cryptobook.us. 15.Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In ASIACRYPT, 2013. 16.Joseph Bonneau, Jeremy Clark, and Steven Goldfeder. On bitcoin as a public randomness source. IACR Cryp- tology ePrint Archive, 2015.

17.Elette Boyle, Sha Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In PKC, 2014. 18.Benedikt Buenz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh. Zether: Towards privacy in a smart contract world. 2018. 19.Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrede Lepoint, Mara Naya-Plasencia, Pascal Paillier, and Renaud Sirdey. Stream ciphers: A practical solution for ecient homomorphic-ciphertext compression. J. Cryptology, 31(3):885{916, 2018. 20.Ignacio Cascudo and Bernardo David. SCRAPE: scalable randomness attested by public entities. In ACNS, 2017. 21.Jeremy Clark and Urs Hengartner. On the use of nancial data as a random beacon. In 2010 Electronic Voting Technology Workshop / Workshop on Trustworthy Elections, EVT/WOTE ’10, Washington, D.C., USA, August 9-10, 2010, 2010. 22.Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. In EUROCRYPT, 2018. 23.Whiteld Die and Martin E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, 22(6):644{654, 1976. 24.Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel, and Christian Rechberger. Rasta: A cipher with low anddepth and few ands per bit. In CRYPTO), 2018. 25.Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identication and signature problems. In Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986, Proceedings, pages 186{194, 1986. 26.Chaya Ganesh, Claudio Orlandi, and Daniel Tschudi. Proof-of-stake protocols for privacy-aware blockchains. IACR Cryptology ePrint Archive, 2018. 27.Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 40{49, 2013. 28.Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. J. Cryptology, 20(1):51{83, 2007. 29.Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In SOSP, 2017. 30.Oded Goldreich, Sha Goldwasser, and Silvio Micali. On the cryptographic applications of random functions. In Advances in Cryptology, Proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, pages 276{288, 1984. 31.David M. Goldschlag and Stuart G. Stubblebine. Publicly veriable lotteries: Applications of delaying functions. In Financial Cryptography, 1998. 32.Jens Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT, 2016. 33.Johan Hastad. The square lattice shue. Random Struct. Algorithms, 29(4):466{474, 2006. 34.Johan Hastad. The square lattice shue, correction. Random Struct. Algorithms, 48(1):213, 2016. 35.Thomas Kerber, Markulf Kohlweiss, Aggelos Kiayias, and Vassilis Zikas. Ouroboros crypsinous: Privacypreserving proof-of-stake. IACR Cryptology ePrint Archive, 2018. 36.Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In CCS, 2013. 37.Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In CRYPTO, 2017. 38.Protocol Labs. Secret single-leader election (ssle). https://github.com/protocol/research- RFPs/blob/master/RFPs/rfp-6-SSLE.md. 39.Arjen K. Lenstra and Benjamin Wesolowski. A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015. 40.Pierrick Meaux, Anthony Journault, Francois-Xavier Standaert, and Claude Carlet. Towards stream ciphers for ecient FHE with low-noise ciphertexts. In EUROCRYPT, 2016. 41.Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. 42.Adam O’Neill. Denitional issues in functional encryption. IACR Cryptology ePrint Archive, 2010. 43.QuantumMechanic. Topic: proof of stake instead of proof of work, 2011. 44.Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1{34:40, 2009.

45.Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In STOC, 2014. 46.Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris-Kogias, Nicolas Gailly, Linus Gasser, Ismail Kho, Michael J. Fischer, and Bryan Ford. Scalable bias-resistant distributed randomness. In IEEE Symposium on Security and Privacy, 2017.

A Standard Cryptographic Primitives

n n n Denition 21(Pseudorandom Function [30]). Let F : f0*;* 1g f0*;* 1g! f0*;* 1g be an eciently computable, length-preserving keyed function. We say that F is a pseudorandom function (PRF) if for all probabilistic polynomial time distinguishers D,

$$ F:{0,1}^{n}\times{0,1}^{n}\rightarrow{0,1}^{n} $$

$$ |{\sf P r}[D^{F_{k}}(1^{n})=1]-{\sf P r}[D^{f_{n}}(1^{n})=1]| $$

n is negligible where k f 0*;* 1g is chosen uniformly at random and f_nis chosen uniformly at random from the set of functions mapping n-bit strings to n-bit strings. If D is restricted to only querying its oracle on n randomly chosen elements from f0*;* 1g, then we call F a weak PRF.

$$ k\gets{0,1}^{n} $$

$$ f_{n} $$

$$ {0,1}^{n} $$

Denition 22(Public Key Encryption). A public-key encryption scheme PKE consists of algorithms PKE=(PKE.Setup, PKE.Encrypt, PKE.Decrypt) over a message space M, a randomness space R, and a ciphertext space T with the following properties

{ PKE.Setup(1) ! (pk,sk): On input the security parameter, the setup algorithm generates a public key pk and a secret key sk.

$$ -\ P P E.S e t u p(1^{\lambda})\to(p k,s k) $$

{ PKE.Encrypt(pk, m; r) ! ct: On input a public key pk, a message m 2M, and optional randomness r 2R, the encryption algorithm returns a ciphertext ct2T .

$$ Pcdot E E E E n N/t(\ p,k,m;r)\to c\ !cdot $$

$$ m\in{\mathcal{M}} $$

$$ r\in\mathcal R $$

$$ c t\in\mathcal{T} $$

{ PKE.Decrypt(sk, ct) ! m: On input a secret key sk and a ciphertext ct2 T , the decryption algorithm outputs a message m 2M[f?g.

$$ m\in\mathcal{M}\cup{\bot} $$

We say that a PKE scheme is correct if for all keys pk,sk PKE.Setup(1), and for all messages m 2M, we have that Pr[PKE.Decrypt(sk, PKE.Encrypt(pk, m)) = m]= 1*.*

$$ m\in{\mathcal{M}} $$

$$ \leftarrow P K E.S e t u p(1^{\lambda}) $$

$$ (P K E.E n c r p t(p k,m))=m\ j=1 $$

We will require our public key encryption scheme to satisfy the standard notion of CPA security [14].

Denition 23(Commitment Scheme). A commitment scheme COM consists of algorithms COM=(COM.com,COM.verify) over a message space M and randomness space R with the following properties

{ COM.com(m; r) ! c: On input a message m 2M and optionally a commitment randomness r 2R, the algorithm returns a commitment c.

$$ C O M.c o m(m;r)\to c! $$

$$ m\in{\mathcal{M}} $$

$$ r \in \mathcal {R} $$

{ COM.verify(c, m, r) ! 1*=0: On input a commitment c, a message m 2M and randomness r 2R, the* opening algorithm outputs a bit.

$$ m,,r!)\rightarrow1/0 $$

$$ m\in{\mathcal{M}} $$

$$ r \in \mathcal {R} $$

We say that a COM scheme is correct if for all all messages m 2M and all randomness r 2R, we have Pr[COM.verify(COM.com(m, r), m, r)]= 1*.*

$$ m\in{\mathcal{M}} $$

$$ r\in\mathcal{R} $$

$$ P r [ C O M. v e r i f y (C O M. c o m (m, r), m, r) ] = 1 $$

We will require our commitment scheme to satisfy the standard binding and hiding properties [14].

Denition 24(DDH Assumption [14,23]). Let G be a cyclic group of prime order q generated by g 2 G*.* For a given adversary A, we dene two experiments. Experiment b: (for b = 0*;* 1*)*

$$ g\in\mathbb{G} $$

$$ (f{\mathit{o o}}r,,=0,1) $$

{ The challenger computes

$$ \alpha,\beta,\gamma\xleftarrow{\ }\mathbb{Z}{q},u\leftarrow g^{\alpha},v\leftarrow g^{\beta},w{0}\leftarrow g^{\alpha\beta},w_{1}\leftarrow g^{\gamma} $$

and gives the triple (u;v;w^b) to the adversary.

$$ \left(u,v,w_{b}\right) $$

{ The adversary outputs a bit ^b 2f0*;* 1g:

$$ \hat{b}\in{0,1} $$

If W_bis the event that A outputs 1 in Experiment b, we dene A’s advantage in solving the Decisional Die-Hellman problem for G as

$$ W_{b} $$

$$ \mathbb{G} $$

$$ D D\ {\ d a}d{}[\mathcal{A},\mathbb{G}]:=\Big|\ mathsf P P r[W_{0}]-\mathsf P r[W_{1}]\Big|. $$

We say that the Decisional Die-Hellman (DDH) assumption holds for G if for all ecient adversaries A, the quantity DDHadv[A;G] is negligible.

$$ \mathcal{A}_{\circ} $$

B Proof of Theorem 15

Uniqueness. Since each user has a copy of Pe generated during an honest setup phase, it is not possible for an adversary to tamper with Pe in order to change the election result. The circuit P will always pick exactly one index i to receive a commitment to 1 and all others will receive commitments to 0. We will prove the scheme has uniqueness by showing that if an adversary could break uniqueness, it would break the binding property of the commitment scheme COM. Suppose there is an election with a winning proof (i;r_i) and that an adversary can produce another winning proof (j;r_j) 6= (i;r_i). Then since, by construction, there is only one commitment to 1 output by P, one of the two winning proofs is an opening to 1 of a commitment to 0, which breaks the binding property of COM.

$$ \tilde{P} $$

$$ \tilde{P} $$

$$ (i,r_{i}) $$

$$ (j,r_{j})\neq(i,r_{i}) $$

$$ P, $$

Unpredictability. Unpredictability will be proven through a series of hybrids. As is common with constructions based on obfuscation, we only prove selective security for unpredictability and fairness, using the fact that we know the public keys for the challenge election ahead of time to choose the point at which we puncture the PRF. We will use punctured programming [45] to replace the evaluation of the PRF at one point with a random value and then hard-code the corresponding output ciphertexts into the program, replacing the commitment to b with a commitment to 0 and replacing r with a random string.

{ H₀[x]: This hybrid corresponds to the real selective unpredictability experiment UNPRED[A;;‘;N;n;c], except the experiment outputs 0 if the uncorrupted user U_xdoes not win the challenge election.

$$ \mathsf{H}_{0}[x] $$

$$ \mathsf{U N P R E D}[\mathcal{A},\lambda,\ell,N,n,c] $$

{ H₁[x]: This hybrid changes the user which the challenger counts as the \winner" of the election. Instead of the winner being the user that can produce a proof of leadership that will be accepted by Verify, the winner is the user U_ifor which i = w mod n. This hybrid is indistinguishable from the preceding hybrid because these two denitions of \winner" are identical in the construction.

$$ U_{x} $$

$$ \mathsf{H}_{1}[x] $$

$$ \ {cal U}_{i} $$

$$ i=w $$

$$ n $$

{ H₂[x]: In this hybrid, the challenger picks the randomness R to be used in the challenge election in the setup phase before running Setup. The output of this game is identical to the preceding hybrid because R is chosen uniformly at random in both hybrids.

$$ \mathrm {H} _ {2} [ x ] $$

For the following hybrids, let s be the value of (R; pk₀*;:::;* pk_{n 1}) to be used in the challenge election. { H₃[x]: In this hybrid, we modify step 2 of the circuit P where we previously set (w;r;r⁰) F (k;s). We replace this operation with a conditional branch where if s = s, then (w;r;r⁰) (w ;r ;r⁰) for hard-coded values (w ;r ;r⁰) F (k;s). Otherwise (w;r;r⁰) F (k(s);s), where k(s) is the key k punctured at s. This hybrid is indistinguishable from H₂[x] by the security of the indistinguishability obfuscator, as shown in Lemma 25.

$$ s^{*} $$

$$ (R,{\mathsf{p k}}{0},...,{\mathsf{p k}}{n-1}) $$

$$ (w,r,r^{\prime})\gets F(k,s) $$

$$ s=s^{*} $$

$$ \left(w,r,r^{\prime}\right)\leftarrow\left(w^{},r^{},r^{\prime*}\right) $$

$$ (w^{},r^{},r^{\prime*})\gets F(k,s^{*}) $$

$$ (w,r,r^{\prime})\gets F(k(s^{*}),s) $$

$$ k(s^{*}) $$

$$ s^{*} $$

$$ \mathsf{H}_{2}[x] $$

{ H₄[x]: In this hybrid, instead of setting (w ;r ;r⁰) F (k;s) when s = s in the modied second step of P, we set (w ;r ;r⁰) to be uniformly random values. This hybrid is indistinguishable from H₃[x] by the security of the puncturable PRF F, as shown in Lemma 26.

$$ \mathrm {H} _ {4} [ x ] $$

$$ \big(w^{},r^{},r^{\prime*}\big)\gets F\big(k,s^{*}\big) $$

$$ s=s^{*} $$

$$ (w^{},r^{},r^{\prime*}) $$

$$ P, $$

$$ \mathsf{H}_{3}[x] $$

{ H₅[x]: In this hybrid, we modify step 5 of the circuit P so that if s = s it outputs a hard-coded value ct PKE.Enc(pk_i;r;r⁰) and outputs ct PKE.Encrypt(pk_i;r;r⁰) otherwise. This hybrid is indistinguishable from H₄[x] by the security of the indistinguishability obfuscator, as shown in Lemma 27. { H₆[x]: In this hybrid, we further modify step 5 of the circuit P so that if i = x, we replace the value of ct with an encryption of a random string r⁰⁰ 2R. This hybrid is indistinguishable from H₅[x] by the CPA-security of the encryption scheme PKE, as shown in Lemma 28.

$$ \mathsf{H}_{5}[x] $$

$$ s,=,s^{*} $$

$$ \mathsf{c t}\leftarrow\mathsf{P K E.E n c r y p t}(\mathsf{p k}_{i},r;r^{\prime}) $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{6}[x] $$

$$ ^{27} $$

$$ i=x $$

$$ r^{\prime\prime}\in\mathcal{R} $$

$$ \ {tt c c}^{*} $$

$$ \mathsf{H}_{5}[x] $$

{ H₇[x]: In this hybrid, we modify step 4 of the circuit P so that if s = s it outputs a hard-coded value c COM.com(b;r) and outputs c COM.com(b;r) otherwise. The circuit will include hard-coded commitments to b = 0 and b = 1 and output the appropriate one based on the value of b. This hybrid is indistinguishable from H₆[x] by the security of the indistinguishability obfuscator, as shown in Lemma 29. { H₈[x]: In this hybrid, we further modify step 4 of the circuit P so that if i = x, we replace the value of c , with a commitment to 0. This hybrid is indistinguishable from H₇[x] by the hiding property of the commitment scheme COM, as shown in Lemma 30.

$$ s=s^{*} $$

$$ -\mathsf{H}_{7}[x] $$

$$ \mathrm {c} ^ {} \leftarrow \operatorname {C O M}. \operatorname {c o m} \left(b, r ^ {}\right) $$

$$ \mathsf{c}C\gets mathsf{C O M.c o m}(b,r) $$

$$ b=0 $$

$$ b=1 $$

$$ \mathrm {H} _ {6} [ x ] $$

$$

• \mathrm {H} _ {8} [ x ] $$

$$ P $$

$$ i=x. $$

$$ \mathrm {C} ^ {*} $$

$$ {\mathsf{H}}_{7}[x] $$

From H₈[x] the output of Pe when run on the public keys of the participants and the public election randomness R consists only of a commitment to 0 and an encryption of a random string under pk_i, regardless of which uncorrupted user is the winner. Thus the view of the adversary A is independent of the winner of the challenge election, and it cannot do better than guessing the index of the election winner with probability ¹ (if the winner is uncorrupted). n c

$$ \mathsf{H}_{8}[x] $$

$$ \tilde{P} $$

$$ {\mathsf p k}_{i} $$

Since no ecient adversary A can distinguish between each pair of hybrids above with more than negligible advantage, we have that

$$ \frac{1}{n-c} $$

$$ \left| \Pr [ \mathrm {H} _ {8} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] - \Pr [ \mathrm {H} _ {0} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] \right| \leq \operatorname {n e g l} (\lambda). $$

Next, since all our hybrids were parameterized by the condition that uncorrupted user U_xwins the challenge election, we take the union bound over all N users to get

$$ U_{x} $$

$$ \begin{array}{l} \Pr [ \mathrm {U N P R E D} [ \mathcal {A}, \lambda , \ell , N, n, c ] = 1 \mid i \in [ N ] \backslash M ] \ = \frac {1}{n - c} + \Sigma_ {x = 1} ^ {N} \left| \Pr [ \mathrm {H} _ {8} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] - \Pr [ \mathrm {H} _ {0} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] \right| \ \leq \frac {1}{n - c} + \Sigma_ {x = 1} ^ {N} \operatorname {n e g l} (\lambda) \ \leq \frac {1}{n - c} + N \operatorname {n e g l} (\lambda) \ \leq \frac {1}{n - c} + \operatorname {n e g l} (\lambda). \ \end{array} $$

This completes the proof of selective unpredictability. We now state and prove the remaining Lemmas that establish the indistinguishability of hybrids H₀[x] through H₈[x]. For a hybrid experiment H[x] and an adversary A, we use Hx to denote the random variable that represents the output of experiment H[x] with adversary A.

$$ \mathsf{H}_{0}[x] $$

$$ {\mathcal A}, $$

$$ {\mathsf H{}}[x] $$

$$ \mathsf{H}_{8}[x] $$

$$ {\mathsf{H}}[x]{\ (\mathcal{A})} $$

$$ {\mathsf H}[x] $$

Lemma 25. Suppose that O is an indistinguishability obfuscator (Denition 1). Then, for all ecient adversaries A, we have Pr[H₃x = 1] Pr[H₂x = 1] negl():

$$ {\mathcal A}, $$

$$ \mathsf{P r}[\mathsf{H}{3}x=1]-\mathsf{P r}[\mathsf{H}{2}x=1]\leq\mathsf{n e g l}(\lambda). $$

Proof. Let A be an adversary that distinguishes between H₂[x] and H₃[x]. We construct an algorithm B that uses A to break the security of the obfuscator O. Algorithm B simulates the unpredictability challengers of H₂[x] and H₃[x] exactly except for in the invocation of O( ), where the two challengers dier. For this step, it uses the challenger implied by the obfuscation security denition, and sends the obfuscation challenger the circuits P₂ and P₃ used in H₂[x] and H₃[x] respectively. Algorithm B passes on the output of A as its own output. If B receives O(P₂) from its challenger, it provides a perfect simulation of H₂[x], and if it receives O(P₃), it provides a perfect simulation of H₃[x]. Thus B distinguishes between O(P₂) and O(P₃) with the same advantage that A distinguishes between H₂[x] and H₃[x].

$$ \mathsf{H}_{2}[x] $$

$$ \mathsf{H}_{3}[x] $$

$$ \mathsf{H}_{2}[x] $$

$$ \mathcal{O}. $$

$$ \mathsf{H}_{3}[x] $$

$$ \mathcal{O}(\cdot) $$

$$ \mathsf{H}_{2}[x] $$

$$ P_{2} $$

$$ \mathsf{H}_{3}[x] $$

$$ P_{3} $$

$$ \mathcal{B} $$

$$ \mathcal{A} $$

$$ \mathsf{H}_{2}[x] $$

$$ \ {mathcal O(P_{2})} $$

$$ \mathsf{H}_{3}[x] $$

$$ \ {\mathcal{O}}(P_{3}) $$

$$ \ {mathcal O(P_{3})} $$

$$ \mathsf{H}_{2}[x] $$

$$ \mathsf{H}_{3}[x] $$

$$ \mathcal{O}(P_{2}) $$

Lemma 26. Suppose that F is an puncturable PRF (Denition 2). Then, for all ecient adversaries A, we have Pr[H₄x = 1] Pr[H₃x = 1] negl():

$$ {\cal A}, $$

$$ \mathsf{P r}[\mathsf{H}{4}x=1]-\mathsf{P r}[\mathsf{H}{3}x=1]\leq\mathsf{n e g l}(\lambda). $$

Proof. Let A be an adversary that distinguishes between H₃[x] and H₄[x]. We construct an algorithm B that uses A to break the security of punctured PRF F. Algorithm B begins by sending the punctured PRF challenger the value s as the point at which to puncture the PRF. It receives the punctured key k(s) and values (w ;r ;r⁰) in return, where (w ;r ;r⁰) are either the output of F (k;s) or a uniformly random string. Algorithm B completes the setup of H₃[x] and H₄[x] (which are identical outside of the choice of (w ;r ;r⁰)) according to the description of their challengers, using the values of (w ;r ;r⁰) that it received from the punctured PRF challenger. For the rest of the experiment it simulates the (identical) challengers of the two hybrids exactly, and passes on the output of A as its own output.

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{3}[x] $$

$$ s^{*} $$

$$ (w^{},r^{},r^{\prime*}) $$

$$ (w^{},r^{},r^{\prime*}) $$

$$ k(s^{*}) $$

$$ F(k,s^{*}) $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathcal{B} $$

$$ \mathsf{H}_{3}[x] $$

$$ \left(w ^ {}, r ^ {}, r ^ {\prime *}\right) $$

$$ (w^{},r^{},r^{\prime*}) $$

Since A never sees the PRF key k, B provides a perfect simulation of H₃[x] when it receives values (w ;r ;r⁰) F (k;s), and a perfect simulation of H₄[x] when it receives uniformly random values. Thus B wins the punctured PRF security game with the same advantage that A distinguishes between hybrids H₃[x] and H₄[x].

$$ (w^{},r^{},r^{\prime*})\gets F(k,s^{*}) $$

$$ \mathsf{H}_{3}[x] $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{3}[x] $$

$$ \mathsf{H}_{4}[x] $$

Lemma 27. Suppose that O is an indistinguishability obfuscator (Denition 1). Then, for all ecient adversaries A, we have Pr[H₅x = 1] Pr[H₄x = 1] negl():

$$ \mathsf{P r}[\mathsf{H}{5}x=1]-\mathsf{P r}[\mathsf{H}{4}x=1]\leq\mathsf{n e g l}(\lambda). $$

Proof. Let A be an adversary that distinguishes between H₅[x] and H₄[x]. We construct an algorithm B that uses A to break the security of the obfuscator O. B simulates the unpredictability challengers of H₄[x] and H₅[x] exactly except for in the invocation of O( ), where the two challengers dier. For this step, it uses the challenger implied by the obfuscation security denition, and sends the obfuscation challenger the circuits P₄ and P₅ used in H₄[x] and H₅[x] respectively. Algorithm B passes on the output of A as its own output. If B receives O(P₄) from its challenger, it provides a perfect simulation of H₄[x], and if it receives O(P₅), it provides a perfect simulation of H₅[x]. Thus B distinguishes between O(P₄) and O(P₅) with the same advantage that A distinguishes between H₄[x] and H₅[x].

$$ \mathsf{H}_{5}[x] $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathcal{A} $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathrm {H} _ {5} [ x ] $$

$$ \mathcal{O}(\cdot) $$

$$ P_{4} $$

$$ P_{5} $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{5}[x] $$

$$ \mathcal{O}(P_{4}) $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{5}[x] $$

$$ \ {mathcal O(P_{5})} $$

$$ {\mathcal{O}}(P_{4}) $$

$$ {\mathcal{O}}(P_{5}) $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{5}[x] $$

Lemma 28. Suppose that PKE is a CPA-secure public key encryption scheme (Denition 22). Then, for all ecient adversaries A, we have

$$ {\mathcal A}, $$

$$ \sf{P r}[\sf{H}{6}x=1]-\sf{P r}[\sf{H}{5}x=1]\leq n e g l(\lambda). $$

$$ \mathsf{H}_{6}[x] $$

Proof. Let A be an adversary that distinguishes between H₆[x] and H₅[x]. We construct an algorithm B that uses A to break the CPA security of PKE. During setup, B sets pk_ito be the public key received from the R CPA security adversary. Then it samples r⁰⁰ R as well as the uniformly random values (w ;r ;r⁰) before sending the CPA security challenger r and r⁰⁰. It sets ct to be the encryption it gets back. From this point on B behaves identically to the unpredictability challengers in H₅[x] and H₆[x], which behave identically after setting the value of ct in the circuit P. At the end of the experiment, B passes on the output of A as its own output.

$$ \mathsf{H}_{5}[x] $$

$$ {\mathsf p{k}}_{i} $$

$$ r^{\prime\prime}\xleftarrow{\mathbb R} $$

$$ (w^{},r^{},r^{\prime*}) $$

$$ r^{*} $$

$$ r^{\prime\prime} $$

$$ \ {tt c c}^{*} $$

$$ \mathrm {H} _ {5} [ x ] $$

$$ \mathbf{c}^{\dagger}{\bf{}}^{*} $$

$$ \mathsf{H}_{6}[x] $$

$$ \mathcal{A} $$

$$ \mathcal{B} $$

Since the only dierence between hybrids H₅[x] and H₆[x] is in the value of ct , B presents a perfect simulation of the H₅[x] challenger when it receives an encryption of r from the CPA security challenger, and a perfect simulation of the H₆[x] challenger when it receives an encryption of r⁰⁰, so long as A is not given the secret key sk_i. But if A is given sk_i, then the game always outputs 0 anyway, and the adversary can have no advantage. Thus B wins the CPA security game with the same advantage that A distinguishes between H₅[x] and H₆[x].

$$ \mathsf{H}_{5}[x] $$

$$ \mathsf{H}_{6}[x] $$

$$ \mathbf{c}\mathbf{}^{*}} $$

$$ \mathsf{H}_{5}[x] $$

$$ \mathrm {H} _ {6} [ x ] $$

$$ r^{*} $$

$$ r^{\prime\prime} $$

$$ \ {sf s s k}_{i} $$

$$ \mathcal{A} $$

$$ \mathsf{s k}_{i}, $$

$$ \mathsf{H}_{5}[x] $$

$$ \mathsf{H}_{6}[x] $$

Lemma 29. Suppose that O is an indistinguishability obfuscator (Denition 1). Then, for all ecient adversaries A, we have Pr[H₇x = 1] Pr[H₆x = 1] negl():

$$ \mathsf{P r}[\mathsf{H}{7}x=1]-\mathsf{P r}[\mathsf{H}{6}x=1]\leq\mathsf{n e g l}(\lambda). $$

Proof. This proof is analogous to the proof of Lemma 27, so we omit a full proof.

Lemma 30. Suppose that COM is a hiding commitment scheme (Denition 23). Then, for all ecient adversaries A, we have Pr[H₈x = 1] Pr[H₇x = 1] negl():

$$ {\mathcal A}. $$

$$ \mathsf{P r}[\mathsf{H}{8}x=1]-\mathsf{P r}[\mathsf{H}{7}x=1]\leq\mathsf{n e g l}(\lambda). $$

Proof. This proof is analogous to the proof of Lemma 28 except that we invoke the indistinguishability denition associated with the hiding property of the commitment scheme COM instead of that of the CPAsecurity of encryption. We thus omit a full proof.

Fairness. The proof of selective fairness is similar to the rst part of the proof of unpredictability where we puncture the PRF F at the point where it will be called in the challenge election, replacing its output with a random value.

$$ F $$

{ H₀: This hybrid corresponds to the real selective fairness experiment FAIR[A;;‘;N;c;n].

$$ \mathsf{F A I R}[\mathcal{A},\lambda,\ell,N,c,n] $$

$$ \mathbb{H}_{0}. $$

{ H₁: In this hybrid, the challenger picks the randomness R to be used in the challenge election in the setup phase before running Setup. The output of this game is identical to the preceding hybrid because R is chosen uniformly at random in both hybrids.

$$ \ {sf H}_{1:} $$

For the following hybrids, let s be the value of (R; pk₀*;:::;* pk_{n 1}) to be used in the challenge election. { H₂: In this hybrid, we modify step 2 of the circuit P where we previously set (w;r;r⁰) F (k;s). We replace this operation with a conditional branch where if s = s, then (w;r;r⁰) (w ;r ;r⁰) for hard-coded values (w ;r ;r⁰) F (k;s). Otherwise (w;r;r⁰) F (k(s);s), where k(s) is the key k punctured at s. This hybrid is indistinguishable from H₁ by the security of the indistinguishability obfuscator via a proof identical to that of Lemma 25.

$$ s^{*} $$

$$ (R,{\mathsf{p k}}{0},...,{\mathsf{p k}}{n-1}) $$

$$ \ {mathfrak H_{{}22}}. $$

$$ \left(,,,,r r{r'}),\leftarrow,F(,r\ \ ),\right. $$

$$ s=s^{*} $$

$$ \left(w,r,r^{\prime}\right)\gets\left(w^{},r^{},r^{\prime*}\right) $$

$$ (w^{},r^{},r^{\prime*})\gets F(k,s^{*}) $$

$$ (w,r,r^{\prime})\gets F(k(s^{*}),s) $$

$$ k(s^{*}) $$

$$ s^{*} $$

$$ \ _11 $$

{ H₃: In this hybrid, instead of setting (w ;r ;r⁰) F (k;s) when s = s in the modied second step of P, we set (w ;r ;r⁰) to be uniformly random values. This hybrid is indistinguishable from H₂ by the security of the puncturable PRF F via a proof identical to that of Lemma 26.

$$ (w^{},r^{},r^{\prime*})\gets F(k,s^{*}) $$

$$ s=s^{*} $$

$$ P, $$

$$ (w^{},r^{},r^{\prime*}) $$

$$ \ _22 $$

Once the outputs of F are replaced by truly random values, it is clear that the winner of the challenge election is chosen uniformly at random from among all participants in the election. Since each user has a copy of Pe generated during an honest setup phase, it is not possible for an adversary to tamper with Pe in order to change the election result. Thus the probability that any participant wins the election is at most ¹ , and since the adversary controls c participants, it can produce proof that it controls the winner with n c probability at most. If the adversary does not control the winner, then one of the uncorrupted users can n produce a proof that it is the winner. Since H₃ can only be distinguished from the real fairness game with negligible probability, this completes the proof.

$$ \tilde{P} $$

$$ \frac{1}{n} $$

$$ \frac{c}{n} $$

$$ \ !!{\sf H}_{3} $$

C Proof of Theorem 17

Uniqueness. We will rst prove uniqueness. Since H is a random function with a large enough output 0 0 0 length, no ecient adversary can nd values k^L;k^RH(k), k^L;k^RH(k⁰), such that k^L= k^Lunless ⁰ k = k⁰. Colliding values of k_L= k_Larising from the case where k = k⁰ are ruled out because they would 0 0 result in k_R= k_R, causing the RegisterVerify checks to fail when k_Rwas added to st.

$$ k_{L},k_{R}\gets H(k),,k_{L}^{\prime},k_{R}^{\prime}\gets H(k^{\prime}) $$

$$ k_{L}=k_{L}^{\prime} $$

$$ k=k^{\prime} $$

$$ k_{L}=k_{L}^{\prime} $$

$$ k=k^{\prime} $$

$$ k_{R}=k_{R}^{\prime} $$

$$ k_{R}^{\prime} $$

The process of expanding the logN random bits into N bits always results in a vector v that is zero at all but one point, so the dot product we compute between v and the user secrets s_iwill select exactly one value from the set of user secrets to choose the leader. Decryption of s_iwill always succeed so long as there are t uncorrupted users to send valid values of l_i, and by the robustness of the encryption scheme, there will 0 0 be only one possible decryption of the chosen sⁱvalue. But if there are no values of k^L;k^Lsuch that k^L= k^L encrypted among s₁;:::;s_n, then each time an element of the list is chosen to select an election winner, there is exactly one (k_L;k_R) pair in st, and therefore exactly one value of k among all the registered users, that can successfully be used to prove leadership.

$$ s_{i} $$

$$ s_{i} $$

$$ l_{i}, $$

$$ k_{L}=k_{L}^{\prime} $$

$$ k_{L},k_{L}^{\prime} $$

$$ s_{i} $$

$$ s_{1},...,s_{n} $$

$$ (k_{L},k_{R}) $$

$$ s{\bf t}, $$

Unpredictability. Intuitively, TSSLE provides unpredictability because the threshold FHE ensures that no coalition of fewer than t malicious users can reveal the inputs or internal wire values of the circuit C_e. We will prove unpredictability through a series of hybrids. Suppose the adversary A makes at most Q_R= poly() requests for an uncorrupted user to register for an election.

$$ C_{e} $$

$$ \mathcal{Q}_{R}=\mathsf{p o l y}(\lambda) $$

{ H₀[x]: The real unpredictability game UNPRED[A;;‘;N;n;c] except the experiment outputs 0 if the th challenge election has a winner, but the uncorrupted user U_j(^the x uncorrupted user to register) does not win.

$$ \mathsf{H}_{0}[x] $$

$$ \mathcal{A},\lambda,\ell,N,n,c] $$

$$ {_{}{cal U}}, $$

{ H₁[x]: This hybrid changes the user which the challenger counts as the \winner" of the election. Instead of the winner being the user that can produce a proof of leadership that will be accepted by Verify, the winner is the user U_ifor which v_i= 1 when evaluating C_e. This hybrid is indistinguishable from the preceding hybrid because these two denitions of \winner" are identical in the construction.

$$ x^{\mathrm{t h}} $$

$$ \mathsf{H}_{1}[x] $$

$$ \mathcal{U}_{i} $$

$$ v_{i}=1 $$

$$ C_{e} $$

{ H₂[x]: In this hybrid, the experiment outputs 0 if the adversary ever queries the random oracle on the secret k_iof an uncorrupted user who participates in the challenge election. It is otherwise identical to H₁[x].

$$ \mathrm {H} _ {2} [ x ] $$

$$ k_{i} $$

$$ \mathsf{H}_{1}[x] $$

Any values of k_iL;k_iRbelonging to an uncorrupted user U_iappear independently random to the adversary until k_iis revealed to prove that U_ihas been elected leader, unless the adversary queries H at k_i. Since the view of the adversary is independent of kⁱuntil it is revealed, it queries H at kⁱwith probability q at most if it makes q queries. Taking a union bound over the secrets of all uncorrupted users, the 2 probability that the adversary queries H at a point corresponding to any uncorrupted user’s secret is at ^Nq most negl(). As such, no PPT adversary could distinguish between the previous hybrid and this 2 one.

$$ k_{i L},k_{i R} $$

$$ k_{i} $$

$$ \ 7!{}_{i} $$

$$ H $$

$$ k_{i} $$

$$ k_{i} $$

$$ k_{i} $$

$$ \frac{q}{2^{\lambda}} $$

$$ \textstyle\frac{N q}{2^{\lambda}}\leq\mathsf{n e g l}(\lambda) $$

{ H₃[x]: In this hybrid, the challenger runs the extractor E provided by the plaintext extractability of the TFHE scheme to extract the values of k_iLfor each user as well as their contributions to rk, aborting if extraction fails. This is indistinguishable from the previous hybrid by the plaintext extractability of the TFHE scheme.

$$ \mathsf{}cdot mathsf H{}_{3}[x]\colon $$

$$ \mathcal{E} $$

$$ k_{i L} $$

$$ r\mathsf k{,} $$

{ H₄[x]: In this hybrid, the challenger replaces its invocations of TFHE.Setup with the simulator S₁ and invocations of TFHE.Eval(pk, C_e, rk, s₁,..., s_n) and TFHE.PartDec(pk, p_i, sk_i) with the simulator S₂(C_e; frk*;s₁;:::;s*_ng; C_e(r;k₁_L;:::;k_nL);M) (using the plaintext and randomness values obtained from the extractor to send the plaintexts and randomnesses required by the real and ideal experiments and to evaluate C_e). These simulators are guaranteed to exist and be indistinguishable from the functions they replace by the simulation security of TFHE.

$$ \mathrm {H} _ {4} [ x ] $$

$$ \mathcal{S}_{1} $$

$$ C_{e}, $$

$$ \mathsf{T F H E.P a r t D e c}(\mathsf{p k},,p_{i},,\mathsf{s k}_{i}) $$

$$ s_{1},...,s_{n}) $$

$$ \mathcal{S}{2}(C{e} $$

$$ {\mathsf{r k},s_{1},...,s_{n}},\ C_{e}(r,k_{1L},...,k_{n L}),M) $$

$$ C_{e}) $$

{ H₅[x]: In this hybrid, the challenger replaces its invocations of TFHE.Encrypt(pk, k_{j L}) during registration R of the winner of the challenge election with invocations of TFHE.Encrypt(pk, r⁰), where r⁰ F₂ is a freshly chosen random value. The input to the simulator is unchanged from H₄[x] { only the values s^j;^sreect this change. This hybrid is indistinguishable from the preceding hybrid by the semantic j security of TFHE.

$$ k_{j^{*}L}) $$

$$ \mathrm {H} _ {5} [ x ] $$

$$ r^{\prime}\big) $$

$$ r^{\prime}\xleftarrow{\mathbb{R}}\ \mathbb{F}_{2}^{\lambda} $$

$$ \mathrm {H} _ {4} [ x ] - $$

$$ s_{j^{}},\pi_{s_{i}^{}} $$

We could use an adversary A that distinguishes between H₄[x] and H₅[x] to construct an adversary B that wins the semantic security game. B acts as the challenger in the unpredictability game while also playing as the adversary in the semantic security game. B sends the semantic security challenger the plaintexts r⁰ and k_{j L}as potential challenges, and gets back an encryption ct and a proof_s. It reproduces the unpredictability game of the preceding hybrid exactly except it appends ct and_sto st at the end of registration. At the end of the unpredictability game, B passes on A’s output as its own output for the semantic security game. The semantic security challenger’s choice of challenge determines which of the two successive hybrids A interacts with, so B wins the semantic security game with exactly the same advantage that A distinguishes between the hybrids.

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{5}[x] $$

$$ r^{\prime} $$

$$ k_{j^{*}L} $$

$$ \pi_{s} $$

$$ \pi_{s} $$

$$ \mathcal {A} ^ {\prime} \mathrm {s} $$

From H₅[x], the output of the circuit C_ein the challenge election will be a uniformly random value dierent from any registered user’s registration secret. Thus the view of the adversary A is independent of the winner of the challenge election, and it cannot do better than guessing the index of the election winner 1 with probability (if the winner is uncorrupted). n c

$$ \mathsf{H}_{5}[x] $$

$$ C_{e} $$

Since no ecient adversary A can distinguish between each pair of hybrids above with more than negligible advantage, we have that

$$ \frac{1}{n-c} $$

$$ \Big|\mathsf{P r}[\mathsf{H}{5}x=1\mid i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}{0}x=1\mid i\in[N]\setminus M]\Big|\leq\mathsf{n e g l}(\lambda). $$ th Next, since all our hybrids were parameterized by the condition that U_j, ^the x uncorrupted user to register, wins the challenge election, we take the union bound over all Q_Rregistrations to get

$$ \ _{j^{*}} $$

$$ x^{\mathrm{t h}} $$

$$ \ {underline{{{Q}}}}_{R} $$

$$ \begin{array}{l} \Pr [ \mathrm {U N P R E D} [ \mathcal {A}, \lambda , \ell , N, n, c ] = 1 \mid i \in [ N ] \backslash M ] \ = \frac {1}{n - c} + \Sigma_ {x = 1} ^ {\mathcal {Q} _ {R}} \left| \Pr [ \mathrm {H} _ {5} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] - \Pr [ \mathrm {H} _ {0} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] \right| \ \leq \frac {1}{n - c} + \Sigma_ {x = 1} ^ {\mathcal {Q} _ {R}} \operatorname {n e g l} (\lambda) \ \leq \frac {1}{n - c} + \mathcal {Q} _ {R} \operatorname {n e g l} (\lambda). \ \end{array} $$

This completes the proof of unpredictability since Q_Rnegl() is still negligible in.

$$ \mathcal{Q}_{R}\mathsf{n e g l}(\lambda) $$

$$ \lambda $$

Fairness. Intuitively, TSSLE provides fairness because generating the PRF key inside the threshold FHE ensures that no coalition of fewer than t malicious users can see the key. Thus the choice of leader should appear random to any set of fewer than t malicious users. We will prove fairness through a series of hybrids.

{ H₀: The real fairness game FAIR[A;;‘;N;c;n].

$$ \mathbf{H}}_{0}^{\cdot} $$

$$ \mathsf{F A l R}[\mathcal{A},\lambda,\ell,N,c,n] $$

{ H₁: Same as H₀, except the experiment outputs 0 if the adversary ever queries the random oracle on the secret k_iof an uncorrupted user who participates in the challenge election.

$$ \ _11. $$

$$ \mathsf{H}_{0} $$

$$ k_{i} $$

$$ k_{i L},k_{i R} $$

$$ \mathcal{U}_{i} $$

$$ H $$

$$ \mathcal {U} _ {i} $$

$$ k_{i} $$

$$ k_{i}. $$

$$ k_{i} $$

$$ k_{i} $$

$$ \frac{q}{2^\lambda} $$

$$ \frac{N q}{2^{\lambda}}\leq\mathsf{n e g l}(\lambda) $$

{ H₂: Same as H₁, except the challenger runs the extractor E provided by the plaintext extractability of the TFHE scheme to extract the values of k_iLfor each user as well as their contributions to rk, aborting if extraction fails. This is indistinguishable from the previous hybrid by the plaintext extractability of the TFHE scheme.

$$ \ {mathfrak H_{{}22}}. $$

$$ \mathcal{E} $$

$$ k_{i L} $$

{ H₃: Same as H₂, except the challenger replaces its invocations of TFHE.Setup with the simulator S₁ and invocations of TFHE.Eval(pk, C_e, rk, s₁,..., s_n) and TFHE.PartDec(pk, p_i, sk_i) with the simulator S₂(C_e; frk*;s₁;:::;s*_ng; C_e(r;k₁_L;:::;k_nL);M) (using the plaintext and randomness values obtained from the extractor to send the plaintexts and randomnesses required by the real and ideal experiments and to evaluate C_e). These simulators are guaranteed to exist and be indistinguishable from the functions they replace by the simulation security of TFHE.

$$ \ {mathsf H_{{}33}}. $$

$$ \ \ {\mathsf H{}}_{2}.. $$

$$ \mathcal{S}_{1} $$

$$ C_{e},;\mathsf{r k},;s_{1},...,;s_{n}) $$

$$ \mathsf{T F H E.P a r t D e c}(\mathsf{p k},:p_{i},:\mathsf{s k}_{i}) $$

$$ \mathcal{S}{2}(C{e},:{\mathsf{r k},s_{1},...,s_{n}},:C_{e}(r,k_{1L},...,k_{n L}),M) $$

$$ \ {cal C C}) $$

{ H₄: Same as H₃, except the challenger outputs 0 if the adversary outputs a proof_jcontaining values l₁;:::;l_tsuch that TFHE.VerifyDec(pk, l_i;p_i)= 1 for all i 2 [t] but TFHE.FinDec(pk, p_i; fl₁;:::;l_tg) is not equal to the value given to S₂ as the simulated output of the circuit C_e. Such a set l₁;:::;l_tcould be used to win the robustness game because it is a second set of veried partial decryptions on which TFHE.FinDec gives a dierent nal decryption of p_ithan it did on the simulated partial decryptions. Thus this hybrid is indistinguishable from the preceding hybrid by the robustness of TFHE.

$$ \mathsf{H}_{4}. $$

$$ \pi_{j} $$

$$ l_{i},p_{i})=1 $$

$$ l_{1},...,l_{t} $$

$$ i;\in;[t] $$

$$ p_{i},{l_{1},...,l_{t}}\ ) $$

$$ \ mathcal\ S_{2} $$

$$ C_{e} $$

$$ l_{1},...,l_{t} $$

$$ p_{i} $$

$$ \mathsf{H}_{5:} $$

{ H₅: Same as H₄, except the challenger replaces the input C_e(r;k₁_L;:::;k_nL) given to S₂ with an evaluation of C_e0(r;k₁_L;:::;k_nL) where the evaluation of the PRF f(rk*;*) has rk replaced with a hard-coded random value r corresponding to the decryption of rk. This function computes an output identical to C_e, so the hybrid is identical to the preceding one.

$$ C_{e}(r,k_{1L},...,k_{n L}) $$

$$ C_{e}^{\prime}(r,k_{1L},...,k_{n L}) $$

$$ \ {\mathcal{S}}_{2} $$

$$ f(\mathsf{r k},\cdot) $$

$$ r^{*} $$

$$ C_{e}. $$

{ H₆: Same as H₅, except the challenger replaces the ciphertext rk with a ciphertext rk’ = TFHE.Encrypt(pk, 0). This hybrid is indistinguishable from the preceding hybrid by the semantic security of TFHE.

$$ H_{5} $$

$$ \mathsf{H}_{6}\ `cdot $$

$$ r k ^ {\prime} = T F H E $$

We could use an adversary A that distinguishes between H₅ and H₆ to construct an adversary B that wins the semantic security game. B acts as the challenger in the unpredictability game while also playing as the adversary in the semantic security game. B sends the semantic security challenger the plaintexts 0 and r (the plaintext corresponding to rk) as potential challenges, and gets back an encryption ct and

$$ \ _\mathrm{H} $$

$$ \ _66 $$

$$ \mathcal{B} $$ a proof_s. It reproduces the unpredictability game of the preceding hybrid exactly except it uses ct in place of rk. At the end of the unpredictability game, B passes on A’s output as its own output for the semantic security game. The semantic security challenger’s choice of challenge determines which of the two successive hybrids A interacts with, so B wins the semantic security game with exactly the same advantage that A distinguishes between the hybrids.

$$ \pi_{s} $$

$$ A^{\prime}\mathrm{s} $$

{ H₇: Same as H₆, except the challenger replaces the input C_e0(r;k₁_L;:::;k_nL) given to S₂ with an evaluation of C_e00(r;k₁_L;:::;k_nL) where the evaluation of the PRF f (r ;) is replaced with invocations of a random function F( ). This is indistinguishable from the previous hybrid by the weak PRF security of f.

$$ \ {\ {\sf H}_{7}} $$

$$ C_{e}^{\prime}(r,k_{1L},...,k_{n L}) $$

$$ \mathsf{H}_{6} $$

$$ \ mathcal\ S_{2} $$

$$ C_{e}^{\prime\prime}(r,k_{1L},...,k_{n L}) $$

$$ f(r^{*},\cdot) $$

$$ F(\cdot) $$

We could use an adversary A that distinguishes between the outputs of H₆ and H₇ to construct another adversary B that wins the weak PRF security game. B acts as the challenger in the unpredictability game while also playing as the adversary in the weak PRF security game. It reproduces the unpredictability game of H₆ exactly except that in the description and evaluation of circuit that it gives to S, any query to f (r ;) is forwarded to the PRF challenger and has its output replaced with the PRF challenger’s output. At the end of the unpredictability game, B passes on A’s output as its own output for the PRF security game.

$$ f. $$

$$ \ _66 $$

$$ #_{6} $$

$$ \ , $$

$$ f(r^{*},\cdot) $$

Since A never sees r (it is chosen randomly by the challenger and only used in its input to S₂), the evaluation of f (r ;) is on a key unknown to it. f is only ever evaluated on R, a public random value. As such, if B is interacting with a PRF f, then it provides A with exactly H₆. On the other hand, if B is interacting with a random function F, then A sees exactly H₇. If A distinguishes between H₆ and H₇ with non-negligible advantage, then B distinguishes between the weak PRF f and a random function with non-negligible advantage, breaking the weak PRF security of f.

$$ r^{*} $$

$$ \ {\mathcal{S}}_{2}) $$

$$ f(r^{*},\cdot) $$

$$ f, $$

$$ \mathsf{H}_{6} $$

$$ \ _66 $$

$$ f. $$

From hybrid H₇, A wins the FAIR game with probability c=n + negl() and therefore has negligible advantage. Since the vector u is chosen by a random function F( ), the non-zero index of the vector v output by Expand(u) is chosen uniformly at random as well. This is because for each possible output of F( ), Expand returns a dierent value of v. Thus the value s_iselected by v is chosen uniformly at random too, and the value of k_iLrevealed (of which there can only be one or else the challenger aborts) belongs to a random user, and that random user is the winner of the election. Since the winner is chosen uniformly at random among the users, the adversary can only produce the proof needed to win the fairness game if the winner is corrupted (probability c=n) or if it guesses the correct proof (with probability negl()). If the adversary does not control the winner, then one of the uncorrupted users can produce a proof that it is the winner.

$$ \ _{7},{\mathcal{A}} $$

$$ c/n+\mathsf{n e g l}(\lambda) $$

$$ F(\cdot) $$

$$ \ \ v, $$

$$ F(\cdot) $$

$$ s_{i} $$

$$ k_{i L} $$

$$ c/n) $$

Since the adversary in H₇ wins the fairness game with negligible advantage, the advantage of the adversary in H₀ is the sum of its advantage in distinguishing between each successive pair of hybrids plus negl(), each of which is itself negligible. Thus the adversary wins the original fairness game with probability c=n+ negl(), completing the proof.

$$ \mathsf{H}_{0} $$

$$ \mathsf{n e g}|(\lambda) $$

$$ c mathord n+{sf}e e g(\lambda) $$

D Proofs of Theorems 19 and 20

Uniqueness. Since H is a random function with a large enough output length, no ecient adversary can nd 0 0 0 0 values k^L;k^RH(k), k^L;k^RH(k⁰), such that k^L= k^Lunless k = k⁰. Colliding values of k^L= k^Larising 0 from the case where k = k⁰ are ruled out because they would result in k_R= k_R, causing the RegisterVerify 0 checks to fail when k_Rwas added to st. But if there are no duplicate values of k_Lin l corresponding to dierent values of k_R, then each time an element of l is chosen to select an election winner, there is exactly one k_Rin st, and therefore exactly one corresponding k, that can successfully be used to prove leadership.

$$ k_{L}=k_{L}^{\prime} $$

$$ k_{L},k_{R}\gets H(k),k_{L}^{\prime},k_{R}^{\prime}\gets H(k^{\prime}) $$

$$ k_{L}=k_{L}^{\prime} $$

$$ k=k^{\prime} $$

$$ k=k^{\prime} $$

$$ k_{R}=k_{R}^{\prime} $$

$$ k_{R}^{\prime} $$

$$ k_{L} $$

$$ k_{R} $$

$$ k_{R}. $$

Fairness. Fairness follows directly from the construction, as exactly one entry is selected uniformly at random to be the leader in each election. The checks done in RegisterVerify ensure that each entry in l belonging to an uncorrupted user corresponds to a dierent secret k_iLand therefore to a dierent user. Thus any given 1 uncorrupted user has probability of beiⁿg elected, so the adversary, who controls c users, controls the n c winner of the election with probability at most. If the adversary does not control the winner, then one of n the uncorrupted users can produce a proof that it is the winner.

$$ k_{i L} $$

$$ \frac{1}{n} $$

$$ \frac{c}{n} $$

Unpredictability. We will prove unpredictability through a series of hybrids. Suppose there are at most Q_R= poly() registrations of uncorrupted users in the elections phase of the security experiment.

$$ \mathcal{Q}_{R}=\mathsf{p o l y}(\lambda) $$

{ H₀[x]: The real unpredictability game UNPRED[A;;‘;N;n;c] with an additional abort condition dened as follows. Let b be the bucket from which the winner of the challenge election is chosen. The experiment th aborts if ^the x registration is not the last registration of an uncorrupted user into bucket b before the challenge election. Note that, so long as there is a single uncorrupted user in bucket b during the challenge election, such a registration will always exist, and otherwise the winner of the challenge election will not be an uncorrupted user.

$$ \mathsf{H}_{0}[x] $$

$$ \mathsf{U N P R E D}[\mathcal{A},\lambda,\ell,N,n,c] $$

$$ b^{*} $$

$$ b^{*} $$

$$ x^{\mathrm{t h}} $$

$$ b^{*} $$

{ H₁[x]: This hybrid changes the user which the challenger counts as the \winner" of the election. Instead of the winner being the user that can produce a proof of leadership that will be accepted by Verify, the kiL winner is the user U_ifor which u = v, where (u;v) 2 l is the entry chosen by the election randomness R. This hybrid is indistinguishable from the preceding hybrid because these two denitions of \winner" are identical in the construction.

$$ \mathsf{H}_{1}[x] $$

$$ \mathcal{U}_{i} $$

$$ u^{k_{i L}}=v $$

$$ (u,v)\in l $$

{ H₂[x]: In this hybrid, the experiment outputs 0 if the adversary ever queries the random oracle on the secret k_iof an uncorrupted user who participates in the challenge election.

$$ \mathsf{H}_{2}[x] $$

$$ k_{i} $$

$$ k_{i L},k_{i R} $$

$$ k_{i} $$

$$ H $$

$$ k_{i} $$

$$ k_{i} $$

$$ k_{i} $$

$$ \frac{q}{2\ lambda} $$

$$ \textstyle\frac{N q}{2^{\lambda}}\leq\mathsf{n e g l}(\lambda) $$

$$ \ _\mathrm{H} $$

$$ \mathsf{H}_{2} $$

{ H₃[x]: In this hybrid, the challenger chooses the value of R to be used in the challenge election during the setup phase instead of during the challenge phase, so the challenger knows at setup time which bucket b the leader will be chosen from in the challenge election. This hybrid is indistinguishable from H₂ because it makes no changes to the distribution of messages sent by the challenger. That is, it is identical to H₂ in terms of the adversary’s view.

$$ \mathrm {H} _ {3} [ x ] $$

$$ b^{*} $$

$$ \mathrm {H} _ {2} $$

$$ \ !!!{\sf H}_{2} $$

th { H₄[x]: In this hybrid, we change the behavior of the challenger in ^the x registration. During this ki0 L rj ki0 Lrj registration, instead of replacing each l_{j b}= (uj b;v_{j b}) = (u_{j b};u) with l_{j b}(u;u) _{j b (j) b} (^j) b ^R for r_jZ_q, for entries corresponding to the secrets k_i0_Lof uncorrupted users U_i0, it sets l_{j b} rjki0Lr^j R (u;u), fo^r a new random key k 0 Zq, which from then on plays the role of ki0Lin (j) b (j) b i L determining whether the user U_i0 has won an election.

$$ {mathsf\mathsf H{}}_{4}[x]: $$

$$ x^{\mathrm{t h}} $$

$$ l_{j\cdot b^{}}=\left(u_{j\cdot b^{}},v_{j\cdot b^{}}\right)=\left(u_{j\cdot b^{}},u_{j\cdot b^{*}}^{k_{i^{\prime}L}}\right) $$

$$ l_{j\cdot b^{}}\leftarrow(u_{\varPi(j)\cdot b^{}}^{r_{j}},u_{\varPi(j)\cdot b^{*}}^{k_{i^{\prime}L}r_{j}}) $$

$$ r_{j}\ xleftarrowleftarrow{!}\mathbb{{}Z}_{q} $$

$$ k_{i^{\prime}L} $$

$$ U_{i^{\prime}} $$

$$ l_{j\cdot b^{*}}\gets $$

$$ (u_{\varPi(j)\cdot b^{}}^{r_{j}},u_{\varPi(j)\cdot b^{}}^{k_{i^{\prime}L}^{*}r_{j}}) $$

$$ k_{i^{\prime}L}^{*}\xleftarrow{R}\mathbb{Z}_{q}. $$

$$ k_{i^{\prime}L} $$

$$ \ {\mathcal U{}_{i^{\prime}}} $$

We show that this hybrid is indistinguishable from H₃, assuming the DDH assumption holds in G, in Lemma 31.

$$ \mathsf{H}_{3}. $$

$$ \mathbb{G} $$

In Lemma 32 below, we show that an adversary A wins the unpredictability game in H₄[x] with probability p ¹ at most. _N c

$$ \mathrm {H} _ {4} [ x ] $$

$$ \frac{1}{\sqrt{N-c}} $$

Since no ecient adversary A can distinguish between each pair of hybrids above with more than negligible advantage, we have that

$$ \Big|\mathsf{P r}[\mathsf{H}{4}x=1\mid i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}{0}x=1\mid i\in[N]\setminus M]\Big|\leq\mathsf{n e g l}(\lambda). $$

Next, since all our hybrids were parameterized by x, we take the union bound over all Q_Runcorrupted registrations to get

$$ x, $$

$$ \mathcal{Q}_{R} $$

$$ \begin{array}{l} \Pr [ \mathrm {U N P R E D} [ \mathcal {A}, \lambda , \ell , N, n, c ] = 1 \mid i \in [ N ] \backslash M ] \ \leq \frac {1}{\sqrt {N} - c} + \Sigma_ {x = 1} ^ {\mathcal {Q} _ {R}} \left| \Pr [ \mathrm {H} _ {4} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] - \Pr [ \mathrm {H} _ {0} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M ] \right| \ \leq \frac {1}{\sqrt {N} - c} + \Sigma_ {x = 1} ^ {\mathcal {Q} _ {R}} \operatorname {n e g l} (\lambda) \ \leq \frac {1}{\sqrt {N} - c} + \mathcal {Q} _ {R} \operatorname {n e g l} (\lambda) \ \leq \frac {1}{\sqrt {N} - c} + \operatorname {n e g l} (\lambda). \ \end{array} $$

This completes the proof of unpredictability. We now state and prove the remaining Lemmas used in the proof above. For a hybrid experiment H[x] and an adversary A, we use Hx to denote the random variable that represents the output of experiment H[x] with adversary A.

$$ {\mathcal A}, $$

$$ {\mathsf H{}}[]x] $$

$$ {\mathsf{H}}x $$

$$ {\mathsf H}[x] $$

Lemma 31. Suppose that G is a group in which the DDH problem is hard. Then, for all ecient adversaries A, we have p

$$ {\mathcal A}. $$

$$ \mathsf{P r}[\mathsf{H}{4}x=1\ i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}{3}x=1\ |\ i\in[N]\setminus M]\leq\sqrt{N}\mathsf{n e g l}(\lambda)=\mathsf{n e g l}(\lambda). $$

p p Proof. We prove this lemma through a sequence of N inner hybrids H₃_;[x]; 2 [ N], dened as follows: th { H₃_;[x]: In this hybrid, we change the behavior of the challenger in ^the x registration. During this ki0 L registration, if j < , instead of replacing each lj b= (uj b;vj b) = (uj b;u) with lj b j b rj ki0L^r_j R ₍u;u₎ fo^r r^jZ_q, for entries corresponding to the secrets k_i0_Lof uncorrupted users U_i0, it (j) b (j) b rjki0Lrj R sets l^j b(u;u), fo^r a new random key ki0LZq, which from then on plays the role of (j) b (j) b k_i0_Lin determining whether the user U_i0 has won an election.

$$ \sqrt{N} $$

$$ \mathsf{H}_{3,\gamma}[x],\gamma\in[\sqrt{N}] $$

$$ -\mathsf{H}_{3,\gamma}[x] $$

$$ x^{\mathrm{t h}} $$

$$ jtextit<<\gamma $$

$$ l_{j\cdot b^{}}=(u_{j\cdot b^{}},v_{j\cdot b^{}})=(u_{j\cdot b^{}},u_{j\cdot b^{*}}^{k_{i^{\prime}L}}) $$

$$ l_{j\cdot b^{*}}\gets $$

$$ (u_{\varPi(j)\cdot b^{}}^{r_{j}},u_{\varPi(j)\cdot b^{}}^{k_{i^{\prime}L}r_{j}}) $$

$$ r_{j}\xleftarrow{\ {mathbb R R}},{\ }\mathbb Z{}_{q}, $$

$$ k_{i^{\prime}L} $$

$$ \ {\cal U_{{i^{\prime}}}}. $$

$$ l_{j\cdot b^{}}\leftarrow(u_{\varPi(j)\cdot b^{}}^{r_{j}},u_{\varPi(j)\cdot b^{}}^{k_{i^{\prime}L}^{}r_{j}}) $$

$$ k_{i^{\prime}L}^{*}\xleftarrow{\mathbb{R}}{\mathbb{Z}}_{q} $$

$$ k_{i^{\prime}L} $$

$$ \ {\mathcal U{}_{i^{\prime}}} $$

By denition, we have that H₃_;0[x] is identical to H₃[x] and H₃ [x] is identical to H₄[x]. To prove the ;pN lemma, we prove that each successive pair of inner hybrids, H₃_{; 1}[x] and H₃_;[x], are indistinguishable.

$$ \mathsf{H}_{3}[x] $$

$$ \mathsf{H}_{3,0}[x] $$

$$ \mathsf{H}_{3,\sqrt{N}}[x] $$

$$ \mathsf{H}_{4}[x] $$

$$ \mathsf{H}_{3,\gamma-1}[x] $$

$$ \mathsf{H}_{3,\gamma}[x] $$

Claim. Suppose that G is a group in which the DDH problem is hard. Then, for all ecient adversaries A that make at most Q_Rregistrations of honest users in the elections phase, we have

$$ \mathbb{G} $$

$$ \mathcal{Q}_{R} $$

$$ \Pr \left[ \mathrm {H} _ {3, \gamma - 1} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M \right] - \Pr \left[ \mathrm {H} _ {3, \gamma} [ x ] (\mathcal {A}) = 1 \mid i \in [ N ] \backslash M \right] \leq Q _ {R} \operatorname {n e g l} (\lambda) = \operatorname {n e g l} (\lambda). $$

First, if the entry l_bdoes not correspond to a secret k_i0 of an uncorrupted user U_i0, the two hybrids are identical. Thus, we only consider the case where this entry corresponds to the secret of an uncorrupted user.

$$ l _ {\gamma \cdot b ^ {*}} $$

$$ k_{i^{\prime}} $$

$$ U_{i^{\prime}} $$

Let A be an adversary that distinguishes between H₃_{; 1}[x] and H₃_;[x]. We use A to construct an algorithm B that breaks DDH in G. Algorithm B begins by receiving a DDH challenge tuple (u ;v ;w) from the DDH challenger. Then B behaves as the challenger in H₃_;[x] except it guesses a registration index th y and for ^the y registration of an uncorrupted user (call this user U), and instead of having user U add r rk^iLr ^r (g;g) to l, it adds (g;u).

$$ \mathsf{H}_{3,\gamma-1}[x] $$

$$ \mathsf{H}_{3,\gamma}[x] $$

$$ (u^{},v^{},w^{*}) $$

$$ \mathsf{H}_{3,\gamma}[x] $$

$$ y^{\mathrm{t h}} $$

$$ (g^{r},g^{r k_{i L}}) $$

$$ U^{*}] $$

$$ U^{*} $$

$$ (g^{r},u^{*r}) $$

th Next, during ^the x registration, if B knows the secret k_i0_Lused in entry l_b= (u_b;v_b) = k^i0L (u^b;u) from registration of user Uⁱ⁰, B aborts and outputs 0. Note that the only time that B does b not abort and i 2 [N]n M is when entry l_bcorresponds to user U. If B does not abort, instead of setting rjki0L^rj l_b(u;u₎, it sets l_b(v ;w). (j) b (j) b

$$ (u_{\gamma\cdot b^{}},u_{\gamma\cdot b^{}}^{k_{i^{\prime}L}}) $$

$$ l_{\gamma\cdot b^{}};=;\left(u_{\gamma\cdot b^{}},v_{\gamma\cdot b^{*}}\right),= $$

$$ k_{i^{\prime}L} $$

$$ x^{\mathrm{t h}} $$

$$ \mathcal{U}_{i^{\prime}},,\mathcal{B} $$

$$ i\in[N]\setminus M $$

$$ l_{\gamma\cdot b^{*}} $$

$$ U^{*} $$

$$ l_{\gamma\cdot b^{}}\leftarrow(u_{\varPi(j)\cdot b^{}}^{r_{j}},u_{\varPi(j)\cdot b^{}}^{k_{i^{\prime}L}^{}r_{j}}) $$

$$ l_{\gamma\cdot b^{}}\leftarrow\left(v^{},w^{*}\right) $$

During the challenge experiment, if B does not know the secret of the entry chosen for the winner, it outputs the index of U. Note that whenever this happens, either the index i =2 [N] n M (for i being the

$$ U^{*} $$

$$ i,\notin,[N],\setminus,M $$ index of the winner), or the winner is U. At the end of the experiment, B outputs 1 i the unpredictability experiment outputs 1, i.e., if A guesses the index of the winner of the challenge election.

$$ U^{*} $$

Observe that if B does not abort, it provides A a perfect simulation of when the DDH challenger sets R 0 w = g, for u = g;v = g with*;* Z_q, and a perfect simulation of H₃_;[x] when w = g for ^{0 R} R Z , conditioned on the winner’s index_qi 2 [N] n M. Since y Q^Ris chosen uniformly at random 1 from among all uncorrupted registrations, there is a chance that B does not abort. Thus B distinguishes QR 1 between the DDH experiments with probability times the probability that A distinguishes between QR H₃_{; 1}[x] and H₃_;[x], completing the proof of the claim.

$$ w^{*},=,g^{\alpha\beta} $$

$$ u^{},=,g^{\alpha},v^{},=,g^{\beta} $$

$$ \alpha , \beta \leftarrow^ {\mathrm {R}} \mathbb {Z} _ {q}, $$

$$ \mathsf{H}_{3,\gamma}[x] $$

$$ \gamma^ {\prime} \leftarrow^ {\mathrm {R}} \mathbb {Z} _ {q}, $$

$$ w^{*}=g^{\gamma^{\prime}} $$

$$ i,\in,[N],\setminus M, $$

$$ \ \ y xxleftarrow{\ {cal Q Q}}_{R} $$

$$ \mathrm {a} \frac {1}{\mathcal {Q} _ {R}} $$

$$ \frac{1}{\mathcal{Q}_{R}} $$

$$ \mathsf{H}_{3,\gamma-1}[x] $$

$$ \mathsf{H}_{3,\gamma}[x] $$

Lemma 32. For all adversaries A, we have (unconditionally) that

$$ \mathcal {A}, $$

$$ \mathsf{P r}[\mathsf{H}_{4}x=1\ |\ i\in[N]\setminus M]\leq\frac{1}{\sqrt{N}-c}. $$

a b R Proof. In H₄[x], all the uncorrupted users’ entries in bucket b appear random, i.e., as (g;g);a;b Z_q. Thus the contents bucket b are distributed independently of the \winning" user U_i. Thus the adversary A can do no better than choosing an uncorrupted user at random from those users registered in bucket b. In the worst case, every corrupted user is in bucket b, so the A wins the unpredictability game in H₄[x] with p 1 probability at most. _{N c}

$$ {mathsf\mathsf H{}}_{4}[x] $$

$$ b^{*} $$

$$ (g^{a},g^{b}),a,b\xleftarrow{\mathbb{R}}\mathbb{Z}_{q}. $$

$$ b^{*} $$

$$ \ {cal U}_{i}. $$

$$ b^{*} $$

$$ b^{*} $$

$$ \frac{1}{\sqrt{N-c}} $$

$$ \mathsf{H}_{4}[x] $$

Security for randomly-assigned buckets (Theorem 20). We now describe how to modify the security analysis above to apply to a scheme where users’ buckets are assigned randomly at registration time. The arguments for uniqueness and fairness will be exactly the same, but the unpredictability argument will require an additional step in the portion of the proof corresponding to Lemma 32. The reasoning in that lemma proves the claim that this scheme is 1*=h*^-unpredictable, where h^ is the minimum number of honest q ^ph p2h users in any one bucket. We show that h wit_{h p}robability at most e, where h is the total N N number of honest users.

$$ 1/\hat{h} $$

$$ \hat{h} $$

$$ \hat{h}\leq\frac{h}{\sqrt{N}}-\sqrt{\frac{2\lambda h}{\sqrt{N}}} $$

$$ e^{-\lambda} $$

p1 The probability that a given user is assigned to a particular bucket is, and users are assigned to N ph buckets independently, resulting in ^honest users per bucket in expectation. Thus, by a Cherno bound, N the number of honest users assigned to one particular bucket is bounded by h i

$$ \frac{1}{\sqrt N} $$

$$ \frac{h}{\sqrt{N}} $$

$$ \operatorname*{P r}\left[\hat{h}\leq(1-\delta)\frac{h}{\sqrt{N}}\right]\leq e^{\frac{-\delta^{2}h}{2\sqrt{N}}}. $$

q_p 2 N Setting = yields _h

$$ \delta=\sqrt{\frac{2\lambda\sqrt{N}}{h}} $$

$$ \operatorname*{P r}\left[\hat{h}\leq\frac{h}{\sqrt{N}}-\sqrt{\frac{2\lambda h}{\sqrt{N}}}\right]\leq e^{-\lambda}=\mathsf{n e g l}(\lambda). $$

p We next take a union bound over the N buckets to nd the probability than any bucket has fewer than q ^ honest users, but since we showed that a single bucket only has fewer than_ph _p2h h honest users with N N p negligible probability, the union bound over N buckets will also have fewer honest users in any bucket with at most negligible probability. Plugging back in to the claim proved above, we get that the scheme is

$$ \sqrt{N} $$

$$ \hat{h} $$

$$ \textstyle\frac{h}{\sqrt{N}}-\sqrt{\frac{2\lambda h}{\sqrt{N}}} $$

$$ \sqrt{N} $$

$$ 1/\hat{h}\geq\frac{1}{\frac{h}{\sqrt{N}}-\sqrt{\frac{2\lambda h}{\sqrt{N}}}}=\frac{N^{1/4}}{N^{3/2}-c\sqrt{N}-\sqrt{2\lambda(N-c)}}\ {operatorname{u u p r e d i c t a b l e}}. $$

The (informal) statement of Theorem 20 follows from using the steps above and substituting this bound for the one found in Lemma 32.