Author: Ed Felten
-
Needle-in-a-Haystack Problems, and P vs. NP
Last week I wrote about needle-in-a-haystack problems, in which it’s hard to find the solution but if somebody tells you the solution it’s easy to verify. A commenter asked whether such problems are related to the P vs. NP problem, which is the most important unsolved problem in theoretical computer science. It turns out that…
-
Needle-in-a-Haystack Problems
Sometimes the same idea comes flying at you from several directions at once, and you start seeing that idea everywhere. This has been happening to me lately with needle-in-a-haystack problems, a concept that is useful but often goes unrecognized. A needle-in-a-haystack problem is a problem where the right answer is very difficult to determine in…
-
Google Publishes Data on Government Data and Takedown Requests
Citizens have long wondered how often their governments ask online service providers for data about users, and how often governments ask providers to take down content. Today Google took a significant step on this issue, unveiling a site reporting numbers on a country-by-country basis. It’s important to understand what is and isn’t included in the…
-
Flash, Scratch, Ajax: Apple's War on Programming
Any ambitious regulatory scheme will face pressure to expand, in order to protect the flanks of the main regulation against users’ workarounds. Apple’s strategy of regulating which apps can run on the iPhone and iPod is just such a regulation, and over the last week or so Apple has been giving in to the pressure…
-
iPad: The Disneyland of Computers
Tech commentators have a love/hate relationship with Apple’s new iPad. Those who try it tend to like it, but many dislike its locked-down App Store which only allows Apple-approved apps. Some people even see the iPad as the dawn of a new relationship between people and computers. To me, the iPad is Disneyland. I like…
-
CITP Expands Scope of RECAP
Today, we’re thrilled to announce the next version of our RECAP technology, dramatically expanding the scope of the project. Having had some modest success at providing public access to legal documents, we’re now taking the next logical step, offering easy public access to illegal documents. The Internet Archive, which graciously hosts RECAP’s repository of legal…
-
Pseudonyms: The Natural State of Online Identity
I’ve been writing recently about the problems that arise when you try to use cryptography to verify who is at the other end of a network connection. The cryptographic math works, but that doesn’t mean you get the identity part right. You might think, from this discussion, that crypto by itself does nothing — that…
-
Side-Channel Leaks in Web Applications
Popular online applications may leak your private data to a network eavesdropper, even if you’re using secure web connections, according to a new paper by Shuo Chen, Rui Wang, XiaoFeng Wang, and Kehuan Zhang. (Chen is at Microsoft Research; the others are at Indiana.) It’s a sobering result — yet another illustration of how much…
-
Web Certification Fail: Bad Assumptions Lead to Bad Technology
It should be abundantly clear, from two recent posts here, that the current model for certifying the identity of web sites is deeply flawed. When you connect to a web site, and your browser displays an https URL and a happy lock or key icon indicating a secure connection, the odds that you’re connecting to…
-
Mozilla Debates Whether to Trust Chinese CA
[Note our follow-up posts on this topic: Web Security Trust Models, and Web Certification Fail: Bad Assumptions Lead to Bad Technology] Sometimes geeky technical details matter only to engineers. But sometimes a seemingly arcane technical decision exposes deep social or political divisions. A classic example is being debated within the Mozilla project now, as designers…