Large Scale Secure Sortition Part 1: Generating Randomness Collectively with In-Person Gatherings

Matthew Gray is a Mathematician, Software Engineer, and Theoretical Computer Scientist currently teaching at Renton Technical College after working at Microsoft Norway. His primary research interests are in Secure Multiparty Computation, Quantum Cryptography, and Coding Theory. Over the last year he has been researching how sortition can be conducted in secure and trustworthy ways.

Judging from the aftermath of contested elections around the world, if large numbers of people question the fairness of a sortition selection there could be dire consequences. Our current systems for generating the randomness needed for selections are not secure enough to silence those questions, especially when used to select national representatives. The current systems are all centralized and non-participatory, some are vulnerable to local cheating, and all are vulnerable to sabotage from well-resourced malicious actors, such as state security services. This article proposes a new option. It lays out a specific decentralized and participatory method of selecting representatives by explains how two people can go about fairly choosing one of them to be selected and then showing how the method can be scaled up for larger selections. It also touches on some of the mathematics surrounding these methods.

Current systems for generating the randomness needed for drawings fall into two main categories. First are physical systems such as dice, floating balls, or names in hats. These work better in small communities where every member can show up and observe. But even in those spaces, if people distrust their neighbors, they will worry about the dice being weighted or someone sneaking extra copies of their name into the hat. Second are digital systems that take some outside sources of randomness and process them to get some final randomness. These outside sources of randomness include stock market indexes, lava lamps, or cameras whose lenses have been painted over. 

Digital systems tend to involve math that is fairly complicated, don’t feel that random, and aren’t interesting to look at. Also, because of the complicated math involved, there’s a chance that these processes aren’t actually random after all. Neither category produces systems that involve citizens or are particularly resilient to sabotage efforts. Weighting dice or hacking a computer is easy. Manipulating the stock market is hard but may not be beyond the abilities of a state security service. However if we include everyone in the process of generating the randomness we can create systems that have no single point of failure.

To introduce the ideas used by the system I am about to propose, let’s imagine that the team captains (Luka and Hugo) in the last FIFA World Cup didn’t trust the coin that was going to be used at the start of the match. One way they could generate the “coin flip” together is for both captains to bring their own coins and flip them simultaneously. If both coins land on the same side (i.e. both heads or both tails) then France wins the coin toss, if they land on different sides (i.e. heads tails or tails heads) then Croatia wins. What is important to note here is that even if one coin is weighted, as long as the other one is unweighted, then the overall “coin flip” is fair. 

Figure 1. The odds of each possible result when one captain brings an 80/20 coin, and the other brings a 50/50 coin.

Let’s scale this up a bit. Instead of having to choose between 2 options, what if we need to choose between 5 (maybe Luka and Hugo need to decide which bar to go to after the match). One option would be to try to find 5-sided dice and do the same thing as above. But let’s try something a little different. First, they assign each of the 5 bars a number between 0 and 4. Then Luka and Hugo each individually write down a number between 0 and 4 then put their papers face down. They then simultaneously flip them over. After the papers have been flipped over they add their two “submissions” together, divide by 5 (the number of bars) and take the remainder (which will always be 0, 1, 2, 3 or 4) as the final outcome. 

This divide-and-take-the-remainder system is actually the same as the method used in the coin toss. If we treat the coins as having a 0 side and a 1 side then (0+0)÷2 = 0 with a remainder of 0 and (1+1)÷2 = 1 with a remainder of 0. While (0+1)÷2 and (1+0)÷2 both equal 0 with a remainder of 1. So if both coins come up the same, then the remainder and our final result is 0 and if they come up differently then our result is 1. 

As long as one captain submits a random number then this process leads to fair outcomes when choosing between 5 (or more) options as well. To see this, let’s imagine that Luka submits 0, then the final answer is whatever Hugo submitted (0+H)÷5 = 0 with a remainder of H. If Hugo submitted something random then that final answer is random. If Luka wrote down 1, then the final answer is one more than what Hugo wrote down (unless Hugo wrote 4 in which case it wraps back around to be 0). No matter what Luka submits, each of Hugo’s possible submissions leads to a different final answer. 

Figure 2. All the possible combinations of Luka and Hugo’s submissions. The yellow section illustrates how when Luka picks “1”, each of Hugo’s 5 choices leads to a different one of the 5 outcomes.

