Sarah Meiklejohn – Security and Cryptography

Sarah Meiklejohn As a child, Sarah Meiklejohn thought she might become a linguist, largely because she was so strongly interested in the work being done to decode the ancient Greek writing systems Linear A and Linear B.

“I loved all that stuff,” she says. “And then I started doing mathematics.” At that point, with the help of Simon Singh’s The Code Book, she realised the attraction was codebreaking rather than human languages themselves. Simultaneously, security and privacy were increasingly in the spotlight.

“I’m a very private person, and so privacy is near and dear to my heart,” she says. “It’s an important right that a lot of people don’t seem interested in exercising, but it’s still a right. Even if no one voted we would still agree that it was important for people to be able to vote.”

It was during her undergraduate years at Brown, which included a fifth-year Masters degree, that she made the transition from mathematics to cryptography and began studying computer science. She went on to do her PhD at the University of California at San Diego. Her appointment at UCL, which is shared between the Department of Computer Science and the Department of Crime Science, is her first job.

Probably her best-known work is A Fistful of Bitcoins: Characterizing Payments Among Men with No Names (PDF), written with Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, and Stefan Savage and presented at USENIX 2013, which studied the question of how much anonymity bitcoin really provides.

“The main thing I was trying to focus on in that paper is what bitcoin is used for,” she says. The work began with buying some bitcoin (in 2012, at about £3 each), and performing some transactions with them over a period of months. Using the data collected this way allowed her to uncover some “ground truth” data.

“We developed these clustering techniques to get down to single users and owners.” The result was that they could identify which addresses belonged to which exchanges and enabled them to get a view of what was going on in the network. “So we could say this many bitcoins passed through this exchange per month, or how many were going to underground services like Silk Road.”

That macro view – how many services, how many bitcoins, which is the wealthiest service – was interesting enough. But the bigger point was to understand how much – or how little – anonymity the system really gives its users. The researchers were able to develop a tracking technique that enabled them to answer this question: not very much.

“If you’re buying on the exchanges you’re really leaving yourself vulnerable to real-world deanonymisation,” she says. While there are ways of buying bitcoins without using the exchanges, such as meeting in a park to do the exchange, they don’t really scale.

“One of my motivation concerns was that if something is truly anonymous, what are the implications? What are people using it for?” Meiklejohn says. For her, this is a natural area of study: “We’re scientists. We’re curious about the limitations of the technology and what are realistic expectations.”

After the paper was published, new forms of digital coins were released claiming greater anonymity. Meiklejohn expects this to be an iterative process: someone will find flaws with the new coins, too, followed by new attempts at improvements.

In a follow-up paper, Botcoin: Monetizing Stolen Cycles (PDF), presented at the 2014 Network and Distributed System Security Symposium, Meiklejohn and Danny Yuxing Huang, Hitesh Dharmdasani, Vacha Dave, Chris Grier, Damon McCoy, Stefan Savage, Nicholas Weaver, Alex C. Snoeren, and Kirill Levchenko looked into one criminal purpose related to bitcoin: cycle theft. In this case, malware installed on a victim’s computer users it to mine bitcoins or its easier-to-mine competitors, Lightcoins or Feathercoins. The study did longitudinal measurements to understand how profitable this activity was for the criminals, along with how they used mining tools and which ones, and which addresses they used. Given the addresses, they looked for the points where the criminals cashed out.

“We concluded that it was profitable, and that people certainly are making hundreds of thousands of dollars doing it, but they’re switching away from mining bitcoins because it’s computationally intensive unless you have dedicated hardware.” The lighter-weight currencies are better options, but the markets are thinner.

Part of Meiklejohn’s research for her master’s degree was studying the work of Jens Groth on zero knowledge proofs. Her contribution to this area has focused on a particular property of these proofs, malleability, a setting in non-interactive zero knowledge proofs. The idea is to find ways to publicly transform proofs about certain statements into new proofs about statements related to those that the proof has already covered. For example: let’s say that Alice has proved that she knows the value of a variable, x, and that value is between 0 and 100. Logically, that would tell you a lot of related things, such as that x + 5 is between 5 and 105.

“I’ve done four papers looking at malleability,” she says. These have looked at how to define and control it so that only certain related operations would be accepted. “We’ve showed that it has applications in all sorts of things.” For example, malleable signatures could be used to build primitives called “delegatable anonymous credentials”. In e-voting, it might be used to allow individual election authorities to publish a combined compact proof that suffices to prove the validity of the entire election rather than having each authority publish its own individually.

In Algebraic MACs and Keyed-Verification Anonymous Credentials (PDF), written with Melissa Chase and Greg Zaverucha and presented at the 2014 ACM Conference on Computer and Communications Security, Meiklejohn studied anonymous credentials.

“My co-authors and I observed that in a lot of settings the person who issues you the anonymous credential is the same as the person who verifies it. Using this observation, we were able to come up with significantly more efficient credentials – using a symmetric cryptograph instead of asymmetric  cryptography.” In addition, “It turns out that exploiting that issuer and verifier is the same makes it possible to use message authentication codes, which can be much more efficient.”

Meiklejohn’s original interest in security began with mathematics but has gained in significance over the last few years of publicised attacks and revelations. “Security has never been more important than it is right now,” she says.


This post is part of the Inside Infosec series, summarising the research and teaching done by UCL Information Security group members. This research portrait was written by Wendy M. Grossman.

Leave a Reply

Your email address will not be published. Required fields are marked *