Blog Author: Eleanor Rieffel

Computing with Secrets

on Comments (1)

Tom Simonite of Technology Review interviewed me about the breakthrough in fully homomorphic encryption that I blogged about here. I very much enjoyed talking with him, and was pleased to see that he wrote a good article on the subject: Computing with Secrets, but Keeping them Safe: A cryptographic method could see cloud services work with sensitive data without ever decrypting it. He quotes me a couple of times on the second page of the article and generously gives me the last word.

I’ve been surprised at how little has been written about this breakthrough, little enough that my blog post continues to be among the top 20 hits for a number of related queries. The field is definitely hot, with DARPA recently announcing two related solicitations, DARPA-RA-10-80 and DARPA-BAA-10-81, on PROgramming Computation on EncryptEd Data (PROCEED). The first solicits research proposals for development of new mathematical foundations for efficient computation on encrypted data via fully homomorphic encryption. The second solicitation is broader, with the goal of developing practical methods for computation on encrypted data without decrypting the data and modern programming languages to describe these computations.

Computing with Secrets, but Keeping them Safe

Computing with Secrets, but Keeping them Safe

Revisualizing a past FXPAL researcher

on Comments (1)
Traces of Gold, by Chris Culy

Traces of Gold, by Chris Culy

Chris Culy, who worked on discourse parsing at FXPAL a number of years ago, is now in Italy working as a Senior Researcher and the Language Technologies Technical Officer at the Institute for Specialised Communication and Multilingualism. He oversees language-related software development and leads a research project on linguistic data visualization. But the real excitement is that he has a solo art show, Revisualizing the visual, opening today.  His work combines his  interest in photography with his  interest in how information is structured and perceived. The software he has written to support his work transforms colors into shapes or uses color information to create rambling colorful paths based on the image. To create effective artworks, Chris carefully chooses the original photograph and tunes the algorithms to it. Don’t miss the video that shows some of this process in action!

Research advice and a search challenge

on Comments (9)

I was intending to write a post on the varied reasons mathematicians give for taking long walks as an aid to research. I couldn’t find my favorite quote, so instead I’m posting a search challenge.

I thought I remembered reading, in the book Littlewood’s Miscellany, something along the lines of the following advice:

Researchers spend the vast majority of their time feeling frustrated. To improve the ratio of time feeling fulfilled to time feeling frustrated, whenever you find a new result or succeed in completing a proof, take the time to enjoy it, preferably by taking a long walk.  Definitely don’t dive into the next problem, or go back and check the proof. There is plenty of time for that later.

However, it doesn’t seem to be in that book. Littlewood certainly approved of walking, and the tone of much of his advice is consistent with this quote, but this particular piece of advice doesn’t appear to be there.  I couldn’t find it in a web search either.

I would love to know the true source for this piece of wisdom.

Tcho chocolate bar to anyone who can track down the source!

Toward pragmatic definitions of privacy

on Comments (1)

The success of de-anonymization efforts, as discussed here, suggests that older anonymization methods no longer work, especially in light of the large amount of publicly available data that can serve as auxiliary information. The quest to find suitable replacements for these methods is ongoing. As one starting point in this broader quest, we need useful definitions of privacy.

It has proven surprisingly difficult to find pragmatic definitions of privacy, definitions that capture a coherent aspect of privacy, are workable in the sense that it is possible to protect privacy defined in this way, and are sufficiently formal to provide means for determining if a method protects this type of privacy and, if so, how well.

The best attempt to date is the notion of differential privacy. Continue Reading

Whither data privacy?

on Comments (3)

On Friday Netflix canceled the sequel to its Netflix prize due to privacy concerns. The announcement of the cancellation has had a mixed reception from both researchers and the public. Narayanan and Shmatikov, the researchers who exposed the privacy issues in the original Netflix prize competition data, write “Today is a sad day. It is also a day of hope.”