This means that if Hugo chooses his submission randomly, then no matter how Luka chooses, the answer is random. And vice versa.

Note: in this next section I assume that we are picking a single representative from a group of people. This makes the math easier to explain. When explaining the system’s flexibility I show how the same system can be used to select panels.

Okay, we now have a method for two people to choose between some arbitrary number of choices such that as long as one of them is submitting randomness the result is random. We can now scale this process even further. As is, it already works for lots of submitters. Let’s leave Hugo and Luka behind and imagine you are part of a pool of 1000 people who have stood to serve in the legislature. You have been given a ticket with a number from 0 to 999 and if your number is generated you will be the new local representative.

Now this same group of 1000 people will collectively generate the random number that will select a representative from among them. To do this, first each participant writes down a random number between 0 and 999 and submits it. Then (through some mechanism) everyone’s submissions are opened simultaneously. From your point of view, everyone else’s submissions (not including your own) can be added up, divided by 1000, and have its remainder taken which we’ll call R. The final answer is the reminder of (R plus your submission) ÷ 1000. Which means that if we think of everyone else’s submissions as set then your submission decides the final answer. So as long as you submitted randomness then the final answer is random. This same argument holds from every participant’s perspective. Meaning that as long as a single participant submits randomness the final result is random.

A brief aside on why it’s important that everyone’s submissions are opened simultaneously: In the analysis we just did, we said that your submission determines the final answer. The dark side of that is that if you know everyones submission you can choose a submission that guarantees an outcome to your liking. The upside though is that if you don’t know the submission of even just one other submitter then you have no control over the final answer. This is why the simultaneous reveal is essential. If people reveal their submissions over an extended period of time, then the last person to reveal could possibly cheat by calculating the number they need to submit to achieve their desired outcome based on the other submissions and, through sleight of hand, adjust their submission accordingly. Given that they would likely have only seconds to do this, it would be very difficult to do, but the simultaneous reveal eliminates this remote possibility. There are multiple ways for this simultaneous reveal to be done. My preferred option (because of its ceremonial appeal) is to use flame-proof submission cards and burn the envelopes that contain them. While I prefer simultaneous revealing, it is not the only solution to this problem. If you’d like to learn about the others please take a look at the other two articles in this series.

To scale this up so that millions of people can participate in generating the randomness, we can take this same ceremony and build a tiered “tournament” style system out of it. India has the largest ratio of citizens to Lower House of Representatives seats in the world at about 2 million citizens for each seat. There is no way we could get those 2 million people into even the largest of sports arenas. But we can comfortably get 1000 people into a large shared space. Let’s assume that there are 2 million people interested in getting a specific seat. The organizers split them up into 2000 groups of 1000 people who meet up on the morning of the selection. They carry out a selection like the one described above to choose one “candidate” to move onto the next level. In the evening those 2000 candidates gather at some central location and conduct a second selection to pick which of the 2000 people will be the lower house representative. From the point of view of every participant they have exactly a 1 in 2 million chance of getting the seat: they have a 1 in 1000 chance of winning the first round and a 1 in 2000 chance of winning the second. The chance of doing both is 1/2000 times 1/1000 which is 1 in 2 million. 

This tiered system (or something similar) is what I would like to propose for picking representatives.

This system has several main advantages. First, its participatory nature. In my explanation I assumed that the 1000 people standing for office also were the only ones submitting randomness. But those are two different roles in the process. We can have 1000 people submit randomness to select one of 12 people by having each submitter submit a number between 0 and 11. This means everyone, even those who aren’t standing for office, can help generate the randomness. Second, its scalability. The number of people we can select from grows exponentially with the number of rounds. We were able to select one of 2 million people in just 2 rounds of meetings. If for some reason we needed to pick one of a billion people that would take just 3 rounds. Third, the requirements for security are clear and attainable. All we need to have mathematical proof that this system is secure and fair is some physical seal, envelope, or system that facilitates a simultaneous reveal. Fourth is its simplicity. These proofs of security and fairness only involve (at most) high-school level math and can be done rigorously over a day or two of math class. Finally, because it is simple, secure, and fair it is a system that can generate trust and confidence. 

