November 25, 2008
Who would judge a contest for voting machines?
In a previous entry I suggested creating an AES-style competition for automated voting systems. The idea is to throw the design open to the world's expertise on complex systems, including universities, foundations and corporates, and manage the process in an open fashion to bring out the best result.
Several people said "Who would judge a contest for voting machines?" I thought at first blush that this wasn't an issue, but others do. Why is that? I wonder if the AES experience surfaced more good stuff than superficially apparent?
If you look at the AES competition, NIST/NSA decided who would be the winner. James points out in comments that the NSA is indeed competent to do this, but we also know that they are biased by their mission. So why did we trust them to judge honestly?
In this case, what happened is that NIST decided to start off with an open round which attracted around 30 contributions, and then whittled that down to 5 in a second round. Those 5 then went forward and battled it out under increased scrutiny. Then, on the basis of the open scrutiny, and some other not-so-open scrutiny, the NSA chose Rijndael to be the future AES standard.
Let's hypothesize that the NSA team had a solid incentive to choose the worst algorithm, and were minded to do that. What stopped them doing it?
Several things. Firstly, there were two rounds, and all the weaker algorithms were cleaned out in the first round. All of the five algorithms in the second round were more or less "good enough," so the NSA didn't have any easy material to work with. Secondly, they were up against the open scrutiny of the community. So any tricky choice was likely to cause muttering, which could spread mistrust in the future, and standards are susceptible to mistrust. Thirdly, by running a first round, and fairly whittling the algorithms done on quality, and then leading into the second round, NIST created an expectation. Positively, this encouraged everyone to get involved, including those who would normally dismiss the experiment as just another government fraud, waiting to reveal itself. At a more aggressive extreme, it created a precedent, and this exposed the competition to legal attack later on.
These mechanisms worked hand in hand. Probably, either alone was not sufficient to push the NSA into our camp, but together they locked down the choices. Once that was done, the NSA saw its natural incentives to cheat neutered by future costs and open scrutiny. As it no longer could justify the risk of cheating, its best strategy was to do the best job, in return for reputation.
The mechanism design of the competition created the incentives for the judge to vote how we wanted -- for the best algorithm -- even if he didn't want to.
So, we can turn the original question around. Instead of asking who would judge such a competition, design a mechanism such that we don't care who would judge it. Make it like the AES competition, where even if they had wanted to, the NSA's best strategy was to choose the best. Set yourself a challenge: we get the right result even when it is our worst enemy.
Thank you so much for pursuing this. Humanity has never had a secure platform worth a crap. So many of our most intractable problems can be reduced by secure platforms-- not only the obvious problems like secure identification and communications, and the need to automate our banking transactions but second tier problems like transportation that are fundamentally limited by trust issues, automating car navigation which again depends on much higher security and reliability, etc. etc.
A secure platform is one of the key problems that must be solved in order to decentralize many of the activities now concentrated into downtowns, and carried out manually, causing high costs and wasting petroleum.
Posted by: Todd at November 25, 2008 07:00 PMHmm...
Your analysis of NSA behaviour with regard to AES may not be valid.
It appears to be based on an assumption that the open crypto community is as well versed in analysis as the NSA.
This is a risky assumption to make as demonstrated in the past with DES and the fact that they have significantly more resources both human and technical than the entire open crypto community.
Now a possible senario based on an assumption that they have one or more undisclosed techneques currently unknown to the open crypto community.
1, NSA call for submissions and reject all that fail against published attacks from the open crypto community.
2, The open crypto community then put their weight behind attacking the remaining submissions.
As part of this process they effectivly reveal the latest "state of the art" in the open crypto community to the NSA.
3, now knowing what the open crypto community know and are showing signs of discovering in the way of attacks, the NSA can then filter their unknown attacks to see which is most likley to remain unknown for the longest.
4, The NSA having made a selection of their uknown attack(s) then select which submission left after the open crypto community mauling is going to be vulnerable to the attacks.
If you remember back to the AES final selection there was some surprise expressed in the open crypto community that the "bricklayer" functions did not have a high non linear complexity.
So yes I can easily see why a number of people would be somewhat cautious about the judges selected.
However irrespective of if the NSA has done this (which I put at a low probability) does it actually change the result in any way?
Afterall any new attack is likley to effect considerably more than one crypto alg as they had effectivly been filtered against the same "strengthaning techniques".
Posted by: Clive Robinson at November 28, 2008 08:04 AMThese are great points. Thanks for this discussion.
A minor note: In the AES process, by the time we got near the end of the process, a front-runner had emerged and the research community was, if not at rough consensus, somewhere in the vague neighborhood of a rough consensus. I remember a straw poll at one of the AES conferences (maybe it was the last one?) where attendees were asked to vote for one of the five finalists, and Rijndael had a clear lead over any other candidate. There were of course plenty of votes for the other four, and the poll was entirely informal and unscientific and probably flawed in a dozen ways, but still, Rijndael seemed to be the cipher to beat. So in that particular case, NIST's choice was somewhat easier than it could have been. True, NIST could have picked some other cipher, but they probably would have had to justify such a choice pretty well. It's interesting to think about how to set up such a competition so that the same incentives apply even if the choice doesn't turn out to be so clear-cut.
Posted by: Anonymous at December 31, 2008 11:10 PM