Using structured encryption to search protected photos in the cloud

In a recent presentation at the Real World Crypto symposium, researchers affiliated with Brown University and a startup called Pixek presented their work developing an app that encrypts photos at the moment they're taken and uploads them in encrypted form to a cloud server, in such a way that the keys remain on the user's device, meaning the service provider can't view the photos.

Despite that, the photos remain searchable using automated tags generated by image classifiers, thanks to a largely theoretical tool called "structured encryption," which provides for the ability to do computational work on a system without the system knowing what kind of work it is doing.

If this works, it's a pretty significant advance on the current state of the art, which allows for three kinds of mobile photography: taking pictures and never putting them in the cloud; taking pictures, encrypting them, and storing them in the cloud (but having to refer to metadata you keep on your own devices to remember which encrypted picture is which); or taking pictures and leaving them on a cloud service and praying that the server is never breached or hacked and that you never get your account stolen through a social-engineering attack. (I do the first one: I move photos from my phone to my laptop's encrypted hard drive and leave them there, never putting any sensitive images in the cloud at all).

Andy Greenberg's writeup in Wired makes mention of a seeming contradiction: although Pixek is not supposed to be able to ever see your photos because it doesn't have your key, it does have a key-recovery mechanism for people who lose or forget their passphrases, where you answer questions and get a new key emailed to you. This suggests that Pixek is storing its users' keys in a format that could be breached, exposing the whole system.

When someone uses Pixek to take a photo, the software performs machine learning analysis on their device to recognize objects and elements of photos, then adds tags to the image for each one. It then encrypts the image along with its tags, using a unique key stored only the user's phone.

Next, Pixek's server adds the encrypted, tagged photo to a cloud-based data structure with some very specific properties: Kamara describes it as a kind of "maze." No one, not even someone controlling the server, can map out which encrypted keywords are connected to which encrypted image. But when the user searches for a term—like "dog" or "beach"—that word is encrypted with their secret key to produce a special "token" that unlocks encrypted components of the database structure. "Using that token, the server can navigate a part of the maze, and unlock pointers to whatever it's supposed to return back," Kamara says.

An App That Encrypts Your Photos From Camera to Cloud [Andy Greenberg/Wired]