Monday, April 8, 2013

A Report on NSDI'13: P3: Toward Privacy-Preserving Photo Sharing

This is a report of the presentation done by Moo-Ryong Ra on 2013-04-05. Paper co-authors are Moo-Ryong Ra, Ramesh Govindan, and Antonio Ortega, University of Southern California.

 Cloud-based photo sharing service providers (PSPs) are very popular. However, there are a number of privacy concerns on the way sharing services are currently provisioned. In his talk, Moo-Ryong Ra argued that shared photos may be over-exposed, either by accident or because poor PSP system design. He also mentioned that the PSP itself may use inference techniques to extract information from shared photos. In other words, one can trust the (mobile) device, but cannot fully trust on everything else (e.g. the network and the PSPs).

On one hand, these privacy concerns are real. Moo-Ryong showed several news headlines that reported privacy issues with Photobucket, Facebook, and Instagram. On the other hand, PSPs provide valuable and useful services to users: a shared photo may be adapted to the various types of devices that see these photos (smart-phones, computers, etc), and perform image quality processing. The only question is: can we protect users' privacy while still performing cloud-side image transformation? The answer: yes, we can. In the remainder of his talk, Moo-Ryong described P3, a privacy-preserving photo encoding algorithm. The algorithm extracts and encrypts a small part of the photo that contains significant visual information (the "secret part"), while preserving the larger part (the "public part"), which contains no significant information, in a standards-compatible format. With P3, PSPs can still provide their services without being required to redesign their systems.

P3 concentrates on JPEG images, and exploits the fact that DCT (Discrete Cosine Transform) coefficients of natural images are sparse, with a few coefficients holding most of the useful information. To extract the "secret part", P3 encodes the most significant bits of the most important coefficients; the remaining coefficients (and the least significant bits of the most important ones) form the "public part". There is a challenge, however: how to reconstruct the original image out of the secret and public parts? If the public part has not been modified, a straightforward series of linear operations can reconstruct the image. In case it has been modified, the PSP must also send the linear operator used for processing it. Along the talk, Moo-Ryong discussed the (easy-to-deploy) architecture of P3, provided evidences regarding its privacy-preserving aspect (through a set of examples and evaluation experiments), and showed that it causes minimal storage overhead (in the worst case, the image file-size increased at most 20%). Regarding the privacy-preserving aspect, Moo-Ryong showed that P3 virtually broke face recognition algorithms: the number of successful face recognitions in the public part was decreased significantly.

Nikita Borisov (University of Illinois at Urbana-Champaign) started the question & answer session by asking if one can obtain the original picture solely with the secret part. Moo-Ryong answered negatively, saying that one needs both parts to obtain the original picture. In a follow up, Nikita posed the situation in which the P2P is fully malicious. Moo-Ryong said that in this particular case P3 is broken. However, it was emphasized that in this case it is a functionality problem rather than a privacy problem -- the P2P will not be able to do anything malicious without the secret part anyway. The session chair (Krishna Gummadi, Max Planck Institute for Software Systems) asked for the high-level intuition as for why the smallest part of the image contained most of the visual information, whereas the larger part of the image contained almost none information. Moo-Ryong replied that this is related to why JPEG works, and revisited the discussion about the process of extracting the secret part from the image. Finally, someone (not identified) asked about the privacy guarantees of P3. Moo-Ryong replied that they are still trying to prove privacy guarantees of P3 using mathematical tools. However, they are unaware of any techniques that could break the algorithm.