I've seen many proposed implementations but they all fail because if I can prove my vote to myself in any way, someone else can make me prove it to them either to buy or coerce my ballot.
If the 'real' code shows one thing and the 'fake' codes another what assurance do you have that the counting was done with your 'real' code and the voting machine didn't put another one in there?
1) When voters enter the booth, they throw a large number of multi-sided dice.
2) The resultant throw is scanned via computer-vision. Voter verifies it is correct, and it becomes the voter's ID. Voter votes normally and the vote is recorded alongside that generated "ID".
3) The voter receives a print-out that contains their (ID, vote), however it is randomly shuffled in among other real (ID, vote) pairs. The print-out is guaranteed to have at least one vote for each candidate.
4) The entire list of (ID, vote) pairs can be published nationally. Everyone can verify that the right number of votes were counted, and that their vote was accurately counted since they can find both their ID and vote in the national list.
They can show their receipt to others but cannot prove which one of the many IDs on the receipt was actually theirs.
I can see that working, particularly part 3 there being key.
Seriously I've been asking for years and this is the first time anyone's actually spelled out a scheme that allows the person to go back and prove the vote to themselves and have genuine plausible deniability to others who may seek to coerce them. Thanks :)
Vote: 0 for Gore, 1 for Bush
Provide, in the polling booth: a random salt of either 0 or 1
Publish: vote XOR salt
Now, the issue becomes obvious - if someone can falsify votes, why can't they falsify salts as well? Less obviously, this is true of any verification system - abstractly, you can always count the vote one way, and "verify" it the other way. So what you have to do is have completely different possession chains for the vote roll and the salt roll. Make it so that at no point does any one person have access to all three of 1) the voter id, 2) the vote cast, and 3) the salt. This means that nobody has the required information, or access, to undetectably falsify a vote.
Extending this to handle more than two options, and making it easy enough to comprehend that the average voter won't get caught out if they try to lie, is left as an exercise for the reader. But it's possible.
In any case it was only meant as an existence proof, not a practical system. I like aeternus's suggestion much more, since it has the useful property that everyone can see all the votes - just not whose is whose. (Although I'm not sure what function the receipt serves)
There is a way to prove that your vote was counted without being able to prove what you voted for by using homomorphic encryption. So, if someone wanted to coerce you or pay you for voting at all for whomever you want, they could do it, but that's fine. Microsoft is actually working with Galois on a system operating on this principle, and here's a good video explaining the basic concepts of how it works.