Aydin Abadi

Sotirios Terzis

Changyu Dong

O-PSI: Delegated Private Set Intersection on Outsourced Datasets

Private set intersection (PSI) has a wide range of applications such as privacy-preserving data mining. With the advent of cloud computing it is now desirable to take advantage of the storage and computation capabilities of the cloud to outsource datasets and delegate PSI computation. In this paper we design O-PSI, a protocol for delegated private set intersection on outsourced datasets based on a novel point-value polynomial representation. Our protocol allows multiple clients to independently prepare and upload their private datasets to a server, and then ask the server to calculate their intersection. The protocol ensures that intersections can only be calculated with the permission of all clients and that datasets and results remain completely confidential from the server. Once datasets are outsourced, the protocol supports an unlimited number of intersections with no need to download them or prepare them again for computation. Our protocol is efficient and has computation and communication costs linear to the cardinality of the datasets. We also provide a formal security analysis of the protocol.

Introduction

Cloud computing allows clients with limited computation and storage capabilities to outsource their private data and at a later time, ask the cloud to perform computation on them. Delegation of data storage and computation to the cloud has become common practice for individuals and big enterprises alike [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF][START_REF] Backes | Verifiable delegation of computation on outsourced data[END_REF]. As a result, often the need arises for clients to perform computation on their outsourced private data jointly, ideally without the need to download the data.

In this paper, we consider a particular such scenario, in which the private data take the form of sets and the computation of interest is set intersection, i.e. private set intersection (PSI).

In PSI, two parties want to find out the intersection of their sets and also want to prevent the other party from finding out anything more about their own set than the elements of the intersection. In general, PSI captures a wide range of real-world applications such as privacy preserving data mining [START_REF] Agrawal | Privacy-preserving data mining[END_REF], homeland security [START_REF] Cristofaro | Practical private set intersection protocols with linear complexity[END_REF] and so on. For example, consider a case where a law enforcement agency has a list of suspects and wants to compare it against flight passenger lists. Here the names of the suspects should be kept hidden from the airlines while the agency should not be able to find out about other passengers in order to protect their privacy. As another example, consider the situation where a social welfare organization wants to know whether any of its members receives income from another organization, but neither organization can reveal their list of members.

Although a number of protocols have been proposed for PSI (see section 2 for a survey), cloud computing introduces additional challenges as the private datasets are outsourced and the private set intersection is delegated to cloud servers. In addition to keeping their sets confidential, clients are also interested in preventing cloud servers from finding out anything about their sets and the intersection. In other words, clients are interested in delegated private set intersection on outsourced data. To allow for more flexibility it is desirable that clients should be able to engage in PSI computation with any other client of the cloud provider. However, they should remain in charge of deciding which clients are allowed to use their sets. To fully take advantage of the cloud capabilities and minimize costs, clients should not have to keep locally or download their datasets every time an intersection needs to be computed, while their involvement to the computation should be limited.

We propose O-PSI, a PSI protocol that addresses these requirements. Our protocol uses homomorphic encryption and a novel point-value polynomial representation for datasets that allows clients to independently secure their sets and outsource them to the cloud, while cloud servers are able to calculate their intersection. The protocol ensures that intersections can only be computed with the permission of the clients and that the result will remain secret from the server. The protocol also allows sets to be used an unlimited number of times securely without the need to secure them again. More interestingly, the novel set representation means that computation and communication costs are linear to the size of the sets.

The paper starts with a survey of related work in section 2, followed by a brief overview of our security model and key concepts we rely on in section 3. Section 4 presents the design of our protocol, while section 5 proves its security. Section 6 proposes extensions to support data integrity verification and multiple clients, while section 7 presents an analysis of its computation and communication complexity, and a comparison to work that is closest to our aims. Section 8 concludes the paper and identifies directions for future work.

Related Work

Private set intersection (PSI) was introduced in [START_REF] Freedman | Efficient private matching and set intersection[END_REF]. Following that [START_REF] Kissner | Privacy-preserving set operations[END_REF] proposed a number of protocols supporting further set operations and multiple clients based on additive homomorphic encryption and polynomial representation of sets. More recently, several efficient protocols have been proposed. For example, [START_REF] Cristofaro | Practical private set intersection protocols with linear complexity[END_REF][START_REF] Cristofaro | Linear-complexity private set intersection protocols secure in malicious model[END_REF] use blind signatures and hash functions to provide efficient PSI in the semi-honest and the malicious security models respectively, [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF] uses Bloom filters, secret sharing and oblivious transfer to offer even more efficient protocols, and [START_REF] Pinkas | Faster private set intersection based on OT extension[END_REF] extends [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF] and uses hash tables and a more efficient oblivious transfer extension protocol for better efficiency. However, all these regular PSI protocols are interactive, in the sense that clients jointly compute the intersection. They are not designed with the capability to outsource any data or delegate any of the computation to a third party.

In another line of research, in [START_REF] Papamanthou | Optimal verification of operations on dynamic sets[END_REF][START_REF] Canetti | Verifiable set operations over outsourced databases[END_REF] the protocols proposed for outsourced verifiable dynamic set operations, including set intersection. These protocols make use of bilinear map accumulators and authenticated hash tables (i.e. accumulator trees) to verify the correctness of operations carried out by a server on outsourced sets. However, these protocols are designed for a single client to outsource a collection of sets to a server and later to compute the intersections of its own sets. The protocols are designed to provide verifiability of computation, not data privacy. Data are outsourced in plaintext and the protocols do not work if data are encrypted.

More interestingly, a number of PSI protocols have been proposed in which clients delegate computation to a server [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF][START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF][START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF][START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF][START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF]. A protocol proposed in [START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF] allows clients to outsource their sets to a server by hashing each element and adding a random value. They then delegate the computation of the intersection to the server. However, this protocol is not fully private, as it reveals to the server the cardinality of the intersection. In addition to the above issue, because of the way the sets are encoded if the intersection between the sets of client A and B is computed, followed by that between the sets of client A and C, then the server will also find out whether some elements are common in the sets of client B and C without their consent. In [START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF] clients also delegate the computation to a server. Clients encrypt their sets and outsource them. The server also provides a proof that allows the clients to verify the correctness of the result. However, the protocol is not fully private and suffers from the same issues described above. Another protocol that delegates computation to a server is proposed in [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF]. The protocol is based on a pseudorandom permutation (PRP) of the set elements with the key for the PRP generated jointly by the clients at setup. One variant of the protocol can hide the cardinality of the intersection. However, in this variant computation is delegated to one of the clients rather than the server. The server's role is limited to re-encoding one client's set to maintain the privacy of the computation. In the protocol, clients can detect if the server provided incorrect results at the cost of replicating a number of times all elements of the sets.

In a similar line of research, a protocol proposed in [START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF] allows one client, say client A, to encrypt and outsource its set, and delegate computation to a server. The server can then engage in a PSI protocol on this client's behalf with another client, say client B. However, this delegation is one-off: if A wants to compute set intersection with C, then A must encrypt its set with a new key and re-delegate to the server. In addition to this protocol, in [START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF] two clients can delegate the PSI computation to a server. In this protocol rather than encrypting and outsourcing their sets, the clients encrypt and outsource bloom filters of their sets that are then used by the server to privately compute their intersection. However, in this case in order for the clients to get the result of the intersection they need to keep a local copy of their sets. So, this protocol does not really allow outsourcing the sets.

From the above discussion, it should be clear that none of the protocols above allows clients to fully delegate PSI computation to the server without the need to either maintain the sets locally or having to re-encode and re-upload the sets for each intersection computation, namely none support delegated private set intersection on outsourced sets. As a result, none of them are particularly suited for a cloud computing setting.

Preliminaries

Security Model

We consider a setting in which static semi-honest adversaries are present. In this setting, the adversary controls one of the parties and follows the protocol specification exactly. However, it may try to learn more information about the other party's input. The definitions and model are according to [START_REF] Goldreich | The Foundations of Cryptography -Volume 2, Basic Applications[END_REF].

In a delegated PSI protocol, three parties are involved: a server P , and two clients A and B. We assume the server does not collude with A or B. As the server (or cloud provider) is often a well established IT company, it is reasonable to assume it will not collude with the clients because collusion will seriously damage its reputation and decrease its revenue. This non-colluding assumption is widely used in the literature [START_REF] Stefanov | Multi-cloud oblivious storage[END_REF][START_REF] Raykova | Secure anonymous database search[END_REF][START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF]. The three-party protocol π computes a function that maps the inputs to some outputs. We define this function as follows:

F : Λ × 2 U × 2 U → Λ × Λ × f ∩ ,
where Λ denotes the empty string, 2 U denotes the powerset of the set universe and f ∩ denotes the set intersection function. For every tuple of inputs Λ, S A and S B belong to P, A and B respectively, the function outputs nothing to P and A, and outputs

