Yu Chen

Song Luo

Zhong Chen

A New Leakage-Resilient IBE Scheme in the Relative Leakage Model

Keywords: identity based encryption, leakage-resilient, relative leakage, bilinear Diffie-Hellman assumption

We propose the first leakage-resilient Identity-Based Encryption (IBE) scheme with full domain hash structure. Our scheme is leakageresilient in the relative leakage model and the random oracle model under the decisional bilinear Diffie-Hellman (DBDH) assumption.

Introduction

Cryptographic schemes are used to be analyzed in an attack model in which the internal secret states are completely hidden from the adversary/attacker. However several works [START_REF] Halderman | Lest we remember: Cold boot attacks on encryption keys[END_REF][START_REF] Kocher | Differential power analysis[END_REF] indicated that the attack model fails to capture many attacks in the real world, since the attacker may obtain some partial information about the secret states via various key leakage attacks. Therefore it is urgent to design leakage-resilient cryptographic schemes which remain provably secure in the strengthened attack model which takes key leakage attacks into account.

Recently, the research community pay a lot of attention to construct IBE schemes with leakage-resilience. Alwen et al. [START_REF] Alwen | Public-key encryption in the bounded-retrieval model[END_REF] presented three leakage-resilient IBE schemes from the Gentry IBE [START_REF] Gentry | Practical Identity-Based Encryption Without Random Oracles[END_REF], the Boneh-Gentry-Hamburg IBE [START_REF] Boneh | Space-efficient identity based encryption without pairings[END_REF], and Gentry-Peikert-Vaikuntanathan IBE [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], respectively. Among them, the first scheme is secure in the standard model, while the other two schemes are secure in the random oracle model. Chow et al. [START_REF] Chow | Practical leakage-resilient identity-based encryption from simple assumptions[END_REF] gave three new leakage-resilient IBE schemes from the Boneh-Boyen IBE [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption without Random Oracles[END_REF], the Waters IBE [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF], and the Lewko-Waters IBE [START_REF] Lewko | New techniques for dual system encryption and fully secure hibe with short ciphertexts[END_REF], respectively. All of them are secure in the standard model.

Boneh-Franklin IBE [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF]), the exponent inversion family (e.g. Gentry-IBE [START_REF] Gentry | Practical Identity-Based Encryption Without Random Oracles[END_REF]), and the commutative blinding family (e.g. Boneh-Boyen IBE [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption without Random Oracles[END_REF]). The existing work [START_REF] Alwen | Public-key encryption in the bounded-retrieval model[END_REF][START_REF] Chow | Practical leakage-resilient identity-based encryption from simple assumptions[END_REF] have shown that IBE schemes from the exponent inversion family and commutative blinding family can be tailored to be leakage-resilient ones. It is natural to ask if we can strengthen the IBE schemes from the full domain hash family to be leakage-resilient.

We give an affirmative answer to the above question by presenting an IBE scheme with the full domain hash structure based on a variant of Boneh-Franklin IBE [START_REF] Coron | A variant of Boneh-Franklin IBE with a tight reduction in the random oracle model[END_REF]. Its leakage-resilient chosen plaintext security can be tightly reduced to the DBDH assumption in the relative leakage model and the random oracle model.

Preliminaries

Notations. x R ← -S denotes that x is picked uniformly at random from the set S. We write PPT for probabilistic polynomial time. By negl(n) we denote a negligible function of n. We denote the bit-wise XOR operation by ⊕. We denote by I the identity space and by SK the private key space.

Bilinear Diffie-Hellman Assumption

The decisional BDH (DBDH) assumption [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption without Random Oracles[END_REF][START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] is defined via the following game: the challenger runs the bilinear group generator GroupGen(1 κ ) to generate (p, G, G T , e), picks four random exponents x, y, z, w from Z p , then computes g x , g y , g z , T 0 = e(g, g) xyz and T 1 = e(g, g) xyw . We denote by D the tuple (p, G, G T , e, g, g x , g y , g z ). The challenger picks a random bit c and gives to the adversary B the challenge instance (D, T c ). We say B succeeds in solving the DBDH problem if it outputs the right guess c for c at the end of the game, whose advantage is defined as:

|Pr[c = c ] -1/2| = |Pr[B(D, e(g, g) xyz ) = 0] -Pr[B(D, e(g, g) xyw ) = 0]| Definition 2.1
The (t, )-DBDH assumption holds if no t-time adversary has at least in solving the DBDH problem in G.

Randomness Extractors

The following notions and primitives will be used in our construction. We refer the readers to [START_REF] Alwen | Public-key encryption in the bounded-retrieval model[END_REF][START_REF] Naor | Public-key cryptosystems resilient to key leakage[END_REF] for a complement knowledge.

For a random variable X, we define H ∞ (X) = -log(max x Pr[X = x]) as its min-entropy. We use the notion of average min-entropy [START_REF] Dodis | Fuzzy extractors: How to generate strong keys from biometrics and other noisy data[END_REF] which captures the remaining unpredictability of a random variable X conditioned on another random variable Y , formally defined as

H∞ (X|Y ) = -log E y←Y max x Pr[X = x|Y = y]
where E y←Y denotes the expected value over all values of Y .

The average min-entropy measures exactly the optimal probability of guessing X given knowledge of Y . The following lemma was proved in [START_REF] Dziembowski | Intrusion-resilience via the bounded-storage model[END_REF] regarding average min-entropy:

Lemma 1. For any random variables X, Y , Z, if Y has 2 possible val- ues, then H∞ (X|(Y, Z)) ≥ H∞ (X|Z) -.
The statistical distance between two random variables X, Y over a finite domain Ω is defined as

SD(X, Y ) = 1 2 ω∈Ω |Pr[X = ω] -Pr[Y = ω]|
Same as [START_REF] Alwen | Public-key encryption in the bounded-retrieval model[END_REF][START_REF] Chow | Practical leakage-resilient identity-based encryption from simple assumptions[END_REF][START_REF] Naor | Public-key cryptosystems resilient to key leakage[END_REF], a main tool used in our construction is the strong randomness extractor, which is formally defined as follows to the setting of the average min-entropy.

Definition 2.2 A polynomial-time function ext : G×{0, 1} µ → {0, 1} m is an average case (k, )-strong extractor if for all pairs of random variables (X, Y ) such that X ∈ G and H∞ (X|Y ) ≥ k, we have that

SD((ext(X, U µ ), U µ , Y )), (U m , U µ , Y )) ≤
where G is a non-empty set, and U µ , U m are two uniformly distributed random variables over {0, 1} µ , {0, 1} m respectively. Dodis et al. [START_REF] Dodis | Fuzzy extractors: How to generate strong keys from biometrics and other noisy data[END_REF] proved that any strong extractor is in fact an averagecase strong extractor, for a proper setting of the parameters: Lemma 2. For any δ > 0, if ext is a worst case (m -log(1/δ), )-strong extractor, then ext is also an average-case (m, + δ)-strong extractor.

As a specific example, they proved the following lemma which essentially gives an explicit construction of an average-case strong extractor:

Lemma 3. Let X, Y be two random variables such that X ∈ G and H∞ (X|Y ) ≥ k. Let H = {H : G → {0, 1} m } be a family of universal hash functions. If m ≤ k -2 log(1/ ) then we have SD((H(X), U s , Y )), (U m , U s , Y )) ≤

Leakage Model for IBE Setting

In this paper we use the relative leakage model suitable for the IBE setting. The leakage-resilient chosen plaintext security is defined by the following LeakCPA game, which is refined from the CpaLeak game introduced in [START_REF] Chow | Practical leakage-resilient identity-based encryption from simple assumptions[END_REF]. Setup. The challenger generates the public parameters mpk and the master secret key msk. It gives mpk to the adversary and keeps msk to itself.

Phase 1. The adversary can make one of the following two types of queries to the challenger: 1. Leak(I, h i ) query, where h i : SK → {0, 1} i . The challenger checks if the overall amount leakage will exceed . If not, it responds with h i (sk). Otherwise it responds with a reject symbol ⊥.

2. Reveal(I) query, where I is the identity. The challenger responds with the associated private key sk.

Challenge. The adversary submits two messages M 0 , M 1 of equal size and a challenge identity I * , with the restriction that I * has not been revealed. The challenger picks a random bit β and encrypts M β under I * . It sends the resulting ciphertext C * to the adversary.

Phase 2. The same as Phase 1 with the restriction that no leakage queries or reveal queries related to I * are allowed.

Guess. The adversary outputs a bit β . We say it succeeds if β = β . The advantage of an adversary A on breaking an IBE scheme E with security parameter κ and leakage bound is defined as Adv CPALeak

A,E (κ, ) = |Pr[β = β ] -1 2 |.
Definition 2.3 An IBE scheme E is -leakage fully secure if for all PPT adversaries A it holds that Adv CPALeak

A,E (κ, ) ≤ negl(κ).

Our Scheme

Our scheme consists of the following four algorithms: 3 , c 2 ). It is easy to verify that if the private key matches, we get the right decryption.

Setup. Run GroupGen(1 κ ) → (p, G, G T , e), pick x R ← -Z p , g 2 R ← -G * ,

Security Analysis

Theorem 3.1 If the DBDH assumption holds and the extractor's second parameter ext is negligible in κ, then the proposed scheme is -leakage secure, where = log |G T | -k and k is the extractor's first parameter.

To prove the theorem, we organize the proof as a sequence of games, which are defined as follows: Game Real : The real CPALeak game.

Game Final : The real CPALeak game except in the challenge phase the challenger generates the ciphertext as follows:

z, w R ← -Z p , β R ← -{0, 1} W = e(u * , g 1 ) z e(g 1 , g 2 ) t * (w-z) c * 1 = g z c * 2 R ← -{0, 1} µ c * 3 = e(g 1 , g 2 ) w c * 4 = M β ⊕ ext(W, c * 2 )
where t * is the tag of private key sk * of the challenge identity I * , z and w are randomly picked from Z p . The challenge ciphertext is

