# Single Secret Leader Election
;2
Dan Boneh¹, Saba Eskandarian¹, Lucjan Hanzlik¹, and Nicola Greco³
1
Stanford University
2
CISPA Helmholtz Center for Information Security
3
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) 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 f*0*;* 1*g, for all x 2f*0*;* 1*g 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 f*0*;* 1*g and state, consider an experiment where K Key*F(1) *and K*S*Puncture*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*k*g is*
*the enumeration of the elements of S in lexicographic order and U*l*denotes 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*N*g 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* F2*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* : F2*!* F2*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*) !* pi*: 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*i*related 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*i*g*i2S*for some*
n
*S fP₁;:::;P*N*g the nal decryption algorithm outputs a plaintext* ^ *2* F2*[?.*
$$
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,* pi*, ct) ! 1/0: On input a public key pk, a partial decryption* pi*, 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₂*!* F2*of depth at most d, access*
n d
*structure* A*, and 2* F2*, the following holds. For (pk, sk₁,...,sk*N*) TFHE.Setup(*1*;* 1*;* A*),*
*ct*i*TFHE.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*j*TFHE.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* : F2*!* F2*of depth at most d, S 2* A*, and*i*2* F2*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*1*;:::;*k*,*
n k n
*a circuit C* : F2*!* F2*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₁* = *f*p₁*;:::;*pt*g and S₂* = *f*p⁰1*;:::;* p⁰t*g 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*N*g such that S =2* A *as well as messages m₀;m₁ 2* F2*.*
$$
S\subseteq\{P_{1},...,P_{N}\}
$$
$$
m_{0},m_{1}\in\mathbb{F}_{2}^{n}
$$
R
*4.The challenger provides fsk*i*g*i2S*along 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*N*g, messages*1*;:::;*k*2* F2*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*i*g*i2S*and 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*N*g;C*) *for circuits C* :
n k n^
F2*!* F2*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*i2S*to 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})
$$
Expt*A;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*;* 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*N*g;C*) *for circuits C* :
n k n
F2*!* F2*of depth at most d. For each query, the challenger runs the simulator fp*i*gi2S* S2(*C; fct₁;:::; ctkg;*
*C*(1*;:::;*k)*;S;* st) *and sends fp*i*g*i2S*to 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 Fp,
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* Fp. The winner of the election is the participant
who has the minimal value of *jR v*id*j*. 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*id*j* 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*id*j* 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*i*and 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*i*and outputting whether user U*i*has 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*i*claiming that a particular user was elected leader, and optionally an intermediate value p*i*from*
*the election, the verication algorithm accepts or rejects the proof that user U*i*has 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*i*for i 2 M.*
$$
ci*for 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*;*rti*;*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*;*rtj*;*pp*;*st) *for any previously regisered user U*j*where*
*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;* ski) *on behalf of each uncorrupted*
*registered user and A sending values l*i*for any subset of corrupted registered users. Let l₁;:::;l*t*be 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*i*generated 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*i*(either corrupted or uncorrupted) who outputs b*i= 1 *and*i*such 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*;*rti*;*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*;*rtj*;*pp*;*st) *for any previously regisered user U*j*where*
*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;* ski) *on behalf of each uncorrupted*
*registered user and A sending values l*i*for any subset of corrupted registered users. Let l₁;:::;l*t*be the*
*set of intermediate values l*i*generated 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*j*for 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*i*be the winner of this election. The game ends with A outputting an index*
*i⁰ 2* [*N*]*. If, for U*i*elected 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*i*for 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*i*for 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 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.*
$$
c0.
$$
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 *P*e *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) *P*e((pk₁*;:::;* pk)*;i;n;R*) and runs COM*:* verify(c*;* 1*;*
i n
PKE*:* Dec(ski*;*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 *P*e. 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 f*0*;* 1*g and use it to create the leader picking circuit P described*
*above. Then Let P*e *O* (*P*)*. Output pp=(; P*e*) 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*i*to st and output*
*(pk*i*,sk*i*) as rt*i*. Output k*i*is 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*i*2 st and there are no duplicate public keys in st.*
*Input k*i*is 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 P*e *from pp. Then run* c*,*
i n i i
ct *P*e(*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 P*e *from pp. Then run c,*
i n i
*ct P*e(*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*i*2f*0*;* 1*g*, 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*i0. 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* F2each 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 log*N* 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 knowledgesof 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* F2
th N th
and returns the *r* standard basis vector *v 2* F2, that is zero in all positions except a 1 in the *r* position. We
show how to instantiate Expand with multiplicative depth log log*N* 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₂ F2*!* 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* At*for 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*;* At*).*
*Choose random r₁;:::;r*N*2* F₂ *and let c*i*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=1*r*i= *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*iR*H*(*k*i)*, set*
*s*i*;*si=*TFHE.Encrypt(pk, k*iL*), and append* (*s*i*;k*iR*;*si) *to st. Output k*i*and 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*n*and 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* F2*. Compute p*i*TFHE.Eval(pk, C*e*, rk, s₁,...,s*n*) for circuit C*e*(described*
*below) with the value of R hard-coded inside of it. Output p*i*and l*i*TFHE.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*n*;k*nR*;*sn)*. Produce a new list l₁;:::;l*t0*of elements from l₁;:::;l*m*such that TFHE.VerifyDec(pk, l*i*,*
0
*p*i*) = 1. Compute the plaintext l TFHE.FinDec(pk,(l₁;:::;l*t0*)). If l 6*= *k*iL*output* (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*iR*H*(*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* F2and *v 2* F2, we use *w* = *u v 2* F₂ to
represent the outer product between two vectors *u* and *v*, dened as *w*ij= *u*i*v*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*i*2* 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 log*N* :
(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 in 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 skifor 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* + *d*log 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 log*N*. 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*;*ski, and registration token rtifor
which SSLE.Elect₂(pp, *l₁*,...,*l*N, *i*, *k*i, ski, rti) 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*i*2* Zqfor 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* Zq. 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, p*l*acing *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-unpredictability, 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~~-un~~p~~redictability (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 un*p*redictability 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*i*f*0*;* 1*g and compute k*iL*;k*iR
R ri ri kiL
*H*(*k*i)*, append k*iR*to st, sample r*iZq*, 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*jZq*. 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*i*as p*i*and 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 p*i(*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*i*mod N) such that u*j= *v*j*,*
*and update p*i*j 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 p*i*mod 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*i*mod 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*i*as 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*pi*from l (putting ? in its position) and k*iR
*from st, set* = (*i;p*i*;k*i)*, and output 1. Input sk*i*is 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*i*;k*i)*, and l*pi*as* (*u;v*)*. Compute*
0
0 0 *k*iL0
kiL*;k*iR*H*(*k*i). *If* pi= *R mod N,* u = v, *and* kiR= kiR, output 1*. Otherwise, output 0. If*
*SSSLE.Verify outputs 1, user U*i*is 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.*
*N*3=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* : *f*0*;* 1*g f*0*;* 1*g! f*0*;* 1*g 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*;* 1*g is chosen uniformly at random and f*n*is 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 f*0*;* 1*g, 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 2f*0*;* 1*g:*
$$
\hat{b}\in\{0,1\}
$$
---
*If W*b*is 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 *P*e generated during an honest setup phase, it is not possible for
an adversary to tamper with *P*e 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₀*;:::;* pkn 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(pki*;r*;*r⁰*) and outputs ct PKE.Encrypt(pki*;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 *P*e 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 pki, 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
1
(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 H[*x*](*A*) 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](A) = 1] Pr[H₂[x](A) = 1] negl():
$$
{\mathcal A},
$$
$$
\mathsf{P r}[\mathsf{H}_{3}[x](\mathcal{A})=1]-\mathsf{P r}[\mathsf{H}_{2}[x](\mathcal{A})=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](A) = 1] Pr[H₃[x](A) = 1] negl():
$$
{\cal A},
$$
$$
\mathsf{P r}[\mathsf{H}_{4}[x](\mathcal{A})=1]-\mathsf{P r}[\mathsf{H}_{3}[x](\mathcal{A})=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*](*A*) = 1] Pr[H₄[*x*](*A*) = 1] negl()*:*
$$
\mathsf{P r}[\mathsf{H}_{5}[x](\mathcal{A})=1]-\mathsf{P r}[\mathsf{H}_{4}[x](\mathcal{A})=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](\mathcal{A})=1]-\sf{P r}[\sf{H}_{5}[x](\mathcal{A})=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 pkito 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 ski. But if *A* is given ski, 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*](*A*) = 1] Pr[H₆[*x*](*A*) = 1] negl()*:*
$$
\mathsf{P r}[\mathsf{H}_{7}[x](\mathcal{A})=1]-\mathsf{P r}[\mathsf{H}_{6}[x](\mathcal{A})=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*](*A*) = 1] Pr[H₇[*x*](*A*) = 1] negl()*:*
$$
{\mathcal A}.
$$
$$
\mathsf{P r}[\mathsf{H}_{8}[x](\mathcal{A})=1]-\mathsf{P r}[\mathsf{H}_{7}[x](\mathcal{A})=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₀*;:::;* pkn 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 *P*e generated during an honest setup phase, it is not possible for an adversary to tamper with *P*e in
order to change the election result. Thus the probability that any participant wins the election is at most
1
, 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*R*H*(*k*), *k*L*;k*R*H*(*k⁰*), such that *k*L= *k*Lunless
0
*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 log*N* 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*ivalue. 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*iuntil it is revealed, it queries *H* at *k*iwith 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, ski) with the simulator *S₂*(*C*e*;*
*f*rk*;s₁;:::;s*n*g; 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 Las potential challenges, and gets back an encryption ct and a proofs. It reproduces the
unpredictability game of the preceding hybrid exactly except it appends ct andsto 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](\mathcal{A})=1\mid i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}_{0}[x](\mathcal{A})=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, ski) with the simulator
*S₂*(*C*e*; f*rk*;s₁;:::;s*n*g; 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 proofjcontaining 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*t*g*) 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 proofs. 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*R*H*(*k*), *k*L*;k*R*H*(*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 being 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;vj b) = (*u*j b*;u*) with *l*j b(*u;u*)
j b (j) b (j) b
R
for *r*jZq, for entries corresponding to the secrets *k*i*0*Lof uncorrupted users *U*i*0*, it sets *l*j b
rjki0Lrj R
(*u;u*), for a new random key *k* 0 Zq, which from then on plays the role of *k*i0Lin
(j) b (j) b i L
determining whether the user *U*i*0* 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 1
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](\mathcal{A})=1\mid i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}_{0}[x](\mathcal{A})=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 H[*x*](*A*) to denote the random
variable that represents the output of experiment H[*x*] with adversary *A*.
$$
{\mathcal A},
$$
$$
{\mathsf H{}}[]x]
$$
$$
{\mathsf{H}}[x]({\mathcal{A}})
$$
$$
{\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](\mathcal{A})=1\ i\in[N]\setminus M]-\mathsf{P r}[\mathsf{H}_{3}[x](\mathcal{A})=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 ki0Lrj R
(*u;u*) for *r*jZq, for entries corresponding to the secrets *k*i*0*Lof uncorrupted users *U*i*0*, it
(j) b (j) b
rjki0Lrj R
sets *l*j b(*u;u*), for a new random key *k*i*0*LZq, which from then on plays the role of
(j) b (j) b
*k*i*0*Lin determining whether the user *U*i*0* 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*i*0* of an uncorrupted user *U*i*0*, 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 rkiLr 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*i*0*Lused in entry *l*b= (*u*b*;v*b) =
ki0L
(*u*b*;u*) from registration of user *U*i0, *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
rjki0Lrj
*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*;* Zq, and a perfect simulation of H₃;[*x*] when *w* = *g* for
0 R R
Z , conditioned on the winner’s indexq*i 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](\mathcal{A})=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* Zq.
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
^p*h* p2h
users in any one bucket. We show that *h* with probability 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
~~p~~h
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}}}.
$$
qp
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
^ *h*onest users, but since we showed that a single bucket only has fewer thanph 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.