Towards Search on Encrypted Graph Data

Abstract

We present an approach where one can execute user de ned SPARQL queries on encrypted graph data. The graph data is only partially revealed to those users authorized for executing a query. The approach is based on eight di erent types of queries, corresponding to the di erent binding possibilities in a single SPARQL triple pattern. The allowed queries can be further restricted by the owner of the graph data, e. g., through pre-de ning a speci c predicate or object. Single triple patterns can be combined to query group patterns as they can be stated in SPARQL queries and allow to execute a wide range of SELECT and ASK queries.

Introduction

When one does not want to provide full public access to some graph data, access control mechanisms can be applied like [ 1 ] that limit access to the data based on, e. g., roles in an organization or credentials issued to individuals. However, there are scenarios where one even wants to go one step further and encrypt the graph data. For example, the knowledge base might be hosted at a service provider that is not fully trusted such as in the cloud [ 2 ]. Legal issues like the Health Insurance Portability and Accountability Act (HIPAA)4 in the US require to encrypt semi-structured data such as medical records and other sensitive health information [ 3 ]. In addition, di erent parties are allowed to view only di erent parts of the data. In another scenario, the graph data might be published in a distributed fashion such as in a peer-to-peer network [ 4 ]. The data owner does not know which peer keeps a local copy of the data, but he wants to restrict access to speci c parties in the network.

A standard approach would encrypt the entire document containing the information to be protected. The only possible operation is to decrypt the entire document, given that the user is in possession of a corresponding decryption key. However, this would not be suitable to the scenarios above as they require a more ne grained and exible solution to access the encrypted graph information. In 4 http://www.gpo.gov/fdsys/pkg/CRPT-104hrpt736/pdf/CRPT-104hrpt736.pdf, last accessed: 19.3.2013 recent time, novel approaches such as functional encryption [ 5 ] and searchable encryption [ 6 ] have been developed to address this issue. Functional encryption de nes a (limited) set of functions that can be applied on the encrypted data by di erent parties. Searchable encryption extends functional encryption by allowing for executing user-de ned operations on the encrypted data. Only at run-time, the operands are bound to their concrete values, which allows for implementing typical information system scenarios like those sketched above.

Our approach for search on encrypted graph data makes use of two-layers: The basic layer provides eight encryption keys for eight views on the encrypted data. These eight di erent views correspond to eight di erent binding possibilities of a single triple pattern in a SPARQL query. The basic layer can be re ned by the data owner on the re nement layer. Here, one can de ne which kind of SPARQL query patterns can be executed on the encrypted data. For example, the data owner can specify that the users can only request instances of a speci c class such as ?x rdf:type foaf:Person. Single query patterns can be combined to query group patterns to formulate a wide range of SELECT and ASK queries on the encrypted data. Please note, blank nodes are supported in our graph search approach as they are encrypted like resources.

In the subsequent section, we describe in more detail our idea of a two-layered approach for searching on encrypted graph data. The related work is presented in Section 3. In Section 4, we present the basic notations for our approach. In Sections 5 and 6, we present the encryption and preparation of the graph data and the execution of queries on that data. 2

Scenario and Envisioned Functionality

A Semantic Web document [ 7 ] consists of several triples and is owned by a data owner. The data owner encrypts the document and publishes it on the web. Di erent users can access parts of the document by performing queries on the encrypted document, i. e., they can search on the encrypted graph document. The data owner de nes which users are allowed to perform which queries. This is done by handing over query keys to the users through a secure channel. A user performs queries on the encrypted document by using the received query keys and self-de ned bindings of the query patterns. The result of a query consists of all triples of the document which satisfy the query.

Thus, our work aims at executing queries based on SPARQL [ 8 ] triple patterns on the encrypted graph data. These patterns allow each part of a triple to be either bound or unbound. Bound parts correspond to parameters that are speci ed in the query whereas unbound parts determine the results of a query. Considering all possible combinations of bound and unbound parts in a SPARQL triple pattern results in eight di erent binding combinations. In our approach, each triple is encrypted individually for each of these eight binding combinations using a corresponding encryption key. As depicted in Fig. 1(a), an encryption key comprises the bound parts of a triple as well as a basic key which de nes the binding combination. Key Creation

Decryption Plaintext Triple Key Creation Encryption Key

Plaintext Triple

Basic Key

Data Owner Restriction

Decryption Key

Encrypted Triple

Encryption Encrypted Triple

Key Creation

Query Key (a) Encrypting triples (b) Creating query keys (c) Performing queries

In order to further restrict the queries that a user can perform on an encrypted document, the data owner de nes restriction patterns. A restriction pattern narrows down the possible query patterns that the user can de ne for querying on the encrypted graph data. To this end, the data owner pre-de nes in a restriction pattern the bound parts of a SPARQL triple pattern. As depicted in Fig. 1(b), a restriction pattern and a basic key are combined into a query key, which is handed over to the users via a secure channel. The basic key de nes the binding combination of a query and the restriction pattern contains the parameters of this query already bound by the data owner.

Performing a query on an encrypted document basically corresponds to decrypting the encrypted triples of this document with a decryption key. As depicted in Fig. 1(c), the decryption key is created from the query key received from the data owner and the user's query pattern. It corresponds to a particular query and encodes all bound query parameters taken either from the query key or from the user's query pattern. If an encrypted triple can successfully be decrypted using a decryption key, the triple satis es the query. If the decryption fails, the triple does not ful ll the query. The decryption of an encrypted triple is successful i the decryption key is identical to the encryption key. This is the case if the combination of the data owner's restriction and the user's query pattern correspond to the bound triple parts of the encryption key. 3

Related Work

A searchable encryption scheme [ 6,9,10 ] allows legitimate users to search encrypted documents for speci c data entries such as triples. The encrypted document is associated with additional metadata and stored on a (potentially untrusted) server such as the cloud. Users search the encrypted document by executing an interactive search protocol with the server. Thus, they communicate with the data owner in order to execute queries. The users receive all triples (in encrypted form) which comply to their query while the server owner learns as little as possible. There are several fundamental di erences between searchable encryption and our approach: i) Searchable encryption deploys interactive protocols with the server owner while we aim for an o ine solution. ii) Searchable encryption usually requires to specify the queries before encrypting the triples. Thus, the encrypted data scales with the number of triples and the list of queries while we aim for a solution which supports any possible query. Our solution even allows to include further encrypted triples to the encrypted document at later points in time. iii) Searchable encryption does not support any ne-grained access control. More precisely, while it may be possible that di erent users can search for di erent triples, it does not support di erent query types. In contrast, our goal is that a user making a query q can only gure out all triples that comply to q while learning nothing about the other encrypted triples.

Attribute-based encryption such as [ 11 ] allows for a more ne-grained access than traditional encryption schemes. Instead of using only one decryption key for each encryption, the encrypted data can be decrypted with di erent decryption keys where each key is associated with some attributes. The data can only be decrypted if the decryption key matches the respective attributes. All of the attribute-based encryption schemes proposed in recent years are covered by functional encryption (e. g., see [ 12,5,13 ]). A functional encryption scheme supports a set of functions and encrypts data such that it can be decrypted for each function using a corresponding decryption key. While functional encryption provides ne-grained o ine access control to encrypted data, it does not support searching on encrypted data. In particular, our requirement that users may freely specify parts of their queries is not covered.

Poh et al. [ 14 ] as well as Kamara and Wei [ 15 ] support searching on encrypted graphs. Both approaches are based on pre-computed indices for each supported query. In order to use them for graph-based documents, one would create an index for each occurring object value since it might later be used for a query. Overall, this would result in as many indices as there are di erent object values. Thus, an attacker would learn how many di erent object values the graph contains. Our approach does not have this problem since the data is encrypted independently from any particular query. Furthermore, query indices created at encryption time must be re-computed and updated if new triples are added. Our approach allows for adding new encrypted triples without changing the already existing encryptions. Relational database solutions such as CryptDB [ 16 ] rely on an online solution with a more or less trusted server. Our approach is designed for o ine use. Furthermore, join operations in CryptDB reveal too much information about the encrypted graph as the ciphertexts in the joins are compared bitwise for equality, thus they become countable. Overall, one might obtain an isomorphic graph that reveals the nature of the original graph. XML based solutions such as [ 17,18 ] require the user to know the internal structure of the queried XML document. In our approach, no information about the encrypted graph is needed. Performing a query only requires a query key.

Basic Notations and Formalization

This section formally de nes the basic components of our approach as introduced in Section 2. Their use is described in Sections 5 and 6.

Plaintext Triples and Plaintext Documents The set of all plaintext triples t is de ned as U U (U [ L) with U as the set of all URIs and L being the set of all literals. It is t = (s; p; o) with s 2 U being the subject of the triple, p 2 U being the predicate, and o 2 U [ L being the object. A graph-based plaintext document d is a set of m triples ti with i = 1 : : : m. It is d = ft1; t2; : : : ; tmg.

Encrypted Triples and Encrypted Documents Encrypting a plaintext triple t results in an encrypted triple c. An encrypted triple is a tuple of eight bit strings. Each bit string supports one of the eight di erent binding combinations of a SPARQL [ 8 ] triple pattern as described in Section 2. It is c = (c---; c+--; c-+-; c--+; c++-; c+-+; c-++; c+++). The indices + and - correspond to the existence and non-existence of a binding in the query at subject, predicate, and object position, respectively. For example, c-+- supports SPARQL queries with a bound predicate that retrieve tuples of subjects and objects for each matching triple. Encrypting a plaintext document d results in an encrypted document dC = fc1; c2; : : : ; cmg.

Basic Keys A basic key kb is a bit string of length l and used for encrypting the triples t of a plaintext document d for a particular binding combination. The data owner choses eight di erent basic keys which are identi ed as k---, k+--, k-+-, k--+, k++-, k+-+, k-++, and k+++. Each of these keys is used for creating a particular bit string of the encrypted triples c. For example, the basic key k+-is used for creating the bit strings c+--.

Queries, Query Patterns, and Query Keys A query is applied on an encrypted document and corresponds to a SPARQL triple pattern. It may have an unbound subject, predicate, and/or object. The type of a query is de ned using the symbols + and - which mark the bound and unbound parts, respectively. For example, a query of type +++ requires a bound subject, a bound predicate, and a bound object. It corresponds to a SPARQL ASK query and asks whether or not the speci ed triple is contained in the document d. All other queries correspond to standard SPARQL queries as they can be stated in SELECT queries. For example, a query of type -++ returns a set of subject URIs and requires a bound predicate and a bound object.

A query is created from a basic key and two query patterns. The basic key de nes the type of the query and the query patterns specify the bound and unbound parts of the query. We distinguish between two di erent types of query patterns which are restriction patterns r and user-de ned query patterns u. A restriction pattern r is de ned a-priori by the data owner and narrows down the possible queries a user can perform. A user-de ned query pattern u represents the query parameters speci ed by the user. The set of all query patterns is de ned as (U [ f?g) (U [ f?g) (U [ L [ f?g). The variable ? identi es unbound parts of a query pattern and corresponds to a variable in a SPARQL triple pattern like ?x. A query pattern is de ned as (s?; p?; o?) with s? as the queried subject, p? the queried predicate, and o? the queried object. A query key kq corresponds to a partially speci ed query which already encodes a basic key kb and a data owner's restriction pattern r. However, a query key does not encode a user's query pattern u. Thus, a complete query is created from a query key by combining it with a user's query pattern u.

Query Functions on Encrypted Data A query function f performs a query on an encrypted document dC and returns a result based on all matching triples t of the plaintext document d. A query function requires a query key kq, a user's query pattern u, and the encrypted document dC as input. Each query function supports one particular type of queries. Thus, there are eight di erent query functions identi ed as f---, f+--, f-+-, f--+, f++-, f+-+, f-++, and f+++. Again, the symbols + and - mark the bound and unbound parts of the supported queries, respectively. For example, + at the rst position requires a subject to be speci ed in the query. At the second or the third position, respectively, the symbol + requires a predicate or an object to be speci ed. The result of a query function f also depends on the symbols + and -. The result can be a set of triples, a set of tuples, a set of URIs, a set of literals, or a boolean value. For example, the query function f+-- returns a set of tuples (y; z) with y 2 U and z 2 U [ L.

The bound and unbound parts of a query (s; p; o) are speci ed by a user's query pattern u = (su; pu; ou) and the data owner's restriction pattern r = (sr; pr; or), which is encoded in a query key kq. The query patterns must comply with the type of the query function. For example, the query function f-++ requires either pr 6= ? or pu 6= ? and either or 6= ? or ou 6= ?. Thus, the data owner may de ne a restriction pattern r = (?; rdf:type; ?) which speci es rdf:type as the predicate of the query being performed. Then, a user can only query for instances of classes, i. e, triples with the predicate rdf:type. In addition, the user has to specify a query pattern u = (?; ?; ou) with ou 6= ? and cannot just leave the object position unbound (which would be possible with the query function f-+-). Furthermore, a value speci ed in the restriction pattern r cannot be speci ed in the user's query pattern u as well. Thus, the data owner can restrict the possible queries a user can perform by specifying the corresponding parts in the restriction pattern r.

For example, the query function f--- returns the complete plaintext document d if neither the restriction pattern r = (sr; pr; or) nor the user's query pattern u = (su; pu; ou) specify any particular binding, i. e., URI or literal. On the other hand, the function f+-- requires either sr 6= ? or su 6= ?. The function searches for all triples t = (s; p; o) 2 d with s = sr or s = su and returns a set of tuples (p; o). The function f++- requires both a subject and a predicate to be speci ed in the query. For every matching triple t = (s; p; o) 2 d, the object o is returned. Finally, the function f+++ corresponds to a SPARQL ASK query. It returns T RU E i a query (s; p; o) matches a triple in d, i. e., i (s; p; o) 2 d.

Encrypting Graph-based Documents for Querying In order to search on encrypted graph-based documents, one rst needs to prepare and encrypt the plain-text triples in an appropriate way. These tasks are part of the general process of searching on graph-based documents, which can be divided into six steps as presented Fig. 2. The rst three steps correspond to the encryption phase in which a plaintext document d is encrypted. The fourth and fth step correspond to the query preparation phase in which the data owner de nes the queries to be performed on the encrypted document. In the following, the details of the rst ve steps are explained. The sixth step corresponds to the querying phase carried out by the user. It is presented in Section 6.

Step 1 Choosing basic keys

Step 2 Creating encryption keys Encryption phase

Step 3 Encrypting the triples

Step 4 Creating query keys

Step 5 Distributing query keys to Users

Step 6 Querying the encrypted document Query preparation phase

Query phase

Step 1: Choosing Basic Keys The data owner choses eight di erent basic keys kb which form the foundation of creating encryption keys kt. Each basic key kb de nes a particular query type and is thus used for one of the eight query functions f de ned in Section 4. If the data owner does not de ne a restriction pattern r, i. e., if r = (?; ?; ?), a basic key kb is identical to a query key kq which is provided to the user. A particular set of basic keys is only used for one plaintext document. This ensures that a user who is able to query one document will not be able to query another document using the same basic keys.

Step 2: Creating Encryption Keys The data owner creates a symmetric encryption key kt for each plaintext triple t 2 d and each basic key kb. An encryption key kt 2 Kt is a bit string of length l with Kt f0; 1gl being the set of all encryption keys. It encodes a basic key kb and those parts of a triple t = (s; p; o) which are required for a corresponding query. For example, the basic key k+-- is encoded into an encryption key kt together with the triple's subject s. Creating an encryption key kt requires a hash function and a combining function %. A hash function transforms a bit string of arbitrary length to a xed length hash value [ 19 ]. Using l as the length of the resulting bit string, the hash function is de ned as : f0; 1g ! f0; 1gl. The hash function is used for reducing the possibility of creating identical encryption keys for di erent input data. An example hash function is SHA-2 [ 20 ] with l = 256. The combining function % combines a single bit string b and a set of n bit strings bi with i = 1; : : : ; n into a single bit string. The function is used to create the encryption key kt based on di erent input data. Given a product N of two large prime numbers, the function The function int transforms a bit string into an integer value and bit transforms an integer into a bit string. In order to create an encryption key kt with the combining function %, a pre x is attached to each part of the triple t. The pre x is used to identify the triple's subject, identi es the triple's predicate, and marks the triple's object. Table 1 depicts the details of creating an encryption key kt for di erent basic keys kb.

Step 3: Encrypting the Triples The encryption key kt is used for encrypting those parts of the triple which are not already encoded into kt. For example, an encryption key kt based on a basic key k+-- encrypts the predicate and object of a triple t. The ciphertext resulting from this operation is denoted as c+--. Encrypting a triple t with an encryption key kt is conducted using an encryption function enc. The function requires a bit string representation of the triple and the encryption key as input and returns an encrypted bit string. It is de ned as enc : Kt f0; 1g ! f0; 1g . Table 1 depicts the details of encrypting a single triple t. Each triple t 2 d is encrypted for each of the eight basic keys kb. This results in an encrypted triple c = (c---; c+--; c-+-; c--+; c++-; c+-+; c-++; c+++). The ciphertext c+++ is created by encrypting the empty bit string ".

Step 4: Creating Query Keys The data owner de nes the queries which can be applied on the document by creating a query key kq for each allowed query. As de ned in Section 4, a query key kq encodes a basic key kb and a restriction pattern r = (sr; pr; or). Since a query key is used in the decryption process, its creation is similar to that of a symmetric encryption key kt. As depicted in Table 2, the creation of a query key is also based on the combining function %. The bound parts of the data owner's restriction pattern r are rst associated with a pre x de ning their function within a triple (see above). The pre xed strings are then combined into a query key together with the basic key by using the function %. The basic key also de nes the number of possible query keys to be created. For example, the basic key k+-- can be used for creating the query keys kr?? and ku??. The index r states that the corresponding part of the krr? = %(k++-; f jjsr; jjprg) kru? = %(k++-; f jjsrg) kur? = %(k++-; f jjprg) kuu? = %(k++-; fg) triple is pre-de ned by the data owner's restriction pattern r and u indicates that the user must specify the part within the query pattern u. The index ? marks the unbound parts, which are returned as the query result.

Step 5: Distributing Query Keys to Users Finally, the data owner sends a set of query keys kS to a user. In doing so, the data owner authorizes the user to perform the queries speci ed by the query keys kq 2 kS . The set kS is transmitted through a secure channel in order to ensure that only authorized users can perform the queries. 6

Performing Queries on Encrypted Documents

In the sixth step, a user queries an encrypted document dC by decrypting each triple c 2 dC with the received query keys kq 2 kS . For each of the query keys, the user must de ne a corresponding query pattern u. As described in Section 4, the combination of a query key and the user's query pattern corresponds to a SPARQL query which is applied by a corresponding query function f . A query key encodes a data owner's restriction pattern r. The more parts a data owner speci es in the restriction pattern, the fewer choices does the user have to formulate a query. For example, the query function f-++ requires a predicate and an object to be either speci ed in r or in u. If the data owner de nes r = (?; rdf:type; foaf:Person), a user can only search for resources of rdf:type foaf:Person from the FOAF [ 21 ] vocabulary. In this case, the user can only state the query u = (?; ?; ?) adding no further constraints on the owner's restriction r. Only by this, the combination of u and r result in valid parameters for f-++. However, if the data owner de nes r = (?; rdf:type; ?), the user can specify di erent values for the query pattern's object. For example, the user may de ne u = (?; ?; foaf:Organization) to search for all resources of rdf:type foaf:Organization. Below we rst describe how a SPARQL query containing a single triple pattern is executed, before we demonstrate the application of a SPARQL query with a query group pattern. A single SPARQL query is performed by applying a single query function f . This requires a query key kq, a user's query pattern u, and an encrypted document dC . A query function basically tries to decrypt each encrypted triple c 2 dC . This process can be further subdivided into three sub-steps. In the rst sub-step, the decryption key is created which is used in the second sub-step to decrypt the encrypted triples. If the decryption is successful, the corresponding plaintext triple t 2 d will be used for creating the query result in the third sub-step.

Step 6a: Computing Decryption Keys A decryption key kt0 is created similar to the encryption key kt. It encodes a query key kq and the user's query pattern u = (su; pu; ou). The number of possible combinations of di erent query keys kq and query patterns u depend on the query function f . For example, a query function f++- requires that the subject and object of the query is either de ned by the user's query pattern u or encoded as a query restriction in the query key. Table 3 depicts the creation of a decryption key kt0 based on the query key kq and the user's query pattern u.

Step 6b: Decrypting the Triples The query function tries to decrypt each encrypted triple c 2 dC using a decryption key kt0 2 Kt and a decryption function dec. The function is similar to the encryption function enc. It requires a decryption key kt0 and a bit string as input and returns a decrypted bit string as output. The decryption function is de ned as dec : Kt f0; 1g ! f0; 1g . If the decryption key kt0 was created correctly, it is kt = kt0. In this case, the decryption process is inverse to the encryption operation, i. e., b = dec(kt0; enc(kt; b)) with b being a bit string representation of the plaintext triples t.

Step 6c: Creating the Query Result The created query result corresponds to the output of a query function f . Creating this output is based on the decryption function dec. If the decryption process of an encrypted triple c is successful, the corresponding plaintext triple t ful lls the speci ed query. If the triple does not ful ll the query, it is kt 6= kt0 and b 6= dec(kt0; enc(kt; b)). In this case, the triple t is not part of the query result. A complex SPARQL query with n triple patterns is conducted by performing a separate query for each of the n patterns and combining their results. The query corresponds to a set kS of n query keys ki with i = 1 : : : n. First, all queries of type +++ are applied. Such queries correspond to SPARQL ASK queries. If at least one ASK query is not satis ed, the whole query cannot be satis ed. In this case, the querying can already be stopped. After applying an ASK query, the corresponding query key is removed from kS. Thus, all query keys ki remaining after the rst step contain at least one unbound variable. Second, the remaining queries are applied as well. The result of each query contains all possible bindings of the query's variables. It can be interpreted as a table with its columns being the variables of the query and its rows being the di erent solutions [ 22 ]. The result tables of all queries are incrementally combined using the join operator on [ 22 ]. Finally, the complete query result is returned. 7

Implementation and Evaluation

We have implemented our approach by using established cryptographic algorithms. For the encryption function enc, we use the Advanced Encryption Standard (AES) [ 23 ] with a key length of 256 bits. For the hash function , we use the Secure Hash Algorithm 2 (SHA-2) [ 20 ] with an output length of 256 bits. As feature by design, the length of the hash value and the key length of the encryption function are the same. Thus, the computed hash value can directly be used as encryption key. The combining function % is based on the RSA algorithm. In our implementation, we use a value of N with 2048 bits [ 24 ].

As rst evaluation of our approach, we have used the Berlin SPARQL benchmark (BSBM) [ 25 ] which provides tools for generating synthetic graph data and SPARQL queries that simulate a user searching the data. We have used the tools to create three di erent RDF graphs for our experiment with 5 104, 105, and 2 105 triples, respectively. Encrypting a document with 5 104 triples takes about 56 minutes. Increasing the size of the plaintext document by a certain factor also increases the time required for its encryption by the same factor. The runtime of each query depends on the number of triples in the document and on the number of triple patterns in the query. For example, evaluating a query with n triple patterns for m 105 triples takes about n m 950 ms. This constant factor is due to the design of our query algorithm as described in Section 6. 8

Conclusion and Future Work

We have presented an approach for searching on encrypted graph data. Queries are authorized by the owner of the encrypted data who can further restrict the allowed queries. A query is applied by decrypting the encrypted triples with a query key received from the data owner. Our approach supports a subset of the SPARQL query language including queries of type SELECT and ASK.

References

1. Knechtel , M. , Stuckenschmidt , H.: Query-based access control for ontologies . In: Web Reasoning and Rule Systems , Springer ( 2010 ) 73 { 87

2. Bellare , M. , Boldyreva , A. , O'Neill , A. : Deterministic and e ciently searchable encryption . In: CRYPTO . Springer ( 2007 ) 535 { 552

3. Scholl , M. , Stine , K. , Hash , J. , Bowen , P. , Johnson , A. , Smith , C.D. , Steinberg , D.: An introductory resource guide for implementing the HIPAA security rule ( 2008 )

4. Cao , X. , Klusch , M. : Dynamic semantic data replication for k-random search in peer-to-peer networks . In: NCA 2012 , IEEE ( 2012 ) 20 { 27

5. Boneh , D. , Sahai , A. , Waters , B. : Functional encryption: A new vision for publickey cryptography . CACM 55 ( 11 ) ( 2012 ) 56 { 64

6. Abdalla , M. , Bellare , M. , Catalano , D. , Kiltz , E. , Kohno , T. , Lange , T. , MaloneLee , J., Neven , G. , Paillier , P. , Shi , H. : Searchable encryption revisited . In: CRYPTO . ( 2005 ) 205 { 222

7. Ding , L. , Finin , T. : Characterizing the semantic web on the web . In: ISWC , Springer ( 2006 ) 242 { 257

8. Prud'hommeaux , E., Seaborne , A. : SPARQL query language for RDF . W3C ( 2008 ) http://www.w3.org/TR/rdf-sparql-query/.

9. Song , D.X. , Wagner , D. , Perrig , A. : Practical techniques for searches on encrypted data . In: S&P 2000 , IEEE ( 2000 ) 44 { 55

10. Goh , E.J.: Secure indexes . IACR Cryptology ePrint Archive 2003 ( 2003 ) 216

11. Sahai , A. , Waters , B. : Fuzzy identity-based encryption . In: EUROCRYPT 2005 , Springer ( 2005 ) 457 { 473

12. O 'Neill , A. : De nitional issues in functional encryption . IACR Cryptology ePrint Archive 2010 ( 2010 ) 556

13. Boneh , D. , Sahai , A. , Waters , B. : Functional encryption: De nitions and challenges . Theory of Cryptography 6597 ( 2011 ) 253 { 273

14. Poh , G.S. , Mohamad , M.S. , Z 'aba, M.R.: Structured encryption for conceptual graphs . In: IWSEC . ( 2012 ) 105 { 122

15. Kamara , S. , Wei , L. : Garbled circuits via structured encryption . In: WAHC . ( 2013 )

16. Popa , R.A. , Red eld, C.M.S. , Zeldovich , N. , Balakrishnan , H.: Cryptdb: protecting con dentiality with encrypted query processing . In: SOSP . ( 2011 ) 85 { 100

17. Wang , W.H. , Lakshmanan , L.V.S.: E cient secure query evaluation over encrypted XML databases . In: VLDB. ( 2006 ) 127 { 138

18. Brinkman , R. , Feng , L. , Doumen , J. , Hartel , P.H. , Jonker , W.: E cient tree search in encrypted data . Information Systems Security 13 ( 3 ) ( 2004 ) 14 { 21

19. Rogaway , P. , Shrimpton , T. : Cryptographic hash-function basics . In: FSE . Volume 3017 ., Springer ( 2004 ) 371 { 388

20. NIST: Secure hash standard . FIPS PUB 180-4 ( 03 2012 ) http://csrc.nist.gov/ publications/fips/fips180-4/fips-180-4.pdf.

21. Brickley , D. , Miller , L. : FOAF vocabulary speci cation ( 2010 ) http://xmlns.com/ foaf/spec/.

22. Cyganiak , R.: A relational algebra for SPARQL . Technical report, HP Labs ( 2005 )

23. NIST: Advanced encryption standard . FIPS PUB 197 ( 2001 ) http://csrc.nist. gov/publications/fips/fips197/fips-197.pdf.

24. Rivest , R. , Shamir , A. , Adleman , L. : A method for obtaining digital signatures and public-key cryptosystems . CACM 21 ( 2 ) ( 1978 ) 120 { 126

25. Bizer , C. , Schultz , A. : The berlin SPARQL benchmark . IJSWIS 5 ( 2 ) ( 2009 ) 1 { 24