Q&A with Brown University’s Anna Lysyanskaya, two-time winner of Facebook research awards in cryptography
In this monthly interview series, we turn the spotlight on members of the academic community and the important research they do — as partners, collaborators, consultants, and independent contributors.
For March, we nominated Anna Lysyanskaya, a professor at Brown University. Lysyanskaya is a two-time Facebook research award recipient in cryptography and is most known for her work in digital signatures and anonymous credentials. In this Q&A, Lysyanskaya shares more about her background, her two winning research proposals, her recent talk at the Real World Cryptography Symposium, and the topics she’s currently focusing on.
Q: Tell us about your role at Brown and the type of research you specialize in.
Anna Lysyanskaya: I am a professor of computer science, and my area of expertise is cryptography, specifically privacy-preserving authentication and anonymous credentials. I’ve had a long career in academia and finished my PhD 19 years ago, so this particular area is something that I started working on basically since I started doing research as a PhD student.
I got into this field mostly by chance, and honestly, I could have ended up anywhere. At the time, everything was new and interesting to me, but I remember I had a chance encounter with the person who would eventually become my adviser. At the time, he had a couple of papers he wanted to take a closer look at, so I started reading them and meeting with him to discuss them.
At the beginning, I was attracted to cryptography because I was interested in the math aspect, as well as the social aspect of solving math problems with interesting people who made everything fun. That initial fascination, paired with being in a great place to study it, led me to where I am today.
Eventually, I learned that it’s not just fun and math, and that there are actually interesting applications of what I’m working on. This is actually why I’m still working on it all this time later, because I just haven’t run out of interesting places to apply this stuff.
Q: You were a winner of two Facebook requests for proposals: the Role of Applied Cryptography in a Privacy-Focused Advertising Ecosystem RFP and the Privacy Preserving Technologies RFP. What were your winning proposals about?
AL: My ads-focused proposal was entitled “Know your anonymous customer.” Let’s start with how a website — say, yourfavoritenewspaper.com — turns content into money: by showing ads. When you click on an ad and buy something, the website that sent you there gets a small payment. At scale, these payments are what pays for the content you find online. The main issue here is that the websites you visit track your activities, and by tracking what you do, they are able to reward the sites that successfully showed you an ad.
My project is about finding a privacy-preserving approach to reward ad publishers — an approach that would not involve tracking a user’s activities but that would still allow reliable accountability when it comes to rewarding a website responsible for sending a customer to, say, a retailer that closed a sale with that customer. The idea is to use anonymous credentials: When you purchase something, your browser obtains a credential from the retailer that just received money from you. Your browser then communicates this credential, transformed in a special way, to whichever website sent you to the original retailer. The crux of the matter is that the transformed credential cannot be linked to the data issued by the retailer, so even if the website and retailer collude, they cannot tell that it was the same user.
My other proposal, which I coauthored with Foteini Baldimtsi from George Mason University, was about private user authentication and anonymous credentials on Facebook’s Libra blockchain. The nature of a blockchain is that it’s very public, but you also want to protect everyone’s privacy, so our goal was to build cryptographic tools for maintaining privacy on the blockchain. Having the opportunity to work with Libra researchers on this project is very exciting.
The tools for both research projects are very similar in spirit, but the stories are different. Because the applications are different enough, you still need to do some original research to solve the problems. The motivations for both projects are achieving user privacy and protecting users.
Q: You recently spoke at Real World Cryptography (RWC). What was your presentation about?
AL: Anonymous credentials have been central to my entire research career. They are what I am most known for, and they were the subject of my talk. An anonymous credential allows you to provide proof that you’re a credentialed user without disclosing any other information. In the aforementioned advertising example, a retail website you visit gives an anonymous credential to your browser that allows you to prove that you have purchased something at this retailer, without revealing who you are or any information that would allow anyone to infer who you are or what you purchased.
Of course, anonymous credentials can be used much more broadly. An especially timely potential application would be vaccination credentials. Suppose that everyone who receives a vaccination also receives a credential attesting to their vaccination status. Then, once you’re vaccinated, you can return to pre-pandemic activities, such as attending concerts and sports events, air travel, and even taking vacation cruises. To gain access to such venues, you’d have to show your vaccination credential. But unless anonymous credentials are used, this is potentially a privacy-invasive proposition, so anonymous credentials are a better approach.
Q: What are some of the biggest research questions you’re interested in?
AL: This talk that I gave at RWC is kind of about this. In a technical field, it’s hard to communicate what you’re doing to people who can actually potentially apply it, mostly because it’s not easy to explain mathematical concepts. Anonymous credentials are especially hard to explain to somebody who hasn’t studied cryptography for at least a few years.
Right now, my focus is to recast this problem in a way that’s a little bit more intuitive. My current attempt is to have an intermediate primitive called a mercurial signature. This is just like a digital signature, but it’s mercurial as in you can transform it in a way that’s still meaningfully signing a statement — just in a way that’s not recognizable to what it looked like when it was first issued.
There are several reasons why I think mercurial signatures are a good building block to study:
- First, we actually do have a candidate construction, so it’s not completely far-fetched, and we know that we can do it. Now, that construction has some shortcomings, but it isn’t a completely crazy idea.
- Second, mercurial signatures are an accessible concept to somebody who has just a basic undergraduate understanding of cryptography. You can actually explain what a mercurial signature is to somebody who knows what a digital signature is in just a few minutes.
- Also, mercurial signatures have very rich applications, and they allow us to build anonymous credentials that have some nice features. One example is delegation. Let’s say I anonymously give a credential to you and then you give a credential to someone else. When they use their credential, it doesn’t reveal what the chain of command is — just that they’re authorized.
This is actually the bulk of my RWC talk, and it’s what I think is the next thing to do.
Q: Where can people learn more about your research?
AL: People can learn more about my research on my Google Scholar profile.