C * = (c * 1 , c * 2 , c * 3 , c * 4
). Note that if w = z, then C * is not a valid ciphertext since it is only decrypted correctly when using the private key with tag t * .

Lemma 3.2 If there exists a PPT algorithm A such that Adv

Game Real A,E - Adv Game Final A,E
= , then we can build a PPT algorithm B with advantage in breaking the DBDH problem.

Proof. Suppose B is given a DBDH challenge (p, G, G T , e, g, g x , g y , g z , T ). We now describe how it interacts with A in the following game: Setup. B sets g 1 = g x (implicitly sets msk = x), g 2 = g y , picks a suitable extractor function ext, then gives A the public parameters mpk = (p, G, G T , e, g, g 1 , g 2 , ext).

Hash queries. For a fresh hash query on I, B picks a, t R ← -Z p and responds with u = g a g t 2 .

KeyGen queries. For an arbitrary identity I, B computes a private key for it as follows: (1) compute u = H(I); (2) set d 1 = t, d 2 = g a 1 = (ug -t

2 ) x = (g a g t 2 g -t 2 ) x ; (3) return sk = (d 1 , d 2 ). We note that the keygen queries are always implicitly called by B when it answers the associated leak queries and reveal queries. Phase 1. To answer the leak queries and reveal queries issued by A, B creates two lists L and K, which are initially empty. L is a list of triples of identities, private keys, and a leakage counter, while K is a list of tuples of identities, private keys.

-Leak(I, h i ) query: B checks if there is a tuple I, sk in the existing K list. If it is not B runs sk ← KeyGen(msk, I), inserts the tuple (I, sk) to the K list and the triple I, sk, 0 to the L list. After this step there must exists a triple I, sk, num in the L list, B checks if num + i ≤ . If this is true, it responds with h i (sk) and sets num ← num + i in I, sk, num . Otherwise B responds with a reject symbol ⊥.