This kind of system can also be adapted to different versions of the problem of selecting representatives. One obvious question about the system laid out above is what if the initial gatherings have uneven numbers of people? Wouldn’t that be unfair to the people who came from larger first round groups to have an equal chance in the second round. Well instead of generating a number from 0 to 1,999, we generate a number from 0 to 1,999,999 and give each candidate a ticket with a range of numbers corresponding to the number of people in their first round group. Similarly we could task the final assembly to generate a number that corresponds to one of a list of possible panels for a local city council instead of choosing just one representative.

This system’s first main disadvantage is that (especially on a national scale) it’s a significant logistical undertaking. While my personal research into election costs makes me think it will likely be cheaper than modern elections, it will still be expensive and time consuming. The second is that its security depends in large part on the integrity of the system used to ensure submissions are revealed simultaneously. If the envelopes are not spy proof then sabotaging the system becomes theoretically possible (though still very difficult). Given that every seal needs to be broken it’s still much more secure than methods with a single point of failure. Lastly, you cannot participate from the comfort of your own home. If you want to help generate the randomness you need to show up in person.

This system solves the major problems of current systems for generating the randomness needed for sortition selections. It uses a participatory decentralized ceremony that avoids a single point of failure (every seal needs to be broken) to create randomness in a simple, transparent, and fair way. If any citizen is worried about the security of a selection, they can easily participate and verify that the process was done honestly. If you would like to use a system like this for your own selections please let me know. 

I’ve posted two companion pieces alongside this one. The first details a method for how a specific cryptographic tool can be used to allow voting from home. The second explains the broad outlines of what approaches can work by looking at the paper that kicked off the field of “multiparty coin flipping”. They can be read in either order.

