March 8th, 2012 at 22:08 UTC by Joseph Bonneau
I spent last week attending Financial Cryptography on Bonaire (a small Dutch island in the Caribbean), along with its attached workshops on Ethics in Computer Security Research and Usable Security. As usual, the conference attracted a broad spectrum of papers mixing applied cryptography and miscellaneous financial security problems (including our own group’s work on PIN guessing statistics and Facebook’s photo-based backup authentication). All of the papers are now online. I’ll point to three papers which thought-provoking for me. I’m not going to claim these are the best or most important papers-the conference featured some very strong work on applying cryptography to practical problems like smart metering and oblivous printing, while perhaps the most newsworthy research was Wustrow et al.’s hacking of the Washington DC Internet voting prototype. I’ll just highlight why these papers were memorable for me.
“The Postmodern Ponzi Scheme: Empirical Analysis of High-Yield Investment Programs” Tyler Moore, Jie Han, Richard Clayton.
This paper was memorable because it exposed a substantial part of the Internet underground that I’d never seen investigated before, in the tradition of similar works on typosquatting and running an online porn server. High-yield investment programs (HYIPs) promise fantastic rates of return (at least 1% per day) to online investors. Of course, they are Ponzi schemes, generating no real wealth but using new investors to pay off old investors up to an inevitable collapse. I found it fascinating to see how this old financial scam has flourished online—the authors present convincing evidence that this is a large-scale industry with perhaps hundreds of thousands of investors falling for the scams. They also present some trends which aren’t too surprising, like schemes requiring longer commitment from investors and paying lower returns surviving longer. I suspect most people who’ve studied offline Ponzi schemes have made the same observations, but in the online world these factors can be quantified automatically by observing hundreds of schemes using crawlers. In fact, this is a place I wish the paper went further, exploring the optimal strategy for running a HYIP. I wonder what kind of theoretical analysis is possible along the lines of the mathematical model of building trust over time proposed by Dusko Pavlovic. The most interesting observation of the paper was how cynical the online world of Ponzi schemes appears. Aggregator sites list and monitor different HYIPs, serving at least some users who clearly know the programs are scams and invest anyway, hoping to get in early enough to profit. Many of the sites themselves make little effort to claim to be doing any legitimate wealth-generating activity (the original Ponzi created a fictitious tale of postal-reply coupons). This is another area for further exploration: how many HYIP investors are actually wise to the scam nature of the sites? Are there a large number of ignorant victims duped by the more convincingly presented sites? The best testament to this paper is that I had no idea what an HYIP was before, and now there are many questions I’d like to see answered.
“CommitCoin: Carbon Dating Commitments with Bitcoin” Jeremy Clark, Aleksander Essex.
This was a short paper based on a simple but interesting problem: how can one commit to some important values without revealing them, without knowing to whom the commitment is being made? Commitment schemes using hash functions are old hat in cryptography, if Alice wants to commit to message x, she sends Bob H(x) at time t using any collision-resistant hash function H, and can later reveal x and Bob will know that Alice had chosen x as of time t. But what if Alice doesn’t know who Bob is and wants to generally commit to x? Perhaps x is a patentable idea. One solution is publish H(x) in a newspaper ad or some other trusted source, but this requires payment and trust in a higher authority. Bitcoin attempts to deal with similar issues in managing a currency, where the community of users must agree to a consistent view of all previous transactions despite strong incentives for everybody to cheat to increase their own holdings. The authors propose CommitCoin as a creative solution to the commitment problem (which they term “Carbon Dating”) using Bitcoin essentially in place of the newspaper in the offline solution. Alice creates an ephemeral key pair using H(x) as the secret key, then inserts a low-value transaction into the Bitcoin log. Eventually this log will be accepted by the system’s hash-chaining calculation, after which point Alice may insert a second transaction reversing the first one, done in a creative way using the same randomness as an earlier signature, such that the secret key is easily cryptanalysed. Of course, this means that H(x) is public and was committed to at the time of the first transaction. I liked this paper for proposing such an unorthodox solution to an interesting problem that we don’t yet have a great solution for. This approach is still vulnerable to Alice committing to many values of x (say, committing to separate predictions of both Labour and the Conservatives winning the next election) and then only revealing one. The authors pointed out one interesting application which doesn’t have this problem, however: committing to parameters prior to a Scantegrity election (which the authors did in last November’s election). This paper left me thinking there’s a lot of work left to do in this area, but I appreciated the creative approach to the problem.
“High Stakes: Designing a Privacy Preserving Registry” Alexei Czeskis, Jacob Appelbaum. (Presented at USEC)
This paper proposes the concept of a unidirectional, non-identifying registry. The specific application is medical marijuana qualification in the United States. The goal of a UDNI is that Bob can prove he is a member of the registry and also deny that he is a member and have nobody else be able to prove that he is. The second requirement extends, in the author’s definition, to the risk of a complete database compromise. In fact, the authors set a strong goal of the registry storing no personally identifiable information. Yet an explicit goal is also that police officers can stop individuals and have them give reasonable proof of being members of the registry even if the officer has no equipment to perform a cryptographic verification of their claims (or communicate to a remote server). This was the strength of this paper and what made it memorable—the authors took on a challenging practical problem, explored the design space and implications carefully, and came up with a reasonable hybrid proposal that they are actively working to craft into a real law for the state of Washington. None of the technology the authors propose is novel or interesting by itself. In fact they end up using no cryptography at all, only storing a database of membership numbers with associated expiration dates. The membership numbers are printed onto forgery-resistant, driver’s license-style cards with nothing but a patient’s photograph, which can be presented to police for visual verification or checked in an online database. If the complete list of random numbers is leaked, there is little harm done. There are a few other nice ideas along the way, like doctors using Tor to hide their location while registering patients, or patients being able to revoke their membership securely by cutting their card in half to remove their photograph and mailing the half with their membership number to the registry maintainers. One major weakness of the system is the inclusion of photographs. With face-recognition improving, this introduces many risks: police might record the photograph surreptitiously, might demand to also see a driver’s license (with name) during a traffic stop where marijuana is found, or the registry maintainers could secretly store photographs during enrollment (which they have to receive to securely print cards with associated membership numbers). Still, I enjoyed the practical and honest approach of the paper, making it a good case study for engineering a real-world system with privacy in mind given very challenging requirements.
Entry filed under: Three Paper Thursday