-Reveal(I) query: B checks if there is a tuple I, sk in the K list. If it is B responds with sk. If it is not B runs sk ← KeyGen(msk, I), inserts the tuple I, sk to the K list and the triple I, sk, 0 to the L list, and responds the leak query with sk. Notice that B can calculate a valid private key for any identity. Therefore, B is able to answer all the leakage queries Leak(I, h i ) and reveal queries Reveal(I), with the corresponding private key sk = (d 1 , d 2 ). We will prove that the advantage of B in breaking the DBDH problem is . To see this, notice that if T = e(g, g) xyz the challenge ciphertext is a correct ciphertext according to the original encryption algorithm and thus A plays the Game Real . This is because W = e(g z , g a * 1 )T t * = e(g a * , g z 1 )e(g t * 2 , g z 1 ) = e(g a * g t * 2 , g z 1 ) = e(u * , g 1 ) z as one can easily verify. Thus the probability that A succeeds in the game is exactly 1 2 + Adv Game Real A,E

  and a cryptographic hash function H : {0, 1} * → G. Let g 1 = g x , = (κ) be an upper bound on the amount of leakage. Then set an average-case (log|G T | -, ext )-strong extractor function ext : G T × {0, 1} µ → {0, 1} n . The message space is M ∈ {0, 1} n , while mpk = (g, g 1 , g 2 ) and msk = x.KeyGen. For a given identity I, pick t R ← -Z p , compute u = H(I), and then generate the private key for I as sk = (d 1 , d 2 ) = (t, (ug -t 2 ) x ). Encrypt. To encrypt a message M under identity I, pick an exponent r R ← -Z p and a seed s R ← -{0, 1} µ for the extractor function, generate the ciphertext as C = (c 1 , c 2 , c 3 , c 4 ) = (g r , s, e(g 1 , g 2 ) r , M ⊕ ext(e(u, g 1 ) r , s)). Decrypt. To decrypt a ciphertext C = (c 1 , c 2 , c 3 , c 4 ) encrypted under I using the associated private key sk = (d 1 , d 2 ) to compute M = c 4 ⊕ ext(e(c 1 , d 2 )c d 1

2 ) 2 .

 22 Challenge. A submits two messages M 0 , M 1 and an identity I * on which it want to be challenged to B. B computes sk * = (d * 1 , d * 2 ) = (t * , g a * 1 ), then generates the challenge ciphertext as follows: W = e(c * 1 , d * 2 )(c * 3 ) d * 1 = e(g z , g a * 1 )T t * c * 4 = M β ⊕ ext(W, c * Phase The same as Phase 1. Guess. A outputs a guess β . B returns 0 if β = β or 1 if β = β .

. 2 +

 2 Since B outputs 0 when A succeeds we get that Pr[B(D, e(g, g) xyz ) = 0] = 1 Adv Game Real

Supported by National Natural Science Foundation of China (No.61073156).

On the other hand if T = e(g, g) xyw = c * 3 then A essentially plays the Game Final , because W = e(g z , g a * 1 )T t * = e(g a * , g z 1 )e(g t * 2 , g (w-z)+z 1

) = e(u * , g 1 ) z e(g 1 , g 2 ) t * (w-z) as one can easily verify. Therefore we have that

Combining the above equations we get that the advantage of

A,E

= . Therefore we prove the lemma.

Lemma 3.3 For any PPT adversary A we have Adv

Proof. In the Game Final , it is true that W = e(u * , g 1 ) z e(g 1 , g 2 ) t * (w-z) . where t * is the tag of the private key for I * . If we assume that the exact private key with tag t * is perfect hidden from the adversary, then W distributes uniformly at random in G T , and therefore the challenge ciphertext C * is totally independent of M β in an PPT adversary A's view. This is because w = z mod p with negligible probability in κ and t * is chosen randomly for I * . Suppose we denote by R the set of all terms (public parameters, private keys, challenge ciphertext) given to the adversary A except the leakage, the random seed c 2 ) from the uniform distribution is at most ext for each β. The statistical distance between the two possible ciphertexts is at most 2 ext and no adversary (even an unbounded one) can distinguish them with advantage more than this.

Suppose DBDH is the maximum advantage of all PPT adversaries in the DBDH game. Then according to the above lemma, for any PPT adversary A we have Adv

The proposed scheme is leakage-resilient CPA secure if both DBDH (κ) and ext (κ) are negligible functions of κ. This proves the theorem.


Florian Kerschbaum
email: florian.kerschbaum@sap.com

Public-Key Encrypted Bloom Filters with Applications to Supply Chain Integrity

Bloom filters provide a space-and time-efficient mean to check the inclusion of an element in a set. In some applications it is beneficial, if the set represented by the Bloom filter is only revealed to authorized parties. Particularly, operations data in supply chain management can be very sensitive and Bloom filters can be applied to supply chain integrity validation. Despite the protection of the represented set, Bloom filter operations, such as the verification of set inclusion, need to be still feasible. In this paper we present privacy-preserving, publicly verifiable Bloom filters which offer both: privacy for the represented set and public Bloom filter operations. We give security proofs in the standard model.

Introduction

Bloom filters provide a space-and time-efficient mean to check the inclusion of an element in a set in constant time. We apply them to supply chain integrity (see Section 2). Yet, they have many more applications in computer science, e.g. in databases [START_REF] Bellovin | Privacy-Enhanced Searches Using Encrypted Bloom Filters[END_REF][START_REF] Goh | Secure Indexes[END_REF] or networks [START_REF] Broder | Network Applications of Bloom Filters: A Survey[END_REF].

We consider situations where the confidentiality of the set represented by the Bloom filter is important. Given an unprotected Bloom filter anyone can check for the inclusion of an element and maybe even enumerate all included elements. In many scenarios this is an undesired property, e.g. when the Bloom filter is stored or used by untrusted service provider [START_REF] Bellovin | Privacy-Enhanced Searches Using Encrypted Bloom Filters[END_REF][START_REF] Goh | Secure Indexes[END_REF]. The content (i.e. its bit mask representing the contained set) of the Bloom filter should remain private. This is particularly true in supply chain integrity where there are risks of industrial espionage [START_REF] Eurich | The Impact of Perceived Privacy Risks on Organizations' Willingness to Share Item-Level Event Data Across the Supply Chain[END_REF][START_REF] Santos | RFID in the supply chain: panacea or pandora's box?[END_REF].

Our idea starts by encrypting the Bloom filter content. Regular encryption renders the Bloom filter content useless. We therefore use a special, carefully crafted form of encryption: public-key and (partially) homomorphic. Now, only the private-key holder can access the Bloom filter content, but in order for the encrypted Bloom filter to be useful we need to still enable regular operations on it despite the encryption.

First, we enable the public-key holder to add elements to the Bloom filter by encrypting them -without interaction. Second, we enable the public-key holder to verify the inclusion or exclusion of an element -also without interaction.

For these purposes we exploit the homomorphism of the encryption scheme to evaluate the Bloom filter operations and then employ zero-knowledge proofs (ZKP) [START_REF] Goldreich | Proofs that Yield Nothing but Their Validity or All Languages in NP have Zero-Knowledge Proof Systems[END_REF] for validating the result. Our ZKPs guarantee that the private-key holder cannot make false claims about the Bloom filter content, yet the publickey holder will learn nothing beyond the validity of the claims. We emphasize that our secured Bloom filter operations can still be computed and verified in constant time.

We propose to apply these Bloom filters to supply chain integrity. Several important supply chain integrity checks can be reduced to set in-or exclusion. Any participant in the supply chain -whether supplier or customer -can verify using our privacy-preserving Bloom filters set inclusion and thereby e.g. product authenticity. Most importantly, no such check will violate any supplier's desire for privacy.

In summary, our contributions are the adaptation of a public-key encryption scheme for Bloom filters non-interactive operations for element addition, element inclusion or exclusion verification and filter content comparison security proofs in the standard model The remainder of the paper is structured as follows. In the next section we present our example application of supply chain integrity and its security requirements. In Section 3 we present our building blocks of Bloom filters, public key encryption schemes and ZKPs. We describe our main result -a public-key encrypted Bloom filter -in Section 4. In Section 5 we review related work before we conclude the paper in Section 6.

Problem: Supply Chain Integrity

Supply chain integrity refers to the integrity of the flow of goods through a supply chain. This integrity can, e.g., be compromised by the introduction of counterfeit products or by the distribution of genuine products on gray markets. The sale of counterfeit products alone costs the United States an estimated 200 billion dollars annually [START_REF] Waldbaum | Using Creativity to Fight a $60 Billion Consumer Problem -Counterfeit Goods[END_REF].

Clearly, tracking of items and increased visibility of items throughout the supply chain help protecting supply chain integrity [START_REF] Sarma | Radio frequency identification and the electronic product code[END_REF]. Nevertheless, this tracking also implies a number of novel security and privacy risks [START_REF] Santos | RFID in the supply chain: panacea or pandora's box?[END_REF]. Given detailed information about one's supply chain operation one can infer strategic relationships, business volumes or planned promotions. Companies are therefore very reluctant to disclose this information despite its benefits [START_REF] Eurich | The Impact of Perceived Privacy Risks on Organizations' Willingness to Share Item-Level Event Data Across the Supply Chain[END_REF].

In this paper we present secure methods for checking supply chain integrity that disclose nothing but the validity of the integrity check. We assume a generic model for item-level tracking in supply chains [START_REF] Sarma | Radio frequency identification and the electronic product code[END_REF]. Each item is equipped with an unique identifier. Let I = {i 0 , . . . , i n } be the set of item identifiers. Also each supplier has an unique identifier. Let S = {s 0 , . . . , s m } be the set of supplier identifiers.

As an item i progresses through the supply chain it is handled by a number of different suppliers s. We can perform a number of simple, yet efficient checks on this process.

As a first application we can collect the set S i of suppliers that have handled an item i. We create a Bloom filter d that represents the set of suppliers and transport it along with the item. This transport can be electronic in an accompanying network message (advanced shipping notification) or even on the item, e.g. an RFID tag [START_REF] Finkenzeller | RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification[END_REF]. Before a supplier ships the item to another supplier it adds the new supplier to the Bloom filter.

Given this Bloom filter d we can perform two distinct checks. First, we can compare the set S i against a black list S bl of known violators. These violators can be e.g. companies dealing on grey markets.

∀s ∈ S bl .s / ∈ S i
Second, we can check the set S i against a white list S wl of mandatory suppliers. These suppliers can be e.g. the authentic manufacturers of the item.

∀s ∈ S wl .s ∈ S i

For the technical implementation we need to be able to check whether an element s is in a set S i . As already mentioned, Bloom filters offer a space-and time-efficient mean for this operation. We just need to protect the confidentiality of the represented set.

As a second application we can collect the set I s of items that a supplier s has handled. We again create a Bloom filter d, but maintain it at one supplier. Each time this supplier handles an item i it adds it to the Bloom filter.

This time we can perform another check. Given two Bloom filters d 1 and d 2 at two suppliers s 1 and s 2 , respectively, we can compare whether they encode the same set I. If they do, we are assured that there is no intermediate diversion of the flow of goods between the two suppliers.

I s1 = I s2
For the technical implementation we need to be able to compare Bloom filter contents. This may seem simple, but we encrypt the Bloom filter contents using IND-CPA secure encryption [START_REF] Katz | Introduction to Modern Cryptography: Principles and Protocols[END_REF], such that an equality comparison of the ciphertexts will fail.

Figure 1 exemplarily depicts these checks in a supply chain and how they capture illegitimate items. There are five suppliers s 1 to s 5 and three items i 1 to i 3 . Each item takes a different path through the supply chain. Supplier s 1 is on the white list, while supplier s 4 is on the black list. The final customer (or any participant of the supply chain) can perform the following exemplar checks: First, for authentic item i 1 it can check whether it has been handled by supplier s 1 : s 1 ∈ S 1 . Second, for authentic item i 2 it check whether it has not been handled by supplier s 4 : s 4 / ∈ S 2 . Third, it can compare the set I 1 of supplier s 1 to the set I 5 of supplier s 5 . While this check succeeds in our example, it would fail if supplier s 4 would have sold the item on the grey market (and thereby avoid the second check).

Security Desiderata

Given a Bloom filter d we require a number of security properties. We distinguish only two parties: an authority and a supplier. The authority controls the Bloom filter. Its help is needed to perform the operations described above. The authority can be the manufacturer of an item or even an independent organization, such as an industry association. The supplier can add elements to the set and verify the checks described above, i.e. the supplier participates in the supply chain by handling goods and verifying the integrity of the supply chain. Loosely speaking, the goal of our algorithms is to protect against malicious suppliers. Most importantly, we do not distinguish between malicious and honest suppliers. This commonly made distinction is difficult to perform in practice, since the reliability of a supplier can vary over time and is difficult to assess. We assume that all suppliers may be malicious and may perform all operations on the Bloom filter.

Furthermore we assume that an attacker has full control over the network. We model the supply chain as a directed graph with vertices representing suppliers and edges representing transportation links. Items pass through the supply chain and along with each item i a Bloom filter for its set of suppliers S i . Furthermore, each supplier s maintains a Bloom filter I s of all of its items. An attacker may read and write any Bloom filter at any point in the graph. Given this powerful type of attacker some attacks cannot be prevented: disruption and cloning. We limit our protection goals to privacy and unlinkability.

Disruption An attacker may simply destroy the Bloom filter and disrupt the communication. This cannot be prevented. Nevertheless, we can assume a de-fault decision. Items without proper security checks can be considered illegitimate. Then an attacker disrupting the supply chain cannot insert counterfeit items, but he can cause false positives resulting in a disruption of goods supply. Alternatively, items without proper security checks could be considered legitimate. This current practice prevents disruptions due to false positives, but the problem of counterfeits is prevalent.

Cloning An attacker may simply copy the information of one Bloom filter to another. This attack is called cloning and is a common problem for anticounterfeiting. There are no item-level (on-tag) countermeasures, but given a global data view, prevention is feasible [START_REF] Kerschbaum | Privacy-Preserving Pattern Matching for Anomaly Detection in RFID Anti-Counterfeiting[END_REF][START_REF] Lehtonen | How to Detect Cloned Tags in a Reliable Way from Incomplete RFID Traces[END_REF][START_REF] Oertel | Tracking based product authentication: Catching intruders in the supply chain[END_REF][START_REF] Zanetti | Privacy-preserving Clone Detection for RFID-enabled Supply Chains[END_REF]. We propose to augment both solutions, since our mechanism can protect against more supply chain integrity threats than just cloning.

Privacy The content of a Bloom filter (i.e. the represented set) should remain private. Given any Bloom filter d an attacker should not be able to tell whether an element e is in the set or not (except with negligible probability). Even given several successful checks of inclusion or exclusion for elements e i , an attacker should not be able to tell whether an element e (∀i.e = e i ) is in the set or not (except with a small probability of false positives). Furthermore, given several successful checks of equality or inequality of sets, an attacker should still not be able to tell.

Unlinkability An attacker should not be able to link a Bloom filter before and after the addition of an element. Given a pair of Bloom filters d 0 and d 1 , an element e and a randomly chosen Bloom filter d b ∈ {d 0 ∪ {e}, d 1 ∪ {e}} with the element e added, an attacker should not be able to tell the random choice b (except with negligible advantage). This prevents an attacker from tracing items through the supply chain. It augments our privacy requirement in preventing supply chain espionage.

Background

Bloom Filter

Bloom filters [START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] provide a space-and time-efficient mean to check the inclusion of an element in a set. An empty Bloom filter b consists of m bits, all set to 0, and k hash functions f i (0 ≤ i < k). We write b j (0 ≤ j < m) for the j-th bit of Bloom filter b. Bloom filters support the operations add(x) for addition of element x to the set and test(x) to test for inclusion of element x. Create(m): m bits (0 ≤ j < m) are set to 0 ∀j.b j = 0 and k hash functions

f i (0 ≤ i < k) are published ∀i.f i : {0, 1} * → {0, . . . , m -1} Add(x):
The element x is hashed with all k hash functions f i and the k bits at the resulting indices l i are set to 1.

∀i.l i = f i (x) ∧ b li = 1
T est(x): Again, the element x is hashed with all k hash functions f i and if all k bits at the resulting indices l i are set, then the test function returns true.

k-1 i=0 b fi(x)
Using Bloom filters false positive are possible, but false negatives are not. The more elements are added to the set, the more likely false positives are. Given the number n of elements to be added and a desired maximum false positive rate p, one can compute the necessary size m of the Bloom filter as [START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] m = -n ln p ln 2

Goldwasser Micali Encryption

Goldwasser-Micali (GM) encryption [START_REF] Goldwasser | Probabilistic Encryption[END_REF] is a public-key, semantically-secure (IND-CPA), homomorphic encryption scheme. Its plaintext length is only 1 bit. GM encryption uses quadratic residuosity modulo a composite of two large primes p and q. A quadratic residue r is a number, such that there exists a number s: s 2 = r mod n. GM encodes a 1 as a quadratic non-residue and a 0 as a quadratic residue. Particularly, the quadratic non-residues are pseudo quadratic residues, i.e. their Jacobi symbols are all 1. Note that differentiating pseudo quadratic residues and quadratic residues implies factoring.

Let n = pq be the composite of two large primes and v be pseudo quadratic residue. The public key is n, v and the private key is p and q. To encrypt a 0 one chooses a random number r and computes r 2 mod n (a quadratic residue).

To encrypt a 1 one also chooses a random number r and computes vr 2 mod n (a quadratic non-residue). To decrypt one computes whether it is a quadratic residue.

We can summarize the operations as follows KeyGen(κ): Let κ be a security parameter. Given κ generate the private key sk = {p, q} and the public key pk = {n = pq, v}. Encrypt(x, pk): Given plaintext x and public key pk produces ciphertext c. Decrypt(c, sk): Given ciphertext c and private key sk produces plaintext x.

Let E(x) denote encryption of x under GM public key pk. Multiplying two ciphertexts, e.g. E(x) • E(y), results in an encryption of the exclusive-or (XOR) denoted by ⊕.

E(x) • E(y) = E(x ⊕ y)
GM encryption is semantically-secure (IND-CPA) [START_REF] Katz | Introduction to Modern Cryptography: Principles and Protocols[END_REF], i.e. one cannot infer from a ciphertext and the public key whether the ciphertext has a specific plaintext, e.g. by encrypting the plaintext and then comparing it.

Sander Young Yung Technique

Sander, Young and Yung operate on GM encryptions and allow the computation of one logical AND operation [START_REF] Sander | Non-Interactive CryptoComputing For NC1[END_REF]. Recall that we can perform any number of logical XOR operations on the ciphertexts. A ciphertext E(x) is expanded as follows.

Expand(c, pk): Given ciphertext c = E(x) and public key pk compute σ i . We repeat this operation u times (0 ≤ i < u).

1. Flip a fresh random coin r i ∈ {0, 1} (i = 1, . . . , u).

2.

Choose plaintext e i according to the random coin and set

σ i ← E(e i ) = E(x) • E(1) = E(x ⊕ 1) if r i = 0 E(0) if r i = 1
The result is a u-length vector σ = (σ 1 , . . . , σ k ) which we call expanded ciphertext. If x = 1, then x ⊕ 1 = 0 and e i = 0. Then also σ i = E(0) for i = 1, . . . , u.

Otherwise, if x = 0, e i is randomly distributed in {0, 1} and σ i is a GM ciphertext of a random bit.

We can now compute a logical AND of two expanded ciphertexts σ (for E(x)) and ρ (for E(y)). We denote σ i = E(e i ) and ρ i = E(d i ). Logical AND is performed by pair-wise multiplication of the elements of the expanded ciphertext vectors:

τ i = σ i • ρ i . If x ∧ y = 1, then τ i = E(c i ) = E(e i ) • E(d i ) = E(e i ⊕ d i ) = E(0 ⊕ 0) = E(
0) for i = 1, . . . , u, but if x ∧ y = 0, then c i remains randomly distributed in {0, 1}, since at least one of e i or d i is randomly distributed in {0, 1}. Therefore τ is the expanded ciphertext of x ∧ y. In order to decrypt an expanded ciphertext σ one decrypts each element D(σ i ) = e i . If e i = 0 for i = 1, . . . , u, then the final plaintext x = 1; otherwise x = 0. There is a 2 -u probability that it is falsely decrypted as 1, since for an expanded ciphertext σ of x = 0 the plaintexts e i are randomly distributed in {0, 1} u .

Quadratic Residuosity Zero-Knowledge Proofs

A simple proof that a ciphertext has plaintext 0 is to present a root s (s 2 = r). It can be verified by squaring s and is zero-knowledge, since it does not reveal the secret key p and q. Furthermore, if r is a quadratic non-residue, no such s exists. Proof-QR(r):

Common input: r, n = pq Prover's secret input: p, q

1. The prover outputs s.

2. The verifier accepts, if s 2 = r.

Nevertheless, this proof cannot be used to prove that a ciphertext has plaintext 1. If the prover claims that there is no root s, there is no way for the verifier to check it. In [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF] Fiat and Shamir present a zero-knowledge proof (ZKP) that r is a quadratic residue. The proof is analogous to the general ZKP for graph isomorphism by Goldreich, Micali and Widgerson in [START_REF] Goldreich | Proofs that Yield Nothing but Their Validity or All Languages in NP have Zero-Knowledge Proof Systems[END_REF]. Furthermore in [START_REF] Goldreich | Proofs that Yield Nothing but Their Validity or All Languages in NP have Zero-Knowledge Proof Systems[END_REF] they present a ZKP for graph non-isomorphism. We adapt this proof to quadratic residues and present a ZKP that r is a quadratic non-residue. We present its interactive form. Proof-QNR(r):

Common input: r, n = pq Prover's secret input: p, q For a ZKP one has to prove three properties: (honest-verifier) zero-knowledge, completeness and soundness. Zero-knowledge means that the verifier learns nothing about the secret input of the prover. We can do so by showing a simulator of the verifier's view from its input (including random coin tosses) and output (of a successful proof). In this case, the simulator is particularly simple, since it simply mirrors the verifier's random choices b and s.

Completeness means that if r is indeed a quadratic non-residue an honest verifier will always accept. Clearly, if r is a quadratic non-residue then rs 2 is a quadratic non-residue, but s 2 is always a quadratic residue. Therefore the prover can distinguish the choice b by computing quadratic residuosity.

Soundness means that if r is not a quadratic non-residue, i.e. t 2 = r an honest verifier will reject with high probability. If b = 1 and t 2 = r, then there exist a s = st, such that s 2 = rs 2 . The message from the verifier is therefore indistinguishable to the prover for both cases of b. The probability of a right guess b is then at most 1 2 . In order to increase the probability for rejecting the ZKP in case of a quadratic residue we can repeat the above ZKP n times in parallel. The probability of a false accept is then 2 -n . Furthermore, we can apply the technique by Blum, Feldman and Micali to make the ZKP non-interactive [START_REF] Blum | Non-Interactive Zero-Knowledge and Its Applications[END_REF]. Given access to a common random string we can simulate the messages from the verifier. In our case it is critical to not simulate the random choices b, but just the messages themselves, i.e. the verifier sends a sequence of numbers u. We can non-interactively verify the correct guess of b by b using s . If the verifier sends a quadratic non-residue u (which he does with probability 1 2 ) and r is a quadratic residue (t 2 = r), then there exists no s , since ur -1 is quadratic non-residue.

Shuffle Zero-Knowledge Proof

In addition to the quadratic residuosity ZKPs we need a further ZKP. Let σ be a u-length vector of GM ciphertexts E(e i ). Let π be a random permutation for 1, . . . , u and ρ be a u-length vector of GM ciphertexts with plaintext 0. We can compute a shuffle τ = π(σ) • ρ, such that given σ and τ (but not the secret key) nothing is revealed about π.

A shuffle ZKP proves that τ is indeed a permutation of σ, i.e. there exist π and ρ. Proof-Shuffle(σ, τ ):

Common input: σ, τ Prover's secret input: π, ρ = (E(0), . . .), such that τ = π(σ) • ρ.

Groth and Ishai present a shuffle ZKP that has sub-linear communication complexity [START_REF] Groth | Sub-Linear Zero-Knowledge Argument for Correctness of a Shuffle[END_REF]. Sub-linear communication complexity means that less than u elements are transmitted.

Public-Key Encrypted Bloom Filter

In this section we present our main result: privacy-preserving, publicly verifiable Bloom filter. Due to our use of public-key encryption we call them publickey encrypted Bloom filter (PEBF). The basic idea of a PEBF is to encrypt each bit b j of the Bloom filter using GM encryption. We present its operations P EBF -Create(m, κ), P EBF -Add(x), P EBF -T est(x) and P EBF -Compare(E(b )). PEBF-Create(m, κ):

1. Create a public-, private-key pair in the GM encryption scheme using KeyGen(κ). We give our first theorem that the public part of the PEBF does not leak any information about the content of the Bloom filter.

Theorem 1 Let the adversary A choose two Bloom filter contents b 0 = (. . . , b 0,j , . . .) and b 1 = (. . . , b 1,j , . . .). Given a random choice β and the public part of a PEBF E(b β ), f i , pk, the probability that any adversary A outputs β is at most

P r [A (b 0 , b 1 , E (b β ) , f i , pk) = β] ≤ 1 2 + 1 poly(κ)
where poly(κ) is an arbitrary polynomial in κ.

Proof. The proof is simple. Such an adversary A would contradict the IND-CPA security of GM encryption. We can simulate a successful adversary against GM encryption by embedding the challenge into the challenge of the adversary A.

PEBF-Add(x):

1. Compute indices of Bloom filter for addition

l i ← f i (x)
2. Recompute each bit of the Bloom filter by replacing it with a plaintext 1 if it is set by the Add(x) operation and re-randomizing if it is not set

E(b j ) = E(1) if ∃i.j = l i E(b j ) • E(0) = E(b j ⊕ 0) otherwise
We can rest assured that the public part of the PEBF before and after an addition does not leak any information about the added item. In fact, this is a corollary of Theorem 1.

Corollary 2 Given two public parts E(b), f i , pk for the same PEBF, but for Bloom filter contents b 0 = (. . . , b 0,j , . . .) and b 1 = (. . . , b 1,j , . . .), such that there exist an index h where b 0,h = b 1,h , the probability that any adversary A outputs h is at most

P r [A (E (b 0 ) , E (b 1 ) , f i , pk) = h] ≤ 1 m + 1 poly(κ)
Proof. Construct an adversary A for Theorem 1 by handing both ciphertexts b 0 and b 1 to adversary A. If A guesses correctly, then A guesses correctly.

PEBF-Test(x):

Checking whether a PEBF contains an element x requires the private key sk. We construct a ZKP P EBF -T est true that x is contained within the public PEBF part E(b), f i , pk.

Common input: x, E(b), f i , pk Prover's secret input: sk Theorem 3 The zero-knowledge proof P EBF -T est true is honest-verifier zeroknowledge, complete and sound.

Proof. For honest-verifier zero-knowledge we need to show a simulator for the view of the verifier. The simulator computes steps 1 to 3. It then invokes u times the simulator for Proof-QR(s 2 ).

We emphasize that the proof reveals that σ i is a quadratic residue and (w.h.p.) that E(b li ) is a quadratic non-residue, but this is implied by the output of the ZKP.

For completeness we need to show that if test(x) = true, then P EBF -T est true is accepted by an honest verifier. If test(x) = true, then E(b li ) is a quadratic non-residue, σ li,j is a quadratic residue and consequently all σ j are quadratic residues.

For soundness we need to show that if test(x) = f alse, then P EBF -T est true will be reject by an honest verifier with high probability. If test(x) = f alse, then there exist an index h (0 ≤ h < k), such that l h = f h (x) and b l h = 0. Then σ l h ,j is (uniformly) randomly distributed in {E(0), E(1)} and so is σ j . Then at least one ZKP for quadratic residuosity will fail with probability 1 -2 -u .

In order to prove that an element x is not contained in a PEBF we need to prove that at least one index of σ has a quadratic non-residue. Unfortunately, knowing that σ j is a quadratic non-residue may imply (w.h.p.) that (one specific) b j = 0. Simply assume that the random choices in the Expand() operation, are such that the ciphertext of only one E(b j ) is used and the others are fixed to E(0).

We therefore need to construct a more complicated ZKP P EBF -T est f alse .

1. Perform steps 1 to 3 as in P EBF -T est true .

2. Choose a random permutation π of (1, ldots, u) and a u-length vector of ciphertexts ρ = (E(0), . . .). Compute

τ ← π(σ) • ρ 3.
Proof in zero-knowledge that τ is a shuffle of σ.

P roof -Shuf f le(σ, τ ) 4. Reveal an index h, such that τ h is a quadratic non-residue and prove it in zero-knowledge

P roof -QN R(τ h )
Theorem 4 The zero-knowledge proof P EBF -T est f alse is honest-verifier zeroknowledge, complete and sound.

Proof. The proof for the properties of completeness and soundness are analogous to the proof for P EBF -T est true .

For honest-verifier zero-knowledge we give the following simulator. Uniformly choose a random h. For τ choose a random permutation of the ciphertexts σ except for τ h choose one with plaintext 1 (a quadratic non-residue). Note that we might replace a quadratic residue at index h. Invoke the simulator for P roof -Shuf f le(σ, τ ). If the simulator fails, because we did replace a quadratic residue, then rewind and choose a new h. The choice of h will fall on a quadratic non-residue with probability 1 2 . Therefore we succeed with high probability. Then invoke the simulator for P roof -QN R(τ h ).

PEBF-Compare(E(b )): Let E(b ) be the encrypted Bloom filter content for the same hash functions f i . Using the secret key sk we construct a ZKP P EBF -Compare that b of the public part of a PEBF is equal.

Common input: E(b ), E(b), pk Prover's secret input: sk 1. Compute the negated, logical XOR of the two encrypted Bloom filter contents using the homomorphism of the encryption scheme

E(b ) ← E(b) • E(b ) • E(1 m ) = E(b ⊕ b ⊕ 1 m ) 2.
Expand the ciphertext for each Bloom filter bit (0 ≤ i < m)

σ i ← Expand(E(b i ), pk)
3. Compute the logical AND of Bloom filter bits using the homomorphism

σ ← σ 0 • . . . • σ m-1
4. Proof in zero-knowledge that σ j (0 ≤ j < u) is a quadratic residue P roof -QR(σ j )

Theorem 5 The zero-knowledge proof P EBF -Compare is honest-verifier zero-knowledge, complete and sound.

Proof. The proof for honest-verifier zero-knowledge is equal to the proof for honest-verifier zero-knowledge for P EBF -T est true . We can use the same simulator.

For completeness we need to show that if b = b , then P EBF -Compare is accepted by an honest verifier. If b = b , then b = 1 m and σ are all quadratic residues.

For soundness we need to show that if b = b , then P EBF -Compare will be reject by an honest verifier with high probability. If b = b , then b contains a 0 and σ contains a quadratic non-residue with probability 1 -2 -u . Consequently, at least one ZKP P roof -QR(σ j ) will be rejected with high probability.

The construction of a ZKP that b = b follows the same ideas as ZKP P EBF -T est f alse . We omit it for brevity.

Related Work

Our work is related to cryptographically secure Bloom filters [START_REF] Bellovin | Privacy-Enhanced Searches Using Encrypted Bloom Filters[END_REF][START_REF] Goh | Secure Indexes[END_REF][START_REF] Nojima | Cryptographically Secure Bloom-Filters[END_REF], private set intersection [6-8, 12, 19, 22] and anti-counterfeiting [START_REF] Blass | Tracker: Security and Privacy for RFIDbased Supply Chains[END_REF][START_REF] Kerschbaum | Privacy-Preserving Pattern Matching for Anomaly Detection in RFID Anti-Counterfeiting[END_REF][START_REF] Lehtonen | How to Detect Cloned Tags in a Reliable Way from Incomplete RFID Traces[END_REF][START_REF] Li | Protecting RFID Communications in Supply Chains[END_REF][START_REF] Oertel | Tracking based product authentication: Catching intruders in the supply chain[END_REF][START_REF] Ouafi | Pathchecker: an RFID Application for Tracing Products in Suply-Chains[END_REF][START_REF] Staake | Extending the EPC Network -The Potential of RFID in Anti-Counterfeiting[END_REF][START_REF] Zanetti | Privacy-preserving Clone Detection for RFID-enabled Supply Chains[END_REF].

Cryptographically protected Bloom filters have been proposed before [START_REF] Bellovin | Privacy-Enhanced Searches Using Encrypted Bloom Filters[END_REF][START_REF] Goh | Secure Indexes[END_REF][START_REF] Nojima | Cryptographically Secure Bloom-Filters[END_REF]. Nevertheless, the type of protection differs significantly from our approach.

In [START_REF] Bellovin | Privacy-Enhanced Searches Using Encrypted Bloom Filters[END_REF][START_REF] Goh | Secure Indexes[END_REF] Bloom filters are used for securely searching documents. It enables checking whether a document contains certain keywords without disclosing all of them. Their protection mechanism is to compute the hash function as a cryptographic pseudo-random function. This prevents reversing the Bloom filter, but it also prevents non-interactively adding an element which we enable.

In [START_REF] Nojima | Cryptographically Secure Bloom-Filters[END_REF] an interactive protocol for securely checking set inclusion via Bloom filters without disclosing the Bloom filter content or the checked element. They also do not enable non-interactive (or even privacy-preserving) element addition. They use blind signatures in order to protect the Bloom filter content.

A related problem is private set intersection. Given two parties, each input a set of elements, privately compute the intersection of these two sets without disclosing either set. The first protocol secure in the semi-honest model has been presented in [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF]. Efficiency improvements have been made in [START_REF] Freedman | Efficient Private Matching and Set Intersection[END_REF]. The malicious model has been first considered in [START_REF] Hazay | Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries[END_REF] and further efficiency improvements have been made in [START_REF] Dachman-Soled | Efficient Robust Private Set Intersection[END_REF][START_REF] De Cristofaro | Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model[END_REF]. An authority to certify the sets has been proposed in [START_REF] Camenisch | Private Intersection of Certified Sets[END_REF]. Note that -as opposed to all work on private set intersection -our operations work non-interactively. This also makes the distinction between semi-honest and malicious adversaries less applicable. Our security definitions are closer to publickey encryption.

The benefits of item tracking for anti-counterfeiting have been first recognized in [START_REF] Staake | Extending the EPC Network -The Potential of RFID in Anti-Counterfeiting[END_REF]. They already outline the two basic approaches beyond item identification itself: on-tag and in-network.

In-network protection collects information about all items and correlates it. It can prevent cloning attacks. A statistical method based on detection of low probability events is presented in [START_REF] Lehtonen | How to Detect Cloned Tags in a Reliable Way from Incomplete RFID Traces[END_REF]. This method requires sharing of information. A similar method that protects this information using secure multi-party computation has been presented in [START_REF] Zanetti | Privacy-preserving Clone Detection for RFID-enabled Supply Chains[END_REF]. A deterministic method for detecting integrity violations has been presented in [START_REF] Oertel | Tracking based product authentication: Catching intruders in the supply chain[END_REF]. It also requires sharing of information. A secure variant using cryptographic hashing has been presented in [START_REF] Kerschbaum | Privacy-Preserving Pattern Matching for Anomaly Detection in RFID Anti-Counterfeiting[END_REF].

On-tag protection only stores information on the RFID tag. Methods using more powerful RFID tags that support cryptographic hashing have been proposed first [START_REF] Li | Protecting RFID Communications in Supply Chains[END_REF][START_REF] Ouafi | Pathchecker: an RFID Application for Tracing Products in Suply-Chains[END_REF]. Recently, a method using only storage on the RFID tag has been described [START_REF] Blass | Tracker: Security and Privacy for RFIDbased Supply Chains[END_REF]. Our public-key encrypted Bloom filters (augmented with standard signatures) implement not only their full functionality, but surpass it in several aspects. First, we enable more checks than just path verification, such as our compare operation. Second, we provide security against the verifier of integrity considering an attacker that is part of the supply chain.

Conclusions

In this paper we have presented public-key encrypted Bloom filters. The content of the Bloom filter is encrypted using public-key, homomorphic encryption. Only the private-key holder can access the Bloom filter content. We enable the publickey holder to non-interactively add elements by encrypting them. Furthermore, we present zero-knowledge proofs for non-interactively verifying the inclusion or exclusion of an element and the equality of two Bloom filter contents.

Given such protected Bloom filters one can perform several privacy-preserving supply chain integrity checks. One can check the path of item through a supply chain against black lists, white lists or for equality. The public-key encryption protects the confidentiality of the Bloom filter content during all these operations.

There are a few possible improvements for future work. First, the set inclusion or exclusion zero-knowledge proofs reveal the element checked. This could be prevented by also encrypting it, but the homomorphism of existing (efficient) public-key encryption schemes is insufficient. When fully homomorphic encryption [START_REF] Gentry | Fully Homomorphic Encryption using Ideal Lattices[END_REF] becomes practical, it may provide a further avenue.

Second, the set inclusion or exclusion zero-knowledge proofs also require the knowledge of the ciphertext. Ideally the private-key holder could issue a security token without knowing the ciphertext in question. This could be done using searchable encryption, but the existing searchable encryption schemes do not support homomorphisms. Given improved, searchable encryption schemes, a new construction might become feasible.

Third, the bit-wise encryption of Goldwasser-Micali encryption is quite storageintensive. While RFID tags with sufficient storage capacity -up to 64 KByteexist [START_REF]Fujitsu Develops World's First 64KByte High-Capacity FRAM RFID Tag for Aviation Applications[END_REF], a reduction of the storage requirements would enable using cheaper RFID tags. Of course, this is no restriction for the collection of all handled items at one supplier.

Fig. 1 .

 1 Fig. 1. Example Supply Chain with Illegitimate Item

1 .

 1 The verifier uniformly chooses a random number s and a bit b ∈ {0, 1}. If b = 0, then the verifier sends s 2 to the prover. If b = 1, then the verifier sends rs 2 to the prover. 2. The prover outputs a guess b of b. The prover also sends a guess s of s. 3. The verifier accepts if b = b and s = s.

  pk, sk ← KeyGen(κ) 2. Create a Bloom filter b j , f i ← Create(m) 3. Encrypt each bit of the Bloom filter E(b j ) ← Encrypt(b j , pk) Let E(b) denote the element-wise encryption of b = (. . . , b j , . . .) with the public key pk. The public part of the PEBF is E(b), f i , pk and the private part is sk.

1 . 2 . 3 .Fig. 2 .Figure 2

 12322 Fig. 2. Public-Key Encrypted Bloom Filter and Ciphertext Expansion


Meixing Le

Krishna Kant
email: kkant@gmu.edu

Sushil Jajodia
email: jajodia@gmu.edu

Cooperative Data Access in Multi-cloud Environments

Keywords: Cloud, Rule Composition, Join Path

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With increasing popularity of virtualization, enterprises are deploying clouds to flexibly support the IT needs of their internal business units or departments while providing a degree of isolation between them. Enterprises may need to collaborate with one another in order to run their businesses. For example, an insurance company needs information from a hospital, and vice versa. Clouds remove the physical boundaries of enterprise data so that several enterprises can share the same underlying physical infrastructure. Physical location of the data is important when planning an optimal query plan with data cooperation among enterprises. However, in this work, it suffices to assume that each enterprise has access to a logically separate cloud. We assume that all data is stored in relational databases and accessed via relational queries. The enterprises disclose some information to others based on their collaboration requirements, but would like to avoid leakage of other information.

Similar data sharing scenarios arise in other contexts as well, including those between independently owned data centers and between the enterprise clouds and the underlying physical infrastructure. Figure 1 shows the latter situation more clearly where the enterprise clouds A and B run on top of the physical infrastructure I. Similarly, enterprise cloud C runs on top of a different physical infrastructure II. In this case, the enterprise clouds need to know suitable configuration information from the infrastructure providers and the providers may need to know the characteristics of the software deployed by the enterprise clouds. Given the standard CIM [START_REF]Common Information Model[END_REF] (common information model) based storage of configuration data, it may even be necessary to consider access to information that is obtained by combining the stored data in some way (much like joins in normal databases). Thus, the collaboration requirements among these entities can be similar to those in the context of multiple enterprises sharing data. If in Figure 1, enterprise A needs data from enterprise B to satisfy its business needs, A and B need to negotiate and establish policies regarding the accessibility of each other's data. This results in authorization rules for A and B to follow. With these authorization rules, A is able to answer some queries that require information from B but not others. If A also has authorization rules for cloud C, then A may be able to answer a query that requires some data from both B and C. In the first part of our work, we want to decide whether a given query against enterprise A is allowed according to all the authorization rules given to A.

In general, there are two ways of specifying the authorizations: explicit (as in reference [START_REF] Capitani Di Vimercati | Controlled Information Sharing in Collaborative Distributed Query Processing[END_REF]), and implicit. The explicit method is easier in that any queries that do not match any explicit authorization rule will not be answered. However, the number of rules could become large and cumbersome to manage. In the implicit approach, the enterprises are only given some basic rules, and are free to compose them and thereby access more information than the rules imply directly. The implicit method can be more concise, and is the focus of this paper. The main problem with implicit method is that there is no way to exclude certain compositions. We fill this gap by introducing deny policies as well.

Deny policies are needed for two reasons. The first reason is simply to avoid certain combinations and thereby achieve the same level of expressiveness as the explicit authorizations. The second reason is that an enterprise may be able to do compositions locally after having obtained the desired data from other enterprises, but such compositions may not be intended.

In this paper, we also present an algorithm to verify whether a deny rule will be violated by the authorization rules. In other words, we check the conflict between allow rules and deny rules. In some cases, the deny rules may still be difficult to enforce with existing parties. In such case, the conflicts found by our algorithm can be used to alert the data owners to change their authorizations or policies in order to remove the conflicts. On the other hand, if it is possible to implement deny rules using a third-party, then they should be given higher priority over the allow rules. Of course, if a deny rule does not conflict with the allow rules, it has no effect and can be ignored. Thus our consistency checking algorithm can be used to reduce the number of deny rules.

The main purpose of this paper is to come up with efficient algorithms for query permission and conflict checking. This paper does not address the next step of actually formulating a query plan as well as the problem of implementing and enforcing all the rules, which will be explored in a subsequent paper.

The outline of the rest of the paper is as follows. Section 2 discusses the related work. Section 3 presents the concepts related to join group and composable rules, and the intuition behind our approach. For checking whether a query originating from a cloud can be authorized, we propose a new two-step algorithm which first selects all the related given rules, and then tries to compose these rules to determine authorization of the query. This is discussed in Section 4. In section 5, we present an algorithm for checking whether the deny rules are consistent with the given authorization rules. Finally, in section 6 we conclude the discussion and outline future work.

Related Work

De Capitani di Vimercati, Foresti and Jajodia [START_REF] Capitani Di Vimercati | Controlled Information Sharing in Collaborative Distributed Query Processing[END_REF] studied the problem of authorization enforcement for data release among collaborating data owners in a distributed computation so as to make sure the query processing discloses only data that has been explicitly authorized. They proposed an efficient and expressive form of authorization rules which define on the join path of relations and they also devise an algorithm to check if a query with given query plan tree can be authorized using the explicit authorization rules. In our work, we follow the format of authorization rules they proposed. However, it is possible that these explicit authorization rules given to the same enterprise can be composed together to implicitly allow more information to be released through queries.

In another work [START_REF] Capitani Di Vimercati | Assessing query privileges via safe and efficient permission composition[END_REF], the same authors evaluate whether the information release the query entails is allowed by all the authorization rules given to a particular user, which is similar to the problem of query permission checking in our work. Their solution uses the graph model to find all the possible compositions of the given rules, and checks the query against all the given allow rules. In our work, the rules are given to different clouds instead of users, and we propose a more efficient algorithm to filter more unrelated rules first. Moreover, we deal with deny policies also.

Processing distributed queries under protection requirements has been studied in [START_REF] Cali | Querying data under access limitations[END_REF][START_REF] Florescu | Query optimization in the presence of limited access patterns[END_REF][START_REF] Li | Computing complete answers to queries in the presence of limited access patterns[END_REF]. In these works, each relation/view is constrained by an access pattern, and their goals are to identify the classes of queries that a given set of access patterns can support. These works with access patterns only considers two subjects, the owner of the data and a single user accessing it, whereas the authorization model considered in this work involves independent parties who may cooperate in the execution of a query. There are also classical works on the query processing in centralized and distributed systems [START_REF] Bernstein | Query processing in a system for distributed databases (SDD-1)[END_REF][START_REF] Aho | The theory of joins in relational databases[END_REF][START_REF] Kossmann | The state of the art in distributed query processing[END_REF], but they do not deal with constraints from the data owners. Superficially, the problem of checking queries against allow and deny rules is similar to checking packets against firewall allow and deny rules [START_REF] Gouda | Firewall Design: Consistency, Completeness, and Compactness[END_REF]. However, firewall rules are usually explicit, and one rule can contain another rule but not compose with another rule.

There are several services such as Sovereign joins [START_REF] Agrawal | Sovereign joins[END_REF] to enforce the authorization rule model we used, such a service gets encrypted relations from the participating data providers, and sends the encrypted results to the recipients. Also, there are some research works [START_REF] Aggarwal | Two can keep a secret: A distributed architecture for secure database services[END_REF][START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF][START_REF] Sion | Query execution assurance for outsourced databases[END_REF] about how to secure the data for out-sourced database services. These methods are also useful for enforcing the authorization rules in our work, and their primary purpose is to provide mechanisms for information sharing among untrusted parties.

Composing Rules for Query Checking

In order to check if a query is admissible according to the authorization rules, one naive idea is to generate all the possible compositions of the given basic rules, so as to convert each implicit rule into explicit one, and then check the query permission. The problem is that the compositions may generate too many rules, which make the approach very expensive.

Instead of generating all possible compositions, we organize the rules based on join attributes, and then use a two-step algorithm to check whether a given query can be authorized. In the first step, we filter as many rules as possible according to the given query. In the second step, we compose these rules based on their join attributes.

In this section we build up the machinery to enable this checking. In order to illustrate the various concept and models, we start with an e-commerce example that we will use throughout the paper. The example has the following schema:

1. Order (order id, customer id, item, quantity) as O 2. Customer (customer id, name, creditcard no, address) as C 3. Inventory (item, retail price, date) as I 4. Warehouse (location, item, supplier id, stock) as W 5. Supplier (supplier id, supplier name, cost price) as S 6. Shipping (location, customer id, days, ship cost) as Sp

The underlined attributes indicate the primary keys of the relations. We assume that relations Order and Customer are stored at Cloud A, and other relations are on the other clouds. The authorization rules for Cloud A are given below. The first two rules define access to local relations, and the following rules define remote access cooperated with other clouds. Each authorization rule has an attribute set, and is defined on one relation or a join path; the rule is also applied to a specified cloud.

1. (order id,customer id,item,quantity),(Order) → Cloud A 2. (customer id,name,creditcard no,address),(Customer) → Cloud A 3. (item,supplier id,supplier name), (Warehouse, Supplier) → Cloud A 4. (item,order id,retail price), (Order, Inventory) → Cloud A 5. (location,supplier id,retail price,stock), (Warehouse, Inventory) → Cloud A 6. (location,item,customer id,ship cost), (Shipping, Warehouse) → Cloud A 7. (ship cost,stock, cost price), (Shipping, Warehouse, Supplier) → Cloud A For simplicity, we assume identical attributes in different relations have the same name, and queries are in simple Select-From-Where form. In addition, relations satisfy the Boyce-Codd Normal Form (BCNF), and possible joins among the relations are all lossless joins. Also, we assume there is no collusion between clouds to bypass access limitations.

To illustrate query authorization, we shall consider two specific queries:

1. Select name, address, ship cost, retail price From Customer as C, Shipping as Sp, Warehouse as W, Inventory as I Where C.customer id = Sp.customer id and Sp.location = W.location and W.item = I.item

Select supplier name, stock

From Supplier as S, Warehouse as W, Inventory as I Where S.supplier id = W.supplier id and W.item = I.item and cost price>'100'

Basic Concepts

In order to perform efficient authorization checking, we group relations according to their join capability. For this we define a Join Group as a set of relations that share the same set of attributes and any subset of them can be joined based on that attribute set. A relation can appear in several Join Groups. A Join Group is identified by the set of attributes that its relations can join over, and we call this as Joinable Attribute Set (JAS) for the group. In our example, relations Shipping, W arehouse are in the same Join Group, and attribute set {location} is the JAS of this group. Other JASes among these relations are: customer id, supplier id, item. In order to address information release by joining two or more relations, we define the notation of Join Path.

Definition 1 (Join Path) Given a set of relations T 1 , T 2 ...T n , a Join Path < T 1 , T 2 ...T n > is an ordered chain of these relations, where each pair of relations < T i , T i+1 > are joined with each other on the JAS.

Each query itself has an associated Join Path called Query Join Path. In contrast, join path associated with a rule is called Rule Join Path. For instance, the Query Join Path of Query 1 is < C, Sp, W, I >, and Rule 7 is defined on the join path < Sp, W, S >. For each rule, the Join Path defines a view, and the attribute set further refines the view. Therefore, a rule for a cloud defines a view that this cloud can access. Similar to relations, views (rules) can also be joined together. By joining two views, the resulting view is defined over a longer join path. Next, we define the concept of Sub-Path relationships between two join paths, which is useful for determining the relevant rules for checking the authorization. Given two join paths A and B, whether A is a Sub-Path of B cannot be determined by a simple linear matching of Join Paths. It is because the order of the relations may be interchanged in a join path, and JASes in the join path also need to be compared. Determining Sub-Path relationship is an important step to figure out the composable rules as we shall show later in Theorem 1. However, a rule defined on a Sub-Path of the Query Join Path is not necessarily a composable rule of the query. Hence, we also look at the attributes that can be used to compose rules in the given query. We call the JAS in a Query Join Path as Query JAS . Each Query JAS is also associated with the relation pair that join over it. For example, in query 2, the Query JASes are: supplier id(S, W ), item(W, I). As rules can be composed using join operations, we define the concept of Composable rule below.

Definition 3 (Composable rule) An authorization rule is a composable rule, if the attribute set of the rule contains at least one JAS.

According to the definition, only Rule 7 in our example is not a composable rule because its attribute set does not contain any of the four JASes. Similarly, with a given query, we define Query Composable rule as an authorization rule whose Join Path is defined on a Sub-Path of the Query Join Path and attribute set contains one Query JAS. For illustration, Rules 2, 5, 6 are the Query composable rules for query 1 since Rule 2 contains customer id and Rule 5 and 6 contain location. As join operations can occur in rules, the concept of Join Groups can also be applied to rules instead of basic relations. Within each Join Group of rules, there are the rules whose attribute sets contain a common JAS.

Definition 4 (Join Group List) Each entry in a Join Group List is a Join Group of composable rules. There is a unique JAS to identify each entry and within the entry there are composable rules whose attribute sets contain this JAS.

It is clear that one rule may appear in multiple entries. The Join Group List can be generated with the given rules, and an example of Join Group List can be found in section 5.3.Query Join Group List is a Join Group List based on the given query. For each entry in such list, it is identified by a Query JAS, and within each entry are the Query composable rules whose attribute set contains this Query JAS. Only rules in the Query Join Group List are the relevant rules that will be considered in the composition step. In section 4.2 we show the Query Join Group Lists of queries in our example.

Rule Composition Rationale

Our mechanism first checks if a single rule can authorize the query. If not, we compose the relevant rules to see whether the given query can be authorized. All the rules within the same entry of the Query Join Group List can be composed together since they are all composable on that Query JAS. Therefore, rules within one entry can be composed into one single composed rule with longer join path and larger attribute set. If one rule appears in two or more entries of the list, it indicates that this rule can be used to connect these Join Groups so that the composed rules from these entries can be further composed.

Such a composition is also transitive. If a rule r a appears in entries of JAS 1 and JAS 2 and a rule r b appears in entries of JAS 2 and JAS 3 , then all the rules within these 3 entries can be composed into one rule. It is because r a and r b share JAS 2 , these two rules can be composed by joining on JAS 2 , and their connected entries can be further composed. Therefore, we group the entries in the Query Join Group List based on their connectivity. All the rules within a connected entry group can be composed into one rule. This procedure produces one or more maximally composed rules such that no further composition is possible. If there is more than one such composed rule, at most one of them can be defined on the Query Join Path. This follows from the fact that if two composed rules are defined on the same join path, then they can be further composed together. In addition, since the Query composable rules are all defined on the Sub-Path of the Query Join Path, composition of the rules will not have a join path longer than Query Join Path. Therefore, we only need to check the composed rule which includes the greatest number of relations (longest join path). If this rule is defined on the same join path as the query join path, then we check whether the attribute set of the composed rule is a superset of the attribute set in the query. The query can be authorized if and only if this is the case.

Theorems and Proofs

In this section, we prove a number of assertions regarding the rule composition and query checking which are useful in formulating the checking algorithm and proving their correctness.

Theorem 1 All authorization rules that are not defined on a Sub-Path of query Join Path are not useful in the rule composition.

Proof. Assume a query q has a Join Path of < T 1 , T 2 ...T n >. A rule r not defined on a Sub-Path of the Query Join Path will have two possibilities by definition. 1) The Join Path of r includes at least one relation T m which is not in the set of {T 1 , T 2 ...T n }. 2) The Join Path of r is defined on the set of relations which is a subset of {T 1 , T 2 ...T n }, but join over different JASes. The composed rule that can authorize the query must have the same Join Path as Query Join Path. Otherwise, the query results will have incorrect tuples because the underlining views are joined differently, and such a case also means the query is not authorized. Thus, if an authorization rule r has T m in its Join Path, then any composed rule using this rule will also have T m in its Join Path which is different from Query Join Path. For the second case, such a rule generates a different view, and any composed rule containing this rule also have a Join Path different from Query Join Path. Therefore, both types of rules need not be included to compose a rule that will authorize the query.

Theorem 2 Only Query Composable rules are useful in the rule composition.

Proof. A rule that is not a Query composable rule can have two possibilities: 1) it is not defined on a Sub-Path of Query Join Path. Theorem 1 indicates these rules are not useful. 2) the rule is defined on a Sub-Path of query Join Path, but the attribute set of the rule does not contain any Query JAS. To compose a rule with others to authorize the query, it must join with other rules on Query JAS. Otherwise, either it cannot compose with any other rule, or the composed rule has a join path different from Query Join Path. Therefore, only the Query composable rules should be included for rule composition step.

Theorem 3 The composition step can cover all the possible ways to authorize the query.

Proof. From Theorem 2, we know that any composition including non-Query Composable rules will not authorize the query. Then the composition step looks for only possible compositions among Query Composable rules. According to the connectivity among the entries, if two rules are in two disconnected entries, then they cannot be composed into one rule. On the other hand, for rules within the connected entries, we compose them into a maximally composed authorization rule. Such a rule maybe more than enough to authorize the query, but the Join Path of the rule can be at most the same as the Query Join Path. From above two observations, all the possible compositions that may authorize the query are included in these composed rules from separate connected entry groups. Finally, only one composed rule that has the same join path as the Query Join Path can authorize the rule, and there is at most one such composed rule.