26 Responses

  1. Math is not my strong point but I suspected there was a preference when we have to choose “randeom” numers and indeed it seems to be so : https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3899545/
    Not all numbers are equal: preferences and biases among children and adults when generating random sequences

    We investigate the number preferences of children and adults when generating random digit sequences. Previous research has shown convincingly that adults prefer smaller numbers when randomly choosing between responses 1–6. We analyze randomization choices made by both children and adults, considering a range of experimental studies and task configurations. Children – most of whom are between 8 and 11~years – show a preference for relatively large numbers when choosing numbers 1–10. Adults show a preference for small numbers with the same response set. We report a modest association between children’s age and numerical bias. However, children also exhibit a small number bias with a smaller response set available, and they show a preference specifically for the numbers 1–3 across many datasets. We argue that number space demonstrates both continuities (numbers 1–3 have a distinct status) and change (a developmentally emerging bias toward the left side of representational space or lower numbers).

    …. There is a very extensive literature on the psychological interpretations of attempts to produce random choices….

    This “preference” exist also when we see the statistics of numbers drawn by the mechanical “lotto” drum. But this preference is “random” and changes in time with each draw.

    Like

  2. The number of people we can select from grows exponentially with the number of rounds. We were able to select one of 2 million people in just 2 rounds of meetings. If for some reason we needed to pick one of a billion people that would take just 3 rounds.

    Although that might make sense mathematically, do you seriously imagine that billions of people would come to the meeting, given the infinitesimally small number who would “win” the lottery? It’s hard enough to get people to turn up at the local polling station at a time convenient to themselves.

    Given that the democratic potential of sortition is conditional on large sample sizes and quasi-mandatory participation this is only of academic interest. Are there widespread reports of punters who buy a weekly lottery ticket claiming that the system is rigged? When I received a jury summons a few years ago it did not occur to me for a moment that the selection was anything but random. I’m sure a trustworthy system could be devised using the stock market index or other publicly-observable dataset. And given the high public profile of a legislative jury it would be hard to conceal if there was a bias on significant population parameters (although there would be if participation were voluntary).

    Like

  3. […] article assumes you’ve read my previous article “Large Scale Secure Sortition Part 1: Generating Randomness Collectively with In-Person Gather…. In particular it assumes a familiarity with the add-divide-remainder procedure for combining […]

    Like

  4. […] article assumes you’ve read my previous article “Large Scale Secure Sortition Part 1: Generating Randomness Collectively with In-Person Gather…. In particular it assumes a familiarity with the add-divide-remainder procedure for combining […]

    Like

  5. Thanks, Matthew, for your thoughts on this issue. I believe that this issue of how trustworthy randomness used for sortition is may not be the most urgent one now, but it could at some point become problematic and important.

    Your analysis of the risks and the considerations involved indeed highlights the important points to be addressed. I think, however that your comment that

    [m]anipulating the stock market is hard but may not be beyond the abilities of a state security service

    underestimates the risk. I think it would be quite easy for a powerful state agency, like the FBI or the CIA, to manipulate stock market readings. It seems to me that an agency like that would have little problem making changes to the software that determines the stock market prices.

    Regarding your proposal in this post: I think securing its fairness is problematic, due to the scale and to the fact that simultaneity is required. If there was some way in which one additional number could be changed or added to the pile of submissions after all the other submissions were revealed, this would completely break the system.

    On the other hand, the issue of getting citizens to participate can be addressed quite easily by using a material incentive. If each person who showed up were to be given a check with, say, a week’s worth of median salary, this would go a long way toward raising participation rates.

    Like

  6. Paul Nollen:
    One of the great things about this system is that if you are worried that trying to come up with a random number won’t result in something random (and as you point out that is something you should be worried about) you can roll dice or flip coins and come up with your random number however you want. And the final result will be at least as random as the your random submission.

    Liked by 1 person

  7. Keith Sutherland:
    I’ve seen some of your and Yoram’s back and forths in the comments of some previous articles. So I know this line of inquiry feels like something of a waste of time to you. I get that, but I really think that it’s important to have these systems ready if people someday decide that they need them.

    We don’t know what the future holds, and it’s not very hard to imagine a future where some political group or news organization decides to attack sortition on the grounds of it being rigged (or riggable). Especially given recent efforts to make people believe that elections have been rigged (and the violence that has accompanied many historical contested elections). Having systems like this ready to go if/when that day comes might save sortition.

    Like

  8. Yorem:
    You’re probably right about security services’ ability to mess with the markets. I hadn’t actually ever thought before about how those indexes are tracked. I wonder exactly how that works. Regardless if it’s computerized and connected to the internet then it could certainly be targeted by state security systems and sabotaged.

    I also agree that the scale involved would be pretty daunting. But given the efforts currently invested in elections I think it could be done.

    I don’t worry much about the concern of someone putting in an extra submission after the reveal. Taking a video (on an analog tape recorder if you are feeling really stressed about hackers) of the reveal and doing an audit yourself on a pocket calculator would catch any such attempt. Somebody snooping every submission and changing their own at the last minute is a bit more of a worry but it would still be insanely difficult.

    We’ll have to wait and see what implementers’ needs and desires end up being. They’ll be the ones deciding which system they want to use. It honestly seems more likely that different groups will decide to use different systems than one system turning out to be perfect for every group’s needs. Especially given what I laid out in Part 3. Cleve more or less proved that we have to accept some set of pros and cons with a system like this. Different sets will likely work better or worse for different situations.

    Like

  9. >Having systems like this ready to go if/when that day comes might save sortition.

    True, but they need to be practicable. Although your proposal is (theoretically) scaleable, it’s not going to work if you assume (like Andre, Terry and me) that statistical representation requires quasi-mandatory participation. I think the democratic objections to small or voluntary sortition bodies carry more purchase than fears about manipulating the sortition mechanism. If the numbers are large it will soon become obvious if the draw has been rigged to give an unrepresentative sample. It’s worth noting that the objections raised against recent sortition bodies have been over the stratification rather than the randomisation algorithm. And I haven’t heard any complaints that lotto draws are rigged from people who buy tickets every week.

    Like

  10. Keith,

    I’m glad we agree that they need to exist, be ready, and be practicable.

    Ah, I get where you are coming from. If we assume we’re using quasi mandatory participation we have two options. First option is to make participation as someone standing for office be mandatory but participation as someone generating the randomness be voluntary. In which case we still get similar guarantees that the result will random as long as one of the volunteers behaves well, but people who don’t care about the randomness system can stay home. The other option is to make working to generate the randomness mandatory as well and have selection day be a national holiday. For most people (if they have the day off) then showing up to a neighborhood morning get together at the local park or school is a pretty small ask, only a handful of people will have to go to the second round and if that proves a hardship for an individual they can send someone to act as a stand in.

    Also, if you end up feeling like the gatherings are still too much of a hassle please take a look at the other two articles in this series. Part 2 lays out a second option, and Part 3 explains why every option will have some drawbacks.

    I agree that stratification is a much more urgent technical issue than the randomization algorithm. This work is preparing for the hoped for future when these systems are used on larger scales.

    Like

  11. >The other option is to make working to generate the randomness mandatory as well and have selection day be a national holiday.

    Both those options make sense. Regarding the latter, have you seen Ackerman and Fishkin’s Deliberation Day? (albeit it addresses the rational ignorance problem, rather than scepticism over fair lotteries). Out of interest, in all the widespread criticisms of the political potential of sortition has anyone come across doubts regarding the integrity of the lottery algorithm?

    Like

  12. I haven’t seen Deliberation Day. It looks interesting though and I’ll likely give it a look. You are right, it does seem to operate along similar lines, and the gatherings could function really well as sites for hyper local and regional deliberation.

    I know Yoram has posted about the integrity of the lottery system before but I haven’t read through that much criticism of sortition, so I don’t know how often it comes up. I suspect that it doesn’t come up too often. In part because it’s not that obvious a critique when you are thinking about sortition abstractly which most critique does. And in part because it’s unlikely to be something that comes up right away when you are being introduced to sortition. There are a lot of more obvious objections that you have to get over first.

    The doubts about the lottery algorithm came up for me when talking about sortition with a friend who was considering using it for a local organization where (because of some recent malfeasance) there was a certain level of mutual suspicion. Because they were thinking about immediate implementation in a contentious environment one of their major concerns was “How do you make sure no one is looking in the hat?”

    Then because I had already done some semi-related research, thought that this question could someday be being vitally important, and started to really enjoyed working on this, I ended up diving really deep into the question.

    Like

  13. I think Keith’s initial worry here is something of a showstopper. Getting a large chunk of the population to come to a meeting is going to be quite a challenge. Making it a mandatory and on a national holiday might solve the problem, but in the ugliest way possible. How many people do you think would resent being ordered to turn up to a meeting where their contribution is negligible? And even then, there’s the logistical challenge would be spectacular.

    However, I think the core idea here *is* useful, and doesn’t need a giant country-wide meeting.

    The meetings are only necessary because you demand participation. But participation in the abstract isn’t valuable. If you want people to contribute the things only people can — creativity, intelligence, compassion, judgement and the like — then it can be. But if it’s something a machine can do, you may as well let the machine do it.

    So let’s do that. Get rid of the people guessing numbers simultaneously and replace them with lottery machines. The mathematics works just them same: Even if most of the machines are compromised, the result is still random.

    For the UK, for example, you might have three machines per constituency. That gives you 1950 machines spread across the country. Any malicious agent trying to compromise them all in a useful way would face a supremely difficult task.

    Machines have another benefit over people picking numbers: You can take them apart and check they’re not compromised. Doing so with a person is rather more difficult.

    So with machines, you can have an independent “sortition audit” body (or even better, multiple bodies) to watch the result and check the machines. As Keith points out, you can also audit at the other end, checking the demographic statistics match the population. (You don’t actually need the sorition legislature to be statistically representative to do this. For an opt-out system, the initial names chosen can be checked against the population, and for an opt-in system you can check the results against the candidates.)

    In the end, then, you get three layers of security any malicious agent would have to evade: The initial machine check, the combination of results, and the statistical analysis of the results. Getting past all of them (and in a way that’s actually useful) isn’t impossible, but in practice it should be so difficult no secret service could accomplish it.

    Like

  14. Liam:

    I like your proposal, that’s a great way of taking the system and adapting it to a set of desires and assumptions. (In this case, the desire to allow people to only have to participate in ways they want to, and the assumption that almost no one will want to participate in generating the randomness).

    You would still need to bring the machines to a single location and arrange a simultaneous reveal. But I’m sure that could be done lots of different ways. (Have them all under cloths that are all pulled away at a single moment, have them output sealed envelopes that are burned away together, etc.)

    I also like your point about how the three layers of security that this system provides makes for a very high level of audit-ability and security.

    I personally hope that people would want to be part of the generation process so that they can engage in local and regional deliberation, community building, and ritual. But if that turns out to not be the case then your proposal is probably the way to go. Less participatory methods of random number generation like yours also have the significant benefit that for most selectoral regions you could probably do away with the tiered system because you can fit all 1950 (or however-many) machines into a single room.

    I really love how your proposal emphases how flexible this system is. And your analysis of how the math works and can be adapted is spot on.

    I do somewhat disagree on one technical-ish point. I don’t think an individual’s participation makes only a negligible difference. I get that this point is a little odd, but if you look at this from the point of view where all other submissions are held equal then the outcome will almost certainly be different if you participate v.s. if you don’t (unlike elections). Though if you look at it from the point of view where the other participants are generating a distribution then yes your contribution will only make a difference if that distribution isn’t already uniform. But by participating you get the personal surety that the result of your gathering is at least as random as your own submission.

    I do think that counts for something, though maybe not enough to overcome people’s resentment for being forced to come out. I do hope that free donuts and coffee would be enough to overcome the resentment given that all they are required to do is spend an hour or so in a neighborhood park or school. But then again maybe not.

    Like

  15. This is all very promising.

    >I personally hope that people would want to be part of the generation process so that they can engage in local and regional deliberation, community building, and ritual

    We shouldn’t underestimate the value of public ritual (it was an important part of the sortition/voting system in the Serene Republic of Venice). It would be great if a tiresome civic obligation could be transformed into a sacred duty for those chosen by the goddess Fortuna to represent their fellow citizens!

    Like

  16. > Liam: the mechanical drum is what we propose in the “Code of good practice” (also discussed here at the blog.) https://www.academia.edu/42201754/Code_of_Good_Practice_for_allotted_mini_publics_involved_with_legislation

    Like

  17. Matthew,

    Thank you for the gracious reply, especially considering I came in to the conversation with knives bared. I think that mathematics you’ve given us here is extremely useful.

    Regarding a simultaneous reveal, I don’t think it’s a good idea to have all the machines together. That makes the location a weak spot and easier to crack.

    If the demand for simultaneous reveal is to ensure a compromised randomness source can’t react to the results of other sources, then mechanical lottery machines have another advantage. Humans and computers can react quickly to new information. However, a malicious agent would struggle to dynamically manipulate a lottery machine in a few seconds, while it’s in operation, and in front of an audience. So we can safely relax the reveal condition a little.

    That said, in the interests of greater security, we can adapt my above proposal as follows:

    1. Start all machines simultaneously (even with uncertain draw times, this should mean they’re no more than a couple of seconds apart). Even if the end times aren’t simultaneous, no machine should begin a draw after another has ended.

    2. Run all machines inside closed rooms, and during the draw forbid all messages into the room. No one inside the room should know what the other machines are doing.

    3. However, transmit a live video of the draw, so anyone outside the rooms can see the results of all machines as they operate and verify the final result. And have an audience of the public (who have given up their phones, of course) in the room to watch the draw.

    This way, you get a good balance of publicity and privacy based security. With in person and televised audiences, you also have to opportunity to make the draw a public event without relying on mass participation.

    And a bonus thought: The key point of security is to stop a malicious agent from accomplishing their goals. In practice, this would be to engineer a sortition body that makes choices they want. This is extraordinarily difficult: Even if the malicious agent can manipulate the results to get one useful person into the sortition body of hundreds of people, that won’t be enough. They will have to do it many times over to have an appreciable effect. And they’ll have to do all that without making the body look unrepresentative. Electoral systems, by contrast, are much easier to break: You only need compromise the leaders of one of the major parties and throw in some media manipulation. Not a big ask for someone with enough money.

    Regarding community building and ritual. I’m fully on board that these are important and valuable parts of human life. However:

    1. I’m wary of having a political system that explicitly relies on rituals. It should be more self-sufficient than that.

    2. Political systems are rather easier to declare than rituals, because the latter are embedded in culture. (Modern Valentine’s day might be a counterexample. But then, it’s based on sentimentality, sex and sugar — a much easier sell than civic duty.)

    3. I don’t see sortition as the sole solution to the current crises of democracy. Other solutions might be better suited to regenerating community. So sortition doesn’t need to carry that burden. (Although I think, if implemented properly, it will have important and beneficial effects across the entire culture, beyond the merely political.)

    Like

  18. Paul, thank you for the link. I’ll have a read through the code of good practice when I have a moment.

    Liked by 1 person

  19. Liam:
    You are very welcome. And thank you for saying that.

    My goal with this article was to give members of the community some useful mathematical tools to solve a problem that I suspect will come up at some point in the future. It’s just a lot easier to write a narrative and get the ideas across when focused on a specific proposal. I have some ways I’d be happiest seeing the tools applied, but at the end of the day mathematic tools like this don’t really care about how they are used. They just work. And it’s more important to me that people can conduct sortition securely than exactly which flavor of sortition they conduct, or which exact way they decide to use these tools. Like I said in the article, one of my favorite things about these tools is that they are flexible.

    Regarding your adapted proposal. That should totally work! The paranoid part of my brain would want to make each of those rooms a Faraday cage. But that’s probably overkill.

    Regarding your bonus thought, I really agree that electoral systems are much much worse. But the risk of someone taking control of the selection system can be significant especially in a modern era when so much of a person’s beliefs can be figured out from their online presence. When using stratified panels the draws are frequently done to pick one of a list of preselected panels. If an adversary gets control over the drawing, then they can spend their time analyzing all the panels and deciding which one is most to their liking (or even just quite to their liking). That panel already existed as a valid option that could have been legitimately selected by totally random chance. So after they are selected it’ll be hard to argue that they’re unrepresentative and could only have been selected by manipulation. This panel was exactly as likely as any other. But again I agree, doing that kind of work is a lot more complicated and difficult than compromising a single leader who really needs your money to run their campaign.

    I really agree with you that sortition will have massively beneficial effects across culture. I am very hopeful that we’ll get to see them.

    Like

  20. Keith:
    Thank you!!

    When I was working on this project the requirements in my head were:

    1) make it secure as possible
    2) make it simple as possible
    3) make it as fun/exciting/ritually-rich as possible

    This system ended up as my favorite because it nailed all 3. If we are going to replace elections we need a ritual to replace them with. And that ritual should be fun to participate in and look at. I really like that this system has a ritual option which is to have neighborhood parties across the country where people get to set stuff on fire. We don’t have to do it that way, but it would be a heck of a lot more fun than the current system of just dropping my ballot off.

    Like

  21. To me it seems that the proposal suffers from the fundamental flaw that any system relying on secrecy or simultaneity would suffer from: it is easy to cast doubts about its security and it is impossible to dispel those doubts because there is no way to prove secrecy or simultaneity.

    Once the possibility is admitted that a number can be selected after the others have been revealed, the fact that there are multiple machines becomes a liability rather than an advantage. Post-hoc statistical tests would be useless because they are known in advance to the attacker and thus the desired properties could be built into the rigged drawing.

    How important these weaknesses would be is hard to know. But if the public is not too suspicious then a simple prize-lottery-like system could be employed, while if the public is very suspicious then only fully publicly reproducible and verifiable procedure would do. Thus this proposal falls in the middle ground – being both rather complicated and not really convincing in terms of its security.

    Like

  22. Am I missing something? As long as there are multiple inputs from different people, the final random seed number only needs one honest person. Even if all of the others have conspired somehow, they cannot control the result. One of the Italian Republics had a small child reach into a hat to make a selection. While it is true that a competent magician could use slight of hand to fake a draw, a transparent ball tumbler on camera, as in lotteries, seems sufficient. (The seed number plugs into a simple formula to take every Nth person from a public list, for example.)

    Like

  23. > Am I missing something? As long as there are multiple inputs from different people, the final random seed number only needs one honest person.

    The crucial point is that this argument assumes simultaneity, which is hard to assure in practice and impossible to verify retroactively. Without simultaneity, if the attacker chooses their number after having seen all the other numbers, then their single input will allow them to determine the output.

    Like

  24. Yoram and Terry: What are we discussing. Are we discussing Liam’s proposal for trying to enforce simultaneity without a centralized location (which the more I think about the more I’m concerned by)? Or my original proposal? Or something else?

    Liam: I’ve been thinking more about your most recent proposal. And I’m increasingly worried about having the machines be split up. Compromising it would still be difficult, but less difficult (I think) than if the machines were at a central location.

    If the machines are split up then all it would take for an adversary to take control of the whole system is to thoroughly compromise a single location. Let’s assume they have compromised all the participants (the observers, operators, etc.) and have a compromised machine that still looks good over video. Now “no messages are allowed in” can be ignored and they can make sure that their machine is the last one to finish and gives them the answer needed.

    Splitting up the locations seems to actually make things less secure (instead of more-so) because instead of needing to compromise all of the much larger number of people at the central location you just need to compromise all the people at a single location of your choice.

    After thinking about it some more I’m back to thinking that if you want to ensure simultaneity you need to all be at the same place. Otherwise a single corrupt location can start engaging in shenanigans. (For more on shenanigans read part 3).

    Using many machines and combining their randomness is an awesome way of using this math. But since it still relies on simultaneity to ensure security, right now I’m thinking it needs to be done in person.

    But maybe that has downsides I’m not thinking of. Could you outline for me a scenario where having a centralized location makes the manipulation easier?

    Like

  25. > What are we discussing.

    I was referring specifically to Liam’s proposal, but as I noted I think the weaknesses would be there – to varying degrees – in any mechanism that relies on secrecy and simultaneity.

    Like

  26. Matthew, Yoram,

    Sorry about taking so long to reply. I got a little sidetracked.

    I think “compromise all the people in a single location” is much easier said than done. If each location were a separate organisation, that’s a risk. But if you’re treating security seriously, you’re probably going to have multiple independent audit organisations at a national level, each of which send observers or engineers to each of the locations, so any attacker would need to compromise these organisations too. And if you have members of the public in the lottery rooms, the challenge grows even greater.

    However, that’s a minor aside, because the real worry is simultaneity. I think we’re all agreed there. But I think my proposed system is at least as safe on simultaneity as having machines (or people) all together in one room.

    The key is having the results broad live.

    If any machine is clearly behind all the others, that’ll become immediately evident on broadcast. Even a perfectly faked video feed can’t get around this restraint, because they’ll still have to put out numbers. You can have a rule discard any machine that’s behind the others.

    Yoram’s right to worry about secrecy. Live broadcast of results works against this tendency.

    (Aside 1: Why don’t I insist on perfect simultaneity? Just because it’s impossible. The machines take a definite amount of time to output a result, and do so randomly, so you can’t guarantee they stay synchronised. But this point applies equally to machines in the same location, and to people writing down numbers. In practice, I suspect you could get the initial start time simultaneous to the microsecond, but the end end time might vary by a tenth of a second.)

    (Aside 2: I’m also assuming each member of the jury is chosen at random, rather than a stratified sample being chosen all at once. This has benefits beyond security. But it also means that multiple draws will have to take place. Any machine that regularly finishes behind the others in this case will be extremely conspicuous.)

    Why do I think a single location is more risky? The key assumption here is that it’s much easier to compromise a machine to produce a fixed result than it is to dynamically update a machine in real time. (Computers are vulnerable to live updating, but mechanical machines generally aren’t. Bug or feature depends on your use case.) If the machines are in a single location, then an attacker only needs to break into that location in off-hours, at which point they have access to all machines and can compromise them all. If the machines are spread across the country, then an attacker would need to break into every single location in off-hours to fix them. Alternatively, the attacker could compromise a single location, but then they would the double difficulties of dynamical manipulation while everyone is watching AND get past the live broadcast issue.

    *

    Incidentally, this discussion got me thinking about security, and I *may* have come up with another method. But since it’s based on computer science, Matthew, I think you’re better placed to pass judgement on it than I am.

    Suppose we were to publicly release a function for generating random numbers from a physical phenomenon. Then, we could use some openly visible, unpredictably randomness source beyond human control (weather seems the obvious choice) as the input for the function.

    That way, anyone could observe the weather (/other system) and verify the result. The code itself can be examined for tricks by computer scientists with the requisite skills (who I assume are numerous and unruly enough that they can’t all be compromised).

    You’d have to choose a randomness source that’s impossible to manipulate (so lava lamps are out) and also readily observable (so cosmic ray data is also out). You’d also need to to make sure the function doesn’t depend on perspective (reading pixels from a camera pointed at the sky is also out), but I think that should be doable if you operate at a low enough resolution and apply a transform to correct for perspective.

    But, as I say, this isn’t my area of expertise. Is there any hope in this, or am I barking up the wrong tree?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: