Linked Data has become an important standard to describe meta-data about open government data. At the same time, most government data is not released as Linked Data. One reason for this could be the di culty of applying privacy enhancing technologies such as di erential privacy and private information retrieval to Linked Data. We introduce the idea of graph summaries to function as a schema for Linked Data which is schema-less. This in turn can provide a conceptual bridge for applying di erential privacy and private information retrieval to Linked Data.
Linked Data using the DCAT vocabulary is emerging as the de-facto standard for publishing meta-data about data sets released by governments, especially in the EU. At the same time, most of the data sets described by the DCAT meta-data are not being published using Linked Data.
This might be due to the fact that there currently is a lack of best practices
for publishing sensitive data sets as Linked Data. For tabular data, established
methods in the area of di erential privacy [
While Aron [
This is due to one of the main obstacles for applying the idea of di erential
privacy to Linked Data: Linked Data is schema-less, meaning that one data set
can contain properties and classes from many vocabularies and ontologies. In
addition, a priori knowledge about the structure of a linked data set is usually
not possible. Due to this exible and dynamic nature of LD, applying di erential
privacy like in [
In this paper, we will introduce graph summaries as a central enabler for privacy enhancing release and querying of Linked Data. We argue that future best practices for identifying and masking the sensitive parts of an LD data set will incorporate some form of graph summarisation. In addition, we will explain why graph summaries could be very useful in enabling private information retrieval by distributing a query which can be ful lled by one data source to multiple data sources.
The remainder of this paper is structured as follows: In section 2 we will
introduce the background in regards to di erential privacy and private information
retrieval. Then in section 3 we will describe an approach for graph summaries
which was introduced by Campinas et al. in [
The European Data Portal1 is publishing descriptions of data sets using the DCAT vocabulary. In particular, the DCAT-AP pro le is used on the site. In terms of size, currently descriptions of approx. 600,000 data sets from around 70 data portals of 34 countries are hosted by the European Data Portal. Yet, only 1500 of these data sets are declared as explicitly using a form of RDF.
This suggests a mismatch between the requirements for releasing open government data and the tools and best practices available for publishing Linked Data. In particular, this could point to the di culty of anonymising Linked Data sets before releasing them.
The release of anonymised, statistical data sets in tabular form has been solved to the most part using approaches which can be subsumed under the heading of di erential privacy, which we describe below.
This is followed by a description of private information retrieval (PIR). PIR becomes relevant in relation to Linked Data, as SPARQL queries can reveal a lot about the intentions and interests of the query issuing party. 2.1
The goal of releasing an anonymised statistical data, is to release data of a representative sample of a population in order to enable analysis of the common properties of that population, while keeping the properties of individual records secret.
The two most common elements of di erential privacy approaches are
generalisation and suppression in order to reduce the speci city of the quasi-identi ers [
Nevertheless there is a trade o between the utility of the data and the level of anonymization. On one hand, a great perturbation range gives a good randomization but also alters the records at a great extend. Clearly, the data become less expressive. On the other hand, a low bias retains the relevant information, but outlying records mostly remain unvaried and an attacker can identify these easily.
Aron [
As we describe in Section 4, graph summaries can provide a source of a priori knowledge about a linked data set, and have the potential to automate the application of di erential privacy to Linked Data. 2.2
The main idea of Private Information Retrieval (PIR) is that the user requests
a particular element of the database without the database owner knowing which
element the user was interested in [
The main obstacle for traditional (non-SPARQL) multi-server PIR schemes, is that all instances of the database would need to contain the same information. This traditionally did imply the same organisation is in control of all the database instances with its data.
However, this scenario makes collusion of all database instances trivial.
Because of this, more focus was put on research of the single-server PIR scenario.
One of the results was an approach [
In contrast, for federated SPARQL queries the assumption is that each SPARQL
endpoint is controlled by a di erent organisation. This would make collusion
much more unlikely. However, on the other hand, the data which is stored in a
SPARQL endpoint is much more dynamic [
PIR becomes relevant in relation to Linked Data, as SPARQL queries can reveal a lot about the intentions and interests of the query issuing party. If we imagine a hypothetical use case in which open government data is hosted only on the server of a government agency, and made only available via a SPARQL endpoint, then that government agency can monitor all queries to the SPARQL endpoint. If the data were available \in bulk", e.g. as an NTriples le, then all the privacy concerns can be trivially addressed by just downloading the data le and performing all queries locally. However, a malicious data provider will make sure that the data is not available for download or missing important parts.
In such a use case, the government could fully monitor all queries, e.g. made by an NGO or a journalist, as only the SPARQL endpoint provided by the government agency contains the data required to answer the query.
As we discuss in Section 5, the availability of graph summaries for SPARQL endpoints has the potential to enable splitting up a query which can be answered by one SPARQL endpoint to multiple SPARQL endpoints. In our use case, this would enable an NGO or a journalist to hide the details of their query and this their intent from the organisations hosting the SPARQL endpoints. 3
As explained in section 2, in order to apply privacy enhancing approaches to Linked Data, such as di erential privacy or private information retrieval, the contents of the Linked Data sets needs to be known in advance. This is due to the fact that Linked Data is schema-less and fast changing.
Graph summaries can provide a description of the graph, which contains the structure, i.e. the types of links and the classes of entities. As such, it can take the role of a schema as it is used for instance in relational databases. In addition, a graph summary has the bene t of not containing any of the actual information from the graph it summarises, if we assume that the class names and link names contain no information.
Campinas et al. [
Campinas et al. [
In addition, for precise graph summaries the worst case for the size is to be almost as big as the original graph. In contrast, approximate graph summaries are much smaller.
The steps of the algorithm are as follows, more details are in [
Mapping of all nodes to their respective nodes in the summary graph For every node, a corresponding summary node is either created or selected from the list of already generated summary nodes.
Materialisation of summary edges Another pass over all edges of the original graph, in order to decide if that edge needs to be materialised in the summary graph.
After providing formal de nitions for both types of summaries, two
implementations for calculating graph summaries are given in [
Campinas provides the results of an evaluation on over 14 real-world datasets
of various size and complexity in Section 5.3 of [
In comparison to other existing graph summarisation approaches, the
approach presented by Campinas in [
In summary, the approach for graph summaries proposed by Campinas et al. can provide a schema for the schema-less Web of Data, while also having the bene t of not revealing any other properties of a data set.
Graph summaries can provide a source of a priori knowledge about a linked data set, and have the potential to automate the application of di erential privacy to Linked Data.
As described by Aron [
While the use of graph summaries has potential to allow the whole process of anonymising and masking a linked data graph to be automated, there are many reasons to still involve human inspection of the nal data set. In particular, to prove that the responsibilities of an organisation have been ful lled. 5
The availability of graph summaries for SPARQL endpoints has the potential to enable splitting up of queries which can be answered by one SPARQL endpoint to multiple SPARQL endpoints. This would enable an NGO or a journalist to hide the details of their query and this their intent from the organisations hosting the SPARQL endpoints.
In particular, with the availability of graph summaries for all available SPARQL endpoints, we can imagine the role of the query planner to be almost the opposite of query planners which try to optimise the query response time. For private information retrieval, the query planner will attempt to distribute a query across as many SPARQL endpoints as possible. The intended goal then is to make it impossible for any observer with only partial knowledge of the query to determine the goal of the query. This mode of operation could also be called an obfuscating query planner.
Deng et al. [
First we list how the use of graph summaries for di erential privacy addresses
the hard privacy threats as de ned by Deng et al. in [
Identi ability: As entities in the original and anonymised graph are not linkable, the identity of persons is also protected.
Non-repudiation: In addition, as identities are protected, there should be no proof of a persons information being part of the anonymised data set. Detectability: In a similar way, participation of a person in the anonymised data set should be undetectable.
Disclosure of information: Finally, as this approach removes sensitive data before it is released, disclosure of sensitive information is not possible.
In summary, using graph summaries for di erential privacy maintains unlinkability and anonymity of identities in the original data set, and it limits unintended disclosure of information. However, it does not address non-repudiation and detectability.
Next we list how the use of graph summaries for private information retrieval address hard privacy threats: Linkability: Using an obfuscating query planner makes the di erent parts of the query unlinkable to each other, provided there is no collusion between the di erent SPARQL endpoints.
Identi ability: Suitable credentials will be required in order to access all required SPARQL endpoints, if no anonymous access without credentials is available. Therefore the person or organisations initiating the queries is always known.
Non-repudiation: As standard SPARQL access is used, it is not possible to deny having initiated the SPARQL queries.
Detectability: In addition, as SPARQL queries are not sent over an encrypted channel, any potential eavesdropper can listen to the SPARQL queries. Disclosure of information: The information which is hidden from SPARQL endpoints is the intent of the initiator and the original SPARQL query. However eavesdroppers of the SPARQL queries could try to re-assemble the original SPARQL query.
In summary, using graph summaries for private information retrieval, hides the intent behind the split SPARQL queries as the queries are unlinkable if the SPARQL endpoint operators do not collude. In addition, the original query and its intend are not disclosed. However, the privacy threats of identi ability, non-repudiation and detectability are not addressed.
We have introduced the idea of graph summaries as a privacy enhancing technology to enable di erential privacy and private information retrieval.
As graph summaries contain no information about a graph beyond the classes and properties of the original data set, there is no leakage of personally identi able information. Graph summaries can be used almost like the schema for traditional, relational databases. As such they have the potential to provide a conceptual bridge for applying many existing privacy enhancing technologies from relational databases to Linked Data.
In terms of future work, we are planning to implement the graph summary approach as part of a framework for automatic anonymisation of Linked Data sets. In particular, we will develop a testbed for evaluating di erent parameterisations of anonymised release of Linked Data, against several state of the art algorithms for deanonymising graph data as described in the overview of Al Azizy et al. [12]. In addition, we are planning to implement a query processor for obfuscated query planning to enable private information retrieval using graph summaries. 12. Al-Azizy, D., Millard, D., Symeonidis, I., O'Hara, K., Shadbolt, N.: A literature survey and classi cations on data deanonymisation. In: International Conference on Risks and Security of Internet and Systems, Springer (2015) 36{51