October 13, 2024

Posts Comments

On the future of voting technologies: simplicity vs. sophistication

December 3, 2008 by

Yesterday, I testified before a hearing of Colorado’s Election Reform Commission. I made a small plug, at the end of my testimony, for a future generation of electronic voting machines that would use crypto machinery for end-to-end / software independent verification. Normally, the politicos tend to ignore this and focus on the immediately actionable stuff (e.g., current-generation DREs are unacceptably insecure; optical-scan is the best thing presently on the market). Not this time. I got a bunch of questions asking me to explain how a crypto voting system can be verifiable, how you can prove that the machine is behaving properly, and so forth. Pretty amazing. What I realized, however, is that it’s really hard to explain crypto machinery to non-CS people. I did my best, but it was clear from conversations afterward that a few minutes of Q&A did little to give them any confidence that crypto voting machinery really works.

Another of the speakers, Neil McBurnett, was talking about doing variable sampling-rate audits (as a function of how close the tally is). Afterward, he lamented to me, privately, how hard it is to explain basic concepts like what it means for something to be “statistically significant.”

There’s a clear common theme here. How do we explain to the public the basic scientific theories that underly the problems that voting systems face? My written testimony (reused from an earlier hearing in Texas) includes links to papers, and some people will follow up. Others won’t. My big question is whether we have a research challenge to invent progressively simpler systems that still have the right security properties, or whether we have an education challenge to explain that a certain amount of complexity is worthwhile for the good properties that can be achieved. (Uglier question: is it a desirable goal to weaken the security properties in return for greater simplicity? What security properties would you sacrifice?)

Certainly, with our own VoteBox system, which uses a variation on Benaloh‘s voter-initiated ballot challenge mechanism, one of the big open questions is whether real voters, who just want to cast their votes and don’t care about the security mechanisms, will be tripped up by the extra question at the end that’s fundamental to the mechanism. We’re going to need to run human subject tests against these aspects of the machine design, and if they fail in practice, it’s going to be a trip back to the drawing board.

[Sidebar: I’m co-teaching a class on elections with Bob Stein (a political scientist) and Mike Byrne (a psychologist). The students are a mix of Rice undergrads, most of whom aren’t computer scientists. I experimentally built a lecture that began by teaching just enough number theory to explain how El Gamal cryptography works and how it allows for homomorphic vote tallying. Then I described how VoteBox uses this mechanism, and wrapped up with an explanation of how to do Benaloh-style challenges. I left out a lot of details, like how you generate large prime numbers, or how you construct NIZK proofs, but I seemed to have the class along with me for the lecture. If I can sell the idea of end-to-end cryptographic mechanisms to undergraduate non-science students, then there may yet be some hope.]

Filed Under: Uncategorized Tagged With: , , , , ,

Watching Google's Gatekeepers

December 1, 2008 by

Google’s legal team has extraordinary power to decide which videos can be seen by audiences around the world, according to Jeffrey Rosen’s piece, Google’s Gatekeepers in yesterday’s New York Times magazine. Google, of course, owns YouTube, which gives it the technical ability to block particular videos — though of course so many videos are submitted that it’s impractical to review them all in advance.

Some takedown requests are easy — content that is offensive and illegal (almost) everywhere will come own immediately once a complaint is received and processed. But Rosen focuses on more difficult cases, where a government asks YouTube to take down a video that expresses dissent or is otherwise inconvenient for that government. Sometimes these videos violate local laws, but more often their legal status is murky and in any case the laws in question may be contrary to widely accepted free speech principles.

Rosen worries that too much power to decide what can be seen is being concentrated in the hands of one company. He acknowledges that Google has behaved reasonably so far, but he worries about what might happen in the future.

I understand his point, but it’s hard to see an alternative that would be better in practice. If Google, as the owner of YouTube, is not going to have this power, then the power will have to be given to somebody else. Any nominations? I don’t have any.

What we’re left with, then, is Google making the decisions. But this doesn’t mean all of us are out in the cold, without influence. As consumers of Google’s services, we have a certain amount of leverage. And this is not just hypothetical — Google’s “don’t be evil” reputation contributes greatly to the value of its brand. The moment people think Google is misbehaving is the moment they’ll consider taking their business elsewhere.

As concerned members of the public — concerned customers, from Google’s viewpoint — there are things we can do to help keep Google honest. First, we can insist on transparency, that Google reveal what it is blocking and why. Rosen describes some transparency mechanisms that are in place, such as Google’s use of the Chilling Effects website.

Second, when we use Google’s services, we can try to minimize our switching costs, so that moving to an alternative service is a realistic possibility. The less we’re locked in to Google’s service, the less we’ll feel forced to keep using those services even if the company’s behavior changes. And of course we should think carefully about switching costs in all our technology decisions, even when larger policy issues aren’t at stake.

Finally, we can make sure that Google knows we care about free speech, and about its corporate behavior generally. This means criticizing them when they slip up, and praising them when they do well. Most of all, it means debating their decisions — which Rosen’s article helpfully invites us to do.

Filed Under: Censorship & Filtering Tagged With: , , ,

Economic Growth, Censorship, and Search Engines

November 26, 2008 by

Economic growth depends on an ability to access relevant information. Although censorship prevents access to certain information, the direct consequences of censorship are well-known and somewhat predictable. For example, blocking access to Falun Gong literature is unlikely to harm a country’s consumer electronics industry. On the web, however, information of all types is interconnected. Blocking a web page might have an indirect impact reaching well beyond that page’s contents. To understand this impact, let’s consider how search results are affected by censorship.

Search engines keep track of what’s available on the web and suggest useful pages to users. No comprehensive list of web pages exists, so search providers check known pages for links to unknown neighbors. If a government blocks a page, all links from the page to its neighbors are lost. Unless detours exist to the page’s unknown neighbors, those neighbors become unreachable and remain unknown. These unknown pages can’t appear in search results — even if their contents are uncontroversial.

When presented with a query, search engines respond with relevant known pages sorted by expected usefulness. Censorship also affects this sorting process. In predicting usefulness, search engines consider both the contents of pages and the links between pages. Links here are like friendships in a stereotypical high school popularity contest: the more popular friends you have, the more popular you become. If your friend moves away, you become less popular, which makes your friends less popular by association, and so on. Even people you’ve never met might be affected.

“Popular” web pages tend to appear higher in search results. Censoring a page distorts this popularity contest and can change the order of even unrelated results. As more pages are blocked, the censored view of the web becomes increasingly distorted. As an aside, Ed notes that blocking a page removes more than just the offending material. If censors block Ed’s site due to an off-hand comment on Falun Gong, he also loses any influence he has on information security.

These effects would typically be rare and have a disproportionately small impact on popular pages. Google’s emphasis on the long tail, however, suggests that considerable value lies in providing high-quality results covering even less-popular pages. To avoid these issues, a government could allow limited individuals full web access to develop tools like search engines. This approach seems likely to stifle competition and innovation.

Countries with greater censorship might produce lower-quality search engines, but Google, Yahoo, Microsoft, and others can provide high-quality search results in those countries. These companies can access uncensored data, mitigating the indirect effects of censorship. This emphasizes the significance of measures like the Global Network Initiative, which has a participant list that includes Google, Yahoo, and Microsoft. Among other things, the initiative provides guidelines for participants regarding when and how information access may be restricted. The effectiveness of this specific initiative remains to be seen, but such measures may provide leading search engines with greater leverage to resist arbitrary censorship.

Search engines are unlikely to be the only tools adversely impacted by the indirect effects of censorship. Any tool that relies on links between information (think social networks) might be affected, and repressive states place themselves at a competitive disadvantage in developing these tools. Future developments might make these points moot: in a recent talk at the Center, Ethan Zuckerman mentioned tricks and trends that might make censorship more difficult. In the meantime, however, governments that censor information may increasingly find that they do so at their own expense.

Filed Under: Censorship & Filtering Tagged With: , , , ,

Does Your House Need a Tail?

November 25, 2008 by

Thus far, the debate over broadband deployment has generally been between those who believe that private telecom incumbents should be in charge of planning, financing and building next-generation broadband infrastructure, and those who advocate a larger role for government in the deployment of broadband infrastructure. These proposals include municipal-owned networks and a variety of subsidies and mandates at the federal level for incumbents to deploy faster broadband.

Tim Wu and Derek Slater have a great new paper out that approaches the problem from a different perspective: that broadband deployments could be planned and financed not by government or private industry, but by consumers themselves. That might sound like a crazy idea at first blush, but Wu and Slater do a great job of explaining how it might work. The key idea is “condominium fiber,” an arrangement in which a number of neighboring households pool their resources to install fiber to all the homes in their neighborhoods. Once constructed, each home would own its own fiber strand, while the shared costs of maintaining the “trunk” cable from the individual homes to a central switching location would be managed in the same way that condominium and homeowners’ associations currently manage the shared areas of condos and gated communities. Indeed, in many cases the developer of a new condominium tower or planned community could lay fiber along with water and power lines, and the fiber would be just one of the shared resources that would be managed collectively by the homeowners.

If that sounds strange, it’s important to remember that there are plenty of examples where things that were formerly rented became owned. For example, fifty years ago in the United States no one owned a telephone. The phone was owned by Ma Bell and if yours broke they’d come and install a new one. But that changed, and now people own their phones and the wiring inside their homes, with your phone company owning the cable outside the home. One way to think about Slater and Wu’s “homes with tails” concept is that it’s just shifting that line of demarcation again. Under their proposal, you’d own the wiring inside your home and the line from you to your broadband provider.

Why would someone want to do such a thing? The biggest advantage, from my perspective, is that it could solve the thorny problem of limited competition in the “last mile” of broadband deployment. Right now, most customers have two options for high-speed Internet access. Getting more options using the traditional, centralized investment model is going to be extremely difficult because it costs a lot to deploy new infrastructure all the way to customers’ homes. But if customers “brought their own” fiber, then the barrier to entry would be much lower. New providers would simply need to bring a single strand of fiber to a neighborhood’s centralized point of presence in order to offer service to all customers in that neighborhood. So it would be much easier to imagine a world in which customers had numerous options to choose from.

The challenge is solving the chicken-and-egg problem: customer owned fiber won’t be attractive until there are several providers to choose from, but it doesn’t make sense for new firms to enter this market until there are a significant number of neighborhoods with customer-owned fiber. Wu and Slater suggest several ways this chicken-and-egg problem might be overcome, but I think it will remain a formidable challenge. My guess is that at least at the outset, the customer-owned model will work best in new residential construction projects, where the costs of deploying fiber will be very low (because they’ll already be digging trenches for power and water).

But the beauty of their model is that unlike a lot of other plans to encourage broadband deployment, this isn’t an all-or-nothing choice. We don’t have to convince an entire nation, state, or even city to sign onto a concept like this. All you need is a neighborhood with a few dozen early-adopting consumers and an ISP willing to serve them. Virtually every cutting-edge technology is taken up by a small number of early adopters (who pay high prices for the privilege of being the first with a new technology) before it spreads to the general public, and the same model is likely to apply to customer-owned fiber. If the concept is viable, someone will figure out how to make it work, and their example will be duplicated elsewhere. So I don’t know if customer-owned fiber is the wave of the future, but I do hope that people start experimenting with it.

You can check out their paper here. You can also check out an article I wrote for Ars Technica this summer that is based on conversations with Slater, Wu, and other pioneers in this area.

Filed Under: Broadband Tagged With: ,

Discerning Voter Intent in the Minnesota Recount

November 21, 2008 by

Minnesota election officials are hand-counting millions of ballots, as they perform a full recount in the ultra-close Senate race between Norm Coleman and Al Franken. Minnesota Public Radio offers a fascinating gallery of ballots that generated disputes about voter intent.

A good example is this one:

A scanning machine would see the Coleman and Franken bubbles both filled, and call this ballot an overvote. But this might be a Franken vote, if the voter filled in both slots by mistake, then wrote “No” next to Coleman’s name.

Other cases are more difficult, like this one:

Do we call this an overvote, because two bubbles are filled? Or do we give the vote to Coleman, because his bubble was filled in more completely?

Then there’s this ballot, which is destined to be famous if the recount descends into ligitation:

[Insert your own joke here.]

This one raises yet another issue:

Here the problem is the fingerprint on the ballot. Election laws prohibit voters from putting distinguishing marks on their ballots, and marked ballots are declared invalid, for good reason: uniquely marked ballots can be identified later, allowing a criminal to pay the voter for voting “correctly” or punish him for voting “incorrectly”. Is the fingerprint here an identifying mark? And if so, how can you reject this ballot and accept the distinctive “Lizard People” ballot?

Many e-voting experts advocate optical-scan voting. The ballots above illustrate one argument against opscan: filling in the ballot is a free-form activity that can create ambiguous or identifiable ballots. This creates a problem in super-close elections, because ambiguous ballots may make it impossible to agree on who should have won the election.

Wearing my pure-scientist hat (which I still own, though it sometimes gets dusty), this is unsurprising: an election is a measurement process, and all measurement processes have built-in errors that can make the result uncertain. This is easily dealt with, by saying something like this: Candidate A won by 73 votes, plus or minus a 95% confidence interval of 281 votes. Or perhaps this: Candidate A won with 57% probability. Problem solved!

In the real world, of course, we need to declare exactly one candidate to be the winner, and a lot can be at stake in the decision. If the evidence is truly ambiguous, somebody is going to end up feeling cheated, and the most we can hope for is a sense that the rules were properly followed in determining the outcome.

Still, we need to keep this in perspective. By all reports, the number of ambiguous ballots in Minnesota is miniscule, compared to the total number cast in Minnesota. Let’s hope that, even if some individual ballots don’t speak clearly, the ballots taken collectively leave no doubt as to the winner.

Filed Under: Uncategorized Tagged With: