High hopes for unscrambling the vote

Tue Jun 8 07:30:37 EDT 2004

<http://news.com.com/2102-1028_3-5227789.html?tag=st.util.print>

CNET News
     http://www.news.com/

 High hopes for unscrambling the vote

 By  Declan McCullagh
 Staff Writer, CNET News.com
 http://news.com.com/2100-1028-5227789.html

 Story last modified June 8, 2004, 4:00 AM PDT

PISCATAWAY, N.J.--Computer scientists gathered here recently and bobbed
their heads into an odd-looking contraption for a glimpse of emerging
technology that might just help make the digital world safer for democracy.

 Beneath the viridian green glow of a viewfinder flowed an inch-wide strip
of paper that inventor David Chaum says will prove with mathematical rigor
whether a vote cast on a computer in a ballot box has been tampered with
after the fact.

 The system was demonstrated publicly for the first time at a Rutgers
University voting conference late last month. The technology builds on the
increasingly popular notion that computerized voting machines need to leave
behind a paper trail to safeguard against fraud--something that's lacking
in most current models and the subject of furious debate.
 News.context

What's new:
 Computer scientists are developing cryptography techniques that promise
powerful new tools for verifying computerized voting results.

 Bottom line:The technology is still in its prototype stage--but a bigger
obstacle may be whether notoriously conservative voting officials can be
convinced to try something new.

 More stories on this topic

 Chaum has raised the concept to an entirely new level, according to
electronic-voting experts, by including breakthrough cryptographic
techniques that will provide instant feedback on irregularities while
ensuring voter anonymity. While still a clunky prototype, the system could
represent the next evolutionary step in improving the security and
reliability of the voting process, some believe.

 "The math is fine," said Ron Rivest, a professor of computer science at
the Massachusetts Institute of Technology and the co-creator of the popular
RSA encryption algorithm. "I view this as the early days of the practical
applications...The paradigm is a new and interesting one. I'm optimistic."

 Chaum is not alone among researchers vying to better voting's state of the
art. Fed up with what they view as antediluvian punched cards and
mechanical lever systems--and with an eye to the problems of the 2000
Florida recount--scientists are borrowing from decades of academic work to
invent systems that are probably secure against malfeasance.   Their
inventions are also designed to one-up current electronic voting machines
that have limited audit capabilities and may include bugs that
surreptitiously alter vote totals.

 "I'd like to think that we have some" influence, said Josh Benaloh, a
cryptographer at Microsoft Research. "All acting en masse, maybe we'll have
an impact."

 Encrypted receipts
 The leading contenders so far, independently created by Chaum and
mathematician Andrew Neff, represent two variants of a voting technology
that uses encrypted printed receipts to solve many of the problems that
have bedeviled existing hardware. These prototypes work in the lab. But one
obstacle may be whether notoriously conservative voting officials can be
convinced to try something new.

 The idea of having computerized voting machines produce paper receipts,
providing a physical record that can be audited, is belived among voting
experts to be a useful safeguard against fraud. But some counties that have
already installed printerless, computerized voting systems oppose any
requirement that they add new equipment to provide paper receipts of any
kind.

 Other proposals for providing paper receipts in computerized voting
systems include attaching printers to voting machines that spit out a hard
copy of votes recorded below a glass barrier.  Once voters reviewed the
receipts and confirmed that they were accurate, the receipts would be
placed in a secure box. If a recount were required, voting officials would
open the boxes and proceed to tally up the results by hand.

 Critics of this type of receipt argue that the end product is little
better than a punch card ballot, subject to many of the same kinds of
miscount problems that plagued the Florida election in 2000. Encrypted
systems like Chaum's, on the other hand, would not be vulnerable to many of
those flaws, because only the records that were tampered with would be
subject to verification in a recount. In addition, tampering could be
detected the moment a voter left the polling station.

 Chaum, who declines to give his age for privacy reasons, boasts a dazzling
resume as one of the brightest computer scientists of the 1980s, whose
ideas led to the creation of anonymous remailers, privacy-protecting Web
browsing techniques and secure electronic cash. He returned to the topic of
secure voting four years ago and came up with his crucial
innovation--encrypted receipts on plain paper--in late 2003. Chaum owns
patents covering the use of the technology.

 Quantum voting

Today's electronic voting systems rely on the arcane science of
cryptography to guarantee that votes aren't altered or intercepted.

 But what if encryption stopped being secure one day?

 That's not likely to happen any time soon, but a still-to-be-invented
quantum computer could do just that. When working at Bell Labs in 1994, a
mathematician named Peter Shor demonstrated that a quantum computer could
break popular public-key encryption algorithms.

 As its name implies, such a computer would adhere to the laws of quantum
mechanics. That means it could be in multiple states at once (rather than
limited to the on-off binary state of today's processors), making it far
more adept at handling the permutations of any encryption scheme.

 "Sometime this century, a quantum computer will be readied," said Tatsuaki
Okamoto, a researcher at NTT Labs in Japan. "Then (all existing electronic
voting systems) will disappear."

 Okamoto has a potential solution: a quantum voting system. It would rely
on untappable quantum channels, "blank quantum pieces" and complex
mathematics, but Okamoto says it works in theory. If quantum computing is
decades away, he should have plenty of time to make it work in practice,
too.

 After the Florida recount debacle, "I decided that maybe there was a
chance that these systems would be used," Chaum said. "But I needed to find
a way to make them practical."

 Chaum's insight was to invoke the logic of cryptography to prove that
votes can't be changed after the voter leaves the polling booth. For each
voter, his machine prints bar code-like dots on two strips of paper that,
when combined under the carefully angled lens of a custom viewfinder,
reveal the name of the candidate in plain English. The voter can keep only
one encrypted strip as a receipt for use in post-election auditing--but
without its mate, an individual strip will not reveal which candidate was
chosen.

 For cryptographers, the inherent beauty of such a system is that it
safeguards privacy and security--and doesn't require voters to trust the
government or untested software on a voting machine. "The next real issue
is, 'When can I buy it?'" said Chaum, who created a company called
Votegrity to develop and sell the hardware. "That's why we have to
aggressively push forward with the company at this stage to make it an
option." He is looking for investors and a CEO to bring his system to
market.

 This isn't the first time that Chaum has launched a start-up with a clever
idea and a sheaf of patents. A decade ago, he founded the pioneering
DigiCash company, but it ended up filing for Chapter 11 bankruptcy
protection in 1998. Chaum said voting systems are an easier sell because
digital cash wasn't attractive until many people were using it--a catch-22
that ultimately doomed the plan.

 Injecting encryption into elections, central to both the Chaum and Neff
systems, began receiving serious attention after a group of top scientists
convened a small workshop in Tomales Bay, Calif., nine months after the
Florida recount. At the May 26 and 27 conference sponsored by Rutgers
University's DIMACS computer science center this year, experts in the field
seemed ready to accept that the Chaum and Neff systems were secure enough
to be used in a real-world election.

 "It's an important step forward," Moti Young, a professor of computer
science at Columbia University, said of Chaum's design. "I don't see any
bugs. It's technically very sound."

 Poorvi Vora, an assistant professor of computer science at George
Washington University, is also enthusiastic. Vora and her graduate students
wrote their own software, based on Chaum's two-strip concept, and
demonstrated it at the Rutgers conference.  Instead of using a custom
viewfinder, they printed on transparencies that can be laid on top of each
other on an overhead projector.

 But not everyone in the e-voting community is so enthusiastic about the
Chaum and Neff systems. Rebecca Mercuri, who wrote her Ph.D. dissertation
on electronic vote tabulation, said she remains skeptical.

 "I can read the math," Mercuri said. "I am holding the bar very very
high...I will continue to serve as a skeptic. I have not been convinced
yet. It does not exist in the form where people can use it yet."

 VoteHere's take on encryption
 Chaum isn't the only contender seeking to bring encryption to the voting
verification process. A similar cryptographic system was invented by Neff,
who holds a doctorate in theoretical mathematics from Princeton University
and is now the chief scientist at VoteHere in Bellevue, Wash. Neff's
invention also draws from mathematics but does not require a viewfinder
that combines two receipts into a human-readable ballot.

 Instead, VoteHere's patented system prints personalized, encrypted
receipts for each voter. A vote for president could be represented as
"DGA1," and governor as "3QLK." After the election, voters can confirm that
their vote was counted by checking the county Web site to make sure the
encrypted sequence corresponds to what's posted. Or, if they choose, they
can hand their receipt to a trusted organization like the League of Women
Voters and ask them to do the verification.

 "It's conceptually easy," Neff said during an interview at the conference
sponsored by Rutgers University's theoretical computer science center. "But
it has to be plugged into the process that (voting machine) vendors use."

 Concocting arcane mathematical formulae is almost trivial, compared with
the arduous process of convincing vendors and state election officials to
adopt verifiable, encrypted systems. Neither group is known as an
aggressive early adopter of new technologies.

 Hundreds of millions of dollars are at stake. State governments are racing
to install electronic voting machines as a result of the federal Help
America Vote Act, which was enacted after the 2000 election and gives
states hefty federal grants if they meet certain deadlines.

 One key date: Any state accepting those grants must replace all its punch
card and lever machines by Nov. 2, 2004. Because of that looming deadline,
many states have already bought replacements for their oldest systems and
are reluctant to write a second set of checks to add encrypted receipt
technology. In addition, Chaum's system won't be in production until after
the November election.

 Neff expressed frustration at the difficulty of convincing voting vendors
such as Diebold Election Systems to license VoteHere's technology and
produce encrypted receipts. "They're just not technically savvy," Neff
said. "They've got incredibly limited technical abilities, and they're
desperately clinging to the hope that all this (concern about e-voting)
will blow over. They want to sing the praises of the little box they plop
on someone's table and not worry about it. The other conjecture is that
somewhere, they appreciate the fact that, moving toward the future, the
verification technology follows what Microsoft did to hardware in the early
days. It becomes more important than the box."

 So far, Neff's VoteHere company has inked a deal with Sequoia Voting
Systems to license its encrypted receipt technology, though it's
nonexclusive. Unlike Chaum's system that requires a special viewfinder, any
electronic voting machine equipped with a printer can produce the receipts.
State election officials aren't exactly biting, but Neff says "it looks
very realistic that we can do a pilot in California or Maryland for the
November election."

 Diebold has attracted the most criticism of any e-voting machine maker. In
April, the California Secretary of State took the drastic step of banning
Diebold-made systems from being used in some counties. Last November,
California began investigating allegations of illegal vote tampering with
Diebold machines. An earlier blow came in June 2003, when university
researchers concluded that a voter could cast unlimited ballots without
detection.

 Neff of VoteHere acknowledged that encrypted ballots aren't a complete
solution for all voting problems. For instance, election officials must be
trusted to prevent people from voting twice under different names or at
multiple voting locations. "We've addressed 80 percent of the threats and
100 percent of the really bad threats," Neff said. "We can't (seem to) get
beyond that remaining 20 percent."

 But skeptic Mercuri argued that even that number is optimistic. "I don't
agree you've addressed 80 percent of the threats," she said. "It depends on
your threat model."

Related News
	* 	Fight over e-voting leaves election plans as casualties  May 20, 2004
http://news.com.com/2100-1028-5216643.html

	* 	California votes against Diebold  April 22, 2004
http://news.com.com/2100-1028-5197870.html

	* 	E-voting smooth on Super Tuesday  March 2, 2004
http://news.com.com/2100-1028-5168670.html

	* 	Voting machine fails inspection  July 24, 2003
http://news.com.com/2100-1009-5054088.html

	* 	Get this story's "Big Picture"
http://news.com.com/2104-1028-5227789.html

-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com