# Secret Leader Election

###### tags: `Tag(HashCloak - Validator Privacy)`

Authors: Dan Boneh, Saba Eskandarian, Lucjan Hanzlik, and Nicola Greco3Single

Paper: https://eprint.iacr.org/2020/025

Definitions:
* PPT - probabilistic polynomial time

### Table of Contents
[toc]

:::info
>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 efficient proof-of-stake based cryptocurrencies have recently received increased attention.

>This paper formally defines 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
Existing proposals for secret leader election work by electing a few potential leaders in expectation and describing a simple run-off 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 effort and potentially even forks in the blockchain in case of attacks on the run-off 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.

### 1.1 Our Contributions
1. SSLE from indistinguishability obfuscation. Our first and simplest solution from indistinguishability obfuscation [5, 27] serves to show the feasibility of constructing an SSLE scheme as we define it and gives an example of a scheme that demonstrates all the qualitative properties one could want from an SSLE scheme.
2. 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_i$ when they register to participate and use computation under the FHE with the public randomness as input to select one string $s_i$ from the registered set.
3. SSLE from DDH and shuffles. Our final and most lightweight construction assumes only the hardness of DDH in some group. Instead of encrypting each user’s string s*\i as we do with the FHE-based solution, we hide the link between each user and his or her $s_i$ by shuffling $s_i$ into the database of secrets at registration time.

## 3 Defining Single Secret Leader Election
**SSLE requirements:**
Informally, an SSLE scheme involves $N$ users $U_1$, . . . , $U_N$ with 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_{i*}$, such that only $U_{i*}$, knows 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.

**The scheme must satisfy a number of properties:**
1. Uniqueness means that exactly one leader is chosen in each election;
2. Fairness means that each user has a $1/N$ probability of becoming the leader, and as long as there is at least one honest user, a set of malicious users cannot influence 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.

> 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.
### 3.2 Formalizing SSLE Definitions
We now formally define the syntax and security properties of SSLE:

We now formalize our security definitions:
* Uniqueness requires that exactly one participant in an election can prove that she is the elected leader.
* Our definition 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.


We define 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:

If the adversary can manipulate an SSLE protocol so that it always controls the winner, our unpredictability definition becomes vacuous. We require fairness to protect against such an adversary. The key idea behind our definition 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:

## 4 SSLE from Obfuscation
In this section, we answer the question affirmitively by presenting an SSLE protocol built from indistinguishability obfuscation (iO) \[5,27\] that satisfies all the requirements set forth in Section 3, albeit with selective unpredictability and fairness

* 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 find 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, first, 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 $\widetilde{P}$ ← O(P ) that is posted to the ledger, where O is an indistinguishability obfuscator and P implements the following function.

P((pk$_{(),...,}pk_{n-1}$),i,n,R):


* For each election with n participants, user $U_i$ sets (c,ct) ← $\widetilde{P}$(($pk_1$, ...,pk),i,n,R) and run COM.verify(c,1,PKE.Dec(sk$_i$,ct)) with the output R of the randomness beacon to recover a bit 1 or 0.
* By construction, all users will receive a 0 except the leader, who receives a 1.
* Moreover, the choice of leader is determined by the 11 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 $\widetilde{P}$ .

We formalize the protocol below:


**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_i$ a 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.

## 5 SSLE from TFHE
This section shows how to build an SSLE scheme based on threshold fully homomorphic encryption (TFHE) 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 $\boldsymbol\ell$ = 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$∈{0,1}$^λ$, 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$^J_i$.

To realize this scheme, we need to show, first, how to get secret randomness in the TFHE and, second, how to use it to select a leader.

**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.

**Selecting a leader**
> Once we have generated a TFHE ciphertext containing log N random bits, we can use them to select a leader.

1. 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.
2. Then we pair off 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 efficient (e.g. depth 4 for N = 2$^{16}$ participants).

Having computed $v$ under the TFHE, we take the inner product between $v$ and $s$ to get the value $s_i$ which determines the leader. This step has a multiplicative depth of 1, bringing the total depth of the entire leader election circuit to as little as 10 for N = 2$^{16}$ participants.

**Defending against duplication and modification attacks**
The scheme as described thus far remains vulnerable to two attacks that we call duplication and modification attacks.

* A duplication attack compromises uniqueness. Two malicious users who choose the same secret $k_i$ can both legitimately claim to be the winner of the election if $k_i$ is chosen as the winning key.
* A modification attack targets unpredictability. A malicious user $U_j$registers by uploading a value of $s_j$ that corresponds to the plaintext of $s_j$ plus one for some honest user $U_i$ (and uploading a random value for $k_{jR}$). This ciphertext $s_j$ can easily be obtained because the encryption is homomorphic. Then if $U_j$ “wins” an election, the value $k_i$ + 1 will be revealed.
* $U_j$ j cannot prove that he has won this election, but note that in the definition of unpredictability, malicious users are not required to prove they have won an election.
* Later, if $U_i$ wins an election, the malicious user can recognize that that the decrypted value $k_i$ matches the one copied from $U_i$ and predict that $U_i$ is the winner before she reveals herself.

We defend against this attack by having each user $U_i$ upload a proof of knowledge $\pi{_s}$ of the plaintext corresponding to $s_i$ at registration time, thus ruling out attackers that register by modifying another user’s secrets.

### 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 use cases

Our construction makes use of a subroutine v ← Expand(r ) that takes a random vector r ∈ $F^{logN}_2$ and returns the $r^{th}$ standard basis vector v ∈ $F^{N}_2$, that is zero in all positions except a 1 in the $r^{th}$ position. We show how to instantiate Expand with multiplicative depth log log N after presenting the main construction.

### 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.

**Maintaining security over time**
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.

**Unequal election probabilities**
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.

Extra registrations have no impact on the multiplicative depth of the $C_e$ circuit, meaning they do not cause ciphertexts to get larger except through a limited number of additional ciphertexts added to the state $\boldsymbol{st.}$

**PRF instantiation and optimization**
> 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\].

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.

**Reducing on-chain costs**
We can reduce the final storage costs for each election in a blockchain usecase by making a trade-off where we increase communication and computation for each election.

Instead of publicly posting and perpetually storing partial decryptions of the final threshold FHE ciphertext, users can communicate the decryptions to each other off-chain. When the leader reveals herself, she posts a short proof that the partial decryptions communicated during the election successfully decrypted her secret.

## 6 SSLE from DDH and Shuffling
This 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 simplification that incurs more communication and computation.

**A high-communication scheme**
In this scheme, the setup operation initializes an empty list l on a public ledger, effectively requiring users to do nothing at all. Registration will involve a user choosing a secret value $k_i$ ∈ $Z_q$ for some λ-bit prime q, uploading a special commitment to $k_i$ to the list, and shuffling/re-randomizing all elements of l.
> Moreover, we require each user who shuffles l to post a NIZK proof that they have honestly shuffled 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.

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_i$ can identify a re-randomized commitment as her own after it has been shuffled.

To reveal, a user outputs $k_i$ , and the commitment ($u$, $v$) can be verified by checking that $v$ = $u$ $k_i$ . To rerandomize a commitment, anyone can compute Rerand(($u$,$v$), $r^{'}$) = ($u^{r'}$ , $v^{r'}$ ).

**Reducing communication**
As described, the high-communication scheme above requires each user who registers to compute a shuffle over $N$ list items, re-randomize each, and post the new list along with a proof of honest shuffling and re-randomization. We can reduce communication costs by shuffling new entries into only a part of the list $l$ instead of shuffling the entire list each time a new participant joins, resulting in a linear tradeoff between communication costs and security.

**Improving the communication/security tradeoff**
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 different sizes.

**Removing NIZKs**
We can also remove the need for NIZK proofs that shuffles were carried out honestly, saving even more space and time. Since each shuffle only operates on $\sqrt{N}$ entries, users whose entries were included in a shuffle can check every shuffled entry, requiring only $\sqrt{N}$ exponentiations, to ensure that their entry still appears after the shuffle.

**Defending against duplication attacks**
It is 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.

#### Conclusion
Efficient constructions for SSLE are an important tool in the blockchain space. This paper formally defines SSLE and constructs three SSLE schemes. Our protocols based on obfuscation, FHE, and DDH offer a range of tradeoffs between security and performance, with the last construction providing levels of security and performance that may satisfy practical requirements.