Privacy-respecting programming

Project start: 

01 December 2011

iCareNet Fellow: 

Abstract of the Project

Privacy leaks can occur if an individual submits data to a third party service or program which then in turn sends non-anonymised versions of it to further third party services or programs. A naive solution to this problem is forcing all parties to use a common middleware that allows users to track all data computed using their private data, and delete it if they wish to do so. This solution leaves third party services and programs at the mercy of users deleting their data. We propose a framework that allows the above-mentioned tracking and deleting of personal data while trying to preserve services/programs functionality. Our framework aims at automatically recognising anonymised data, which can be kept in third-party services and programs safe from user deletions. This encourages developers to use and store anonymous data, which promotes privacy-respecting programming. Related work in privacy-preserving data dissemination focuses on validating attributes of entities (access control paradigm)  [3, 4, 5]; anonymising or obfuscating sensitive data [2]; aggregating encrypted data using homomorphic encryption[6, 7]; and using active bundlesto control and log access to data on entities with embedded virtual machines [1].

Our approach creates a data ownership map across the framework for each user in order to implement the tracking and deletion of personal data. To do so, we represent the code of a program as a set of functions and check for the existence of the corresponding inverse function f -1. If f -1 does not exist, the output can be stored without compromising the input, we call the function privacy respecting.












Fig. 1. Graph notation for ‘var b = f (a)’. (a) f -1 exists, not privacy-respecting (b) f -1 does not exist, privacy-respecting. f is a function, ‘E1’ and ‘E2’ stand for the entities that hold variables ‘a’ and ‘b’ respectively.

We then track an owner’s dissemination of personal data using a network wide map. The resulting map can be used to form a system of equations for each datum. If this system has only one solution then the sensitive data can be deduced from the dependent data resulting in privacy leaks (deanonymisation). 











Fig. 2. A new ‘var c = f (a)’ is created, which results in a potential privacy leak of ‘a’, although f and g are non-bijective (one arrow). In this case, the last created dependent data ‘c’ becomes marked (double arrow), which means that this data will be deleted if E1 wants to delete not privacy-respecting dependent data of ‘a’.


Research Achievements to date

  • Literature review on privacy preserving data dissemination techniques and approaches focusing on validation of program behaviour by identifying anonymised and deanonymised data.
  • Formalisation of privacy leak identification in data dissemination based on strategies for checking (refuting) the existence of inverse functions, e.g. strictly monotonic functions, and unique solution for a system of arbitrary equations.


1. Ben Othmane, L., and Leszek Lilien. "Protecting Privacy of Sensitive Data Dissemination Using Active Bundles." Privacy, Security, Trust and the Management of e-Business, 2009. CONGRESS'09. World Congress on. IEEE, 2009.

2. Byun, Ji-Won, et al. “Privacy-preserving incremental data dissemination.” Journal of Computer Security 17.1 (2009): 43-68.

3. De Cristofaro, Emiliano. "Sharing Sensitive Information with Privacy DISSERTATION." PhD diss., UNIVERSITY OF CALIFORNIA, 2011.

4. De Cristofaro, Emiliano, Stanislaw Jarecki, Jihye Kim, and Gene Tsudik. "Privacy-preserving policy-based information transfer." In Privacy Enhancing Technologies, pp. 164-184. Springer Berlin/Heidelberg, 2009.

5.Stolfo, Salvatore J., and Gene Tsudik. "Privacy-Preserving Sharing of Sensitive Information." Security & Privacy, IEEE 8, no. 4 (2010): 16-17.

6.Nabeel, Mohamed, Ning Shang, and Elisa Bertino. "Efficient privacy preserving content based publish subscribe systems." In Proceedings of the 17th ACM symposium on Access Control Models and Technologies, pp. 133-144. ACM, 2012.

7. Atallah, Mikhail, and Wenliang Du. "Secure multi-party computational geometry." Algorithms and Data Structures (2001): 165-179.