How might one create a system of election by lot (sortition) that is both secure and verifiable?

Question

I've been puzzling recently over sortition, a democratic method of selection for public office which I find very fascinating. Basically, instead of choosing candidates like Hillary Clinton or Donald Trump through voting, under sortition citizens would be randomly selected to fill public offices (in which, under many models, they would then be FORCED to serve for some period of time). There are of course many nuances, but that is the general gist. It would be rather like jury duty in the modern United States.

One particular problem for which I haven't been able to find a fully-formed solution online is ensuring that the random selection is actually random (so that it statistically represents the full population, one of the goals of sortition when a large-enough body is selected, rather than representing special interests or folks who paid off the people in charge).

Let me be clear: I am not a cryptology expert by any means. Indeed, I am only in high school and have never taken a proper computer science course.

Nevertheless, I was wondering if anyone here had any ideas (phrased at a fairly elementary level) for how fraud in the random selection could be prevented. (EDIT: While, as pointed out in the comments below, you could just have blind-folded people pull the names out of a hat, that might not be enough to keep citizen confidence high given the high-stakes and temptation for bribery and other such shenanigans.)

I've been wondering if maybe there could be a connection to RSA public-key encryption, cryptographic hash functions or other one-way functions, Bitcoin, etc (all those are subjects I know at least a bit about). I'm thinking there'd need to be a way for everybody to verify that the sortition wasn't rigged in any way (perhaps through some sort of blockchain?). But the method of choosing (let's say it's a function of some sort) couldn't be too simple because it would probably also need to be difficult for anyone to predict in advance what input would map to a given output, right? (If a selected individual for a public office was an output but people could predict which inputs would lead to that individual getting selected, then the choice of inputs into the function might get rigged by special interests, right?)

And, also, if you're utilizing a fully determinate mathematical function that would be, of course, not truly random (although maybe that's okay - political pollsters don't do truly random sampling either in that sense, but no one really seems to mind). So there's that issue too -- what do we do when we say we want "random sampling" but also want to be able to verify that the sample wasn't tampered with? (I have heard of the topic of pseudo-random functions - is that related to this perhaps?) Perhaps randomness can be approximated well enough by introducing real-world data observations that are somewhat unpredictable?

Sorry for the length and it could be that these are fairly elementary questions (or maybe they are in fact very hard questions, I have no idea). I sincerely thank anyone who responds with any thoughts they may have on any aspects of this question.

One last thing: If there is a potential solution to this question that involves basic prime number/modulus RSA stuff, that would be really awesome -- since that's one of the few crytology concepts I actually sort of know. :) I don't really care at this point if potential solutions would actually work out in the super-complicated real world. I'm more concerned with finding something that's superficially plausible given the very elementary knowledge of cryptology I currently possess (e.g., basic RSA). Once I get more advanced I could then come back and refine everything.

Answer 1

I'm going to try to answer a more modest version of your question.

Imagine that the Dishonest Society, a small club of 100 members, needs to take care of an Arduous Task that will require 5 people to complete. The members are lazy and so there are no volunteers. The members also don't trust each other very much, so they want to use a _sortition_ protocol to elect a random committee to do the Arduous Task.

Let's assume for the following that the members have all come to agreement on the membership list of their club:

$$ M = \{ M_1, M_2, \dots, M_{99}, M_{100} \} $$

A physical protocol

The intuition is that the members will collectively generate a random number, and then each member will try to guess the number. We'll rank the members based on how close their guess was to the random number, and select the 5 lowest-ranked members for the committee.

First we have to decide "how big" our numbers will be. We are going to have 100 guesses, so let's pick the range 0 through 8190, which should be enough. All of our calculations will be done modulo 8191. Because 8191 is $2^{13}-1$, a Mersenne prime, we are actually working in the finite field $\mathbb{F}_{8191}$ -- it will come in handy later when we look at the cryptographic protocol.

Now obviously we need the members to commit to their guesses before we generate the random number, so each member $M_i$ secretly makes a guess $g_i \in \mathbb{F}_{8191}$. We don't trust the members to be honest, so we'll ask them to put their guess inside a sealed envelope and write their name $<M_i>$ on the outside. Once all the members have prepared their guesses, we put all of the envelopes in a box and lock it. If a member tries to cheat by writing down a nonsense guess, we'll find out later when opening the envelopes. (And if a member tries to put someone else's name on his envelope, we assume someone will catch him when he attempts to put it in the box.)

Next the members need to generate a random number. $\mathbb{F}_{8191}$ is fairly large, so dice would be impractical. Instead we will ask each member $M_i$ to pick a random number $r_i \in \mathbb{F}_{8191}$. Then we have them write $r_i$ on a slip of paper and toss it into a hat. Once all members have put their random numbers in the hat, we can sum them up to get a truly random number that no member can influence:

$$ r = \sum_{i=1}^{100} r_i \pmod {8191} $$

It is easy to see that as long as at least one member was honest and selected their $r_i$ at random then the result $r$ is also random. It is also easy to see that none of the members knew anything about what $r$ would be at the time that they made their guesses $g_i$. And they can't go back and change their guess, because it's in a sealed envelope inside a locked box.

Now we can open the box with the guesses and calculate each member's ranking based on how close their guess $g_i$ was to the chosen number $r$:

$$ rank(M_i) = r - g_i \pmod {8191} $$

The committee for the Arduous Task can now be formed by choosing the 5 lowest-ranked members. Ties can be broken by a roll of the dice.

A cryptographic protocol

Assuming that all of the players can communicate with each other over a secure authenticated channels (standard in the multiparty computation literature) we can transform this physical voting protocol into a cryptographic protocol:

1. $M_i$ makes a random guess $g_i \in \mathbb{F}_{8191}$.
2. $M_i$ broadcasts a commitment $Com(g_i)$.
3. Wait until every $M_i$ has broadcast their commitment.
4. $M_i$ picks a random number $r_i \in \mathbb{F}_{8191}$.
5. $M_i$ sends each $M_j$ an additive share $[r_i]_j$ such that $\sum_{j=1}^{100} [r_i]_j = r_i$.
6. $M_i$ broadcasts $r'_i = \sum_{j=1}^{100} [r_j]_i$ and $g_i = Open(g_i)$.
7. Each player can now calculate the ranking of every other player as:

$$ rank(M_i) = g_i - \sum_{i=1}^{100} r'_i $$

We use a commitment scheme to force each player to select their $g_i$ before they have received any information about $r$. Because the commitment hides $g_i$ until the openings are broadcast, the players must select their $r_i$ before they have any information about the other players' choices of $g_i$.

We use a secret sharing scheme so that no player (or coalition of players) has enough information to determine the $r_i$ of any other player, and so this allows all of the players to send their $[r_i]_j$ shares to each other simultaneously.

In the real world we'd want to also use a linear message authentication code to verify each of the $[r_i]_j$ shares; otherwise a dishonest player could lie about $r'_i$ in step 6. We'd also want to consider a dishonest player who aborts in step 6 (without sending his $r'_i$ or his $Open(g_i)$) after learning enough information to determine that he would be one of the "losers".

No fancy public key cryptography required! :)