Assignment 9, due Apr 19

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday), and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

1. Background: All of Cham's end-to-end auditable voting system proposals rest on the use of mix net decryption to protect a voter's right to a secrtet ballot. The encrypted contents of the ballot box are published, so voters may verify that their encrypted ballots are in fact included in the count, and in theory, the use of mix net decryption prevents anyone from knowing which ballot was whose at the end of the decryption process. (Google any of the italicized terms above for detail.)

   The parts of this question have to do with the "in theory" statement above. One obvious threat to voter privacy occurs when the key custodians (each of whom provides the key to one stage of the mix net) collude to violate voter privacy. If a single custodian remains honest, voter privacy is assured. This question asks what other threats to voter privacy exist in a mix-net-based system.

   a) Each stage in the mix net requires a computer and software. As the exclusive provider of this equipment, what threat do you pose? (0.5 points)

   b) What attack could the custodian of the key to the final mix make if he knew that his stage of the mix net would not be subject to challenge. (0.5 points)

2. Background: There one model for providing a public test of the integrity of an N-layer mix net is as follows:

   After the totals are computed, require randomly selected key custodians to reveal the keys to some stages of the mix net so that all computations performed by that stage can be independently checked.

   a) How many key custodians should reveal their keys? How does this depend on our degree of confidence in the integrity of the key custodians. Suppose we suspect that k out of N custodians may be dishonest, but we don't know which ones. (0.5 points)

   b) What are the constraints on the disposition of the intermediate versions of the ballot produced between consecutive mixnet stages. Should these be disclosed, when and to whom. (0.5 points)

3. Background: One way to test a voting system is to add a number of test ballots to the ballot box during the election, where test ballots are all votes for a fictional candidate named TEST BALLOT, and then verify that these ballots emerge from the final stage of the mix. These ballots are, of course, ignored in the election results.

   a) Adding test ballots to the ballot box looks like ballot box stuffing. How could you verify, or indeed, could you verify that the ballot box had not been stuffed in a mix-net-based voting system where test ballots were used. (0.5 points)

   b) In Internet-based voting systems, voting the test ballots described here can be used to deal with several threats outside the realm of mix-nets. Identify such a threat and describe how voting the test ballots can help detect or defend against it. (0.5 points)

4. Background: For each link in the end-to-end verification chain given below, describe who does it, whether the test is public or private, and how to achieve 99% confidence that the election is correct (that is, that no more than 1% of the ballots are corrupt).

   a) The voter's ballot was correctly deposited in the ballot box. (0.5 points)

   b) The mix net operated correctly. (0.5 points)

5. Background: Suppose that two parties use the Diffie-Hellman algorithm to create a shared secret value. Unfortunately, both of them are worried about the possibility of data corruption. There are several ways that they can assure themselves that the shared secret value they have created is in fact correctly shared without revealing this value to the world.

   a) Explain how they can demonstrate this by exchanging nonces. (0.5 points)

   b) Explain how they can demonstrate this by exchanging encrypted messages. Make sure you clearly distinguish your answers to parts a and b. The data flow involved is distinctly different. (0.5 points)