The Netflix prize data example is probably the third most famous example of de-anonymization of data that was released with the explicit claim that the data had been anonymized. These examples differ from the privacy breaches discussed by Maribeth Back in her post on ChatRoulette or the issues with Google Buzz discussed as part of Gene Golovchinsky’s post “What’s private on the Web?” . Those examples made sensitive information available directly. In the case of the following three de-anonymization attacks, the data itself was “anonymized,” but researchers were able, with the addition of  publicly available auxiliary information, de-anonymize much of the data.

Continue Reading

Recent Progress in Quantum Algorithms


Dave Bacon, who wrote the elegant overview of the research discussed in my New Year’s Day post, just published his review, joint with Wim van Dam, of Recent Progress in Quantum Algorithms. Bacon writes beautifully, and this piece is no exception.

Most people have heard of no more than two quantum algorithms: Shor’s factoring algorithm and Grover’s search algorithm. For five years after Grover’s algorithm, no one discovered a significantly novel quantum algorithm, only variations on Shor’s and Grover’s algorithms were found. The first truly new quantum algorithms were discovered starting in 2001. Now there are many quantum algorithms found using a variety of approaches, though the applications remain restricted.  My recent overview of quantum computing mentions many of these algorithms. Bacon and van Dam provide a more detailed, but still high level, view of these algorithms. They group the algorithms into four categories corresponding to different approaches: quantum random walks, wave packet scattering, finding hidden symmetries, and simulating quantum physics. I hope many of you will enjoy learning more about, in their words, “the benefits of … studying the notion of an algorithm through the perspective of the physical laws of the universe.”

How to compute without knowing anything

on Comments (5)

In my post on quantum inspired classical results, I gave as one example Gentry’s recent discovery of a fully homomorphic encryption scheme. His beautiful work deserves its own blog post. Initially I approached his work with trepidation, worried that it would be so technical I would not understand anything without a lot of work. Others have mentioned not  having looked at his work for the same reason. That is a shame! While the details are technical, the key idea, bootstrappable encryption, is both a non-obvious approach and an easily understandable concept.  I remember smiling while I read the first couple of pages of his paper in response to the elegance and surprising simplicity of his approach.

Continue Reading

Summer intern position in privacy preserving computation

on Comments (1)

This is the third of a series of posts advertising internship positions at FXPAL for the summer of 2010.  A listing of all blog posts about our 2010 internship positions is available here.

Significant privacy issues arise when personal data is stored and analyzed. This issue is exacerbated when part or all of the storage and analysis is outsourced to a third party. To support such analysis in an awareness system, while addressing the privacy concerns, we are building into our system a facility that supports computation of simple statistics on encrypted data. This facility can be extended in a number of ways to support a greater variety of computations. There are a wealth of research questions related to designing such a system to support the types of computations useful to our application while choosing the best tradeoffs in terms of storage, bandwidth, division of labor between the third party and the clients, computation time at encryption, time to compute the statistics, and time to decrypt.

Prospective candidates should be enrolled in a PhD program and have significant experience in privacy and security, particularly computation on or search of encrypted data.

The intern will be hosted by Eleanor Rieffel.  For more information on the FXPAL internship program, please visit our web site.

768 bites the dust!

on Comments (1)

A multinational team announced on January 7th that they, together with hundreds of computers, running for two years, carrying out about 2^67 instructions, factored RSA-768.  For more details, see their paper. They suggest that this result should encourage everyone to follow NIST’s recommendation to phase out 1024-bit RSA keys.

Which 2009 research results excited you the most?

on Comments (3)

Which research result excited you the most in the past year? We’re not asking for the one you thought most important, or the one that would be most exciting to everyone, but which one got you, personally, most excited.

I’ll start things off with a result that delighted me so much I went around smiling all day, only feeling sad that more people couldn’t appreciate it! The result, that appeared in two papers almost simultaneously, is that some quantum states are too entangled to be able to compute one way. The result enchants me because it is surprising, fundamental, and related to topics close to my heart. Prior to these papers, the conventional wisdom held that more entanglement could only help quantum computation. It came as a complete surprise that it could hurt!  Dave Bacon writes beautifully and succinctly about these startling results in his viewpoint, published in Physics, about the two papers published together in Physics Review Letters 102 last May. Here I give an briefer account in order to explain why these result delighted me so much.

Continue Reading