Verifying Query Admissibility

Our two-step algorithm first builds up the Query Join Group list, and then uses composition step to construct rules that can possibly authorize the query.

Algorithm For Checking Query Permission

In the first step, the algorithm examines all the given rules and builds the Query Join Group List as discussed above. Each Query composable rule is put into the entries based on its Query JAS. If one rule appears in multiple entries, these entries are connected. Also, each entry is augmented with the relations which are accessible from the rules in this entry. At the end of this step, the algorithm maintains the connected entry group with the greatest number of relations.

In the second step, the algorithm can compose rules efficiently with Query Join Group List. The algorithm only examines all the entries within the connected group that holds the largest number of relations (can be multiple), and entries with only one rule are also ignored. The rules within each connected entry group are composed into one rule as discussed above. As the algorithm examines the groups with most relations, if these composed rules cannot authorize the query, then the query is not authorized.

We assume the complexity of the basic operation that checks whether a given rule r can authorize the query q is C, and there are N given rules, and the query q is defined on a Join Path of m relations. In the algorithm, step one has the worst case complexity of O(N * C * m). It is because the complexity of Sub-Path determination is lower than that of checking the query authorization; both of them need to compare the Join Paths and attribute set. If all the rules pass the Sub-Path checks, then the algorithm compares each rule with the m -1 Query JASes to decide which entries to put in. None of the rest operations is more expensive than C. Similarly, in step two, at most m entries and N rules are checked, and composing the rules is not expensive than C also, thus, the complexity of step two is O(N * C). Therefore, the overall complexity of the algorithm is O(N * C * m). Considering the fact that most join paths in practice involves less than 4 or 5 relations, the number of m is expected to be very small in most cases. Therefore, in average cases, we can expect the complexity of the algorithm close to O(N * C).

