Luca Ferretti
email: luca.ferretti@unimore.it

Michele Colajanni
email: michele.colajanni@unimore.it

Mirco Marchetti
email: mirco.marchetti@unimore.it

Guaranteeing Correctness of Bulk Operations in Outsourced Databases

Keywords: database, outsourcing, cloud, integrity, authenticity, completeness, aggregate, signature, accumulator, bilinear map, ECRH, BLS

The adoption of public cloud services, as well as other data outsourcing solutions, raises concerns about confidentiality and integrity of information managed by a third party. By focusing on data integrity, we propose a novel protocol that allows cloud customers to verify the correctness of results produced by key-value databases. The protocol is designed for supporting efficient insertion and retrieval of large sets of data through bulk operations in read and append-only workloads. In these contexts, the proposed protocol improves state-of-the-art by reducing network overheads thanks to an original combination of aggregate bilinear map signatures and extractable collision resistant hash functions.

Introduction

The adoption of cloud services and other data outsourcing solutions is often hindered by data confidentiality needs and by limited trust about the correctness of operations performed by the service provider. Data confidentiality issues are addressed by several proposals based on encryption schemes (e.g., [START_REF] Ferretti | Distributed, concurrent, and independent access to encrypted cloud databases[END_REF][START_REF] Hacigümüş | Executing sql over encrypted data in the database-service-provider model[END_REF][START_REF] Popa | CryptDB: protecting confidentiality with encrypted query processing[END_REF]). The correctness may be guaranteed through standard authenticated data structures [START_REF] Miller | Authenticated data structures, generically[END_REF][START_REF] Tamassia | Authenticated data structures[END_REF] based on message authentication codes [START_REF] Bellare | Keying hash functions for message authentication[END_REF] and digital signatures [START_REF] Nist | Digital signature standard[END_REF] that are affected by large network overheads and by limited database operations. Recent proposals, such as [START_REF] Hong | Query integrity verification based-on mac chain in cloud storage[END_REF][START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Narasimha | Dsac: An approach to ensure integrity of outsourced databases using signature aggregation and chaining[END_REF][START_REF] Popa | Enabling security in cloud storage slas with cloudproof[END_REF], improve standard protocols but they cannot be adopted to guarantee results correctness in outsourced keyvalue databases because they incur either in network overheads [START_REF] Hong | Query integrity verification based-on mac chain in cloud storage[END_REF][START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Popa | Enabling security in cloud storage slas with cloudproof[END_REF] or in high computational costs [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Narasimha | Dsac: An approach to ensure integrity of outsourced databases using signature aggregation and chaining[END_REF][START_REF] Crosby | Authenticated dictionaries: Real-world costs and trade-offs[END_REF]. For these reasons, we propose Bulkopt, a novel protocol that allows us to detect unauthorized modifications on outsourced data, as well as the correctness of all results produced by a cloud database service. Bulkopt guarantees authenticity, completeness and freshness of results produced by outsourced databases including cloud related services. It is specifically designed to work efficiently in read and append-only workloads possibly characterized by bulk operations, where large amounts of records may be inserted in the key-value database through one write operation. Moreover, Bulkopt supports efficient fine-grained data retrievals by reducing network overhead related to the verification of bulk read operations in which multiple, possibly dispersed, keys are retrieved at once.

Closer cryptographic protocols [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF][START_REF] Kosba | Trueset: Faster verifiable set computations[END_REF] proposed for memory checking data model [START_REF] Blum | Checking the correctness of memories[END_REF] efficiently support operations on large numbers of records, but they do not support standard database queries and they cannot be immediately extended to database outsourcing scenarios. Bulkopt supports standard insert and read operations on key-value databases and limits communication overhead and verification costs of bulk operations. It recasts the problem of verifying the correctness of results produced by an untrusted database in terms of set operations by leveraging an original combination of bilinear map aggregate signatures [START_REF] Boneh | Short signatures from the weil pairing[END_REF] and extractable collision resistant (ECR) hash functions [START_REF] Bitansky | From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again[END_REF][START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF].

The remainder of the paper is structured as following. Section 2 outlines the system and threat models assumed by the Bulkopt protocol. Section 3 describes the main ideas behind the Bulkopt protocol and outlines the high-level design of the solution. Section 4 proposes the implementation based on aggregate signatures and ECR hash functions. Section 5 outlines the Bulkopt main contributions and compares it with related work. Finally, Section 6 concludes the paper and outlines future work.

System and threat models

We adopt popular terminology for database outsourcing [START_REF] Samarati | Data protection in outsourcing scenarios: Issues and directions[END_REF]. We identify a data owner that stores data on a database server managed by an untrusted service provider, and many authorized users that retrieve data from the server. The server offers a query interface that can be accessed by the data owner and the authorized users to retrieve values by providing a set of keys. We consider a publicly verifiable setting [START_REF] Samarati | Data protection in outsourcing scenarios: Issues and directions[END_REF] and assume that only the data owner knows his private key, that is required to insert data into the database, and that authorized users know the public key of the owner that is required to verify results produced by the server. We note that in this first version of the protocol, we do not consider delete and update operations and focus on efficient insert and read database operations.

Our threat model assumes that the owner and all users are honest, while the server is untrusted. In particular we assume that the server (or any other unauthorized party, that does not have legitimate access to the private key) may try to insert, modify and delete data on behalf of the owner. The Bulkopt protocol allows all users and the owner to verify the correctness of all results produced by the server. We distinguish three types of results violations:

-authenticity: results that contain records that have never been previously inserted by the data owner or that have been modified after insertion; -completeness: results that do not include all keys requested by the client but that have been previously inserted by the data owner; -freshness: results that are based on an old version of the database. In the considered operation workload the server can only violate freshness if he returns results that are both authentic and complete, but refer to an old version of the database.

Protocol overview

We describe the formal model used by Bulkopt to represent data and operations (Section 3.1) and to express authenticity and completeness guarantees as set operations (Sections 3.2 and 3.3). We note that since in this version of the protocol we do not consider delete and updates, the server can only violate freshness if he returns results that are both authentic and complete, but that refer to an old version of the database. As a result, clients can detect freshness violations by always using updated cryptographic digest to compute authenticity and completeness proofs. For details about verification operations please refer to the candidate implementation of the protocol described in Section 4.

Data model

We model the key-value database as a set of tuples

D = {(k, v)},
where k is the key and v is the value associated to k. The owner populates the key-value database by executing one or more insert operations. For each insert operation the owner sends a set of tuples B i = {(k, v)}, where i is an incremental counter that uniquely identifies an insert operation. The set B i contains at least one tuple, and may contain several tuples in case of bulk insertions. Without loss of generality, in the following we refer to each set of tuples B i as a bulk. We define as K i the set of keys included in B i , and D n = ∪ n i=1 B i the set of records stored in the database after n bulk insertions.

We assume that the server has access to a lookup function that given a set of keys {k} allows him to retrieve the set of insert operation identifiers {i} in which these keys were sent by the owner. Such function can be obtained by deploying any standard indexing data structure of preference (e.g., a B-tree).

Any client (including the owner) can issue a read operation requesting an arbitrary set of keys X = {k}. If the server behaves correctly he must return the subset of the database A, defined as:

A = {(k, v) ∈ D n | k ∈ X} (1)
We define R as the set of keys included in A, that is:

R = {k ∈ X | (k, v) ∈ A} (2)
While executing read operations issued by clients, the server distinguishes two different sets of keys: T and T .

T is the union of all sets K i that contain at least one key among those requested by a client:

T = K i | K i ∩ X = ∅ (3)
Within each K i we identify two subsets of keys:

R i = K i ∩ X and Q i = K i \R i .
We define Q as the union of all sets Q i , and we note that the union of all sets R i is equal to set R (see Equation ( 2)). Thus, set Q is the complement of R in T .

T is the union of all sets K i that do not contain any key among those requested by a client:

T = K i | K i ∩ X = ∅ (4)
To better explain how these sets are built and the relationships among them, we refer to a simple example shown in Figure 1. In this example we have a key- value database on which the owner already executed five bulk insert operations, each involving a different amount of tuples. The keys included in the database are represented by sets K 1 to K 5 . We assume that a legitimate client executes a read operation, asking to retrieve six keys belonging to three different bulks. The set of keys requested is represented by X. Since X includes keys belonging to bulks K 1 , K 3 and K 4 , all keys of these bulks belong to T , while T includes all keys belonging in the remaining bulks (K 2 and K 5 ). Sets R 1 , R 3 and R 5 include only the keys requested by the client and belonging to K 1 , K 3 and K 5 , respectively. Set R includes all the keys belonging to the union of R 1 , R 3 and R 5 . Sets Q 1 , Q 3 and Q 5 include only the keys that were not requested by the client and that belong to K 1 , K 3 and K 5 , respectively. Finally, set Q includes all the keys belonging to the union of Q 1 , Q 3 and Q 5 .

Sets Q and T are the main building blocks that Bulkopt leverages to identify a violation of the security properties or to prove the correctness of results produced by the server.

Authenticity

Bulkopt builds proofs of authenticity by demonstrating that:

R ∪ Q ∪ T = K D ( 5
)
where K D represents the set of keys included in D n . We recall from Section 2 that authenticity is violated if the server produces a result containing a key that has not been inserted by the owner. Let us assume that R includes a fake key k f that has been created by the server but does not belong to K D . Then it is obvious that Equation ( 5) does not hold, since R is not a subset of K D . An obvious solution to demonstrate that R is a subset of K D would be for the client to have the complete set K D . Of course this is not applicable, since it would require all clients to maintain a local copy of the whole key-value database.

To overcome this issue, Bulkopt requires the owner to maintain a cryptographic accumulator σ(K D ) that represents the state of the keys stored in the database D n . This accumulator is updated after each insert operation and has to be available to all users. Moreover, the server builds two witness data structures W Q and W T that represent the sets Q and T , and sends them to the client together with its response A. We remark that cryptographic accumulators and witnesses are small and fixed-size data structures, that can be transmitted with minimal network overhead [START_REF] Benaloh | One-way accumulators: A decentralized alternative to digital signatures[END_REF][START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF].

To verify Equation ( 5) a client can extract the set of keys R from A, and use two accumulators verification functions. In particular, it checks whether the witness data structures received by the database validates the results with respect to the requested data and the current state of the database that is maintained locally. Intuitively, the client verification process can be represented as following:

verify (verify (σ(R), W Q ) , W T ) ? = σ(K D ) (6)
where verify denotes accumulators verification functions. If Equation ( 6) is verified, then the user knows that the two witnesses produced by the server are correct and that Equation ( 5) is also verified. Hence R is a subset of K D and authenticity holds. On the other hand, if Equation ( 6) is not verified, either the witnesses produced by the server are not correct or R is not a subset of K D . In both cases, the client is able to efficiently detect a misbehavior of the server.

Completeness

Bulkopt builds proofs of completeness by demonstrating that:

X ∩ (K D \R) = ∅ (7)
that is, the set of keys requested by the client X and the set of keys not returned by the server K D \R share no common keys. We recall that K D \R is equal to Q ∪ T , hence Equation ( 7) can be expressed as the following equation:

X ∩ (Q ∪ T ) = ∅ (8)
Bulkopt proves such conditions by leveraging properties of ECR hash functions.

In particular, as shown by [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF], ECR hash functions can be used to efficiently express set intersections by using polynomial representations of sets. That is, an empty intersection between sets correspond to polynomials having great common divisor (gcd ) equal to 1 (that is, informally we say that since the sets do not share any common elements, the corresponding polynomials do not have common roots).

Let us denote as C M (s) a polynomial representation of a generic set M w.r.t. variable s [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF][START_REF] Freedman | Efficient private matching and set intersection[END_REF], and a set P = Q ∪ T . To prove that the gcd of the polynomials is 1, the server must generate two polynomials ṗ, ẋ such that:

C P • ṗ + C X • ẋ = 1, (9)
The server sends witnesses W P , W ṗ and W ẋ in addition to W Q and W T that were already sent to prove authenticity. A user can now exploit verification functions of the considered cryptographic signature to verify Equation [START_REF] Crosby | Authenticated dictionaries: Real-world costs and trade-offs[END_REF]. If Equation ( 9) is verified, then the client knows that the witnesses produced by the server are correct and that Equation ( 7) is also verified. Hence R includes all keys X requested by the client that are available in the server database, and completeness holds. On the other hand, if Equation ( 9) is not verified, either the witnesses produced by the server are not correct or X shares common elements with sets of keys Q or T that were not sent by the server, thus violating completeness. In both cases, the client is able to efficiently detect a misbehavior of the server.

Protocol Implementation

In this section we describe the Bulkopt protocol by referring to its main three phases: setup and key generation (Section 4.1), insert operations (Section 4.2) and read operations (Section 4.3).

Setup and key generation

Setup. Let g be a generator of the cyclic multiplicative group G of prime order p, G T a cyclic multiplicative group of the same order and ê : G × G → G T be the pairing function that satisfies the following properties: bilinearity: ê(m a , n b ) = ê(m, n) ab ∀m, n ∈ G, a, b ∈ Z * p ; non-degeneracy: ê(g, g) = 1; computability: there exists an efficient one-way algorithm to compute ê(m, n), ∀m, n ∈ G.

Let h be a cryptographic hash function and h z (•), h g (•) be two full domain hash functions (FDH) secure in the random oracle model [START_REF] Bellare | The exact security of digital signatures-how to sign with rsa and rabin[END_REF][START_REF] Boneh | Short signatures from the weil pairing[END_REF] defined as following:

h z : {0, 1} * → Z * p ( 10
)
h g : {0, 1} * → G (11)
Let us denote as C M (s) the characteristic polynomial that uniquely represents the set M , generated by using as roots of the polynomial the sum opposite of the elements of the set and as variable the secret key s [START_REF] Preparata | Computational complexity of fourier transforms over finite fields[END_REF]. Polynomial C M (s) can be computed as following:

C M (s) = m∈M (m + s) (12)
Let F M = (f (M ), f (M )) be the output of an extractable collision resistant (ECR) hash function [START_REF] Bitansky | From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again[END_REF] with secret key (s, α) ∈ Z * p × Z * p and public key [g, g s , . . . , g s q , g α , g αs , . . . , g αs q ], where M denotes a set of values m ∈ Z * p . The output of the function can be computed through two different algorithms depending on the knowledge of the secret key s. For this reason, we denote as f sk (M ), f sk (M ) the computation of (f (M ), f (M )) with knowledge of the secret key and f pk (M ), f pk (M ) the computation of (f (M ), f (M )) with only knowledge of the public key. We will use notation F M , f (M ) and f (M ) to identify the black-box outputs of the functions when it is indifferent if they were computed with or without knowledge of the secret key. Functions f sk (M ) and f sk (M ) can be computed by using straightforwardly the polynomial C M (s) shown in Equation ( 12) as following:

f sk (M ) = g C M (s) = g |M | i=1 (mi+s) , (13)
f sk (M ) = g αC M (s) = g α |M | i=1 (mi+s) , (14)
Functions f pk (M ) and f pk (M ) can be computed by using the coefficients of the polynomial C M (s). That is, if we consider the set of the coefficients

{a i } i=[1,...,|M |] of the polynomial C M (s) such that C M (s) = |M | i=1 a i • s i , f pk (M ) and f pk (M )
can be computed as following:

f pk (M ) = |M | i=1 g s i ai ( 15
)
f pk (M ) = |M | i=1 g αs i ai (16)
Although functions (f sk (•), f sk (•)) and (f pk (•), f pk (•)) have the same behavior, computing of (f sk (•), f sk (•)) is more efficient due to the computation of only one exponentiation in the group G. Without knowledge of the secret key, ECR hash functions can be verified as following:

ê(f (M ), g α ) ? = ê(f (M ), g) (17)
Otherwise, the secret key allows a more efficient verification:

f (M ) α ? = f (M ) (18)
Although knowledge of the secret key improves the algorithm efficiency, it allows one to cheat in the computation of the hash function. Hence, it cannot be given to parties that have advantages in breaking the security of the ECR hash function. Key Generation. We denote the owner's secret and public keys as sk and pk and generate them as follows:

sk = (u, s, α), (u, s, α) R ← -Z * p × Z * p × Z * p ( 19
)
pk = (U, [g s , . . . , g s q , g α , g αs , . . . , g αs q ]), U = g u (20

)
where q ∈ N must be greater than or equal to the maximum number of records involved for each insert or read operation, and u, s and α be different from each other.

Insert operations

The owner issues an insert operation by sending the tuple (B i , σ i , Γ i ), where:

i ∈ N is the operation identifier, that is the incremental counter maintained locally by the owner and by the server that identifies the insert operation (see Section 3); -B i = {(k, v)} is the set of keys and records inserted in the database at operation i. We also denote as K i the set of the keys {k} inserted in this operation; σ i is the bulk signature of the set of keys K i inserted at operation i. It is computed by the tenant as:

σ i (K i ) = [h g (i) • f sk (K i )] u , h g (i) • f sk (K i ) u = = h g (i) • g k∈K i (k+s) u , h g (i) • g α k∈K i (k+s) u (21)
-Γ i is the set of the record signatures of the records B i , computed by using a BLS aggregate signature scheme [START_REF] Boneh | Short signatures from the weil pairing[END_REF]:

Γ i (B i ) = {γ i (k, v)} (k,v)∈Bi (22) γ(k, v) = h g (k v) u ( 23
)
where denotes the concatenation operator. We assume that the concatenation of the values k and v does not compromise the security of h g (•). If the security of the candidate implementation of h g (•) in this context, one should apply a collision resistant hash function or a message authentication code algorithm on the value v previous to the concatenation operation [START_REF] Bellare | Keying hash functions for message authentication[END_REF].

We note that the bulk signature σ i (Equation ( 21)) is similar to the computation of a bilinear map accumulator [START_REF] Nguyen | Accumulators from bilinear pairings and applications[END_REF]. The original scheme would compute the signature of f sk (K i ) as f sk (K i ) u . Our scheme differs for the factor h g (i) u , that could be seen as a BLS signature of the operation identifier i. This variant allows us to bind the bulk signature σ i (K i ) to the operation identifier i in which the insert operation is executed. As we describe in Section 4.3, this design choice also allows us to verify correctness of the server answers by using security proofs that were originally proposed for the memory checking setting [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF].

Both the owner and the server keep track of the operation identifier i locally, without exchanging it in each insert operation. After each insert operation, the server stores all records B i , the bulk signatures σ i and the record signatures Γ i in the database associated to the operation identifier i.

The owner does not store any bulk signature σ i or record Γ i , but he maintains a cryptographic structure of constant size to keep track of the state of the database. We call it the database signature D = (σ last , F D last ), where last is the value of the operation identifier i for the last insert operation executed on the server, and σ last and F D last are the bulk signature and ECR hash function of all the keys inserted in the database.

The owner computes the bulk signature σ last as following:

after the first insertion (i = 1) he sets the initial value of the database signature as σ 1 = σ 1 ; after any other insert operation (i > 1), the owner computes the database signature σ i by computing the product of the current version of the database signature σ i-1 and the bulk signature σ i of the last executed insert operation as

σ i = σ i-1 • σ i-1 .
As a result, the value of the database signature σ last is equal to the product of all the bulk signatures σ i ever sent by the owner to the server:

σ last = i=last i=1 σ i ( 24
)
The owner computes the database ECR hash function F D last as following:

after the first operation (i = 1), the database accumulator is equal to the ECR hash function of the keys included in the first bulk of data, that is F D1 = (f sk (K 1 ), f sk (K 1 )); after any other operation (i > 1), the database accumulator is computed as

F Di = F C K i (s)
Di-1 . As a result, the value of F D last after the last insert operation is the following:

F D last = (g last i=1 C K i (S) , g α last i=1 C K i (S) ) ( 25
)

Read operations

To execute a read operation a client must send a set of keys X = {k} to the server. The server returns the following tuple:

response (X) := (I, A, π auth , π comp , π rec ) ( 26
)
where I = {i} is the set of the operation identifiers associated to the bulks that include at least one of the keys X requested by the client; A = {A i } i∈I is the set of the key-value records that compose the actual response to the client, grouped by the corresponding operation identifier i from which the server retrieved it; π auth , π comp and π rec are the keys authenticity proof, the keys completeness proof and the records authenticity proof used to prove keys authenticity, completeness for the returned keys and authenticity of the values associated to the keys, respectively. Although from a security perspective keys authenticity and completeness proofs depend on each other, we distinguish them for the sake of clarity. We also observe that guaranteeing records correctness does not require any completeness proof because we are considering a key-value database where projection queries are not allowed. We recall from Section 3 that the elements of each set of the response A i is a key-value tuple (k, v), and we denote as R i the set of the keys included in the set A i . In the following we describe separately the generation and the verification processes for keys authenticity proofs, keys completeness proofs and records authenticity proofs.

Keys authenticity. The keys authenticity proof is a tuple that includes the following values:

π auth = ({F Qi } i∈I , F T , W T ), (27)
where {F Qi } i∈I is the set of the bulk witnesses, F T is the aggregate ECR hash function of bulks that include at least one of the keys requested by the client, W T is the aggregate bilinear signature of the bulks that do not include any of the keys requested by the client. The server generates each bulk witness F Qi by computing the ECR hash function f pk (see Equation ( 16)) on the set complement Q i of R i with respect to K i , as following:

F Qi = f pk (Q i ), f pk (Q i ) = f pk (K i \R i ), f pk (K i \R i ) = = g C K i \R i (s) , g α•C K i \R i (s) , ∀i ∈ I (28)
Moreover, the server computes the aggregate bilinear signature W T as the witness for bulks that do not include any keys requested by the client by aggregating the owner signatures as following:

W T = i∈I σ i (K i ) = i∈I h g (i)g C K i u (29)
The client verifies authenticity of the keys {R i } returned by the server by using values included in the authentication proof π auth and the database signature σ last stored locally (see Equation ( 24)). The client verifies correctness of the ECR hash function F T by using Equation [START_REF] Narasimha | Dsac: An approach to ensure integrity of outsourced databases using signature aggregation and chaining[END_REF]. Then, the client verifies that the ECR hash function F T is built correctly with respect to the aggregate bilinear signature W T by using the locally maintained database signature σ last , as following:

ê (F T , U ) ? = ê σ last W T , g (30)
Finally, the client uses F T to verify authenticity of the returned records {R i } i∈I by using the bulk witnesses {F Qi } i∈I , as following:

ê i∈I h g (i), g i∈I ê (f pk (R i ), F Qi ) ? = ê (F T , g) (31)
After this verification process the client is sure about the following guarantees:

-F T is a valid witness for the bilinear aggregate signature W T , as the probability of generating or extracting any other owner signature would break the non-extractability guarantees of aggregate bilinear signatures [START_REF] Boneh | Short signatures from the weil pairing[END_REF]; all the returned keys {R i } i∈I are authentic, because the server proved existence of the witnesses Q i with respect to bulks aggregate hash function F T and generating false witnesses would break extractable collision resistance (ECR) guarantees of the ECR hash function (f (•), f (•)) [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF]; all the operation identifiers i ∈ I sent by the client are authentic, as generating identifiers that satisfy Equation (31) would break either the FDH function h g (•) or the collision resistance guarantees of aggregate bilinear signatures [START_REF] Boneh | Short signatures from the weil pairing[END_REF].

Keys completeness. As described in Section 3.3, to prove completeness of the response the server must produce witnesses that prove disjunction the requested keys X with respect to the complement sets Q and T . The completeness proof is a tuple that includes such witnesses, and additional values that allow the client to verify that the server generated them correctly:

π comp = (F P , F ṗ, F ẋ), (32)
where F P is the ECR hash function of the set union including the complement sets Q and T , (F q and F ẋ) the witnesses that prove disjunction of the set of the requested keys X with respect to sets T and Q.

First, the server computes the ECR hash function of Q ∪ T as:

F P = f pk (Q ∪ T ), f pk (Q ∪ T ) = g C Q∪ T (s) , g α•C Q∪ T (s) (33)
The two witnesses F ṗ and F ẋ of polynomials ẋ and ṗ are generated by the server to show that the gcd between the characteristic polynomials C X and C Q∪ T of sets X and Q ∪ T is 1, that is equivalent to prove disjunction of sets X, and T , as shown in [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF]:

ẋ, ṗ : C X (s) • ẋ + C P (s) • ṗ = 1 ( 34
)
F ṗ = f pk ( ṗ), f pk ( ṗ) (35)
F ẋ = f pk ( ẋ), f pk ( ẋ) (36)
The client verifies correctness of the ECR hash functions F P , F q and F ẋ sent by the server by using Equation [START_REF] Narasimha | Dsac: An approach to ensure integrity of outsourced databases using signature aggregation and chaining[END_REF]. Then, he verifies whether F P represents the set complement of R with respect to D by checking the value of F P against the database accumulator F D last (see Equation ( 25)) publicly distributed by the owner:

ê (f pk (R), F P ) ? = ê (F D last , g) (37)
Now that the client verified the correct generation of the witnesses F P , he can verify disjunction of X, Q and T by testing Equations (34) as following:

ê(f pk (X), F ẋ) • ê(F P , F ṗ) ? = ê(g, g) (38)
Records authenticity. The server computes the proof of authenticity π rec by aggregating all the record signatures γ k,v = γ(k, v) previously received by the owner for all the records returned to the client, as following:

π rec = (k,v)∈Ai,∀Ai∈A γ k,v (39)
The client verifies authenticity of the response A given the server integrity proof π int and the owner public key U by verifying the following condition:

ê   (k,v)∈Ai,∀Ai∈A h g (k v), U   ? = ê(π rec , g) (40)
This concludes the description of the protocol: any client that is enabled to query the database and that knows the owner's public key pk and the state of the database D can verify correctness of the results by using the described verification operations. We recall that if a client knows the secret key sk, such as in symmetric settings, he can verify results correctness more efficiently by using the secret exponents u and α.

Most literature related to security of data outsourcing and cloud services aims to protect data confidentiality of tenant data against malicious insiders of cloud providers. These works typically assume the honest-but-curious threat model where an insider within the cloud provider may access and copy tenant data without corrupting or deleting them. To solve this issue several works already proposed in the literature leverage architectures based on partially homomorphic and property preserving encryptions that allow cloud computations and efficient retrieval on encrypted data (e.g., [START_REF] Ferretti | Distributed, concurrent, and independent access to encrypted cloud databases[END_REF][START_REF] Hacigümüş | Executing sql over encrypted data in the database-service-provider model[END_REF][START_REF] Popa | CryptDB: protecting confidentiality with encrypted query processing[END_REF]). Unlike these works, in this paper we do not trust the cloud provider to behave correctly, but we assume a threat model where the cloud provider can violate authenticity and completeness of tenant data, either due to hardware/software failures or deliberate attacks. The main problem in this context is to combine authenticity and completeness guarantees without affecting the database performance and functionalities. As an example, standard message authentication codes or digital signatures can guarantee authenticity of outsourced data. However, they cannot guarantee results completeness without incurring in great network overhead.

A well-known solution to guarantee results correctness is to adopt Merkle hash trees [START_REF] Crosby | Authenticated dictionaries: Real-world costs and trade-offs[END_REF], that allow to build efficient proofs for range queries by authenticating the sorted leafs of the tree with respect to an index defined at design time. However, they do not support efficient queries on arbitrary values and efficient proofs on dispersed key values. Other solutions allow the tenant to verify authenticity and completeness of outsourced data by means of RSA accumulators [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Narasimha | Dsac: An approach to ensure integrity of outsourced databases using signature aggregation and chaining[END_REF][START_REF] Hong | Query integrity verification based-on mac chain in cloud storage[END_REF]. Although RSA accumulators provide constant asymptotic complexity for read and update operations, their high constant computational overhead often prevent their practical application in most scenarios [START_REF] Crosby | Authenticated dictionaries: Real-world costs and trade-offs[END_REF]. A different approach is proposed in [START_REF] Xie | Integrity auditing of outsourced data[END_REF], that relies on the insertion of a number of fake records in the database. These records are then retrieved to verify their presence, and possibly identify completeness violations. However, since no cryptographic verification is executed on the real database, such a solution provides lower security guarantees based on probabilistic completeness verification. The protocols proposed in [START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF] guarantees authenticity of operations in a memory-checking model by maintaining an N-ary tree of constant height. Since only the values of the nodes change (but not the number of cells), these protocols can produce proofs of constant size with respect to the cardinality of the sets stored in each memory cell. However, their proposal cannot be easily adopted in the data outsourcing scenario because the amount of sets is not constant and the tree structure would require expensive re-balancing operations.

Conclusion

This paper proposes Bulkopt, a novel protocol that provides authenticity and completeness guarantees for key-value databases. Bulkopt is specifically designed for providing data security guarantees in the context of cloud-based services subject to read/write workloads, and efficiently support bulk insert operations, as well as read requests that involve the retrieval of multiple and not contiguous keys at once. Efficient verification of bulk operations is achieved by modeling data security constraints in terms of set operations, and by leveraging cryptographic proofs based for set operations. In particular, Bulkopt is the first protocol that combines extractable collision resistant hash functions and aggregate bilinear map signatures to achieve novel cryptographic constructions that allow the verification of authenticity and completeness over large sets of data by relying on small cryptographic proofs. More work is needed to tune the protocol performance by using data structures to cache partial proofs at the server side, as well as further developments to also support update operations.

Fig. 1 .

 1 Fig. 1. Example of sets computed over a key-value database.

Acknowledgments. The authors acknowledge the support of HORIZON 2020 FCT-1-2015 project ASGARD "Analysis System for Gathered Raw Data".


Sjouke Mauw

Rolando Trujillo-Rasua

Bochuan Xuan

Counteracting active attacks in social network graphs

Keywords: privacy, social networks, active attacks, antidimension

The growing popularity of social networks has generated interesting data analysis problems. At the same time, it has raised important privacy concerns, because social networks contain personal and sensitive information. Consequently, social graphs, which express the relations between the actors in a social network, ought to be sanitized or anonymized before being published. Most work on privacy-preserving publication of social graphs has focused on dealing with passive attackers while active attackers have been largely ignored. Active attackers can affect the structure of the social network graphs actively and use structural information, as a passive attacker does, to re-identify a user in a social graph. In this article we propose, to the best of our knowledge, the first anonymization method that resists to active attacks.

Introduction

Human interaction and socialization has changed as communication and information technology evolves. Emotions, feelings, thoughts, can all be shared instantly by simply pressing a button in one's favorite social network application. This adds a degree of freedom to what we share and how we show it in comparison to, for example, face-to-face communication. While the latter is confined to a bounded physical space and builds upon the subtleties of human physical interaction, online social networks make it easier to disclose personal feelings as users are typically hidden behind a computer screen.

A social graph is a static representation of a social network; a sort of snapshot. Every vertex corresponds to a user who connects to other users through edges representing social links, e.g., friendship, co-authorship, and financial exchange. Researchers rely on graph theory and methods from modern sociology to extract useful knowledge by means of community detection, link prediction, identification of prominent actors, etc.

People tend to appreciate the discovery and revelation of new knowledge, but when it comes to personal information, one immediately perceives a privacy risk. Social graph analysis, although useful, may indeed jeopardize an individual's privacy. An adversary could identify a user in a published social graph and learn sensitive information such as political and religious preferences. Ergo, social 1 graphs ought to be sanitized or anonymized before making them available for analysis.

A fundamental anonymization technique consists in removing identifying attributes from the social graph, such as name, email address, and social security number [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF]. Other types of attributes, often called quasi-identifiers, which in combination may uniquely identify an individual, ought to be removed as well. This makes it harder to identify the user behind a node in a social graph, which is often call re-identification. The challenge is that even a simple graph without attributes attached to its vertices can be subject to re-identification attacks. For example, an adversary who knows the number of social links of a target victim can identify the victim as a hub1 in the social network. The re-identification can be made more precise if the number of connections is unique in the network.

Re-identification attacks to social graphs are typically categorized as passive or active. In a passive attack the adversary attempts to re-identify the victim only after the social graph has been published. In an active attack, instead, the adversary proactively inserts sybil nodes in the network and tries to establish links with the targeted victims. The links are made in such a way that every victim connects to the set of sybil nodes in a unique and re-identifiable manner. Once the social graph is released, the adversary identifies his own set of sybil nodes, which are used to re-identify users by using their connections to the set of sybil nodes [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF][START_REF] Wei | A Two-Stage Deanonymization Attack against Anonymized Social Networks[END_REF].

Active attacks are by definition stronger than passive attacks, yet little attention has been paid to counteract this type of privacy attack. The first privacy notion that accounts for such active privacy attacks has been proposed just recently in [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF]. This notion, which is called (k, )-anonymity, expresses that a user cannot be re-identified with probability higher than 1/k by an active attacker able to introduce sybil nodes in the graph. It has been shown in [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF] that reallife social graphs tend to be (1, 1)-anonymous, which is the lowest privacy level possible. Indeed, in terms of offered privacy, (k, )-anonymity forms a lattice (a square grid) where (1, 1)-anonymity is the minimum. This leads to the question whether it is possible to define privacy-preserving transformation techniques that defy active attacks by transforming a graph with low anonymity into a graph with higher anonymity that can be published without risking re-identification. In this paper, we take a first stab at defining such transformations. In particular, we will study the transformation of a graph into a graph with higher anonymity than (1, 1)-anonymity, while only adding edges.

Contributions:

In this article we propose, to the best of our knowledge, the first privacy-preserving anonymization approach that resists active attacks. We use the privacy measure (k, )-anonymity as proposed in [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF] and provide an efficient method to transform a graph G into another graph G such that G is not (1, 1)-anonymous. That is to say, the obtained graph G satisfies (k, )anonymity with k > 1 or > 1. Our anonymization method is based on edge addition operations only. As such, it preserves the original number of vertices in the graph. We provide a theoretical bound on the number of edges that our method needs to add in order to transform a graph into one that is not (1, 1)anonymous. Finally, we provide empirical results showing the impact of our transformational approach in terms of resistance to well-known active attacks such as the walk-based attack [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF].

Structure of the paper: Section 2 explains in detail passive and active privacy attacks in social graphs. Definitions and useful notions used throughout this article are provided in Section 3. Section 4 presents and proves properties of (1, 1)-anonymous graphs, which form the theoretical foundation of the proposed anonymization approach (also introduced in Section 4). Section 5 consists of empirical evaluations of the proposed method on random graphs. Conclusions are drawn in Section 6.

Related work

Most privacy notions for social graphs are based on k-anonymity [START_REF] Sweeney | Uniqueness of Simple Demographics in the[END_REF], which was originally proposed as a privacy measure for microdata. We thus start this section by briefly depicting the role of k-anonymity in microdata, and how it has been adapted to social graphs in order to resist passive attacks. Related work on active attacks is provided at the end of this section. k-anonymity in microdata. A pioneer study on re-identification attacks was published in 2002 by Sweeney [START_REF] Sweeney | Uniqueness of Simple Demographics in the[END_REF]. Sweeney estimated that 87% of the population in United States can be uniquely identified by combining seemingly innocuous attributes such as gender, date of birth and zip code.

Background knowledge is what makes a privacy attacker stronger. Either through public sources (e.g., census data) or by malicious actions, an adversary harvests information about a target victim which is used later to re-identify the victim in other databases. Hence, the challenge is how to publish data in such a way that users cannot be re-identified, regardless of the adversary's background knowledge. A property known as k-anonymity gives a possible solution approach [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF].

A dataset is said to satisfy k-anonymity if every record is indistinguishable from k -1 other records with respect to a given adversary's background knowledge. Consequently, k-anonymity ensures that the considered adversary cannot pinpoint the user behind a record with probability higher than 1/k. Moreover, a k-anonymous dataset can still be considered useful for analysis; researchers are interested in aggregate data describing the general behavior of a population rather than in the characteristics of a single individual. k-anonymity in social graphs. While Sweeney's revelation mainly concerns relational databases, later in 2009 Narayanan et al. showed that one third of social network users in Flickr and Twitter can be re-identified by a simple passive attack on the anonymized Twitter graph with only 12% error rate [START_REF] Narayanan | De-anonymizing social networks[END_REF]. Several notions of k-anonymity have been consequently proposed in order to mitigate the impact of passive attacks in social graphs.

Privacy notions based on k-anonymity rely on a proper definition of the adversary's background knowledge. In microdata this knowledge consists of a set of quasi-identifiers, while in social graphs it is normally defined as a structural property on the graph, e.g., vertex degree or distance. Two vertices are said to be indistinguishable if they are structurally equivalent with respect to the considered structural property. For example, Liu et al. [START_REF] Liu | Towards identity anonymization on graphs[END_REF] considered an adversary who knows the degree of the victim node. This simple structural property leads to the notion of k-degree anonymity, which is satisfied if for every vertex there exist k -1 other vertices with the same degree.

A privacy notion strictly stronger than k-degree anonymity is k-neighbourhood anonymity [START_REF] Zhou | Preserving privacy in social networks against neighborhood attacks[END_REF]. This property requires that for every vertex v in the graph there exist at least k -1 other nodes v 1 , ...v k-1 such that the subgraph induced by v's neighbours is isomorphic to the subgraph induced by v i 's neighbours, for every i ∈ {1, . . . , k -1}. This notion was soon generalized to k-automorphism [START_REF] Hay | Resisting structural re-identification in anonymized social networks[END_REF][START_REF] Zou | K-automorphism: A general framework for privacy preserving network publication[END_REF]. Two vertices u and v are equivalent if there exists an isomorphism from the graph to itself where u maps to v [START_REF] Hay | Resisting structural re-identification in anonymized social networks[END_REF]. The problem, however, is that real-life social graphs can hardly satisfy k-anonymity with respect to automorphism [START_REF] Zou | K-automorphism: A general framework for privacy preserving network publication[END_REF].

Active attacks. The privacy notions described above do not account for an adversary with the ability to actively manipulate the structure of the social network. That would allow the adversary to influence the structural property of a victim node, which is actually stronger than just knowing structural information.

Backstrom et al. were the first to show the impact of active privacy attacks in social networks [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF]. They propose an attack where the adversary plants a wellconstructed and uniquely identifiable subgraph in the social network graph. The nodes in the adversary's subgraph are used to establish links with the victim nodes (e.g., by sending friendship requests), in such a way that every victim has a unique fingerprint of links to the adversary's subgraph. Once the social graph is released, the adversary retrieves the planted subgraph and re-identifies those nodes that preserve the expected fingerprint.

A recent improvement over the methods in [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF] is the Seed-and-Grow attack proposed by Wei et al. [START_REF] Wei | A Two-Stage Deanonymization Attack against Anonymized Social Networks[END_REF]. They combine the creation of a uniquely identifiable subgraph with a progressive and self-reinforcing strategy, which starts with the initial fingerprint and extends to other new vertices by using the knowledge acquired during the re-identification procedure.

Preventing active attacks is challenging. Indeed, none of the privacy notions described above [START_REF] Liu | Towards identity anonymization on graphs[END_REF][START_REF] Zhou | Preserving privacy in social networks against neighborhood attacks[END_REF][START_REF] Hay | Resisting structural re-identification in anonymized social networks[END_REF][START_REF] Zou | K-automorphism: A general framework for privacy preserving network publication[END_REF] is well-suited to counteract active attacks. To the best of our knowledge, the first privacy measure to evaluate the resistance of social graphs to active attacks was proposed just recently in [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF]. Trujillo-Rasua and Yero model the adversary's background knowledge as the distance vector of a vertex with respect to the adversary's subgraph. This leads to the privacy notion (k, )-anonymity [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF].

In this article we take a first step on defining graph transformations aimed at improving privacy in terms of (k, )-anonymity. Therefore, we provide in the next section a formal definition for this privacy concept and introduce various notations that we use throughout the article.

Preliminaries

We model a social graph G = (V, E) as a simple graph where V represents individuals and E their relationships. The distance d G (v, u) between two vertices v and u in G is the number of edges in the shortest path connecting them. Often we simply write d(v, u) if it does not lead to ambiguity. The degree of a vertex is the number of edges connected to it. An end-vertex is a vertex with degree one. The eccentricity G (v) of a vertex v in a connected graph G is the greatest number of edges in a shortest path between v and any other vertex in G. We call a shortest path an eccentricity path for v if its length is equal to G (v).

Definition 1 (Metric representation). The metric representation of a vertex v with respect to an ordered subset of vertices

S = {u 1 , ..., u t } in a graph G = (V, E) is the vector r(v|S) = (d G (v, u 1 ), . . . , d G (v, u t )).
The metric representation is the structural property used in [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF] to represent the adversary's background knowledge in active attacks.

Definition 2 (k-antiresolving set). Let G = (V, E) be a simple connected graph and let S = {u 1 , • • • , u t } be a subset of vertices of G. The set S is called a k-antiresolving set if k is the greatest positive integer such that for every vertex v ∈ V -S there exist at least k -

1 different vertices v 1 , • • • , v k-1 ∈ V -S with r(v|S) = r(v 1 |S) = • • • = r(v k-1 |S).
As an example, consider the star graph in Figure 1. The distance from v 1 to any other vertex in the graph is 1, thus {v 1 } is a 4-antiresolving set. On the other hand, any set {v i } with i ∈ {2, 3, 4, 5} is a 1-antiresolving set because r(v 1 |{v i }) = (1) while r(v j |{v i }) = (2) for every j ∈ {2, 3, 4, 5} and j = i. Finally, we consider the subset {v 1 , v 5 }. We observe that r(v Considering again the star graph depicted in Figure 1, we observe that {v 2 } is a 1-antiresolving set with cardinality 1. Ergo, the 1-metric antidimension of this graph is 1. Determining the 2-metric antidimension is a bit more troublesome. We should first notice that v 1 should be included in any 2-antiresolving set, while {v 1 } itself is a 4-antiresolving set. Therefore, the 2-metric antidimension of the star graph is greater than or equal to 2. However, the subset {v 1 , v i } for every i ∈ {2, 3, 4, 5} is a 3-antiresolving rather than a 2-antiresolving set. Consequently, the 2-metric antidimension of the graph in Figure 1 is 3, given that {v 5 , v 1 , v 3 } is a 2-antiresolving set. We refer the interested reader to [START_REF] Harary | On the metric dimension of a graph[END_REF] and [START_REF] Trujillo-Rasua | Characterizing 1-metric antidimensional trees and unicyclic graphs[END_REF] for results on the metric dimension and the k-metric antidimension, respectively.

2 |{v 1 , v 5 }) = r(v 3 |{v 1 , v 5 }) = r(v 4 |{v 1 , v 5 }) = (1, 2), implying that {v 1 , v 5 } is a 3-antiresolving set. v 1 v 2 v 3 v 4 v 5

Definition 4 ((k, )-anonymity).

A graph G is said to meet (k, )-anonymity if k is the smallest positive integer such that the k-metric antidimension of G is lower or equal than .

A graph G satisfying (k, )-anonymity ensures that every subset of vertices with cardinality at most is a k -antiresolving set for some k ≥ k. Thus, every vertex in G is indistinguishable from at least k -1 other vertices with respect to their metric representation to any subset of vertices of cardinality at most .

Protecting (1, 1)-anonymous graphs

In this section we provide theoretical properties of (1, 1)-anonymous graphs, and use them to prove convergence of our anonymization method.

Properties of (1, 1)-anonymous graphs

If G contains a 1-antiresolving set, say {v}, then there exists a vertex u such that d(v, u) = d(v, w) for every w ∈ V -{v, u}. Following terminology from [START_REF] Trujillo-Rasua | k-metric antidimension: A privacy measure for social graphs[END_REF], we call such a vertex u a 1-resolvable vertex, in particular, we say that u is 1-resolvable by {v}. It follows that containing a 1-resolvable vertex is a sufficient and necessary condition for a graph G to be (1, 1)-anonymous. Proposition 1. A simple connected graph G = (V, E) satisfies (1, 1)-anonymity if and only if it contains a 1-resolvable vertex.

Proof. If G contains a 1-resolvable vertex v, then there exists a vertex u in G such that {u} is a 1-antiresolving set. Ergo G is (1, 1)-anonymous. Now, let us assume that G is (1, 1)-anonymous and that there does not exist a 1-resolvable vertex in G. This implies that there does not exist a 1-antiresolving set of cardinality 1 in G. Therefore, if a 1-antiresolving set in G exists then G is (1, )-anonymous for some > 1, otherwise G is (k, )-anonymous for some k > 1. In either case G is not (1, 1)-anonymous, which is a contradiction.

Because the presence of 1-resolvable vertices implies (1, 1)-anonymity, we are interested in finding those vertices in the graph which are 1-resolvable. A first trivial result in this direction is the following. Lemma 1. For every end-vertex v in a graph G = (V, E) it holds that v's neighbour is 1-resolvable by {v}.

Proof. We should first notice that if |V | = 2 then both v and v's neighbour are 1resolvable. Thus, let us assume that |V | > 2 and let u be v's neighbour. Because any path to v passes through u, we obtain that d(w, v) = d(w, u) + d(u, v) > d(u, v) = 1 for every w ∈ V -{v, u}. Therefore, {v} is a 1-antiresolving set and u is a vertex 1-resolvable by {v}.

A consequence of Lemma 1 is that every graph with end-vertices is (1, 1)anonymous. Hereinafter we thus assume that social graphs do not contain endvertices; they can be either removed from the social network or connected to other nodes. It is also worth remarking that, if v is an end-vertex, then v's neighbor lies in every eccentricity path of v. We prove next that, indeed, every vertex 1-resolvable by {v} lies in an eccentricity path of v.

Lemma 2. Let G be a simple connected graph, let {v} be a 1-antiresolving set in G, and let v 1 • • • v m be an eccentricity path of v, i.e., v 1 = v. For every vertex u that is 1-resolvable by {v} there exists i ∈ {1, . . . , m} such that u = v i .

Proof. Let us assume that u = v i ∀i ∈ {1, . . . , m}. By definition, the eccentricity of v satisfies that (v) ≥ d(v, w) for every w ∈ V (G) and, in particular, (v 2 left). Consequently, either u = v i or u is not 1-resolvable by {v}, which both lead to a contradiction.

) ≥ d(v, u). Given that d(v, v m ) = (v) ≥ d(v, u), there must exist i ∈ {1, . . . , m} such that d(v, u) = d(v, v i ) (see Figure
The next result is rather simple, yet it is the core of our anonymization approach. It provides a necessary condition for a vertex to be not 1-resolvable by vertices within a cycle of odd order.

A graph transformation approach

Our elimination approach of 1-resolvable vertices is based on Proposition 2 and Lemma 2. We aim at including all 1-resolvable vertices lying in a given eccentricity path into a cycle of odd order by adding a single edge. This transformation is defined as follows.

Definition 5 (v-transformation). Let v be a vertex in a graph G = (V, E) such that {v} is a 1-antiresolving set, and let v 1 • • • v m be an eccentricity path of v where v 1 = v. Let i and j be the lowest and largest positive integers, respectively, such that v i and v j are

1-resolvable by v in G. A v-transformation results in the graph (V, E ∪ {(v i-1 , v j )}) if j -i is odd, otherwise in (V, E ∪ {(v i-2 , v j )}).
The remaining results within this section are aimed at proving properties of a v-transformation in a graph.

Theorem 1. Let G = (V, E) be a simple connected graph, {v} a 1-antiresolving set, and G the graph resulting from a v-transformation in G. Let S be the set of vertices in G contained in an eccentricity path of v in G. Every w ∈ S is not 1-resolvable by {v} in G .

Proof. Let v 1 • • • v m be an eccentricity path where v 1 = v. Let i and j be the lowest and largest positive integers, respectively, such that v i and v j are 1resolvable by v in G. G 1 and G 2 denote the v-transformation of G when ji is odd and even, respectively. Next, we consider a vertex w ∈ {v 1 , . . . , v m } and analyze different cases regarding the position of w in the eccentricity path v 1 • • • v m . Figure 3 depicts the three scenarios. Case 1 (w ∈ {v 1 , . . . , v i-2 }). In this case w is not 1-resolvable by

{v 1 } in G. Therefore, let w ∈ V -{v 1 , . . . , v m } such that d G (v 1 , w) = d G (v 1 , w ).
We choose k ∈ {1, . . . , m} to be the largest positive integer such that d

G (v 1 , w ) = d G (v 1 , v k )+d G (v k , w ). On the one hand, it holds that d G (v k , w ) = d G1 (v k , w ) = d G2 (v k , w
). On the other hand, it is easy to note that k

< i -1, otherwise d G (v 1 , w ) ≥ i -1 > d G (v 1 , w). This implies that d G (v 1 , v k ) = d G1 (v 1 , v k ) = d G2 (v 1 , v k ) and, thus, d G (v 1 , w) = d G1 (v 1 , w) = d G2 (v 1 , w) = d G (v 1 , w ) = d G1 (v 1 , w ) = d G2 (v 1 , w ). Ergo, w is not 1-resolvable by {v} in G 1 and G 2 .
Case 2 (w ∈ {v i-1 , . . . , v j }). Now consider that w ∈ {v i-1 , . . . , v j }, which means that w is contained in the cycles

v i-1 v i • • • v j v i-1 and v i-2 v i • • • v j v i-2 from G 1
and G 2 , respectively. Considering Proposition 2, we obtain that if j -i is odd then w is not 1-resolvable by {v} in G 1 , otherwise w is not 1-resolvable by {v} in G 2 .

Case 3 (w ∈ {v j+1 , . . . , v m }). Finally, consider that w ∈ {v j+1 , . . . , v m }. In this case we obtain the following.

d G1 (v 1 , w) = d G1 (v 1 , v i-1 ) + d G1 (v i-1 , v j ) + d G1 (v j , w) = d G (v 1 , w) -(j -i) (1)
Similarly we obtain:

d G2 (v 1 , w) = d G (v 1 , w) -(j -i + 1) (2)
On the other hand,

d G1 (v 1 , w ) = d G1 (v 1 , v k ) + d G1 (v k , w ) and d G2 (v 1 , w ) = d G1 (v 1 , v k )+d G1 (v k , w ) for some k, k ∈ {1, . . . , m}. We notice that d G1 (v k , w ) = d G (v k , w ) and d G1 (v 1 , v k ) ≥ d G (v 1 , v k ) -(j -i), which gives the following in- equality. d G1 (v 1 , w ) ≥ d G (v 1 , v k ) + d G (v k , w ) -(j -i) (3)
Analogously we obtain:

d G2 (v 1 , w ) ≥ d G (v 1 , v k ) + d G (v k , w ) -(j -i + 1) (4) Moreover, d G (v 1 , v k ) + d G (v k , w ) ≥ d G (v 1 , w ) = d G (v 1 , w) and d G (v 1 , v k ) + d G (v k , w ) ≥ d G (v 1 , w ) = d G (v 1 ,
w), which applied to Equations 3 and 4 gives:

d G1 (v 1 , w ) ≥ d G (v 1 , w) -(j -i) d G2 (v 1 , w ) ≥ d G (v 1 , w) -(j -i + 1). (5)
Finally, Equations 1 and 2 together with the inequalities in 5 give that

d G1 (v 1 , w ) ≥ d G1 (v 1 , w) and d G2 (v 1 , w ) ≥ d G2 (v 1 , w). Therefore, there exists a vertex w in the v 1 -w path such that d G1 (v 1 , w ) = d G1 (v 1 , w). We observe that w = w, given that d G (v 1 , w ) ≥ d G1 (v 1 , w ) ≥ k implying that d G (v 1 , w)
must be greater or equal than k as well. We conclude that w is not 1-resolvable by {v} in G 1 . We draw the same conclusion for G 2 by following an analogous reasoning.

We conclude this proof by recalling Lemma 2, which states that every 1resolvable vertex by {v} lies in the path v 1 • • • v m . This means that i and j are unique amongst all eccentricity paths of v in G.

Theorem 1 states that a v-transformation G satisfies that all vertices in G which are included in an eccentricity path of v are not 1-resolvable by {v} in G . Consider, for example, the vertex v i in Figure 3

. While d G (v 1 , v i ) = d G (v 1 , u) for every vertex u in G, it is easy to see that d G1 (v 1 , v i ) = d G1 (v 1 , v j ) and d G2 (v 1 , v i ) = d G2 (v 1 , v j-1
). We next determine sufficient conditions by which a vertex not contained in an eccentricity path of v is not 1-resolvable by {v} in a v-transformation.

Theorem 2. Let G = (V, E) be a simple connected graph, {v} a 1-antiresolving set, and G the graph resulting from a v-transformation in G. Let S be the set of vertices in G contained in an eccentricity path of

v in G. Let v 1 • • • v m an eccentricity path of v where v 1 = v. For a given vertex w ∈ V -S let k ∈ {1, . . . , m} be the largest positive integer such that d G (v 1 , w) = d G (v 1 , v k ) + d G (v k , w). Then k < i or k ≥ j implies that w is not 1-resolvable by {v} in G .
Proof. As above, we use G 1 and G 2 to denote the v-transformation of G when j -i is odd and even, respectively, where i and j are the lowest and largest positive integers, respectively, such that v i and v j are 1-resolvable by v in G.

First, consider that k < i, in which case

d G (v 1 , w) < d G (v 1 , v i ), other- wise there exists w ∈ V -{v 1 , . . . , v m } such that d G (v 1 , w ) = d G (v 1 , v i ), a contradiction. This means that d G (v 1 , w) ≤ i -2. Because G 1 and G 2 result from the addition of one edge to G, then d G1 (v 1 , w) ≤ d G (v 1 , w) ≤ i -2 and d G2 (v 1 , w) ≤ d G (v 1 , w) ≤ i -2. If d G (v 1 , w) = i -2, then v i-1 and v j satisfy that d G1 (v 1 , w) = d G1 (v 1 , v i-1 ) = i-2 and d G2 (v 1 , w) = d G2 (v 1 , v j ) = i-2 in G 1 and G 2 , respectively. If d G (v 1 , w) < i -2, then d G1 (v 1 , w) = d G1 (v 1 , v l ) = d G2 (v 1 , v l )
where l = d G (v 1 , w) + 1. We conclude that in both G 1 and G 2 the vertex w is not 1-resolvable by {v}.

Next, consider that k ≥ j. Given that G 1 and G 2 result from the addition of the edge (v i-1 , v j ) and (v i-2 , v j ), respectively, to G, we obtain that d G (v j , w) = d G1 (v j , w) = d G1 (v j , w). Therefore, we obtain the following equalities.

d G (v 1 , w) = d G (v 1 , v j ) + d G (v j , w) d G1 (v 1 , w) = d G1 (v 1 , v j ) + d G (v j , w) d G2 (v 1 , w) = d G2 (v 1 , v j ) + d G (v j , w) Let v l be the vertex in v 1 • • • v m such that d G (v 1 , v l ) = d G (v 1 , w). It should be noticed that l > j and d G (v 1 , v l ) = d G (v 1 , v j ) + d G (v j , v l ), hence d G (v j , w) = d G (v j , v l ). As before, we obtain that d G (v j , v l ) = d G1 (v j , v l ) = d G1 (v j , v l ). Be- cause d G (v j , w) = d G (v j , v l )
, we can rewrite the equalities above as follows.

d G (v 1 , w) = d G (v 1 , v j ) + d G (v j , w) d G1 (v 1 , w) = d G1 (v 1 , v j ) + d G1 (v j , v l ) d G2 (v 1 , w) = d G2 (v 1 , v j ) + d G2 (v j , v l ) Consequently, d G1 (v 1 , w) = d G1 (v 1 , v l ) and d G2 (v 1 , w) = d G2 (v 1 , v l ), imply- ing that in both G 1 and G 2 the vertex w is not 1-resolvable by {v}.
We observe that even if i ≤ k < j a vertex w can still remain not 1resolvable by {v} in a v-transformation. This is the case, for example, in the v 1 -transformation shown by Figure 4. We thus provide next a sufficient condition for a vertex w to be not 1-resolvable by {v} in a v-transformation regardless of the position of k with respect to i and j. Proposition 3. Let G = (V, E) be a simple connected graph, {v} a 1-antiresolving set, G the graph resulting from a v-transformation in G, and

v 1 • • • v m an ec- centricity path of v where v 1 = v. For every w ∈ V -{v 1 , . . . , v m } it holds that d G (v 1 , w) ≤ m -j + i -1 implies that w is not 1-resolvable in G . Proof. Let v 1 • • • v m be
an eccentricity path where v 1 = v. Let i and j be the lowest and largest positive integers, respectively, such that v i and v j are 1resolvable by v in G. We call G 1 and G 2 to the v-transformation of G when j -i is odd and even, respectively.

If d G1 (v 1 , v m ) ≥ d G1 (v 1 , w) then w is not 1-resolvable by {v 1 } in G 1 . It is easy to note that d G1 (v 1 , v m ) = d G1 (v 1 , v i-1 )+d G1 (v i-1 , v j )+d G1 (v j , v m ) = i-1+m- j and analogously d G2 (v 1 , v m ) = i-2+m-j. Given that d G1 (v 1 , w) ≤ d G (v 1 , w) and d G2 (v 1 , w) ≤ d G (v 1 , w) we conclude that if d G (v 1 , w) ≤ m -j + i -1 then w is not 1-resolvable by {v 1 } in G 1 . Similarly, we can conclude that if d G (v 1 , w) ≤ m -j + i -2 then w is not 1-resolvable by {v 1 } in G 2 .
Finally, we provide a convergence result for our approach.

Theorem 3. Let G be a simple graph. We define a sequence of graphs G i (for i ≥ 0) inductively as follows:

-G 0 = G. -If there exists a 1-antiresolving set {v} in G i then G i+1 is the result of applying a v-transformation to G i . -Otherwise, G i+1 = G i . Let S i be the set of vertices in G i such that v ∈ S i implies that {v} is a 1- antiresolving set in G i . Then S j is empty for j ≥ ∀v∈V G0 (v) -|V |. Proof. Consider G i-1 = (V i-1 , E i-1 ) and G i = (V i , E i ) where G i-1 = G i . That is to say, G i results from a v-transformation to G i-1 where {v} is a 1- antiresolving set in G i-1 . Let v 1 • • • v m be the eccentricity path of v in G i-1 , i.e., v 1 = v, such that G i = (V i-1 , E i-1 ∪ {(v i , v j )}) for some i, j ∈ {1, . . . , m}.
On the one hand,

d Gi (v 1 , v m ) = d Gi (v 1 , v i ) + d Gi (v i , v j ) + d Gi (v j , v m ) = d Gi-1 (v 1 , v i )+1+d Gi-1 (v j , v m ). On the other hand, by definition of a v-transformation the edge (v i , v j ) satisfies that j -i ≥ 2. Therefore, d Gi-1 (v i , v j ) ≥ 2, which im- plies that d Gi-1 (v 1 , v m ) > d Gi (v 1 , v m ). We conclude then that Gi (v) < Gi-1 (v).
The result above states that every v-transformation from G i-1 to G i makes the eccentricity of v to decrease. Because an eccentricity path cannot be shorter than 1, the maximum number of v-transformations that can be applied to G 0 is bounded by G0 (v) -1. Considering that every vertex could potentially form a 1-antiresolving set, we obtain the following upper bound: ∀u∈V G0 (v) -|V |. Consequently, the graph G i with i = ∀v∈V G0 (v) -|V | does not contain 1resolvable vertices.

Our anonymization approach simply consists of the successive application of v-transformations until a graph without 1-resolvable vertices is found. The number of v-transformations depends on how fast these transformations converge to a graph without 1-resolvable vertices. According to Theorem 3, this number is upper bounded by ∀v∈V G (v)-|V |, which is higher than or equal to |V |( G -1) where G is the eccentricity of G. Considering that finding the shortest path between every pair of vertices in a graph has computational complexity O(|V | 3 ), we obtain that the computational complexity of our method is O(|V | 4 ( G -1)).

We end this section by remarking that the upper bound provided in Theorem 3 is tight. That is, there exists a graph G = (V, E) such that the number of edges added by our method is equal to ∀v∈V G (v) -|V |. Moreover, such an upper bound corresponds to the minimum number of edges required to transform G into G through edge addition operations only and such that G is not (1, 1)-anonymous. The graph G we are referring to can be constructed as follows.

Consider the complete graph 5). On the one hand, any edge added to G has the form (v n+1 , v i ) for some i ∈ {1, . . . , n}, which makes the distance between v n+1 and v i to become 1. On the other hand, if the edge (v n+1 , v i ) for some i ∈ {1, . . . , n} is not added to G, then the distance between v n+1 and v i remains equal to 2, implying that v n+1 is 1-resolvable by {v i }. Therefore, there exists only one transformation of G into a graph that is not (1, 1)-anonymous, that is, the transformation to the complete graph C n+1 . This requires n additional edges, which is equal to

C n = (V, E) with n vertices V = {v 1 , . . . , v n }. Given a vertex v n+1 , G is defined by G = (V ∪ {v n+1 }, E ∪ {(v n , v n+1 )}) (see Figure
∀v∈V G (v) -|V | = G (v n ) + ∀v∈V -{vn} G (v) -|V | = 1 + 2n -(n + 1) = n.

Experiments

In this section we evaluate the proposed anonymization method in terms of privacy and utility loss2 . Privacy is measured as the resistance of a graph to the walk-based attack introduced in [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF], while utility loss is measured as the number of added edges.

The walk-based attack

Given a social graph G = (V, E), the walk-based attack consists of inserting new nodes X = {x 1 , . . . , x n } into G, resulting in the graph G = (V ∪ X, E). The attacker chooses an arbitrary set Y = {y 1 , . . . , y m } of users in G as the target of the attack. For each vertex y i ∈ Y , a subset N i ⊆ X is designated as the fingerprint of y i , such that i = j =⇒ N i = N j ∀i, j ∈ {1, . . . , m}. The fingerprint is created by connecting each vertex y i ∈ Y to all vertices in N i . It is worth remarking that such a fingerprint is nothing but the metric representation of the vertex y i ∈ Y with respect to X, i.e., r(y i |X).

The goal of the attacker is to re-identify the set of vertices X in an anonymized version of G , which is used to re-identify the set of targeted vertices Y by considering their unique fingerprints with respect to X. To do so, the attacker creates random internal connections between the vertices in X by adding the edge (x i , x j ) with probability 1/2 for every i = j ∈ {1, . . . , n}. We use G(X) to denote the sub-graph in G induced by the vertices in X. Once G is released, the attacker computes the set X containing all sub-graphs in G isomorphic to G(X). Assuming that G(X) does not have a trivial automorphism as advocated in [START_REF] Backstrom | Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography[END_REF], the adversary determines for each fingerprint N i with i ∈ {1, . . . , m} the candidate set

V i = {v ∈ V |u ∈ N i ⇐⇒ d G (v, u) = 1}
containing all vertices in V whose fingerprint to G(X) is determined by N i . We consider that the adversary succeeds if all vertices in Y are correctly re-identified. Therefore, the probability of success of the attack is:

G(X)∈X 1≤i≤m p i |X | where p i = 1/|V i | if y i ∈ V i 0 otherwise.

Empirical evaluation on random graphs

In order to validate the performance of the proposed anonymization method we ran experiments on random graphs with different density values. We fix 50 as the number of vertices in each random graph, implying that every density value corresponds to a fixed number of edges. A random graph is thus created by adding random edges, i.e., connecting random pairs of vertices, until the desired number of edges is reached.

The density values range in {0.1, . . . , 1}, while we considered attacks with 1 and 4 sybil nodes. For each density value and a given number of sybil nodes, we build a random graph G with the previously mentioned density. In order to simulate the walk-based attack, G is transformed into G by adding the sybil nodes and their connections to the victim nodes. Two anonymized versions of G are considered: G 1 and G 2 corresponding to our anonymization method and a random approach, respectively. The random approach consists in adding random edges to G . The particularity is that the random approach adds as many edges as our approach, i.e., the number of edges in G 1 is equal to the number of edges in G 2 . Doing so, both approaches perform equally in terms of utility loss. Their performance in terms of privacy are depicted in Figure 6 (b) Four attacker nodes Fig. 6. Two charts depicting the average probability of success of the walk-based attack in three types of graphs: random graphs ("Original"), random graphs anonymized by our method ("Our approach"), and random graphs anonymized by the random approach ("Random approach"). Left: the adversary can enrol a single node in the network. Right: the adversary can enrol four nodes.

Figure 6 shows the average probability of success of the walk-based attack in 250, 000 random graphs, and their corresponding anonymization versions by our method and the random approach. Both anonymization approaches improve the resistance to the walk-based attack with respect to the original graph. Indeed, this attack succeeds with probability close to 1 on the original graphs for all density values above 0.2. Amongst the two anonymization approaches, ours performs significantly better for most density values. In particular, our method ensures that the probability of success of an adversary with the capability to insert a single attacker node into the network is 0.

The pronounced non-monotonic behaviour of the curves in Figure 6 corresponds to the same type of behaviour of the curves in Figure 7, which shows the average number of added edges by both our method and the random approach. It is indeed an open question what would be the trend of a curve depicting the minimum number of edges needed to transform a graph into another that is not (1, 1)-anonymous for different density values. We observe that, for example, 1 and 2 edges need to be added to a path graph of odd and even order, respectively. This means that such minimum number of edges does not depend on the graph density only. (b) Four attacker nodes Fig. 7. Two charts depicting the average number of edges added by our method, referred to as "Our approach". The charts also show the upper-bound as determined in Theorem 3 ("Upper-bound") and the maximum number of edges that can be added ("Maximum"). Left: the adversary can enrol a single node in the network. Right: the adversary can enrol four nodes.

Figure 7 shows, as sketched in the previous section, that the minimum number of edges added by our method, the upper bound provided by Theorem 3, and the maximum number of edges that can be added, meet when the density of the random graph is 1 and the adversary adds a single node to the graph. This leads to the type of graph shown in Figure 5. For other density values, the upper bound in Theorem 3 is clearly above the actual number of edges added by our technique.

Conclusions

In this article we have proposed, to the best of our knowledge, the first privacypreserving transformation method for social graphs that counteracts active attacks. The proposed method is theoretically sound and outputs a graph that satisfies (k, )-anonymity with k > 1 or > 1. We provide a theoretical upperbound on the utility loss, in terms of number of added edges, of our approach. And we prove that such upper-bound is tight. Experiments on random graphs show that the proposed method effectively counteracts active attack even when the adversary is able to insert more than one sybil node in the network.

Fig. 1 .

 1 Fig. 1. A star graph.

Proposition 2 .Fig. 2 .

 22 Fig. 2. Left: An eccentricity path v1 -vi -vm and a vertex u located out of that path. Right: A cycle of odd order. A vertex (in Black) has the same distance to both diametral vertices (in Gray).

Fig. 3 .

 3 Fig.3. An eccentricity path v1 -vm within the graph G. The dashed edge G1 (resp. G2) represents the v1-transformation if j -i is odd (resp. even).

Fig. 4 .

 4 Fig. 4. An example showing that a v-transformation may create new 1-resolvable vertices.

Fig. 5 .

 5 Fig. 5. An example graph.

  .

		1.2
		1
	Probability of success	0.4 0.6 0.8						Our approach Random approach Original									Our approach Random approach Original
		0.2
		0 0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
						Density									Density
				(a) One attacker node

A hub is a special node in a network with significant more connections than other nodes.

Experiments were performed on the UL HPC platform[START_REF] Varrette | Management of an academic HPC cluster: The UL experience[END_REF].