f ∩ (S A , S B ) = S A ∩ S B to B.
In the semi-honest model, a protocol π is secure if whatever can be computed by a party in the protocol can be obtained from its input and output only. This is formalized by the simulation paradigm. We require a party's view in a protocol execution to be simulatable given only its input and output. The view of the party i during an execution of π on input tuple (x, y, z) is denoted by view π i (x, y, z) and equals (w, r i , m i 1 , ..., m i t ) where w ∈ (x, y, z) is the input of i, r i is the outcome of i's internal random coin tosses and m i j represents the jth message that it received.

Definition 1. Let F be a deterministic function as defined above. We say that the protocol π securely computes F in the presence of static semi-honest adversaries if there exist probabilistic polynomial-time algorithms Sim P , Sim A and Sim B that given the input and output of a party, can simulate a view that is computationally indistinguishable from the party's view in the protocol:

SimP (Λ, Λ) c ≡ view π P (Λ, SA, SB) SimA(SA, Λ) c ≡ view π A (Λ, SA, SB) SimB(SB, f∩(SA, SB)) c ≡ view π B (Λ, SA, SB)

Homomorphic Encryption

A semantically secure additively homomorphic public key encryption scheme has the following properties:

1. Given two ciphertexts E pk (a), E pk (b), E pk (a) • E pk (b) = E pk (a + b). 2. Given a ciphertext E pk (a) and a constant b, E pk (a) b = E pk (a • b).
One such scheme is the Paillier public key cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. It works as follows: Key Generation: Choose two random large primes p and q according to a given security parameter, and set N = pq. Let u be the Carmichael value of N , i.e. u = lcm(p-1, q -1) where lcm stands for the least common multiple. Choose a random g ∈ Z * N 2 , and ensure that s = (L(g u mod N 2 )) -1 mod N exists where L(x) = (x-1)

N . The public key is pk = (N, g) and the secret key is sk = (u, s). Encryption: To encrypt a plaintext m ∈ Z N , pick a random value r ∈ Z * N , and compute the ciphertext:

C = E pk (m) = g m • r N mod N 2 . Decryption: To decrypt a ciphertext C, D sk (C) = L(C u mod N 2 ) • s mod N = m.

Polynomial Representation of Sets

Many PSI protocols e.g. [START_REF] Freedman | Efficient private matching and set intersection[END_REF][START_REF] Kissner | Privacy-preserving set operations[END_REF], use a polynomial representation of sets. Let R be a field, then we denote a polynomial ring as R[x]. The polynomial ring R[x] consists of all polynomials with coefficients from R. Given a set S of size d, |S| = d, we can map each element in S to an element in a sufficiently large field R. Then we can represent this set as a polynomial in the polynomial ring R[x]. The polynomial is defined as ρ(x) = si∈S (xs i ) and has the property that every element s i ∈ S is a root of it.

For two sets S A and S B represented by polynomials ρ A and ρ B respectively, then gcd(ρ A , ρ B ) represents the set intersection S A ∩ S B , where gcd stands for the greatest common divisor. For polynomials ρ A and ρ B of degree d and γ A and γ B that are degree d polynomials chosen uniformly at random from R In section 3.3 we showed that a set can be represented as a polynomial and set intersection can be computed by polynomial arithmetic. All previous PSI protocols using polynomial representation of sets, represent a polynomial as a vector of polynomial's coefficients. They represent a degree d polynomial ρ = d i=0 a i x i as a vector a = (a 0 , a 1 , ..., a d ). This representation, while it allows the protocols to correctly compute the result, has a major disadvantage. The complexity of multiplying two polynomials of degree d in co-efficient representation is O(d 2 ). In PSI protocols, this leads to significant computational overheads. Usually in such protocols, one polynomial needs to be encrypted and the polynomial multiplication has to be done homomorphically. Homomorphic multiplication operations are computationally expensive. Thus using a co-efficient representation means that the protocols are not scalable.

[x], it is proved in [6] that γ A • ρ A + γ B • ρ B = µ • gcd(ρ A , ρ B ) such that µ is
In O-PSI, we solve this problem by representing the polynomials in another wellknown form, point-value. A degree d polynomial ρ can be represented as a set of n (n > d) point-value pairs {(x 0 , y 0 ), ..., (x n-1 , y n-1 )} such that all x i are distinct and

y i = ρ(x i ) for 0 ≤ i ≤ n -1.
If the x values are fixed, we can omit them and represent polynomials as vectors y = (y 0 , y 1 , ..., y n-1 ). A polynomial in point-value form can be translated into co-efficient form by polynomial interpolation [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF]. Polynomial arithmetic in point-value representation can be done by point-wise addition or multiplication. For two degree d polynomials ρ A and ρ B represented in point-value form by two vectors y (A) and y (B) , ρ A + ρ B can be computed as (y

(A) 1 + y (B) 1 , y (A) 2 + y (B) 2 , ..., y (A) n-1 + y (B)
n-1 ), and ρ A • ρ B can be computed as (y

(A) 1 • y (B) 1 , y (A) 2 • y (B) 2 , ..., y (A) n-1 • y (B) n-1
). Note because the product of ρ A • ρ B is a polynomial of degree 2d, ρ A and ρ B must be represented by at least 2d+1 points to accommodate the result. The key benefit of point-value representation is that multiplication complexity is reduced to O(d). This makes O-PSI much more scalable. • r

O-PSI Protocol

(B ) n 1
]

(1 )

v (A ) = [y (A ) 0 • r (A ) 0 , . . . , y (A ) n 1 • r (A ) n 1 ] (1 )
e (B) = [Epk B (r (B) 0 ), . . . , Epk B (r (B) n 1 )]

(2)

e (A ) = [E p k B ( r (B ) 0 • ( r (A ) 0 ) 1 ) , . . . , E p k B ( r (B ) n 1 • ( r (A ) n 1 ) 1 ) ] (3 ) t = [E p kB ( r (B ) 0 • ( w (A ) 0 • y (A ) 0 + w (B ) 0 • y (B ) 0
) ) , . . . ,

E p kB ( r (B )
n 1

• ( w

(A )
n 1

• y

(A ) n 1 + w (B )
n 1

• y

(B ) n 1
) ) ] The interaction between parties in O-PSI is depicted in Fig. 1. At a high level, the protocol works as follows. Each client first outsources its set to the server. To do so, the client uploads a vector that encodes its set to the server. The vector is blinded so that the server cannot figure out the client's set, and the other client cannot figure out any element the intersection. If a client, client B, wants to compute the intersection of its own set and another client's set, say client A's set, it must obtain permission from A. If A agrees, A can compute jointly with B some encrypted values. The encrypted values will be used by the server to remove part of the blinding factors from A's data, and this then allows the set intersection to be computed. At the end of the protocol client B receives an encrypted vector which it can decrypt and use the decrypted values to interpolate a polynomial that encodes the intersection. The protocol is described below. We will explain the rationale behind the protocol design after the protocol description.

1. Setup Let U be the universe of set elements. There is a public finite field R that is big enough to encode all elements in U and also when an element is picked uniformly at random from R has only negligible probability of representing an element of a set. i ∈S I (xs (I) i ) that represents its set S I . Evaluates τ I at every value in the x published by the server producing y (I) such that y (I) i = τ I (x i ) for 0 ≤ i ≤ n -1. (c) Sends v (I) to the server, where ∀v (I) i ∈ v (I) , v

(I) i = y (I) i • r (I) i , y (I) i is the ith element in y (I) , r (I) i = f (k I , i).
Here, v (I) is a blinded version of its set polynomial.

Set Intersection

≤ i ≤ n -1, e (A) i = (e (B) i ) (r (A) i ) -1 = E pk B (r (B) i • (r (A) i ) -1
) where r (I) i = f (k I , i) for I ∈ {A, B} are the values from step 2c above. (c) After receiving the Compute message from A, the server extracts e (A) and retrieves the data v (A) and v (B) from its storage. The server then chooses two degree d polynomials ω I randomly from R[x] and computes two vectors w (I) (I ∈ {A, B}) such that w (I) i = ω I (x i ) for 0 ≤ i ≤ n -1 where x i is the ith element in the public vector x. (d) The server computes a result vector t such that for 0 ≤ i ≤ n -1:

t i = (e (A) i ) v (A) i •w (A) i • E pk B (w (B) i • v (B) i ) = E pk B (r (B) i • (r (A) i ) -1 • y (A) i • r (A) i • w (A) i ) • E pk B (w (B) i • y (B) i • r (B) i ) = E pk B (r (B) i • (w (A) i • y (A) i + w (B) i • y (B) i ))
The server sends t to client B. (e) After receiving t, client B computes a vector z such that for 0 ≤ i ≤ n -1:

z i = D sk B (t i ) • (r (B) i ) -1 = r (B) i • (w (A) i • y (A) i + w (B) i • y (B) i ) • (r (B) i ) -1 = w (A) i • y (A) i + w (B) i • y (B)
i It then interpolates the polynomial ζ using point-value pairs (x i , z i ). The roots of ζ are the elements in the set intersection.

