Sleator's "cheapo" plan for semi-secure voting

By Danny Sleator with Warren Smith.

CMU professor and computer scientist Danny Sleator objected that the Rivest/Smith ThreeBallot, VAV, and similar secure voting plans, although about as simple as could possibly be hoped for, still were either just too complicated or too great a change in current procedures, to easily gain acceptance. To overcome that, Sleator invented the following, which I call in his honor, the "cheapo" plan. It is simpler and easier, at the cost of providing somewhat less security.

The plan

We use a normal optical scan ballot, except that each ballot has a serial number on it. When I'm about to vote, with probability say p≈1%, I'm selected to be a "receipt voter." Otherwise I'm a regular voter. If I'm a regular voter, I just mark my ballot, check it with the machine, and put it in the ballot box. If I'm a receipt voter, then the machine issues me a duplicate copy of my ballot which I take home with me.

Then, just like the ThreeBallot system, all ballots are posted on a web site, along with the corresponding serial number. The voters who get receipts can check that their vote has been properly posted. Any large scale fraud would be provably detected because it would have overwhelming probability of modifying many of the receipt votes. It's of course essential that nobody know which voters (or which serial numbers) got receipts.

Slight security hole: The receipt voter could sell his vote. But the incentive is pretty small, since I'll only get a receipt with such a small probability. You should probably know whether or not you're going to get a receipt immediately before you vote. So vote buying can only affect a maximum of 1% of the voters.


1. The value p≈1% may be too small. If the government decides to cheat and move the election by 1% to swing it, then the total number of voters who are proveably defrauded=1%*1%, the total number of voters who are provably defrauded and protest=1%*1%*1%, which is 1 in a million. That might not be high enough. (The government could just round up the few protestors and shoot them, at that point.) Perhaps a better value is p≈10%. (Sleator's point is, whatever is the best value of p, must be better than the current system which has p=0.)

2. Bundling multiple races onto one ballot is a big mistake because then a giant number of patterns are possible on that ballot, allowing the voter to sell his (uncopied) vote to a bidder who specifies the full pattern and looks on the bulletin board later to be sure it got posted. This remark rather hurts Sleator's original intent of staying as close as possible to current procedures.

Sleator responds to this bundling criticism: Suppose we fix it this way. Each race (or each candidate in the case of range voting) on each ballot has its own serial number. The presentation on the web site is totally unbundled. However, for simplicity to the receipt voter, the whole thing is copied and left bundled. This should work fine.

The thing I haven't really figured out cleanly is how to make sure that the pollworkers don't end up knowing which ballots were copied and which weren't. Maybe everybody gets a folded up piece of paper when they leave. The receipt voters get a copy. Everybody else gets garbage. The instructions on the outside of the paper says "Open this when you get home. If it's a receipt, check it against the web site, otherwise just throw it out."

3. Collusive attacks were discussed in the old 3ballot full details page. Sleator's cheapo scheme is vulnerable to them too (although by adjusting the value of p we can hope to get the optimal tradeoff between vulnerability to vote-buying and vulnerability to collusive attacks). It is possible to use the same fixes we recommend there to defend against those attacks, also here, but that makes it more complicated, which goes against Sleator's game plan of keeping everything maximally simple.

Return to main page