home > publications > articles

Published in ACM SIGCAS Computers and Society, Volume 40, No. 4, December 2010.

Privacy Enhanced Search

Benjamin Gerber
http://privacy.us/contact

What does Google know about you? A new invention by IBM may hold the key to keeping your thoughts to yourself.

Search engines provide the most important information service of the past decade. Can you imagine the Internet, or even your corporate intranet, without such a feature? Though, like many innovations in their original form, search engines were not designed with privacy or confidentiality in mind.

How much does your search engine know about you? Search terms, i.e., what you type in the Google search box, reveal individual everyday activities, business pursuits, and personal thoughts.

Whether you are using Google or Bing, visit Yahoo or are compelled to Ask Jeeves your search queries can be tied back to you. Even Ask.com’s AskEraser (which “deletes your search activity from Ask.com servers within hours”1) sends your search queries off to Google to serve up ads. Anonymity enabling services such as StartPage.com or TOR2 allow users to mask revealing information about their location and the same-user connection between consecutive searches (which enable search engines to build up a user profile that can persist for years). However, it is often WHAT you are searching on, not just WHERE you appear to be searching from, that reveals a great deal about you.

Does your Internet search engine also host your personal e-mail? With over 360 million Hotmail users3 and some 170 million Gmail users4 if you are not one of them, chances are your friends are. Perhaps your workplace communications and office applications are hosted by Google Apps for Business or you use Microsoft Office Live to share documents? What about your local government’s communications5?

Perhaps search providers will promise to keep your search derived information separate and only use it for certain purposes… we certainly hope so! Though, in innovative environments—sometimes ideas bypass policy. It is doubtful that any of the numerous privacy geeks Google has on staff would have thought secretly performing Wi-Fi sampling while capturing already controversial street view photos was a good idea, yet engineers implemented this feature6. As new ideas for expanding services and developing new revenue opportunities are explored, company practices will evolve and your search queries will be used in new ways7.

What about the risks posed by events out of the search providers control, be they hacks8, subpoenas9 or just bad actors; in September Google fired an engineer for spying on children’s e-mail and chats10.

Some solutions have been proposed.

In August, Stephen Colbert provided his solution, along with some other (humorous) tips on maintaining your privacy11.

“…Gmail keeps track of everyone you ever e-mailed, so, you’ll want to get rid of your old friends and family. And, since Google also tracks all your searches and web history, you should change everything you have ever searched for on the Internet…”

While Colbert’s solution requires us to modify our past, another option exists for the distant future.

Last October, Scientific American ran an intriguing article by Seth Lloyd12, a professor of mechanical engineering at the Massachusetts Institute of Technology, that utilizes quantum mechanics to solve the search privacy problem. The solution requires a “viable quantum Internet” or large “quantum RAMs.”

Lloyd and his colleagues have “nailed down the details of how to build quantum RAM and make quantum private queries” and another team in Italy managed to implement a simple quantum RAM and perform a search against a small database stored in it. This is impressive; however, viable implementation of this quantum technology may be decades away.

Is there a solution possible built upon existing technology? YES.

In 2008 IBM filed a patent application for an invention that does just this (application number: 12/345,842 publication number: US 2010/0169293 A113).

By applying three basic cryptographic building blocks—symmetric cryptography, cryptographic hash functions and salts, described in figure 1—(and considerable cryptographic acceleration) the invention, described in figure 2, achieves privacy enhanced search.

Obviously this approach to delivering search services is in conflict with the status quo business model for search engines (though with a bit more imagination, this too perhaps could be addressed).

Privacy enhanced search could be applied for specialized search engines, where the search terms are particularly sensitive, such as with medical conditions. The technology might also be a very valuable feature for use in cloud computing, such as with the increasingly popular Evernote14 service—if my client maintains control over the keys and salts, I could not only store encrypted information in the cloud, but utilize the cloud’s power to search through it.

For general search engines, perhaps a pay-for-use model could permit users to regain their privacy. In his above mentioned article, Lloyd recanted a conversation he had with Brin and Page where he described his quantum solution (incidentally while they are all relaxing in a hot tub):

“Their first response was that Google’s business model was to keep the information about all queries and to use it to prioritize advertising and future search results. Not retaining the information about queries had not occurred to them. When I put to them the evident advantages of a new, quantum business model—based on charging customers for search results—they thought some more. ‘Okay,’ they said, ‘Let’s see if you can build it.’”

In August, Google’s CEO, Eric Schmidt told us how he sees Google’s future role: “I actually think most people don’t want Google to answer their questions. They want Google to tell them what they should be doing next.”15 That sounds great if you are hunting for the best ramen noodles within a mile, but for many things on our minds, we might want to rethink this future. The technology to change it is within our reach today.

Figure 1

Figure 2

Published in ACM SIGCAS Computers and Society, Volume 40, No. 4, December 2010.

This article (text and illustrations), Privacy Enhanced Search, is © Benjamin Gerber 2009, 2010 and is licensed under a Creative Commons Attribution 3.0 Unported License.

The patent application discussed is IBM’s intellectual property; it is publically available as of June 1, 2010.

privacy.hk