Remark 1: In the Setup step, the server needs to publish a vector x that has 2d + 1 elements, because the polynomial ζ in step 3e is of degree 2d and at least 2d + 1 points are needed to interpolate it. The elements in x are picked at random from R so that the probability of x i being a root of a client's polynomial is negligible. Remark 2: In step 2c, the client blinds its vector. If the client stores y directly on the server without blinding, then the server can use y and x to interpolate the client's polynomial, thus revealing the client's set. With blinding this is not possible unless the server knows the pseudorandom function key used by the client. The protocol blinds values by multiplication. However, multiplication cannot blind a value if the value is 0. This is why we require the probability of x i in x being a root of a client's polynomial to be negligible. If x i is a root then y i is 0 and cannot be blinded.

Remark 3:

The data values stored on the server are blinded by their owner. To compute the set intersection those blinding factors (r (I) i in the protocol) must be eliminated. In step 3b, client A and B jointly compute the vector e (A) to "switch" A's blinding factors to B's blinding factors. In step 3d, e (A) is used to eliminate r (A) i and replace it with r (B) i . This factor switching makes it possible later to eliminate r (B) i in step 3e. The values in e (A) are encrypted with B's public key, so the server learns nothing in this process. Remark 4: The client's original blinded dataset remains unchanged in the server. In fact in step 3.c, the server multiplies a copy of the client's blinded dataset by the vector w (I) .

Proof of Security

Now we sketch the security proof of O-PSI in the semi-honest model (see section 3.1). We conduct the security analysis for the three cases where one of the parties is corrupted.

Theorem 1. If the homomorphic encryption scheme is semantically secure, the O-PSI protocol is secure in the presence of a semi-honest adversary.

Proof. We will prove the theorem by considering in turn the case where each of the parties has been corrupted. In each case we invoke the simulator with the corresponding party's input and output. Our focus is in the case where party A wants to engage in the computation of the intersection. If party A does not want to proceed in the protocol, the views can be simulated in the same way up to the point where the execution stops. Case 1: Corrupted server In this case, we show that we can construct a simulator Sim P that can produce a computationally indistinguishable view. In the real execution, the server's view is as follows: ) , Λ} where r P are the random coins of the server, v (A) , v (B) are the blinded set representations of A's and B's sets, Compute is the command to proceed from A, and e (A) is the encrypted vector that is used in the protocol to switch blinding factors.

view π P (Λ, S A , S B ) = {Λ, r P , v (A) , v (B) , Compute, e (A
To simulate the view, Sim P does the following: it creates an empty view, then appends Λ and uniformly at random chosen coins r P to the view. It then randomly generates two d-element sets S A and S B . It also chooses two random keys k A and k B for a pseudorandom function f . It encodes S A into its polynomial representation, evaluates the polynomial with the public values x, and blinds the evaluation results with r

(A) i = f (k A , i) for 0 ≤ i ≤ n -1.
The result is v (A) . Similarly it can generate v (B) . Then v (A) and v (B) are appended to the view. Following that, the simulator generates the Compute command string with the correct format and appends it to the view. It then computes r

(B) i • (r (A) i
) -1 and encrypts the results with B's public key. This produces e (A) that is appended to the view. Finally, the simulator appends Λ to the view and outputs the view.

We argue that the simulated view is computationally indistinguishable from the real view. In both views, the input parts are identical, the random coins are both uniformly random, and so they are indistinguishable. In the real view v (A) , v (B) are blinded with the outputs of a pseudorandom function, so do the vectors in the simulated view. Since the outputs of the pseudorandom function are computationally indistinguishable, the distributions of v (A) , v (B) , v (A) , v (B) are therefore computationally indistinguishable. If the homomorphic encryption is semantically secure, then e (A) and e (A) are also computationally indistinguishable. The output parts in both views are identical. So, we conclude that the views are indistinguishable.

Case 2: Corrupted client A In the real execution, the A's view is as follows: ) , Λ} The simulator Sim A does the following: it creates an empty view, then appends Λ and uniformly at random chosen coins r A to the view. It then chooses n random values r i and encrypts each r i with B's public key. The result is e (B) and it is appended to the view. The simulator then appends Λ to the view. It is easy to see that If the homomorphic encryption is semantically secure, then e (B) and e (B) are computationally indistinguishable. So, the two views are indistinguishable.

view π A (Λ, S A , S B ) = {S A , r A , e (B
Case 3: Corrupted client B In the real execution, the B's view is as follows:

view π B (Λ, S A , S B ) = {S B , r B , Permit, t, f ∩ (S A , S B )}
The simulator Sim B does the following: it creates an empty view, and appends Λ and uniformly at random chosen coins r B to the view. Then it generates the Permit command string with the correct format and appends it to the view. Following that, it creates two d-element sets S A and S B such that S A ∩ S B = f ∩ (S A , S B ), converts S A to its polynomial representation, evaluates the polynomial using the public values x and obtains y (A) . Similarly the simulator can obtain y (B) . The simulator chooses randomly two degree d polynomials ω A and ω B , evaluates them using the public values x and obtains w (A) and w (B) . It also chooses a random key k B for a pseudorandom function f and computes r

(B) i = f (k B , i) for 0 ≤ i ≤ n -1.
Then the simulator computes for each i, E pk B (r

(B) i • (w (A) i • y (A) i + w (B) i • y (B) i
)). The result is t . The simulator appends t to the view and then appends f ∩ (S A , S B ). It is easy to see that the distributions of t and t are computationally indistinguishable. So, the two views are indistinguishable.

Combining the above, we conclude the protocol is secure and complete our proof.

Extensions

In this section we extend O-PSI to support dataset integrity verification and multiple clients. These extensions require no major modification of the protocol.

Dataset Integrity Verification

To add data integrity verification to O-PSI we can use the verification mechanism of any provable data possession protocol that does not reveal any information about the confidential data to the server. For this purpose, we can adopt the homomorphic verification tags proposed in [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF]. These tags are homomorphic in the sense that given two tags T a and T b for elements a and b one can combine them T a •T b which is equal to the tag T ag a+b of the sum a + b of the two elements.

In O-PSI, client I ∈ {A, B} defines a tag for each element v (I) i of the blinded dataset as:

T v (I) i = (h(k I ||i) • g v (I) i ) d I mod N
, where h is a secure deterministic hashand-encode function that maps strings uniformly to a unique cyclic subgroup of Z * N , QR N , k I is a random value used for all elements in the set, g = a 2 , a R ← Z * N , and N = p q is a RSA modulus, p = 2p + 1, q = 2q + 1 and d I • e I = 1 mod p q , where q and p are prime numbers. The hash value h(k I ||i) binds the tag T v (I) i to the value v (I) i and prevents the server from using the tag to compute a proof for a different value. Note,

v (I) i = y (I) i • r (I)
i is a uniformly random value. Consequently, each tag T v (I) i does not leak any information about the private value y (I) i to the server. In this protocol client I, along with its blinded dataset, outsources a vector tag (I) comprising values T v (I) i (0 ≤ i ≤ n -1) to the server. The challenge, proof generation and verification phases of the protocol remain unchanged to those described in [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF].

Multiple Clients

O-PSI can be used to compute the intersection of the outsourced datasets of multiple clients. In this case, the client interested in the intersection, client B, sends the same request (see step 3a of the protocol) to all other clients, A j (1 ≤ j ≤ m). The protocol for each client A j remains unchanged (see step 3b). For each client A j , the server carries out step 3c, and computes the result vector t such that for 0 ≤ i ≤ n -1:

t i = E pk B (w (B) i • v (B) i ) • 1≤j≤m (e (A j ) i ) v (A j ) i •w (A j ) i = E pk B (r (B) i • (w (B) i • y (B) i + 1≤j≤m w (A j ) i • y (A j ) i ))
Then the server sends t to client B, that carries out the final step, step 3e, unchanged. Note that in this protocol, even if m -1 clients collude, none can infer the set elements of the non-corrupted client, as the random polynomials ω (A j )

I

, picked by the server, are unknown to the clients.

We evaluate O-PSI by comparing its properties to those provided by other protocols that delegate PSI computation to a server. We also compare these protocols in terms of communication and computation complexity. Table 1 summarises the results. Properties. The protocols in [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF][START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF] require clients to interact with each other at setup. In [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF] clients need to generate jointly the key of the pseudorandom permutation used to encode the datasets, while in [START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF] they need to jointly compute some parameters that are used in the encryption of their datasets. In contrast to these protocols, in [START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF][START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF][START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF] and O-PSI the clients can independently prepare and outsource their private datasets. This is desirable in a cloud computing context as organizations and individuals can take advantage of the storage capabilities of the cloud and outsource their data at different points in time and without prior consideration of who is going to use them.

In a delegated PSI protocol, privacy should be maintained and the server should not learn anything about the intersection during the computation, including its cardinality. This is the case for the size-hiding variation of [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF], protocols in [START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF][START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF], and O-PSI. However, as discussed in section 2 this is not the case for [START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF][START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF].

More interestingly, O-PSI is the only protocol in which clients can reuse their outsourced datasets on the server in multiple delegated PSI computations without the need to prepare their datasets for each computation, and computing PSI on the outsourced dataset multiple times does not reveal any information to the server. This is an important advantage in scenarios where outsourced datasets are expected to be used a lot of times, as it significantly reduces the overall communication and storage cost for the clients. This is not the case for any of the other protocols, because the clients either do not outsource their datasets, or need to re-encode them locally for each operation in order to prevent the server from inferring information about the intersection over time.

As we showed in section 6.2, O-PSI can be easily extended to support multiple clients. This is also the case for [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF][START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF][START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF][START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF]. However, this is not possible for [START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF], as this requires an additional logical operation that is not supported by the homomorphic encryption scheme used.

O-PSI has been designed for the semi-honest security model and as a result does not consider the case where the server maliciously deviates from the protocol and computes the wrong result. This is a reasonable assumption in a cloud computing context where cloud providers are keen to preserve their reputation and this assumption is widely considered in the literature [START_REF] Wang | Secure and practical outsourcing of linear programming in cloud computing[END_REF][START_REF] Hahn | Searchable encryption with secure and efficient updates[END_REF][START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF][START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF][START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF]. However [START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF] allows the client to verify the correctness of the results, while as we have seen in section 2, [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF] can detect server misbehavior at an additional cost.

In conclusion, in contrast to other protocols, O-PSI has a unique combination of properties that make it particularly appealing for a cloud computing setting. Communication Complexity. The communication complexity of O-PSI for the client who receives the result, client B, is O(d), where d is the dataset size. This is because, client B sends to client A the n = 2d + 1 encrypted random values E pk B (r (B) i ) for 0 ≤ i ≤ n-1 (see step 3a). The communication complexity for client A, who authorizes the operation on its dataset, is O(d), as for each of the n values it receives from client B it sends to the server E pk B (r (B) i •(r (A) i ) -1 ) (see step 3b). The communication complexity for the server is O(d), as it sends to client B the result vector t of size n (see step 3d). Thus, the overall communication complexity of our protocol is 3n which is linear, O(d), to the dataset size.

In [START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF] for each set intersection, the client engages in a two-round protocol, one round to upload its elements in the form of RSA ciphertexts to the server with O(d) communication complexity, and another to interactively compute private set intersection with the server with O(d 2 ) communication complexity. For the protocol in [START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF], the communication complexity is also quadratic O(sd 2 ), where s is the number of hash functions used for the bloom filter, and the messages contain BGN encryption ciphertexts. On the other hand, the protocols in [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF][START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF] have O(d) communication complexity with messages containing symmetric key encryption ciphertexts, while the protocol in [START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF] has O(k) complexity, where k is the intersection size.

In conclusion, similar to the most efficient protocols, O-PSI has linear communication complexity, however at an increased message size, which results from the additional dataset outsourcing properties and privacy guarantees that it provides. Computation Complexity. We evaluate the computational cost of O-PSI by counting the number of exponentiation operations, as their cost dominates that of other operations. More specifically, client B performs n exponentiations to encrypt the random values in step 3.a, and needs another n exponentiations to decrypt the polynomial sent by the server in step 3.e. So, in total it carries out 2n exponentiations. Client A performs n exponentiations to enable the set intersection in step 3.b, while the server carries out n exponentiations to encrypt client B's dataset and n exponentiations to transform client A's dataset in step 3.d, a total of 2n exponentiations. It is interesting to note that using the point-value representation increases the overall storage costs at the server. However, the modest increase in storage brings a significant decrease in the computational costs, from O(d 2 ) (when using encrypted coefficients such as in [START_REF] Kissner | Privacy-preserving set operations[END_REF]) to O(d). In total O-PSI involves 5n exponentiations. Hence, its computation complexity is linear to the size of the dataset, O(d).

The semi-honest variant of the protocol in [START_REF] Kamara | Scaling private set intersection to billion-element sets[END_REF] also has linear complexity O(d), as the client computing the result and the server invoke the pseudorandom permutation (PRP) d times, while the other client invokes the PRP, 2d times. On the other hand, the computational overhead in [START_REF] Kerschbaum | Collusion-resistant outsourcing of private set intersection[END_REF] is quadratic O(d 2 ), as it involves a joint PSI pro-tocol (plus public key encryption of the dataset elements). The protocol in [START_REF] Kerschbaum | Outsourced private set intersection using homomorphic encryption[END_REF] also has quadratic complexity, as it involves O(d 2 ) BGN public key encryption operations. In [START_REF] Liu | Encrypted set intersection protocol for outsourced datasets[END_REF] the client performs O(d) modular additions, while the server carries out O(d 2 ) operations to compare the expanded sets of the users. Finally, the protocol in [START_REF] Zheng | Verifiable delegated set intersection operations on outsourced encrypted data[END_REF] is based on bilinear maps and requires 6d pairings at the server side and 2k exponentiations at the client side, resulting in O(d) and O(k) computation complexity at the server and client side respectively.

In conclusion, similar to the most efficient protocols, due to the use of polynomials in point-value form, O-PSI incurs only linear computational costs. However, the additional properties it provides come at the cost of more costly exponentiation operations.

Conclusions and Future Work

In this paper we have presented O-PSI, a protocol allows clients to outsource their private datasets and delegate PSI computation to a server. A key building block of O-PSI is a novel representation of sets as polynomials in point-value form. The protocol allows clients to independently prepare and outsource their private datasets, while allowing, with the clients' permission, the server to compute multiple set intersections without revealing any information about the result or the sets, and no need for re-preparation of the sets. O-PSI has been shown to be secure in the semi-honest model, and has linear communication and computation complexity, with respect to the size of the datasets. O-PSI can be easily extended to support multiple clients and dataset integrity verification. As a result, O-PSI is a scalable protocol particularly suited for cloud computing environments. In the future, we plan to investigate how O-PSI can be extended to support additional set operations like set union or subset. We also plan to explore how clients can update their sets without the need to fully re-encode them, and verify the integrity of any computation.

  a uniformly random polynomial. This means that if ρ A and ρ B are polynomials representing sets S A and S B , then the polynomial γ A • ρ A + γ B • ρ B contains only information about S A ∩ S B and no information about other elements in S A or S B . This forms the basis of their PSI protocol in which a party obtains γ A • ρ A + γ B • ρ B to find the set intersection but learns nothing more about elements in the other party's set.

  4 O-PSI: Delegated Private Set Intersection on Outsourced Datasets 4.1 Polynomials in Point-value Form

Fig. 1 :

 1 Fig. 1: Interaction between parties in O-PSI.

  Client A has a set S A ⊂ U and client B has a set S B ⊂ U. Without loss of generality, we let |S A | = |S B | = d. The server publishes a vector x containing n = 2d + 1 random distinct values from R. The server also publishes a pseudorandom function f : {0, 1} l × Z → R, which maps an l-bit string to an element in R pseudorandomly. 2. Outsource This step is the same at both clients. Let I ∈ {A, B}, then the client I does the following: (a) Generates a Paillier key pair (pk I , sk I ) (see section 3.2) and publishes the public key. It also chooses a random private key k I for the pseudorandom function f . All keys are generated according to a given security parameter. (b) Constructs a polynomial τ I = s (I)

  In this step, client B wants to know the intersection of its set and client A's set. (a) Client B sends a request to client A. Along with the request, client B also sends its ID and a vector e(B) , such that e(B) i = E pk B (r (B) i ) where r (B) i = f (k B , i) for 0 ≤ i ≤ n -1 are the values used to blind its set polynomial. (b) Client A can send a Deny message to end the protocol here, or if it agrees to engage in the computation of the set intersection, it sends a Permit message to client B. It also sends a Compute message that contains its own and B's IDs, and a vector e (A) to the server. The vector e (A) is computed as follows: for 0

  Communication complexityO(d) O(d) O(d 2 ) O(d) O(d 2 ) O(k) Computation complexity O(d) O(d) O(d 2 ) O(d 2 ) O(d 2 ) O(d)

Table 1 :

 1 Comparison of different delegated PSI protocols. Set cardinality and intersection cardinality are denoted by d and k respectively.

Acknowledgments We would like to thank the anonymous reviewers. Aydin Abadi is supported by a EPSRC Doctoral Training Grant studentship.


Josep Domingo-Ferrer

Qianhong Wu
email: qianhong.wu@buaa.edu.cn

Alberto Blanco-Justicia
email: alberto.blanco@urv.cat

Flexible and Robust Privacy-Preserving Implicit Authentication

Keywords: Privacy-preserving implicit authentication, privacy-preserving set intersection, implicit authentication, active authentication, transparent authentication, risk mitigation, data brokers

Implicit authentication consists of a server authenticating a user based on the user's usage profile, instead of/in addition to relying on something the user explicitly knows (passwords, private keys, etc.). While implicit authentication makes identity theft by third parties more difficult, it requires the server to learn and store the user's usage profile. Recently, the first privacy-preserving implicit authentication system was presented, in which the server does not learn the user's profile. It uses an ad hoc two-party computation protocol to compare the user's fresh sampled features against an encrypted stored user's profile. The protocol requires storing the usage profile and comparing against it using two different cryptosystems, one of them order-preserving; furthermore, features must be numerical. We present here a simpler protocol based on set intersection that has the advantages of: i) requiring only one cryptosystem; ii) not leaking the relative order of fresh feature samples; iii) being able to deal with any type of features (numerical or non-numerical).

Introduction

The recent report [START_REF]Data Brokers: A Call for Transparency and Accountability[END_REF] by the U.S. Federal Trade Commission calls for transparency and accountability of data brokers. On the one hand, the report describes the pervasive data collection carried out by data brokers as clearly privacy-invasive. On the other hand, it presents risk mitigation services offered by data brokers as the good side of data collection, to the extent that such services protect consumers against identity theft. Indeed, storing information on how a consumer usually interacts with a service (time of the day, usual places, usual sequence of keystrokes, etc.) allows using this information to implicitly authenticate a user: implicit authentication [START_REF] Jakobsson | Implicit authentication for mobile devices[END_REF] (a.k.a. transparent authentication [START_REF] Clarke | Flexible and transparent user authentication for mobile devices[END_REF] or active authentication [START_REF] Aksari | Active authentication by mouse movements[END_REF]) is the process of comparing the user's current usage profile with the stored profile. If both profiles disagree, maybe someone is impersonating the user, e.g. after some identity theft (password theft, etc.).

The above risk mitigation argument is part a long-standing simplistic tendency in digital services (and elsewhere) to justify privacy invasion in the name of legitimate interests, as if the latter were incompatible with privacy (another old example is intellectual property protection, which was portrayed as being incompatible with the anonymity of digital content consumers until anonymous fingerprinting was proposed [START_REF] Pfitzmann | Anonymous fingerprinting[END_REF][START_REF] Domingo-Ferrer | Anonymous fingerprinting of electronic information with automatic identification of redistributors[END_REF][START_REF] Megías | Privacy-aware peer-to-peer content distribution using automatically recombined fingerprints[END_REF]). In fact, implicit authentication turns out to be a weak excuse to justify the storage and/or access by servers to the usage profiles of users. In [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] it was shown how to make implicit authentication compatible with the privacy of users. The idea is that the server only needs an encrypted version of the user's usage profile.

Contribution and plan of this paper

The protocol in [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] needs the server to store the users' accumulated usage profiles encrypted under two different cryptosystems, one that is homomorphic and one that is order-preserving. We present here a protocol for privacy-preserving implicit authentication based on set intersection, which has the advantage that the server only needs to store the users' accumulated usage profiles encrypted under one (homomorphic) cryptosystem. This allows saving storage at the carrier and also computation during the protocol. Also, unlike [START_REF] Safa | Privacy-preserving implicit authentication[END_REF], our protocol does not leak the relative order of fresh feature samples collected by the user's device for comparison with the encrypted profile. Finally, our protocol can deal with any type of features (numerical or non-numerical), while the protocol [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] is restricted to numerical features.

The rest of this paper is organized as follows. Section 2 gives background on implicit authentication and on the privacy-preserving implicit authentication protocol of [START_REF] Safa | Privacy-preserving implicit authentication[END_REF]. Section 3 discusses how to compute the dissimilarity between two sets depending on the type of their elements. Section 4 presents a robust privacy-preserving set intersection protocol that can effectively be used for implicit authentication. The privacy, security and complexity of the new protocol are analyzed in Section 5. Experimental results are reported in Section 6. Finally, conclusions and future research directions are summarized in Section 7. The Appendix gives background on privacy-preserving set intersection, recalls the Paillier cryptosystem and justifies the correctness of the least obvious steps of our protocol.

Background

We first specify the usual setting of implicit authentication and we then move to privacy-preserving implicit authentication.

Implicit authentication

The usual scenario of implicit authentication is one in which the user carries a mobile networked device (called just user's device in what follows) such as a cell phone, tablet, notebook, etc. The user wishes to authenticate to a server in order to use some application. The user may (or not) use a primary password authentication mechanism. To strengthen such a primary authentication or even to replace it, the user resorts to implicit authentication [START_REF] Jakobsson | Implicit authentication for mobile devices[END_REF]. In this type of authentication, the history of a user's actions on the user's device is used to construct a profile for the user that consists of a set of features. In [START_REF] Jakobsson | Implicit authentication for mobile devices[END_REF] empirical evidence was given that the features collected from the user's device history are effective to distinguish users and therefore can be used to implicitly authenticate them (instead or in addition to explicit authentication based on the user's providing a password).

The types of features collected on the user's actions fall into three categories: (i) device data, like GPS location data, WiFi/Bluetooth connections and other sensor data; (ii) carrier data, such as information on cell towers seen by the device, or Internet access points; and (iii) cloud data, such as calendar entries. It is not safe to store the accumulated profile of the user in the user's device, because an intruder might compromise the device and alter the stored profile in order to impersonate the legitimate user. Hence, for security, the profile must be stored by some external entity. However, the user's profile includes potentially sensitive information and storing it outside the user's device violates privacy.

Implicit authentication systems try to mitigate the above privacy problem by using a third party, the carrier (i.e. the network service provider) to store the user's profiles. Thus, the typical architecture consists of the user's device, the carrier and the application servers. The latter want to authenticate the user and they collaborate with the carrier and the user's device to do so. The user's device engages in a secure two-party computation protocol with the carrier in order to compare the fresh usage features collected by the user's device with the user's profile stored at the carrier. The computation yields a score that is compared (by the carrier or by the application server) against a threshold, in order to decide whether the user is accepted or rejected. In any case, the application server trusts the score computed by the carrier.

Privacy-preserving implicit authentication

In the privacy-preserving implicit authentication system proposed in [START_REF] Safa | Privacy-preserving implicit authentication[END_REF], the user's device encrypts the user's usage profile at set-up time, and forwards it to the carrier, who stores it for later comparison. There is no security problem because during normal operation the user's device does not store the user's profile (it just collects the fresh usage features). There is no privacy problem either, because the carrier does not see the user's profile in the clear.

The core of proposal [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] is the algorithm for computing the dissimilarity score between two inputs: the fresh sample provided by the user's device and the profile stored at the carrier. All the computation takes place at the carrier and both inputs are encrypted: indeed, the carrier stores the encrypted profile and the user's device sends the encrypted fresh sample to the carrier. Note that the keys to both encryptions are only known to the user's device (it is the device who encrypted everything).

The carrier computes a dissimilarity score at the feature level, while provably guaranteeing that: i) no information about the profile stored at the carrier is revealed to the device other than the average absolute deviation of the stored feature values; ii) no information about the fresh feature value provided by the device is revealed to the carrier other than how it is ordered with respect to the stored profile feature values.

The score computation protocol in [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] uses two different encryption schemes: a homomorphic encryption scheme HE (for example, Paillier's [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]) and an order-preserving symmetric encryption scheme OP SE (for example, [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]). For each feature in the accumulated user's profile, two encrypted versions are created, one under HE and the other under OP SE. Similarly, for each feature in the fresh sample it collects, the user's device computes two encrypted versions, under HE and OP SE, respectively, and sends them to the carrier. The following process is repeated for each feature:

1. Using the HE ciphertexts the carrier performs some computations (additions and scalar multiplications) relating the encrypted fresh sampled feature value and the set of encrypted feature values in the stored encrypted user's profile. 2. The output of the previous computations is returned to the user's device, which decrypts it, re-encrypts it under OP SE and returns the re-encrypted value to the carrier. 3. Using the order-preserving properties, the carrier can finally compute a dissimilarity score evaluating how different is the fresh sampled feature from those stored in the encrypted user's profile. This score can be roughly described as the number of feature values in the stored encrypted profile that are less dissimilar from the median of the stored values than the fresh sampled value.

The authors of [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] point out that, in case of a malicious user's device (e.g. as a result of it being compromised), one cannot trust the device to provide the correct HE-encrypted version of the fresh sampled feature. Nor can it be assumed that the device returns correct OP SE-encryptions in Step 2 above. In [START_REF] Safa | Privacy-preserving implicit authentication[END_REF], a variant of the privacy-preserving implicit authentication protocol is presented in which the device proves the correctness of HE-encrypted fresh sampled features and does not need to provide OP SE-encrypted values. This version is secure against malicious devices, but its complexity is substantially higher.

Other shortcomings of [START_REF] Safa | Privacy-preserving implicit authentication[END_REF]:

-It is restricted to numerical features, due to the kind of computations that need to be performed on them. However, among the example features listed in Section 2.1, there are some features that are not numerical, like the list of cell towers or Internet access points seen by the user's device.

-It discloses the following information to the user's device: i) how the fresh sample is ordered with respect to the stored profile feature values; ii) the average absolute deviation of the stored feature values.

We present a privacy-preserving implicit authentication protocol based on set intersection that deals with the above shortcomings.

Dissimilarity between sets depending on the data type

Based on [START_REF] Blanco-Justicia | Distance computation between two private preference functions[END_REF], we recall here how the dissimilarity between two data sets X and Y can be evaluated using set intersection. If we let X be the user's profile and Y be the fresh sample collected by the user's device, our privacy-preserving implicit authentication setting presents the additional complication (not present in [START_REF] Blanco-Justicia | Distance computation between two private preference functions[END_REF]) that X is only available in encrypted form (the carrier stores only the encrypted user's profile). Anyway, we describe here the case of two plaintext sets X and Y and we will deal with encrypted sets in the following sections.

Case A: independent nominal feature values

Assume X and Y consist of qualitative values, which are independent and binary, that is, the relationship between two values is equality or nothing. Take as an example the names of the network or phone providers seen by the user's device, the operating system run by the device and/or the programs installed in the device. In this case, the dissimilarity between X and Y can be evaluated as the multiplicative inverse of the size of the intersection of X and Y , that is 1/|X ∩Y |, when the intersection is not empty. If it is empty, we say that the dissimilarity is ∞.

Clearly, the more the coincidences between X and Y , the more similar is the profile stored at the carrier to the fresh sample collected by the device.

Case B: correlated categorical feature values

As in the previous case, we assume the feature values are expressed as qualitative features. However, these may not be independent. For example, if the feature values are the IDs of cell towers or Internet access points seen by the device, nearby cell towers/access points are more similar to each other than distant cell towers/access points.

In this case, the dissimilarity between X and Y cannot be computed as the size of their intersection.

Assume we have an integer correlation function l : E×E → Z + that measures the similarity between the values in the sets of features held by the device and the carrier, where E is the domain where the sets of features of both players take values. For nominal features, semantic similarity measures can be used for this purpose [START_REF] Sánchez | Ontology-based semantic similarity: A new feature-based approach[END_REF]; for numerical features that take values over bounded and discrete domains, standard arithmetic functions can be used. Assume further that both the device and the carrier know this function s from the very beginning.

Here the dissimilarity between the set X and the set Y can be computed as 1/( x∈X y∈Y l(x, y)) when the denominator is nonzero. If it is zero, we say that the distance is ∞.

Case C: numerical feature values

In this case, we want to compute the dissimilarity between two sets of numerical values based on set intersection. Numerical features in implicit authentication may include GPS location data, other sensor data, etc. Assume

U = {u 1 , • • • , u t } and V = {v 1 , • • • , v t }.
A way to measure the dissimilarity between X and Y is to compute

t i=1 |u i -v i |.

Robust privacy-preserving set intersection for implicit authentication

It will be shown further below that computing dissimilarities in the above three cases A, B and C can be reduced to computing the cardinality of set intersections. Furthermore, this can be done without the carrier revealing X and without the user's device revealing Y , as required in the implicit authentication setting. The idea is that, if the dissimilarity stays below a certain threshold, the user is authenticated; otherwise, authentication is refused.

In Appendix A, we give some background on privacy-preserving set intersection protocols in the literature. Unfortunately, all of them assume an honest-butcurious situation, but we need a privacy-preserving set intersection protocol that works even if the adversary is a malicious one: notice that the user's device may be corrupted, that is, in control of some adversary. Hence we proceed to specifying a set intersection protocol that remains robust in the malicious scenario and we apply it to achieving privacy-preserving implicit authentication in Case A. We then extend it to Cases B and C. We make use of Paillier's cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF], which is recalled in Appendix B.

Implicit authentication in Case A

Set-up Let the plaintext user's profile be (a 1 , • • • , a s ). In this phase, the user's device transfers the encrypted user's profile to the carrier. To do so, the user's device does:

1. Generate the Paillier cryptosystem with public key pk = (n, g) and secret key sk.

Compute the polynomial p

(x) = s i=1 (x -a i ) = p 0 + p 1 x + p 2 x 2 + • • • + p s x s . 3. Compute Enc(p 0 ), • • • Enc(p s ) where Enc(p i ) = g pi r n i mod n 2 . 4. Randomly choose R ∈ Z n 2 . Find r 0 , • • • , r s ∈ Z n 2 such that R = r 0 • r 1 aj • r 2 a 2 j • • • r s a s j mod n 2 , j = 1, • • • , s (1)
Note that the system (1) has a trivial solution r 0 = R and r 1 = • • • = r s = 1, but, since it is underdetermined (s + 1 unknowns and s equations), it has many non-trivial solutions too (see correctness analysis in Appendix C).

Compute

R i = r i /r i mod n 2 . Randomly choose integer d ∈ Z n . Send pk, Enc(p 0 ), • • • Enc(p s ); R 0 d , • • • , R s d mod n 2
to the carrier. Locally delete all data computed during the set-up protocol, but keep (d, R ) secretly.

Implicit authentication protocol As discussed in Section 3.1, in case of independent nominal feature values (Case A), dissimilarity is computed as 1/|X∩ Y |. Hence, to perform implicit authentication the carrier just needs to compute the cardinality of the intersection between the fresh sample collected by the user's device and the user's profile stored at the carrier. The challenge is that the carrier only holds the encrypted user's profile and the user's device does no longer hold the plaintext user's profile either in plaintext or ciphertext.

Let Y = {b 1 , • • • , b t } ⊆ E
be the fresh sample collected by the user's device. Then the device and the carrier engage in the following protocol:

Step 1 The carrier randomly chooses θ, and sends pk,

Enc(p 0 ) θ , • • • Enc(p s ) θ ; R 0 d , • • • , R s d to the user's device.
Step 2 The user's device picks a random integer r(j) ∈ Z n 2 for every 1 ≤ j ≤ t.

The device computes for 1 ≤ j ≤ t Enc(r(j)

• d • θ • p(b j )) = Enc(p(b j )) d•θ•r(j) = (Enc(p 0 ) • • • Enc(p s ) b s j ) d•θ•r(j) = g r(j)•d•θp(bj ) γ n•d•θ j mod n 2 where γ j = (r 0 • r 1 bj • r 2 b 2 j • • • r s b s j ) r(j) mod n 2 . The user's device then com- putes Υ j = (R 0 • R 1 bj • R 2 b 2 j • • • R s b s j
) dr(j) mod n 2 . For all j, the device randomly orders and sends

{(Enc(r(j) • d • θ • p(b j )), Υ j , R r(j)d )} (2)
to the carrier.

Step 3 For 1 ≤ j ≤ t, the carrier does:

-Compute Enc(r(j)

• d • θ • p(b j )) • Υ nθ j ; -From Expression (1), if b j = a i for some i ∈ {1, • • • , s}, then p(b j ) = 0 and hence Enc(r(j)d • θ • p(b j )) • Υ nθ j = R r(j)dnθ ; note that the carrier can recognize R r(j)dnθ by raising R r(j)d received in Expression (2) to nθ. Otherwise (if b j = a i for all i ∈ {1, • • • , s}) Enc(r(j) • d • θ • p(b j )) looks random. See correctness analysis in Appendix C.
If both parties are honest, then the carrier learns |X ∩ Y | but obtains no information about the elements in X or Y .

Implicit authentication in Case B

Here, the carrier inputs X and the user's device inputs Y , two sets of features, and they want to know how close X and Y are without revealing their own set. In the protocol below, only the carrier learns how close X and Y are.

We assume that the domain of X and Y is the same, and we call it E. The closeness or similarity between elements is computed by means of a function s.

In particular, we consider functions l : E × E → Z + . Observe that Case A is a particular instance of this Case B in which l(x, x) = 1 and l(x, y) = 0 for x = y.

Let Y be the input of the user's device. For every z ∈ E, the device computes z = y∈Y l(z, y). Observe that z measures the overall similarity of z and Y .

Let Y = {z ∈ E : z > 0}. It is common to consider functions satisfying l(z, z) > 0 for every z ∈ E, and so in general Y ⊆ Y . An implicit authentication protocol for such a computation can be obtained from the protocol in Case A (Section 4.1), by replacing Steps 2 and 3 there with the following ones:

Step 2' For every z ∈ Y , the user's device picks z random integers r(1),

• • • , r( z )∈Z n 2 and for 1 ≤ j ≤ z does -Compute Enc(r(j) • d • θ • p(z)) = Enc(p(z)) d•θ•r(j) = (Enc(p 0 ) • • • Enc(p s ) z s ) d•θ•r(j) = g r(j)•d•θp(z) γ n•d•θ j mod n 2 where γ j = (r 0 • r 1 z • r 2 z 2 • • • r s z s ) r(j) mod n 2 . -Compute Υ j = (R 0 • R 1 z • R 2 z 2 • • • R s z s ) dr(j) mod n 2 . -Let E j = {(Enc(r(j) • d • θ • p(z)), Υ j , R r(j)d )}.
Finally, the user's device randomly re-orders the sequence of all computed E j for all z ∈ Y (a total of z∈Y z elements) and sends the randomly re-ordered sequence of E j 's to the carrier.

Step 3' For every received E j , the carrier does -Compute Enc(r(j)dθ • p(z)) • Υ nθ j ; -From Expression (1), if z ∈ X, then p(z) = 0 and hence Enc(r(j)d • θ • p(z))•Υ nθ j = R r(j)dnθ (see correctness analysis in Appendix C); otherwise (if z ∈ X) Enc(r(j)dθ • p(z)) looks random.

Hence, at the end of the protocol, the total number of E j which yield R r(j)dnθ

is x∈X x = x∈X y∈Y l(x, y),
that is, the sum of similarities between the elements of X and Y . This clearly measures how similar X and Y are. At the end of the protocol, the carrier knows |Y | and the device knows |X|. Besides that, neither the carrier nor the device can gain any additional knowledge on the elements of each other's set of preferences.

Implicit authentication in Case C

Let the plaintext user's profile be a set U of t numerical features, which we denote by U = {u 1 , • • • , u t }. The device's fresh sample corresponding to those features is

V = {v 1 , • • • , v t }.
The carrier wants to learn how close X and Y are, that is,

t i=1 |u i -v i |.
Define X = {(i, j) : u i > 0 and 1 ≤ j ≤ u i } and Y = {(i, j) : v i > 0 and 1 ≤ j ≤ v i }. Now, take the set-up protocol defined in Section 4.1 for Case A and run it by using X as plaintext user profile. Then take the implicit authentication protocol for Case A and run it by using Y as the fresh sample input by the device. In this way, the carrier can compute |X ∩ Y |. Observe that

|X ∩ Y | = |{(i, j) : u i , v i > 0 and 1 ≤ j ≤ min{u i , v i }}| = 1≤i≤t min{u i , v i }.
In the set-up protocol for Case A, the carrier learns |X| and during the implicit authentication protocol for Case A, the carrier learns |Y |. Hence, the carrier can compute

|X| + |Y | -2|X ∩ Y | = t i=1 (max{u i , v i } + min{u i , v i }) -2 t i=1 min{u i , v i } = t i=1 (max{u i , v i } -min{u i , v i }) = t i=1 |u i -v i |

Privacy, security and complexity

Unless otherwise stated, the assessment in this section will focus on the protocols of Case A (Section 4.1), the protocols of Cases B and C being extensions of Case A.

Privacy and security

We define privacy in the following two senses:

-After the set-up is concluded, the user's device does not keep any information about the user's profile sent to the carrier. Hence, compromise of the user's device does not result in compromise of the user's profile. -The carrier learns nothing about the plaintext user's profile, except its size.

This allows the user to preserve the privacy of her profile towards the carrier.

Lemma 1. After set-up, the user's device does not keep any information on the user's profile sent to the carrier.

Proof. The user's device only keeps (d, R ) at the end of the set-up protocol. Both d and R are random and hence unrelated to the user's profile. . Lemma 2. The carrier or any eavesdropper learn nothing about the plaintext user's profile, except its size.

Proof. After set-up, the carrier receives pk, Enc(p 0 ), If we define security of implicit authentication as the inability of a dishonest user's device to disrupt the authentication outcome, we can state the following result.

• • • Enc(p s );R 0 d , • • • , R s d mod n 2 .
Lemma 3. A dishonest user's device has no better strategy to alter the outcome of implicit authentication than trying to randomly guess the user's profile.

Proof. At the end of the set-up protocol, the (still uncompromised) user's keeps no information about the user's profile (Lemma 1). Hence, if the user's device is later compromised and/or behaves dishonestly, it still has no clue on the real user's profile against which its fresh sample is going to be authenticated. Hence, either the user's device provides an honest fresh sample and implicit authentication will be correctly performed, or the user's device provides a random fresh sample with the hope that it matches the user's profile.

Complexity

Case A During the set-up protocol, the user's device needs to compute:

s + 1 Paillier encryptions for the polynomial coefficients; values r 0 , • • • , r s ; as explained in Appendix C, this can be done by randomly choosing r 0 , then solving an s × s generalized Vandermonde system (doable in O(s 2 ) time using [START_REF] Demmel | The accurate and efficient solution of a totally positive generalized Vandermonde linear system[END_REF]) and finally computing s modular powers to find the r 1 , • • • , r s ; s + 1 modular powers (raising the R i values to d).

During the implicit authentication protocol, the user's device needs to compute (Step 2):

t Paillier encryptions; ts modular powers (to compute the Υ j values); t modular powers (to raise R to r(j)d).

Also during the implicit authentication protocol, the carrier needs to compute:

-At Step 1, s + 1 modular powers (to raise the encrypted polynomial coefficients to θ); -At Step 3, t Paillier encryptions; -At Step 3, t modular powers (to raise the Υ j values to nθ).

Case B The set-up protocol does not change w.r.t. Case A. In the implicit authentication protocol, the highest complexity occurs when Y = E and the similarity function l always takes the maximum value in its range, say L. In this case,

z∈Y z = z∈Y y∈Y l(z, y) = |E|sL.
Hence, in the worst case the user's device needs to compute (Step 2'):

-|E|sL Paillier encryptions; -|E|sL modular powers (to compute the Υ j values); -|E|sL modular powers (to raise R to r(j)d).

Also during the implicit authentication protocol, the carrier needs to compute:

-At Step 1, s + 1 modular powers (to raise the encrypted polynomial coefficients to θ); -At Step 3', |E|sL Paillier encryptions; -At Step 3', |E|sL modular powers (to raise the Υ j values to nθ).

Note that the above complexity can be reduced by reducing the range of the similarity function l(•, •).

Case C Case C is analogous to Case A but the sets X and Y whose intersection is computed no longer have s and t elements, respectively. According to Section 4.3, the maximum value for |X| occurs when all u i take the maximum value of their range, say, M , in which case X contains tM pairs (i, j). By a similar argument, Y also contains at most tM pairs. Hence, the worst-case complexity for Case C is obtained by performing the corresponding changes in the assessment of Case A. Specifically, during the setup protocol, the user's device needs to compute:

-tM + 1 Paillier encryptions for the polynomial coefficients; -Solve a Vandermonde system tM × tM (doable in O((tM ) 2 ) time) and then compute tM modular powers to find the r i values; -Compute tM + 1 modular powers (raising the R i values to d).

During the implicit authentication protocol, the user's device needs to compute (Step 2):

-tM Paillier encryptions; t 2 M 2 modular powers (to compute the Υ j values); -tM modular powers (to raise R to r(j)d).

Also during the implicit authentication protocol, the carrier needs to compute:

-At Step 1, tM + 1 modular powers (to raise the encrypted polynomial coefficients to θ); -At Step 3, tM Paillier encryptions; -At Step 3, tM modular powers (to raise the Υ j values to nθ).

Note that the above complexities can be reduced by reducing the range of the numerical values in sets U and V .

Experimental results

As stated in the previous section, the complexity of our implicit authentication protocol ultimately depends on the sizes of the input sets. In Case A, the sizes of the sets are directly given by the user inputs; in Case B, these sizes are the product of the size of the input sets times the range of the similarity function ; and in Case C, the sizes are given by the size of the original sets times the range of their values. We ran an experiment to test the execution times of our protocol, based on Case A, to which the other two cases can be reduced.

The experiment was implemented in Sage-6.4.1 and run on a Debian7.7 machine with a 64-bit architecture, an Intel i7 processor and 8GB of physical memory. We instantiated a Paillier cryptosystem with a 1024-bit long n, and the features of preference sets were taken from the integers in the range [1 . . . 2 128 ]. The input sets ranged from size 1 to 50, and we took feature sets of the same size to execute the set-up and the authentication protocols.

Step 4 of the set-up protocol (Section 4.1), in which a system of equations is solved for r i for 1 ≤ i ≤ s, is the most expensive part of the set-up protocol. As a worst-case setting, we used straightforward Gaussian elimination which takes time O(s 3 ), although, as mentioned above, specific methods like [START_REF] Demmel | The accurate and efficient solution of a totally positive generalized Vandermonde linear system[END_REF] exist for generalized Vandermonde matrices that can run in O(s 2 ) (such specific methods could be leveraged in case of smartphones with low computational power). On the other hand, Step 2 of the authentication protocol (Section 4.1), computed by the user's device, is easily parallelizable for each feature in the sample set. Since parallelization can be exploited by most of the current smartphones in the market, we also exploited it in our experiment. The results are shown in Table 1 (times are in seconds).

Note that the set-up protocol is run only once (actually, maybe once in a while), so it is not time-critical. However, the authentication protocol is to be run at every authentication attempt by the user. For example, if a user implicitly authenticates herself using the pattern of her 20 most visited websites, authentication with our proposal would take 3.37 seconds, which is perfectly acceptable in practice.

Conclusions and future research

To the best of our knowledge, we have presented the second privacy-preserving implicit authentication system in the literature (the first one was [START_REF] Safa | Privacy-preserving implicit authentication[END_REF]). The advantages of our proposal with respect to [START_REF] Safa | Privacy-preserving implicit authentication[END_REF] are:

-The carrier only needs to store the user's profile encrypted under one cryptosystem, namely Paillier's. -Dishonest behavior or compromise at the user's device after the initial setup stage neither compromises the privacy of the user's profile nor affects the security of authentication. -Our proposal is not restricted to numerical features, but can deal also with all sorts of categorical features. -In case of numerical or categorical ordinal features, our proposal does not disclose how the fresh sample is ordered with respect to the feature values in the stored user's profile.

For binary or independent nominal features, the complexity of our proposal is quite low (quadratic in the number of values in the user's profile). For correlated categorical feature values, the complexity is higher, but it can be reduced by decreasing the range of the similarity function used. Finally, in the case of numerical values, the complexity is also higher than in the binary/independent nominal case, but it can be reduced by decreasing the range of the numerical feature values.

Future research will include devising ways to further decrease the computational complexity in all cases. crypts as the sum of their corresponding plaintexts:

D(E(m 1 , r 1 ) • E(m 2 , r 2 ) mod n 2 ) = m 1 + m 2 mod n.
Also, the product of a ciphertext times g raised to a plaintext decrypts as the sum of the corresponding plaintexts:

D(E(m 1 , r 1 ) • g m2 mod n 2 ) = m 1 + m 2 mod n.
-Homomorphic multiplication of plaintexts. An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts:

D(E(m 1 , r 1 ) m2 mod n 2 ) = D(E(m 1 , r 1 ) m2 mod n 2 ) = m 1 m 2 mod n.
More generally, given a constant k, D(E(m 1 , r 1 ) k mod n 2 ) = km 1 mod n.

C Correctness

In general, the correctness of our protocol follows from direct algebraic verification using the properties of Paillier's cryptosystem. We go next through the least obvious steps.

C.1 Set-up protocol

In the set-up protocol, r 0 , • • • , r s are found as a solution of the following system The above system has s + 1 unknowns and s equations. Therefore it has one degree of freedom. To avoid the trivial solution r 0 = R and r 1 = • • • = r s = 1, we choose a random r 0 . Then we divide the system by r 0 and we take logarithms to get The matrix on the right-hand side of the above system is an s × s generalized Vandermonde matrix (not quite a Vandermonde matrix). Hence, using the techniques in [START_REF] Demmel | The accurate and efficient solution of a totally positive generalized Vandermonde linear system[END_REF] it can be solved in O(s 2 ) time for log r 1 , • • • , log r s . Then s powers modulo n 2 need to be computed to turn log r i into r i for i = 0, • • • , s.

C.2 Implicit authentication protocol

We specify in more detail the following derivation in Step 2 of the implicit authentication protocol of Section 4. (

If in Step 3, if we have b j = a i for all i ∈ {1, • • • , s}, then Derivation (3) does not hold and a random number is obtained instead. On the one side, the powers of g does not disappear from Enc(r(j)dθ • p(b j )). On the other side, the exponents b j , • • • , b s j cannot be changed by a i , • • • , a s i as done in the last step of Derivation (3). Hence, a random number different from R r(j)dnθ is obtained.

  Since d is random and unknown to the carrier, R 0 d , • • • , R s d mod n 2 look random to the carrier and will give him no more information about the plaintext user's profile than the Paillier ciphertexts Enc(p 0 ), • • • Enc(p s ). That is, the carrier learns nothing about the user's plaintext profile X = {a 1 , • • • , a s } except its size s. The same holds true for an eavesdropper listening to the communication between the user's device and the carrier during set-up. At Step 2 of implicit authentication, the carrier only gets the fresh sample Y encrypted under Paillier and randomly re-ordered. Hence, the carrier learns no information on Y , except its size t. At Step 3, the carrier learns |X ∩ Y |, but not knowing Y , the size |X ∩ Y | of the intersection leaks to him no information on X.

1 : 2 =mod n 2 .

 122 Enc(r(j) • d • θ • p(b j )) = Enc(p(b j )) d•θ•r(j) mod n 2 = (Enc(p 0 ) • • • Enc(p s ) b s j ) d•θ•r(j) mod n 2 = (g p0 r n 0 • • • (g ps r n s ) b s j ) d•θ•r(j) mod n (g p(bj ) ) d•θ•r(j) (r 0 • r bj 1 • • • r b s j s ) r(j)•n•d•θ mod n 2 = g r(j)•d•θp(bj ) γ n•d•θ jRegarding Step 3 of the implicit authentication protocol, we detail the case b j = a i for some i ∈ {1, • • • , s}. In this case, p(b j ) = 0 and henceEnc(r(j)dθ • p(b j )) • Υ nθ j mod n 2 = Enc(0) r(j)dθ • Υ nθ j mod n 2 = (r 0 • r bj 1 • • • r b s j s ) nr(j)dθ • Υ nθ j mod n 2 = (r 0 • r bj 1 • • • r b s j s ) nr(j)dθ • (R 0 • R bj 1 • • • R b s j s ) dr(j)nθ mod n 2 = (r 0 • r ai 1 • • • r a s i s ) r(j)dnθ mod n 2 = R r(j)dnθ mod n 2 .

Table 1 .

 1 Execution times (in seconds) for different input set sizes

		1	5 10 15 20 25	30	35	40	45	50
	Set-up	0.89 0.79 1.1 1.83 4.67 11.45 24.65 47.6 84.99 144.81 228.6
	Authentication 0.08 0.47 1.05 2.0 3.37 5.4 8.27 12.13 17.3 23.39 31.2

Acknowledgments

The following funding sources are gratefully acknowledged: Government of Catalonia (ICREA Acadèmia Prize to the first author and grant 2014 SGR 537), Spanish Government (project TIN2011-27076-C03-01 "CO-PRIVACY"), European Commission (projects FP7 "DwB", FP7 "Inter-Trust" and H2020 "CLARUS"), Templeton World Charity Foundation (grant TWCF0095/AB60 "CO-UTILITY"), Google (Faculty Research Award to the first author) and Government of China (Natural Science Foundation of China under projects 61370190 and 61173154). The first author is with the UNESCO Chair in Data Privacy. The views in this paper are the authors' own and do not necessarily reflect the views of UNESCO, the Templeton World Charity Foundation or Google.

A Background on privacy-preserving set intersection

Secure multiparty computation (MPC) allows a set of parties to compute functions of their inputs in a secure way without requiring a trusted third party. During the execution of the protocol, the parties do not learn anything about each other's input except what is implied by the output itself. There are two main adversarial models: honest-but-curious adversaries and malicious adversaries. In the former model, the parties follow the protocol instructions but they try to obtain information about the inputs of other parties from the messages they receive. In the latter model, the adversary may deviate from the protocol in an arbitrary way.

We will restrict here to a two-party setting in which the input of each party is a set, and the desired output is the cardinality of the intersection of both sets. The intersection of two sets can be obtained by using generic constructions based on Yao's garbled circuit [START_REF] Yao | How to generate and exchange secrets[END_REF]. This technique allows computing any arithmetic function, but for most of the functions it is inefficient. Many of the recent works on two-party computation are focused on improving the efficiency of these protocols for particular families of functions.

Freedman, Nissim, and Pinkas [START_REF] Freedman | Efficient private matching and set intersection[END_REF] presented a more efficient method to compute the set intersection, a private matching scheme, that is secure in the honestbut-curious model. A private matching scheme is a protocol between a client C and a server S in which C's input is a set X of size i C , S's input is a set Y of size i S , and at the end of the protocol C learns X ∩ Y . The scheme uses polynomialbased techniques and homomorphic encryption schemes. Several variations of the private matching scheme were also presented in [START_REF] Freedman | Efficient private matching and set intersection[END_REF]: an extension to the malicious adversary model, an extension of the multi-party case, and schemes to compute the cardinality of the set intersection and other functions. Constructing efficient schemes for set operations is an important topic in MPC and has been studied in many other contributions. Several works such as [START_REF] Blanton | Private and oblivious set and multiset operations[END_REF][START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF][START_REF] Hohenberger | Honest-verifier private disjointness testing without random oracles[END_REF][START_REF] Kissner | Privacy-preserving set operations[END_REF][START_REF] Vaidya | Secure set intersection cardinality with application to association rule mining[END_REF] present new protocols to compute the set intersection cardinality.

B Paillier's cryptosystem

In this cryptosystem, the public key consists of an integer n (product of two RSA primes), and an integer g of order n modulo n 2 , for example, g = 1 + n. The secret key is φ(n), where φ(•) is Euler's totient function.

Encryption of a plaintext integer m, with m < n involves selecting a random integer r < n and computing the ciphertext c as c = Enc(m) = g m • r n mod n 2 = (1 + mn)r n mod n 2 .

Decryption consists of first computing c 1 = c φ(n) mod n 2 = 1 + mφ(n)n mod n 2 and then m = (c 1 -1)φ(n) -1 mod n 2 .

The homomorphic properties of Paillier's cryptosystem are as follows: