How could I make the results of a yes/no vote inaccessible unless it's unanimous in the affirmative, without a trusted third party?

Question

A family of N people (where N >= 3) are members of a cult. A suggestion is floated anonymously among them to leave the cult. If, in fact, every single person secretly harbors the desire to leave, it would be best if the family knew about that so that they could be open with each other and plan their exit. However, if this isn't the case, then the family would not want to know the actual results, in order to prevent infighting and witch hunting.

Therefore, is there some scheme by which, if everyone in the family votes yes, the family knows, but all other results (all no, any combination of yes and no) are indistinguishable from each other for all family members?

Some notes:

• N does have to be at least 3 - N=1 is trivial, and N=2 is impossible, since a yes voter can know the other person's vote depending on the result.
• The anonymous suggestor is not important - it could well be someone outside the family, such as a someone distributing propoganda.
• It is important that all no is indistinguishable from mixed yes and no - we do not want the family to discover that there is some kind of schism. However, if that result is impossible, I'm OK with a result where any unanimous result is discoverable, but any mixed vote is indistinguishable.

Some things I've already tried:

• Of course, this can be done with a trusted third party - they all tell one person their votes, and the third party announces whether all the votes are yes. However, this isn't quite satisfying of an answer to me, since the third party could get compromised by a zealous no voter (or other cult member) to figure out who the yes votes are. Plus, this person knows the votes, and may, in a mixed vote situation, meet with the yes voters in private to help them escape, which the no voters won't take kindly to.
• One can use a second third party to anonymize the votes - one party (which could really just be a shaken hat) collects the votes without reading them and sends them anonymized to the second party, who reads them and announces the result. This is the best solution I could think of, however I still think I want to do better than this - after all, in a live-in settlement cult, there probably isn't any trustworthy third party you could find. I'd like to find a solution that uses a third party that isn't necessarily trusted.
• However, I do recognize that you need at least something to hold secret information, because if you're working with an entirely public ledger, then participants could make secret copies of the information and simulate what effect their votes would have, before submitting their actual vote. In particular, if all participants vote yes but the last one has yet to vote, they can simulate a yes vote and find out that everyone else has voted yes, but then themselves vote no - they are now alone in knowing everyone else's yes votes, which is power that you would not want the remaining no voter to have.

EDIT: After BlueRaja's comments, I realize that the concept of "trusted third party" isn't quite well-defined, and that at some level, I probably actually do need a trusted third party at least for reliably holding state. The key is what I would be trusting the third party to do - for instance, in the first and second bullet point examples, I may not trust a third party to know who voted what, but may trust them with the contents of the votes. Ideally, of course, I would still like to be able to operate without a trusted third party at all, but failing that, I would like to minimize what I have to trust the third party to do. (Also, yes, a third party can include an inanimate object or machine, as long as it can withhold any amount of information from the participants).

Answer 1

This sounds like a classic case for cryptographically secure Multi-Party Computation.

The functionality to be realised using SMPC would be an AND tree-reduction which requires N-1 AND gates and has a depth of about log_2(N) AND gates with each "yes" vote being a truthy (1) input to the circuit and each "no" being a falsey (0) input.

The simplest solution for this would likely be to use the GMW SMPC protocol which allows for N-1 parties to work together without leaking any secret information. There is also a variant that allows for at most N/2 persons to deviate from the protocol.

The basic flow of the protocol is as follows:

1. Each party has a 1-bit input and chooses N-1 random bits and computes the XOR of the random bits with the input bit. Then one random bit is distributed to one other party each and the owner keeps the XOR of the random bits and the inputs.
2. Then the circuit is evaluated gate-by-gate which gives everyone an XOR-random share of the output value of that gate. XOR gates can be computed locally by simply XORing the shares of the input values. AND gates require an interactive protocol, which is a bit complicated, so I'll refer you to the (formatted) paper for that: "How to Play any Mental Game" by Goldreich, Micali and Wigderson (STOCS'87; PDF).
3. At the end (after all the gates have been evaluated) everyone broadcasts their share of the output bit so that everyone can locally XOR them together.

Overall the above GMW protocol will require N * (N-1)/2 1-out-of-4 Oblivious Transfers from each party which should be somewhat efficiently computable for any reasonably-sized "family" and might not even require fancy techniques like OT Extension for this small number of participants.

As for software, MP-SPDZ seems to be a good starting point to look for implementations (as well as the awesome-mpc list). Though note that you will mostly find more advanced schemes there.

Answer 2

The theory

This could be implemented in several ways, by applying the principle of idempotency.

You want a system that only produces a result (binary 1) if all the inputs are active, that is, it tells you that everybody wants to leave the cult only if everybody has voted yes, otherwise the system must not return any kind of information (binary 0). This is basically an AND relationship between the inputs, as seen in the following table (0 = no/false, 1 = yes/true):

Input: You want to leave the cult.
Output: Everybody wants to leave the cult.

0 0 0 | 0 
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1 ---> hooray, everybody wants to leave, we can talk about it!

Now, that might not be trivial to implement safely, because you need something that can count (N-1 will not be enough to trigger the result, but N will), and something that is able to count might also be able to leak information about the number of votes. So let's forget about that, and realize that since you are actually dealing with single bits of information (either yes or no, 0 or 1), then you will be able to get valuable information if you just check the opposite (no instead of yes, 0 instead of 1, etc.). So if you check if they want to stay in the cult instead of leaving, and if you check if at least one person want to stay instead of checking if they all want to leave, you get the following truth table where all 1s have been replaced with 0s and vice versa:

Input: You want to stay in the cult.
Output: Somebody wants to stay.

1 1 1 | 1
1 1 0 | 1
1 0 1 | 1
1 0 0 | 1
0 1 1 | 1
0 1 0 | 1
0 0 1 | 1
0 0 0 | 0 ---> hooray, nobody wants to stay, we can talk about it!

Note that now we have an OR relationship between the inputs, which I believe is easier to implement safely, because you just need a system that respond to any input in the exact same way. Such a system would be idempotent: one vote is enough to trigger the output, and any subsequent votes would have no effect. Now, what can we use to implement such a system? The system would need the following features:

• It must be trusted by everybody. It can't be built or bought by a single member of the family, or by someone else. So I suppose it must be something very simple that everybody can understand and trust. To avoid malicious manipulation of the system, it should also be operated while being supervised by all the members.
• The voters must not be able to check the output before the experiment is over. This means that the vote must not return any feedback about the current state of the system. For example, blowing out a candle is not safe if you can see it, or feel the heat, or smell anything.

The system

The simplest solution I can think of is something involving an electronic device with an idempotent button, like a remote control to change the channel on a TV. Here's an example of how I would set up the system:

• Get a device with an idempotent button. It might be a TV with a remote control, providing that changing to channel N always has the same effect no matter how many times you do it (idempotency). Or anything else you have at home, like a button to open a gate (if opening an open gate leaves it open), etc. The important thing though is that the system needs to be trusted by everybody, so if you really want to do everything safely the family might consider buying a new device (going to the mall, all together, and buying a trusted device).
• Set up the system safely. All the family must be present while setting up the system, otherwise the system might be corrupted by the one who sets it up. In general, the whole family must be present and check all the operations from the beginning to the end of the experiment (like from buying the equipment to throwing it away safely).
• Avoid any kind of feedback from the system while voting. For example, to change the TV channel, the TV and the remote could be under a huge thick blanket, and to vote you need to slide your hand under the blanket. But the volume should be muted, and maybe you'd better turn on some music in the background, loud enough to not be able to hear any possible buzz or noise from the TV. You might even want to define some delay between one vote and the next, to avoid getting any feedback from the possible heat of the remote control caused by the hand of the previous voter.
• The voting process should be the same for everybody. During the experiment the other members must make sure the voter is not cheating (like peeping under the blanket, acting strange, etc.), so everybody is present during the experiment. There is a relatively fixed length of time that the voter should be able to stay with their hand under the blanket. Sliding it under the blanket and immediately pulling it out is not considered valid, since that would be an obvious and publicly distinguishable NO vote. From the outside, every vote must look pretty much the same.
• Test the system before using it for the real experiment. You need to make sure everybody understand the process, votes correctly, and the system responds accordingly. The whole family takes part in several simulated votes for testing the system (simulated votes are fake and publicly known, not secret).
• At the end, the system must be dismantled safely. Any buttons or parts that have been touched might need to be cleaned carefully, to remove fingerprints. If the family members don't trust the system after the vote, fearing that somebody might be able to extract information from it, all the parts of the system might need to be thrown away.

The vote

Supposing they have chosen to implement the TV-remote-blanket system, what happens is this. "Ok everybody, the TV is on, the current channel is 123. If you want to stay in the cult, change it to channel 0". Each member in turn slides a hand under the blanket and either changes the channel (if they want to stay in the cult), or pretends to change it (if the want to leave). At the end, the blanket is removed and... Channel 123! Then nobody wants to stay in the cult, hooray! ...or ...Channel 0! Then at least one member wants to stay in the cult! Or maybe all of them, there's no way to know.

Final notes

It was fun trying to think of a solution to this problem, but I consider this more of a thought experiment than a real security question. The problem is that the threat model is incomplete, because I don't think this scenario can actually make sense in a family where all the members are part of a cult. Cult members are brainwashed and paranoid by definition. They might not even trust a store to buy a new TV or a remote control, thinking anyone they don't already know (including any sellers) might be "enemies". It is definitely possible to set up a system without any electronic devices, using only simple objects like candles, pots, water, ropes, etc. That stuff might be easier to trust, compared to a black-boxed electronic device, but it might also be harder to make such systems work reliably. I'm also wondering: if a member of the family suggests that a vote is needed, isn't that suspicious? Why should a member of the cult want to know if everybody in the family wants to leave? Chances are the one who proposes this system is the one who wants to leave. Or this might all be a trap to find out who wants to leave.

Answer 3

A very low-tech method: give each voter a card with a hole punched in one end, offset from the center. Make a container that holds the cards, and has a hole punched through it that lines up with where the hole in the card would be if entered face-up. Everyone votes by placing their card in the container face-up for yes, face-down for no (with the box suitably concealed to prevent anyone from seeing the votes themselves). A rod is then inserted through the hole in the container. If everyone voted yes, the rod falls through. If at least one person voted no, the rod will be stopped.

Answer 4

There's a cat in a box with a vial of poison gas. The vial is rigged to a button (marked "No") that will release the gas. Right next to that button, there's also a dummy button that makes an identical clicking sound (marked "Yes"). The box is soundproof and you can't see into it. The family is seated in front. The buttons are at the back. Each person gets a turn to walk behind the box and press a button. When everyone has had a turn, the cat—and hence by extension the cult—is in a superposition of states. Collapse this by opening the box—or, for even better results: put on gas masks, then open the box. Finally, either bury the cat or disband the cult, as appropriate. In the latter case, use a secondary voting procedure to decide who keeps the cat.

Answer 5

This is actually a tough problem! So here's my paper-and-pencil solution, trying to keep it as simple as possible.

1. Every person gets 3 slips of paper. They secretly write down a different 2-digit number on each of them and put them face-down in front of them.

2. Each person grabs 3 slips from other people, ideally no two from the same person.

3. Each person writes what those 3 slips add up to. If they wish to vote no, they may write a number higher than the real total. Go ahead and display this info.

4. Repeat step 2, so each person has 3 new slips of paper.

5. Each person writes what those 3 slips add up to, but this time keeps their sum face down. If they wish to vote no, they should write a number lower than the real total. (This is optional if they already mistotaled back in step 3.)

6. Each person destroys the original slips of paper in front of them. All that's left after this is the sum they did in step 3 and the sum they did in step 5.

7. Everyone displays their sums at the same time.

Do all the sums in step 3 add up to all the sums in step 7? If not, there's at least one 'No' vote.

Why does this work?

There's no secret generated by a third party. Aka, nothing is generating a large prime or anything like that. If 'something' is generating info, it'd have to be trusted by all the parties involved. This bypasses this, because the secret (what the total is) is generated by all the involved parties, while not being something that any of them know.

There's no chaining of info. Person B's work doesn't depend on output from anyone else. They can't use their input to figure out whether Person A is lying.

There's no way of determining whether someone's total is legit. If they say '218', the only way of knowing whether that's a possible number is to know what all the slips of paper said. But nobody has seen all the slips of paper.

Answer 6

Required utensils: Pen and paper.

---

As a group, pick a big prime p.

Everybody picks a secret pair of numbers a_i, b_i with a_ib_i ≡ 1(mod p). For example, pick a_i randomly in the range 1…p − 1 and find b_i by the extended Euclidean algorithm. If either a_i or b_i is suspiciously small (say, less than half as many digits as p), just start over with a new random value. Those who want to answer "no", pick both a_i and b_i at random instead.

Now the numbers are swapped around: Everybody gives their a_i to their left neighbour, and receives a_j from their right neighbour.

Everybody now multiplies mod p their now held pair of numbers and announce the result. Now the announced numbers are multiplied mod p. If everybody voted "yes", the final result will be 1. If any number of them voted "no", the result will be a random number and so very likely not 1 (so we may want to make p bigger to increase confidence).

Answer 7

Can't comment because I am newbie.
To add/comment @reeds and @securityOranges answers:
This seems like it could be easily done with switches as semi low tech option.

Make circuit such as:
Battery to switch to switch to switch to led back to battery.
Then one can even build and demonstrate its fair working in front of all participants.
Wires could be as pretty much as long as needed.
Lights/leds could even be added to next to each switch.
Thou I would probably just give people cardboard box to hold their hand while being in same room.

Buttons can be used to ensure that even if system is physically stolen during votes they return to their original state fast enough that no information can be gained.
Then just people to look at the clock and everyone will vote for ~10 seconds when clock hits certain time.

Edit: I build demonstration of this:
https://i.sstatic.net/pihWA.jpg

In brief:

Above two of three buttons are pressed but no light. Bellow all of the three buttons are pressed and thus light came.

And here hopefully picture to clear connections between components:

1, 2 and 3: From battery to first button
4, 5 and 6: Buttons
7, 8, 9 and 10: connection to resistor
11: the resistor
12: the LED
13:Connection back to "Battery"

I used Arduino as my battery but could have been any other method to deliver power for the led.

Answer 8

This is a really cool and interesting question. I really like this.

So, I think we should start by breaking down what you're trying to do in the most abstract, information theory-y way possible. Here's my understanding:

• N > 3 nodes in a group are communicating with one another.
• They're transmitting either a 0 or a 1, a yes or a no.
• We're going to take all inputs, then AND them. In other words, we don't care about outcome unless everything is a 1; if it's not all 1, it's 0. (If you're not super familiar with logic gates, this might be interesting.)
• Each node's transmission must be unknown by all other nodes.

The question then becomes how technical the solution should be. A more technical solution, with a single fundamental technique, makes this pretty simple:

1. All nodes attest to their identities in-person, and each node produces a public-private key-pair and gives their public keys to a centralized server.
2. They then transmit their votes to the centralized server, which decrypts them using their public keys.
3. The server performs an AND and returns the result.

If we wanted to try and make it lower tech, I think we would want to go with some weirder solutions. Here's one that comes to mind:

• Some dissolvable material is placed in a container, with a small amount of water. Each person takes turn pouring a chemical into it, blindfolded and holding their breath, with significant background noise.
• They select either water for yes or a colorless, odorless acid for no. The acid is strong enough as to dissolve materials in a considerable amount of solvent, over time.
• After pouring their votes, the setup then stands undisturbed for some amount of time. This amount is determined by finding the amount of time required to visibly dissolve the object, given a vote result of N - 1 negative votes.
• After the determined amount of time passes, all members view the results, separately (in order to avoid expressing reactions), then converge to discuss the results.

Ultimately, regardless of how much computers play into the choice, the answer is about preserving confidentiality and integrity in a transmission environment that drops confidentiality if the transmissions pass an AND gate. The water-acid solution is one among many possibles, but in my opinion it still gets the job done.

Great question! This was really fun to think about. If I missed any constraints you already mentioned, stick it in a comment and I'll revise.

Edit: initially I said that water was "no" and acid was "yes". It should've been the other way around. Thanks for pointing that out, @TripeHound.

Answer 9

This improves securityOrange's thoughts, but in a more reliable form without waiting.

Chemical solution using a pH indicator

Let's look at different pH indicators, halochromic chemical compounds i.e. compounds that reacts to the acidity or basicity of the solution by changing color. This corrected picture from EduMission blog shows some examples, and there's a more complete and accurate chart available on Wikimedia.

As we don't want to get hurt while mixing these solutions, it's better to choose compounds where the transition is sharp enough to be clearly noticed, like thymolphthalein that is blue above pH 10.5 and colorless below 9.3. Phenolphthalein is not as good, because it turns back to colorless above pH 10. Also, too accurate measurement of the pH would give away the information on the vote count.

This works for quite large groups, because the pH scale is logarithmic: adding 1 grams of sodium hydroxide into 60 liters of water results in pH 10.6!

Voting arrangement:

1. Prepare e.g. sodium hydroxide solution for casting no votes. If you add e.g. 0.4 grams of sodium hydroxide to 0.4 liters of water, you get a solution with pH 12.4.

2. Have a flask of water for yes votes (pH 7). Both liquids are colorless and impossible to distinguish by eye. Therefore, it's important that the solutions are prepared together with the others.

3. Everyone on their own turn takes a full pipet of either solution and pours it into a third flask; let's call it a ballot box solution. It's important to use a pipet small enough compared to the sizes of the flasks so that the surface height doesn't give any hint on which solution was already used.

4. For counting the votes, drop thymolphthalein to the ballot box solution.

   If it turns blue, at least someone has casted a no vote. Let's see again how the logarithmic nature of pH affects if 10 people votes with this solution. The gray area shows the transition range of thymolphthalein where we cannot say for sure what the color would be.

   

5. To check the results, you could add thymolphthalein in both the original solutions to ensure it works as expected. After that, mix everything together to prevent more accurate measurement of the pH or the volumes afterwards, as it can reveal the exact vote counts.

Answer 10

With household items: Everyone prepares a glass of water, distilled would be best. If you want to vote no, dissolve any amount of salt in your glass. Everyone must stir their glass to prevent stirring motion being a give away.

Simultaneously combine the glasses of water into a pan. Glasses will be submerged in a bowl of water to prevent drops being traced back to the voter. Boil the water off, if there is a salt residue then it was not a unanimous yes vote.

Answer 11

Use layers of encryption, where each family member has a key to only one of the layers.

Step 1: Encryption

At the beginning of a vote, have one member of the family encrypt a simple message that says "Yes, we all want to leave." After the first person encrypts the message with a private key they've just generated, the first person emails it to another family member to encrypt the already-encrypted-message again with their own private key, and then passing it on until all members of the family have added a layer of encryption. This provides an "onion" of encryption, with each member of the family having added a layer of encryption to the message.

Step 2: Decryption

During voting, members email out their real or fake private key. If any fakes are provided, the message cannot be decrypted.

Only when all members of the family have provided their true key to each other, they can all decrypt all layers of the encrypted message.

Step 3: Future voting

If the family decides to hold another vote next year, they'll need to come up with new private keys for themselves and begin the process again from the start.

Answer 12

Trying to keep this as low-tech as possible.

• Everyone is given two small pellets, a steel BB and a plastic airsoft pellet (equal size but different composition).
• Inside the voting booth are two slots, one labeled "Vote" and one labeled "Discard". Each slot leads to an opaque bag. Neither the bags nor their contents can be observed directly.
• The "Vote" bag is pre-populated with several plastic pellets, and the "Discard" bag is pre-populated by several steel pellets.
• If the voter wants to leave, they will place their plastic pellet in the "Vote" slot. If they want to stay they place their steel pellet in the "Vote" slot. The remaining pellet gets placed in the "Discard" slot.
• After everyone has voted, the bags get tested with a rare-earth magnet. If the "Vote" bag is attracted to the magnet, then it contains at least one steel pellet (thus at least one person voted to stay). If it is not attracted to the magnet, then everyone voted to leave.
• The "Discard" bag is the control group. Since it was pre-populated with steel pellets, it should always be attracted to the magnet regardless of the vote.
• Once the result has been determined, each voter visits the voting booth one last time. On this last trip, they can place any number of pellets of either type into either (or both) slots.

This should keep voting anonymous and untraceable. The voting tokens contain no traceable information like handwriting, and the voter uses both of them regardless of their choice. An eavesdropper cannot determine your vote by listening for the sound of the pellet because there's no way to know which bag the voter used first. The magnet allows you to test for the presence of a "stay" vote without directly examining the votes themselves. The final trip through the voting booth adds enough random noise to the data that the original vote counts will be completely unrecoverable by whoever tears down the voting booth.

The only information that leaks from the process is the strength of the attraction between the magnet and the bag's contents. A weaker attraction means fewer "stay" votes. This is an acceptable level of leakage for a couple of reasons. First, attraction strength is not something that humans can quantify without special equipment. Perhaps more importantly, attraction strength will vary considerably based on how the pellets are arranged in the bag (i.e., stronger pull when closer to the magnet). This unpredictability should add a large enough margin of error to any vote count guesses to make those guesses worthless.

The drawback is that this procedure might work for a family but could be tricky if the number of voters grows too large. A single metal pellet mixed in with a large number of plastic pellets could be missed unless you have an unreasonably powerful magnet.

Answer 13

I think this problem can be solved in the following simple low-tech way. Give each voter two rocks, a heavy rock which stands for yes and a light rock which stands for no. Voting is done by putting one of your rocks in a floating object. The object only sinks when all of the voters put their heavy (yes) rock in the floating object.

Answer 14

What you're asking is a system that outputs V = v(1) AND v(2) AND ... AND v(n) where v(i) is the binary vote of the same person. By DeMorgan Law, V = NOT W where W = w(1) OR w(2) OR ... OR w(n) and w(i) = NOT v(i). Hence we can rephrase the question to be simpler. We are only looking for a system that can answer whether:

Of the N people who voted, did at least one vote No?

This follows intuition; if you require unanimous consent then as soon as one person objects it doesn't matter what the rest of the votes are. Or in other words, you are asking for an anonymous veto system.

This can be implemented in many ways.

• An electronic push button switch (labeled "press to stay in cult") in a closed room. The system starts in state 0 and pressing the button puts in state 1. After everyone has had the opportunity to go into the room and secretly press the button, the device is examined to see if anyone has.
• A variation on the above: A button B inside the room that only closes the circuit, and a S outside the room where everyone can see. Both are wired to a light that comes on only if both buttons are pressed. At first S is turned off and B is not pressed. Everyone watches S to make sure it is not prematurely touched, and go inside the room to take turns at possibly pressing B. Once everyone is done, they flip S together to see if B has been pressed during the voting. You can even have multiple rooms, each with their own B connected to the same device, so that voting can happen simultaneously - that way it's not possible to conspire against one voter and flip S right after they vote.
• A mechanical version in the form of a box with a marking in the middle of the inside. A little piece of paper is place exactly on the marker and the box is locked. Every voter has a chance to go in a closed room and shake the box. Once everyone done, the box is opened to see if the paper has moved.
• A more robust version of the above, with many black and white papers arranged in two neat piles (shaking the box would mix them up).

Answer 15

Get some plywood, some small felt (or other soft, non-noisy) balls that are indistinguishable from one another, and some wood screws. Build a box with two holes in the front, one marked "Leave" and the other marked "Stay". It needs to be difficult to disassemble to prevent tampering, so don't skimp on the screws. Each hole leads to a ramp which will deposit a ball in the bottom of the box, however, the "Stay" hole has a notch the size of one ball. Attach the box to the wall (to prevent anyone from tilting it). Set up a "voting booth" of sheets or something around it to keep anyone from seeing another person's vote, and limit the time each person spends in the booth to just long enough to put their ball in a hole.

If anyone puts their ball in the "Stay" hole, that ball will fall into the notch. Any subsequent "Stay" voter's ball will roll over the the notch (similar to the yellow marble in this video; some tuning may be required to make sure other balls roll over the way they're supposed to) and fall into the bottom, same as the "Leave" votes. Once everyone has had a chance to vote, disassemble the box and see if there's a ball in the notch.

Answer 16

Start with an identifiable plaintext: Let's break up. It's not you, it's all of us.

Each person generates a random bit pattern (one-time pad) and keeps it secret. Pass the message around the table, with each person XOR-ing it with their one-time pad. The person after you will be the only one who sees your output.

When you get back to the beginning of the circle, go round once again in the same order. This time, if you want to vote "yes", XOR the message with the same pattern you used before. If you want to vote "no", use a different randomly-generated pattern (again, keep it secret).

At the end of the second circuit, obey the resulting message: either break up, or sdfljhsdfhgvsladfj. In the latter case, nobody will know how many "no" voters were responsible for failing to unscramble the message.

This is very similar to Nick Bonilla's answer, except that the keys are not generally shared. If the family members are A through Z: Bob will be able to compare Alice's first output with the original plaintext, and so will be able to infer Alice's first secret, but will not know whether this was the same as Alice's second secret (only Zach knows Alice's second input). Yolanda will be able to compare the final public message with her own second output, and so will be able to infer Zach's second secret, but she will not know whether this was the same as Zach's first secret (only Alice saw Zach's first output). In the case of N=3, Bob and Yolanda are the same person, but I'm not sure this helps him/her.

Answer 17

This can be reduced to the dining cryptographers problem.

The protocol is relatively simple.

1. Get some dice for generating uniform numbers in the range 0..M-1.

2. Arrange everyone in a circle, so that they are next to two people: one to the left, and one to the right.

3. Everyone meets with their partners and generates a shared secret, a uniform number in the range 0..M-1. Each person ends up with two shared secrets because they are paired with two people.

4. Everyone goes off by themselves, and generates a personal secret, also a uniform number in the range 0..M-1.

5. Everyone submits a number on a piece of paper.

   • If they vote remain, they submit their personal secret number.

   • If they vote stay, they submit the left secret minus the right secret, reduced modulo M.

6. All votes are added up and reduced modulo M. If everyone voted to stay, then the result is 0, since all the shared secrets will appear once positive and once negative. If anyone voted to leave, the result is a uniform random number in the range 0..M-1.

So,

• If all participants vote “leave”, the result will be “leave”.

• If any participant votes “stay“, the result will be “leave” with probability 1/M and “stay” otherwise.

Answer 18

1. Call the number of people N.
2. Each person is assigned a number from 1 to N.
3. Each person creates a random N-order polynomial whose Y-intercept is zero if they wish to vote YES or whose Y-intercept is greater than zero if they wish to vote NO.
4. Each person solves the equation of their polynomial for discrete points from X=1 through X=N.
5. Each person passes the solution for each integer value of X from 1 to N to the person with that corresponding assigned number.
6. Each person sums all their assigned numbers and discloses the sum.
7. The resulting disclosed sums are used as the solutions to an N-order polynomial that goes through the corresponding points.
8. The Y intercept of that resulting polynomial is computed using Lagrange interpolation. (Or any other convenient method if N is small.)
9. If the Y intercept is zero, the result is YES. Otherwise, it's NO.

This works because the sum of any number of polynomials with a zero Y-intercept is a polynomial with a zero Y-intercept. No combination of participants less than all of them has enough points on any polynomial to determine its Y-intercept but of the resulting final curve because everyone discloses their sum point on that one.

You need N points on an N-order polynomial to determine its Y-intercept. The only polynomial any group smaller than all the participants has N points on is the final resulting sum polynomial. So only its Y-intercept can be determined by any subset of the group less than all of them.

Let's try an example with three people. We'll use Alice, Bob, and Charlie. We'll have only Bob vote NO. Each will pick a random polynomial that requires three points to solve whose Y-intercept is zero for YES and non-zero for NO.

Alice is 1. She votes YES. Her polynomial is Y = 3 (X^2) - 2 X
Bob is 2. He votes NO. His polynomial is Y = 2 (X^2) + X + 1
Charlie is 3. He votes YES. His polynomial is Y = 3 (X^2) - X

Notice that Bob has a "+1" term since he voted NO. Everyone else has no such term, so their curves have a zero Y-intercept.

Alice now solves her polynomial at points 1, 2, and 3.
She gives herself a 1, Bob an 8, and Charlie a 21.

Bob now solves his polynomial at points 1, 2, and 3.
He gives Alice a 4, himself an 11, and Charlie a 22.

Charlie now solves his polynomial at points 1, 2, and 3.
He gives Alice a 2, Bob a 10, and himself a 24.

They each now disclose their sums.
Alice computes 1 + 4 + 2 and discloses 7.
Bob computes 8 + 11 + 10 and discloses 29.
Charlie computes 21 + 22 + 24 and discloses 67.

They now need to solve the curve that goes through the points (1,7), (2,29) and (3,67) to see what its Y-intercept is. The solution is Y = 8 (X^2) - 2 (X) + 1.

You'll notice that this equation is the sum of the chosen equations. And it has a "+ 1" on the end because of Bob's vote. Thus, the result is NO, as required. But nobody but Bob can tell whose curve had that "+ 1" on it (unless everyone else conspires against him).

This is a slight variant of the JZSS (Joint Zero Secret Sharing) algorithm. See M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness Theorems for Noncryptographic Fault-Tolerant Distributed Computations, Proceedings of the 20th ACM Symposium on the Theory of Computing, pages 1-10, 1988.

Answer 19

There are two empty cloth bags, and a pan-scale. The first bag represents how they want to vote, the second as a check.

Each person is given two clay or wood discs of slightly different weight. The heavier disc represents leave. They place the disc for their vote into one bag, and the other in the other bag. Afterwards, the bag is checked against a weight. The pan will just balance if all votes are for leave, but will remain fully down if even one is for stay.

If necessary, both bags can be weighted together against another weight to ensure there's been no skulduggery.

Once the vote is checked, both bags are destroyed in a fire.

Answer 20

I took some inspiration from Qmppu852's answer, I'll try to make it simpler:

Get a generator and a really long cable, 10 meters (that's ~30 feet) should do.

Build multiple controllers, one for each family member. Each controller will have two buttons: one is a dummy, which does nothing. The other button is meant to close the circuit. Both buttons are visibly marked so everyone knows which is which.

Splice the controllers on the cable. Since they are all connected serially to the generator, the circuit is only closed while all the non-dummy buttons are pressed simultaneously.

When the voting time comes, everyone sits on a circle. Every family member holds a controller on their back and presses a button. In this way, everyone will see that everyone else is pressing a button, but no one knows which buttons the others are pressing. Every individual only knows which button they are pressing.

If everyone presses the non-dummy button on their controller, the circuit closes. You can connect a light bulb or a buzzer on the circuit so they can see whether it turns on. But I think it's more fun if the generator gives around 50V and the controllers are not insulating. If everyone votes yes, then everyone gets a jolt.

If anyone votes no, then the circuit does not close. But no one knows who is voting for no. To make it even harder to know everyone's vote, they could wear gloves so as not to leave fingerprints on the buttons. Or they could press both buttons prior to the vote, before activating the generator, to leave fingerprint on both buttons.

Answer 21

Take a simple calculator, enter a number. Place it in a stiff box with a hole in it over the clear button. Put the whole thing inside another box with an opening on the side and a piece of cloth draped over the opening.

Everyone reaches into the outer box and pushes something--the clear button to vote no, any other spot to vote yes. An observer might be able to discern the muscle movement of pressing but they certainly can't tell if you're actually on the button.

Remove the calculator, examine it. If there's still a number you have a unanimous yes.

Answer 22

Play a game of telephone. But with numbers.

Have people sit in a circle, and have 1 person start. They pick a random number between 1 and 1000 and keep it secret. Then they whisper that number into the ear of the person on their left. Then that person adds 1 to that number if "no", and they add 100 that number if "yes". That person then whispers the new number to the person on their left. This continues in a circle, making 2-3 "laps" around the group. The last person to receive a number keeps it a secret.

No one knows the starting number except the first person, but they know what number they said to the person on their left. If the 1's digit and 10's digit of the number they said and the number they received when it came around again is the same, then they know that everyone voted yes. If it's not the same, then they know that at least one person voted no.

The important thing is that because they don't know the starting number, and there's no definite end to the loop, they don't know who voted with what number. Everyone now knows if the vote is unanimous, but no one knows who voted what.

EDIT: Instead of adding 100 for yes and adding 1 for no, pick a random number between 1 and 5. If voting yes, multiple it by 100. If voting no, multiply it by 1. Then add that number to the running total and pass the running total to the next person. This solves the issue of leaking how many people voted yes or no.

Answer 23

Construct a container which can have liquid poured into it but cannot be easily observed without obvious tampering. Something like an opaque fuel canister which has a nozzle attached to it.

Everyone gets a chance to add some clear liquid to the container.

Everyone votes by being able to either add some red dye, or pour some red dye down the drain.

At the end, the container is broken open and the contents is revealed. If it contains any amount of red dye then the vote was not unanimous.

Answer 24

Interesting problem. Low tech: A third party gives each voter two identical pieces of paper: one with typewritten "yes" the other with "no" (or some other symbol, 1/0, y/n, etc) This is the end of the third-party involvement. They adjourn to a private area where they can secretly select one piece of paper with their desired answer. All return and simultaneously place their vote in the ballot box which is shaken to randomize.

Although theoretically it may be possible to determine the source of the minority vote, even to the point of DNA sampling from the paper, in the real world even the most paranoid have some practical limitations and methods of control - e.g. burn the ballots after counting.

Medium-tech: hard-wire a relay/flip-flop in series with a "tally" switch that will complete a circuit to turn on a light or similar indicator. There is only one vote button, concealed from the tally button (e.g. in another room, box, etc), the tally button is public so it cannot be touched without witnesses.

Once everyone has a private opportunity to press (or not) the vote button, then together they flip the switch that will complete the circuit if the relay/flip-flop was triggered. In other words, flipping the tally switch only completes the circuit if the vote button was pressed by someone. Because the vote is private, there is only one button and it operates on a single point in the circuit (i.e. the relay or flip-flop, which can only be tripped once) there is no traceback to who tripped the vote.