Algorithm 1 Query Permission Checking Algorithm

Require: Set of authorization rules, the query q Ensure: Query can be authorized or not STEP ONE: 1: for each authorization rule r do 2:

if r authorizes q then 3:

q is authorized 4:

return true 5:

else if Sub-Path(r, q) then 6:

for each Query JAS in q do 7:

if r is composable on this JAS then 8:

Add r into the entry of this JAS in Query Join Group List 9:

Connect this entry with previous entry that r also appears 10:

Update the relation set associated with this entry 11: for each unvisited entry in Query Join Group List do 12:

Follow the link to the connected entries 13:

Update the relation set associated with each entries in the same group 14: Keep the largest connected entry groups with most relations STEP TWO: 15: Construct an empty rule rc 16: for each largest connected groups do 17:

Begin from one entry in the group 18:

Follow the link to the connected entries 19:

Compose the rules in entry with the existing composed rule rc 20:

Generate a composed rule rc 21:

if rc authorizes q then 22:

q is authorized 23:

return true 24: q is denied 25: return false

Illustration with The Running Example

We begin with query 1. In the first step, the algorithm examines all the rules. As no single rule is defined on the Query Join Path, none of the given rule can authorize this query. Based on the definitions, rules 1, 3, 4, 7 are not defined on the Sub-Path of the Query Join Path, so that they are not useful to authorize the query. The Query Join Group List is:

1. customer id (C, Sp) → {Rule 2, Rule 6}. 2. location (Sp, W) → {Rule 5, Rule 6}. 3. item (W, I) → {Rule 6}.
Since Rule 6 appears in all three entries, these three entries form the only connected entry group in this list. Then in second step of the algorithm, the entry item is ignored since there is only one rule in the group, and Rule 6 is composed with Rule 2 by joining on Query JAS customer id which further composes with Rule 5 by joining on Query JAS location. Thus, the composed rule is "(customer id, name, creditcard no, item, address, retail price, stock, ship cost, location), (Customer, Shipping, W arehouse, Inventory) → Cloud A". This composed rule is defined on the Query Join Path of query 1, and the attribute set contains all the attributes required in query 1. Therefore, the query is authorized.

Query 2 has Query Join Path < S, W, I >, attribute set {supplier name, stock, cost price}, and Query JASes are {supplier id (S,W ), item (W ,I)}. Here, attribute cost price appears in Where clause is put into the attribute set, since the query needs the authorization on that attribute to do the select operation. As no single rule can authorize the query, the algorithm builds the Query Join Group List during the first step. Rules 1, 2, 4, 6, 7 are filtered as their Join Paths are not Sub-Paths of Query Join Path. The Query Join Group List is:

1. supplier id (S, W)→ {Rule 3, Rule 5}. 2. item (W, I) → {Rule 3}.

Then the algorithm ignores entry item, and composes the Rule 3, 5 by joining on Query JAS supplier id. The resulting composed rule is "(item, supplier name, supplier id, retail price, stock), (Supplier, W arehouse, Inventory) → Cloud A". Since attribute cost price is not in the attribute set of the composed rule, this query cannot be authorized.

Checking Consistency with Deny Policies

In addition to the authorization rules to allow access, cloud owners usually have deny rules to make sure that certain combinations of attributes are not accessible so that the information contained in such a relationship will not be released. We want to check using all the given authorization rules whether there exists any possible authorized query that violates the deny rules. For example, we can have a deny rule as below:

1. (Inventory.item, Inventory.retail price, Supplier.cost price) → Cloud A This rule means the Cloud A does not allow to get these three attributes from two tables at the same time (in one tuple), however the appearance of two of the attributes at the same time is allowed. Unlike the authorization rule, deny rules are not defined on join paths because such a rule is more restrictive than the one defined on a join path from the perspective of deny. Without join path, a deny rule prohibits any composition result that make the attribute set appear together no matter which join path is used. Since they are not defined on join paths so that they cannot be composed, and we always check them one at a time. To make sure a deny rule is not violated, all the possible join paths and rule compositions that will allow the attribute set need to be checked. To do so, one naive idea is to generate all the possible authorization rules and check if any one of them violates the given deny rules. Again, this is highly inefficient and we need a better algorithm.

Join Group List Approach

If the attributes within one deny rule are not explicitly allowed by an authorization rule, then the only possible way to violate it is the composition of the given authorization rules. We use the Join Group List to check the possible rule compositions that may violate the deny rules. Unlike query authorization considered earlier, the rule composition here is not constrained by the Query Join Path, and any composition of the rules that may violate the deny rule should be considered. Similar to the above algorithm, rules in a connected entry group of the Join Group List can be composed into one rule. Beginning with one basic rule and following all the connected entries, we can get a maximally composed rule including that basic rule.

To test whether a given deny rule is violated, we begin with the deny rule by randomly pick an attribute from the rule. We can randomly pick the first attribute because that for the attributes in a deny rule to appear together in one tuple, there must exist a composed or given rule to include all these attributes. After picking the first attribute, we choose all the basic rules that include this attribute. It is because any composed rule that violates the deny rule must be composed with at least one of such rules. We then compose the rules much like that for the query authorization one. In addition, there is no need to generate the real composed rule, as we are only concerned with the attribute set of the composed rule. This can be achieved by taking the union of the attribute set from all the connected Join Group List entries.

Deny Rule Verification Algorithm

The deny rule verification algorithm first generates the Join Group List with given rule, and then composes rules to check violation. The first step of the algorithm can be treated as a pre-computation step since once the authorization rules are given, the list can be generated. According to the definition, by examining the authorization rules with each JAS, putting the rules in the corresponding entries, and creating the connections among the entries, the list is generated. In the second step, the algorithm goes through all the rules containing the randomly picked attribute and tries to compose maximum possible rules to violate the rule. If and only if one of such rule is found, the deny rule is violated. Algorithm 2 is the detail description of Deny Rule Verification procedure.

Algorithm 2 Deny Rule Verification Algorithm

Require: Set of authorization rules, the deny rule d, the JAS set Ensure: Deny rule can be violated or not STEP ONE(Join Group List Generation): 1: for each authorization rule r do 2:

for each JAS do 3:

if JAS ⊆ Attribute set of r then 4:

Add r into the entry of this JAS in Join Group List 5:

Connect this entry with previous entry that r also appears STEP TWO(Verification): 6: Pick one attribute A from deny rule d 7: Create an empty attribute set U A 8: for each rule r includes attribute A do 9:

if r is in Join Group List and not visited then 10:

Get the attribute set from the rules in the entry that includes r 11:

Follow the links among the entries to get all connected entries 12:

Union all the attributes from the rules in these entries, get set U A In order to examine its complexity, suppose that there are N given rules, and there are m possible JASes among them, and the cost of checking whether an attribute is included in a set is C. Then the complexity of step one is O(N * C * m). If the largest number of rules in each entry in the list is t, and basic operation cost for getting the attribute set from a rule is C, the worst complexity of step two is O(N * C * t). It is because in step two, at most N rules are examined, and for each entry, at most t rules are checked. Therefore, the overall complexity depends on the number of given rules and the relationships among them. On the other hand, since such verification can be done offline with all given authorization rules and deny rules, complexity is not a big concern here.

Illustration of Deny Rule Checking

Based on the definition in section 3, the Join Group List of our running example including all the relations is: For the verification, the algorithm randomly picks one attribute, let us say retail price.

Since retail price appears in Rule 4 and Rule 5, the algorithm only needs to begin with these two rules. Starting with Rule 4, the algorithm first gets the attribute set of the rules within entry item, and then examines the connected entry group including entry item. Since entries location and customer id connect to item with Rule 6, and entry supplier id connects entry location with Rule 5, all the entries in this list are connected. Therefore, Rule 5 does not need to be checked again. Figure 4 depicts how the rules 1 to 6 are composed together with JASes to obtain the attribute set. The resulting composed rule will have the attribute set which is the union of the attribute sets from rule 1 to 6. Because this set is not a superset of {item, retail price, cost price}, the deny rule cannot be violated.

Conclusions and Future Work

In this paper, we examined the problem of cooperative data access in multicloud environments. Given the authorization rules for allow policies, using the join properties among the given rules, we presented an efficient algorithm to decide whether a given query can be authorized. In addition, we proposed an algorithm to check whether the given authorization rules are consistent with the deny rules that the enterprises may have specified to ensure that sensitive data is not released.

As stated earlier, we do not consider the generation of actual query plans in this paper. Generating a query plan may require the help of a trusted third-party in order to do the required join operations without violating the authorizations and deny rules. The query plan generation also involves performance considerations, which, in a multi-cloud environment would require consideration of location of data. The implementation of authorization checks may need to be done at all the parties that contribute data to the query before the query execution can begin. The query execution itself must decide what operations are done where in order to avoid any unauthorized leakage of information.

It may be possible to formulate the query authorization problem formally with first-order logic so as to use traditional SAT based techniques; however, the feasibility and complexity of this approach remain to be investigated.

Fig. 1 .

 1 Fig. 1. Cooperative data access in cloud environment.

Definition 2 (

 2 Sub-Path Relationship) A Join Path A is a Sub-Path of another Join Path B if: 1) The set of relations in Join Path A is a subset of the relation set of Join Path B.2) For each join pair < T i , T i+1 > joins on a JAS henceforth denoted as JAS i , and < T i , T i+1 > also appears in Join Path B and joined on JAS i .

3. 2

 2 Graph Model to Determine Sub-Path Relationship Here, we use a graph model to determine the Sub-Path relationships. We present Join Path via a labeled graph. G =< V, E >, where each node v ∈ V represents a relation in the Join Path, and each labeled edge e ∈ E connects two nodes if the two relations form a join pair in the Join Path, and the label indicates the JAS. The graph model applies to both queries and the authorization rules. To determine whether an authorization rule is defined on a Sub-Path of a query is equivalent to checking whether graph G(r) of a rule r is a sub graph of query graph G(q).

Fig. 2 .

 2 Fig. 2. Rules defined on the Sub-Paths of Query Join Path of Query 1 in example.

Fig. 3 .

 3 Fig. 3. Rules defined on the Sub-Paths of Query Join Path of Query 2 in example.

Figure 2

 2 Figure2shows the query 1 in our example, and the rules in the boxes are the ones defined on the Sub-Path of the Query Join Path. Figure3does the same

  Figure2shows the query 1 in our example, and the rules in the boxes are the ones defined on the Sub-Path of the Query Join Path. Figure3does the same

1 .Fig. 4 .

 14 Fig. 4. Composition of the rules 1 to 6.

This material is based upon work supported by the National Science Foundation under grants CCF-1037987 and CT-20013A. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsoring organizations.