Xuan Thanh Do

Duong Hieu Phan
email: duong-hieu.phan@unilim.fr

David Pointcheval
email: david.pointcheval@ens.fr

Traceable Inner Product Functional Encryption

Keywords: Functional Encryption, IPFE, Traceability

Functional Encryption (FE) has been widely studied in the last decade, as it provides a very useful tool for restricted access to sensitive data: from a ciphertext, it allows specific users to learn a function of the underlying plaintext. In practice, many users may be interested in the same function on the data, say the mean value of the inputs, for example. The conventional definition of FE associates each function to a secret decryption functional key and therefore all the users get the same secret key for the same function. This induces an important problem: if one of these users (called a traitor ) leaks or sells the decryption functional key to be included in a pirate decryption tool, then there is no way to trace back its identity. Our objective is to solve this issue by introducing a new primitive, called Traceable Functional Encryption: the functional decryption key will not only be specific to a function, but to a user too, in such a way that if some users collude to produce a pirate decoder that successfully evaluates a function on the plaintext, from the ciphertext only, one can trace back at least one of them. We propose a concrete solution for Inner Product Functional Encryption (IPFE). We first remark that the ElGamal-based IPFE from Abdalla et. al. in PKC '15 shares many similarities with the Boneh-Franklin traitor tracing from CRYPTO '99. Then, we can combine these two schemes in a very efficient way, with the help of pairings, to obtain a Traceable IPFE with black-box confirmation.

Introduction

Public Key Encryption (PKE) enables people to securely communicate and share sensitive data to others over public channels. Functional Encryption (FE) [SW05, BSW11], proposed by Boneh, Sahai and Waters, overcomes some limitations of PKE. It allows recipients to recover encrypted data in a more fine grained manner. Instead of revealing all-or-nothing of the original encrypted data as in PKE, recipients can get the evaluation of (statistical) functions on the data. As the function can contain an access control that checks some relation between the identity in the functional decryption key and the authorized identity in the plaintext, this primitive generalizes Identity Based Encryption (IBE) and Attribute Based Encryption (ABE), and actually received a large interest from the community. However, there is still no efficient construction of functional encryption for general functions. Currently, there are only simple and effective constructions for linear and quadratic functions [ABDP15, ALS16, BCFG17].

In many practical applications, it is common that people only care about several specific functions on the data, for example the mean value of the data. Allowing many people to get access to the same function, with possible malicious users, has not been really covered by the previous works: the functional decryption key is derived from the function and the master secret key, but independently of the user. Therefore, all the users are given the same key, and if this key is leaked, no one can identify the origin of the leakage. The tracing problem becomes critical for this situation. We define a new primitive, called Traceable Functional Encryption (TFE).

Traitor tracing is a mechanism enabling an authority or an arbitrary party (who is a delegated party in the system to perform tracing tasks) can identify malicious users (traitors) who possibly colluded to produce a pirate decoder that behaves the same as a normal decryption. The very first traitor tracing scheme has been introduced by Chor, Fiat and Naor [CFN94] and made use of combinatorial tools. The first algebraic traitor tracing scheme has been introduced by Boneh and Franklin [BF99], and is the basis for many subsequent schemes. A large number of Our Technique. We exploit the similarities between the Boneh and Franklin's traitor tracing scheme [BF99] and the Abdalla et. al.'s IPFE scheme [ABDP15] to integrate the Boneh-Franklin tracing technique into the IPFE scheme of Abdalla et. al. [ABDP15] which allows in particular to personalize functional decryption keys. Interestingly, our method of personalizing keys and adding traceability does not need a huge extra cost as it is usually required for others primitives such as broadcast encryption.

We first informally recall the main ingredients of the IPFE of Abdalla et. al. [ABDP15], that encrypts a plaintext vector y = (y 1 , . . . , y k ) as follows: the master secret key MSK = s = (s 1 , . . . , s k ) and the public key PK = G, h i = g s i i∈ [k] respectively allow to generate functional decryption keys and ciphertexts:

sk x = s, x = i∈[k] s i • x i , CT y = g r , h r i • g y i i∈[k] .
Here, we are working in a cyclic G of prime order q, with a generator g. The master secret key MSK is a vector s with components s i are taken from Z q . The public key PK consists of k group elements h i . The vector x = (x 1 , . . . , x k ) with components x i is taken from Z q is used to extract a functional decryption key sk x . A ciphertext, which is generated for a plaintext y, denoted by CT y . The Decrypt algorithm computes

i∈[k] h r i • g y i x i × g r -skx = g s,x r • g x,y g s,x r = g x,y
and gets x, y , which is supposed to be relatively small, to allow the computation of the discrete logarithm.

For the mean value, the vector x is (1, . . . , 1). If many users are interested in the mean value then they all get the same functional decryption key sk x and there will be no way to trace the source of the leakage if this secret key is used somewhere. In order to personalize functional decryption keys for each vector x, we have got inspired from the seminal technique of Boneh-Franklin: we associate to each user a representation of g s,x in the basis of b i = g t i i∈[k] , with t i is taken from Z q . Therefore, by adding b r i in the ciphertext, each user can compute g s,x r as above and the decryption works in the same manner. Concretely, each user ID is associated to a public codeword θ ID = (θ 1 , . . . , θ k ) and then, the personal secret key will be simply set to: tk x,ID = s, x / t, θ ID . The master secret key MSK consists of two vectors s = (s 1 , . . . , s k ) and

t = (t 1 , . . . , t k ). The public key PK = G, b i = g t i i∈[k] , h i = g s i i∈[k] . For each plaintext y, the ciphertext is CT y = b r i i∈[k] , h r i • g y i i∈[k] . The Decrypt algorithm then outputs i∈[k] h r i • g y i x i × i∈[k] b r i -tk x,ID θ i = g s,x r • g x,y g s,x r = g x,y .
The use of pairings. The above technique of personalizing secret keys seems to work well as in the Boneh-Franklin traitor tracing. However, there exists an issue specific to the setting of the functional encryption, that goes beyond the framework of Boneh-Franklin traitor tracing. Suppose that we are considering a scheme for two users with identities ID 1 and ID 2 . The first user queries the secret keys corresponding to vectors x 1 and x 2 and gets tk

x 1 ,ID 1 = s,x 1 t,θ ID 1 and tk x 2 ,ID 1 = s,x 2 t,θ ID 1
. The second user only queries secret key to vector x 1 and gets tk x 1 ,ID 2 = s,x 1 t,θ ID 2

. From these three secret keys tk x 1 ,ID 1 , tk x 2 ,ID 1 and tk x 1 ,ID 2 , it is possible to compute the secret key

tk x 2 ,ID 2 = tk x 2 ,ID 1 •tk x 1 ,ID 2 tk x 1 ,ID 1
for the vector x 2 and identity ID 2 . To avoid this attack, we will put the scalar t x,ID in the exponent sk x,ID = g tk x,ID and the decryption will then be performed in the target group of the pairing. The goal of the rest of the paper is to prove this modification actually leads to a secure scheme.

Enhancing the security of IPFE. It is worth noticing that, by putting the secret key in the exponent, we may enhance the security of the functional encryption. In the Abdalla et. al.'s scheme [ABDP15], whenever the adversary queries more than k secret keys, it can get the whole MSK by solving a system of linear equations. In our scheme, there is no way, unless breaking discrete logarithm, to get this master key as it is only put in the exponent. We will though not exploit further this advantage in this work, as we will focus on traceability.

Tracing algorithm. We rely on the classical linear tracing technique but we will adapt this technique into the functional encryption setting and with the strongest notion of pirate, namely pirate distinguisher introduced in [GKW18].

Organization. In Section 2, we will recall some classical assumptions (DDH and BDDH), required for the security of our constructions. In Section 3, we introduce a new concept: Traceable functional encryption (TFE). We then define security game of TFE against adaptively-chosen plaintext attacks and security game of the Tracing algorithm. A concrete TFE construction for inner product will be presented in Section 4. We will prove that our construction achieves selective security. Section 5 will be intended to present a tracing algorithm which achieves one-target security as stated in Theorem 13. The black-box confirmation property of the Tracing algorithm will be proven in the Lemma 11 and 12.

Preliminaries

We denote [k] the set of integers between 1 and k. Given two vectors x = (x 1 , . . . , x k ) and y = (y 1 , . . . , y k ), where x i , y i ∈ Z q for all i ∈ [k], we define x, y = k i=1 x i y i . Next we recall classical assumptions as follows.

Definition 1 (Decisional Diffie-Hellman Assumption). Given a cyclic group G = g of prime order q, the Decision Diffie Hellman (DDH) problem consists in distinguishing the following distributions

D 0 = {(g a , g b , g ab ) | a, b $ ← Z q } D 1 = {(g a , g b , g c ) | a, b, c $ ← Z q }.
The distribution D 0 consists of Diffie-Hellman tuples whereas D 1 consists of random tuples. Roughly speaking, the DDH problem consists in distinguishing DH tuples from random tuples.

The DDH assumption states that the two above distributions D 0 and D 1 are indistinguishable.

Let G 1 , G 2 , G T be multiplicatively written groups of prime order q, and let g 1 , g 2 be generators of G 1 , G 2 , respectively. We write 1 T to denote the unit element of G T . Let e : G 1 × G 2 → G T be a function sending two elements from G 1 and G 2 into the group G T . We say that the tuple (G 1 , G 2 , G T , q, e) is an asymmetric bilinear group if the following properties hold:

-Bilinearity: for all

h 1 ∈ G 1 , h 2 ∈ G 2 and a, b ∈ Z * q , we have e(h a 1 , h b 2 ) = e(h 1 , h 2 ) ab . -Non-degeneracy: e(g 1 , g 2 ) = 1 T .
-The function e can be efficiently computed.

Definition 2 (Bilinear Decisional Diffie-Hellman Assumption). Given an asymmetric bilinear group (G 1 , G 2 , G T , q, e), the Bilinear Decisional Diffie-Hellman (BDDH) problem consists in distinguishing the following distributions, for generators g 1 and g 2

D 0 = g a 1 , g b 1 , g a 2 , g c 2 , e (g 1 , g 2 ) abc |a, b, c $ ← Z q D 1 = g a 1 , g b 1 , g a 2 , g c 2 , e (g 1 , g 2 ) z |a, b, c, z $ ← Z q .
The BDDH assumption states that no PPT adversary can distinguish D 0 and D 1 with non negligible advantage.

Lemma 3 (Two-tailed Chernoff Bound). Let X 1 , X 2 , . . . , X n be independent Poisson trials (yes/no experiments) with success probabilities p 1 , p 2 , . . . , p n . Let X = n i=1 X i and µ = n i=1 p i . For 0 < δ < 1, we have

Pr[|X -µ| ≥ δµ] ≤ 2e -µδ 2 /3 .

Traceable Functional Encryption

We begin by describing the syntactic definition of traceable functional encryption (TFE) for circuits. A functionality (circuit) F ∈ F λ describes the function of a plaintext that can be derived from the ciphertext. More precisely, a functionality is defined as follows.

Definition 4. Let Y = {Y λ } λ∈N and S = {S λ } λ∈N denote ensembles where each Y λ and S λ is a finite set. Let F = {F λ } λ∈N denotes an ensemble where each F λ is a finite collection of circuits, and each circuit F ∈ F λ takes as input a message y ∈ Y λ and outputs F (y) ∈ S λ . Definition 5. A traceable functional encryption scheme T -FE for an ensemble F consists of five algorithms (Setup, Extract, Encrypt, Decrypt, Tracing) defined as follows:

Setup(1 λ ): Takes as input a security parameter λ and outputs a master key pair (PK, MSK). Extract(ID, MSK, F ): Given an identity ID of a user, a circuit F ∈ F λ and the master secret key MSK, this algorithm outputs an individual functional secret key sk F,ID . Encrypt(PK, y): Takes as input the public key PK and a message y ∈ Y λ , this randomized algorithm outputs a ciphertext CT. Decrypt(PK, sk F,ID , CT): Given the public key PK, a secret key sk F,ID and a ciphertext CT, this algorithm outputs F (y) ∈ S λ , if CT encrypts y, or an invalid symbol ⊥. Tracing D F (MSK, F, µ(.), y 0 , y 1 ): The tracing algorithm takes as input the master secret key MSK, a circuit F ∈ F λ , two messages y 0 , y 1 ∈ Y λ which are obtained from D F and a function µ(.) representing the probability that the decoder can distinguish between the ciphertexts of y 0 and of y 1 . The algorithm interacts with a confiscated pirate decoder D F , as a black-box, and outputs an identity or an invalid symbol ⊥.

For correctness, we require that for all (PK, MSK)

← Setup(1 λ ), all y ∈ Y λ , each F ∈ F λ and all identities ID, sk F,ID ← Extract(ID, MSK, F ), if CT ← Encrypt(PK, y), then one should get Decrypt(PK, sk F,ID , CT) = F (y)
, with overwhelming probability.

Requirement on the pirate decoder

-The classical requirement is that the pirate decoder D F is a device that is able to decrypt successfully any normal ciphertext generated by the Encrypt algorithm with high probability. Yet, in another approach, the tracer is only able to interact with D F through an oracle O D F by sending a message-ciphertext pair (tracing signal) to O D F and gets a response that is a bit indicating whether D F can successfully decrypt the ciphertext into the provided message (evaluated with the function F ). We say that the tracing algorithm is executing in minimal access black-box mode.

O D F (CT, y) = 1 if D F (CT) = F (y) 0 otherwise.
-We consider the same setting for the pirate as in [GKW18]: of course, this is not required the pirate decoder D F to output entire message (or an indicator bit as in minimal access model) nor to decrypt with high probability every ciphertexts which are taken from random messages. Instead, it is enough that the pirate decoder can distinguish the encryption of two messages y 0 , y 1 which are chosen by itself (see [GKW18]): Adapted from [GKW18], we define a µ-useful Pirate Distinguisher D F associated to a unique function F as below

Pr       D F (CT b ) = b : (MSK, PK) ← Setup(•) {sk F,i ← Extract(i, MSK, F )} i∈[n] (D F , y 0 , y 1 ) ← A(PK, {sk F,i } i∈[t] ) st. F (y 0 ) = F (y 1 ) b $ ← {0, 1}, CT b ← Encrypt(PK, y b )       - 1 2 ≥ µ(λ),
where the function µ(•) is a non-negligible function in λ. This very strong notion of Pirate Distinguisher has been introduced in [GKW18]. It requires the pirate distinguisher to be able to distinguish the encryption of two different messages y 0 , y 1 . To adapt to the functional encryption, as the goal of the pirate is to compute the function on the message, we require that the pirate distinguisher be able to distinguish the encryption of y 0 , y 1 such that F (y 0 ) = F (y 1 ).

As shown in [GKW18], this notion is stronger than the classical Pirate Decoder which is able to correctly decrypt random messages with non-negligible probability. When considering the case of functional encryption, a pirate decoder for a function F is useful if it can compute F (y) from the encryption of y, for a random message y. Clearly, pirate distinguisher is also stronger than pirate decoder in this case. Indeed, one can build a distinguisher D F from a decoder Dec F : randomly choose y 0 , y 1 such that F (y 0 ) = F (y 1 ), then when receiving the challenge ciphertext CT, call Dec F and check whether this is F (y 0 ) or F (y 1 ) to output the correct guess, if this is none of them, output a random guess. In this work, we will deal with this notion of pirate distinguisher which is actually the strongest notion (i.e., minimal requirement) about the usefulness of pirate decoders.

Security: Indistinguishability. We consider the IND security game between an adversary A and a challenger B as follows: Definition 6. A traceable functional encryption scheme T -FE for an ensemble F, T -FE = (Setup, Extract, Encrypt, Decrypt, Tracing) is semantically secure under chosen-plaintext attacks (or IND-CPA security) if no PPT adversary has non-negligible advantage in the following game:

-The challenger B runs (PK, MSK) ← Setup(1 λ ) and the public key PK is given to the adversary A. -The adversary adaptively makes secret key queries to the challenger. That is, the adversary A chooses some pairs of identities ID and functions F ∈ F λ . A sends them to B and then obtains sk F,ID ← Extract(ID, MSK, F ) from B. -The adversary A chooses distinct messages y 0 , y 1 ∈ Y λ such that F (y 0 ) = F (y 1 ) for all F already asked. This restriction is required in all functional encryption to avoid trivial attacks. Whenever B receives the messages, it randomly picks β $ ← {0, 1} and then transfers to A a ciphertext CT β = Encrypt(PK, y β ).

-Adversary A continues making further decryption key queries for other pairs of identities ID and functions F , and receives sk F,ID from B. Again, it is also required that F (y 0 ) = F (y 1 ) to avoid trivial attacks. -Adversary A eventually returns a guess β for a bit β and wins if β = β.

A weaker version has been defined, when the messages y 0 , y 1 for the challenge ciphertext are chosen before the Setup algorithm started, then the T -FE scheme is said selectively-security against chosen-plaintext attacks, which is denoted by sel-IND-CPA.

Traceability. The security game between the attacker A and the challenger B takes place as follows:

1. The challenger B runs (PK, MSK) ← Setup(1 λ ) and the public key PK sent to the adversary A. B also creates a table T to store pairs of identities of users who queried keys and functions F , for all F ∈ F λ . It means that the table T stores (ID, F ). Initially T is set empty. 2. The adversary adaptively makes secret key queries to the challenger. Concretely, the adversary A chooses some pairs of identities ID and functions F ∈ F λ to query functional secret keys.

The challenger B stores all these pairs in the table T and replies with the secret keys sk F,ID for those pairs. 3. The adversary A outputs (F * , D F * ) and two messages y 0 , y 1 , where D F * is a pirate distinguisher for the function F * . 4. After receiving the messages y 0 , y 1 from A, the challenger B runs the algorithm Tracing D F * (MSK, F * , 1 µ , y 0 , y 1 ) and outputs an identity ID * .

We say that the adversary A wins the game if the output of Tracing is either an invalid symbol ID * = ⊥ or the identity ID * did not ask for F * : (ID * , F * ) ∈ T . When the adversary A is allowed to ask secret keys for the only target function F * (but for any ID), and so for (ID, F * ), the security of Tracing algorithm will then be called one-target security.

As explained in the introduction, this one-target security also covers the case where the adversary outputs any function F such that the target function F * is computable from F with public information. In such a case, when the pirate outputs the function F and the decoder D F (together with two messages), one can define a decoder D F * that calls D F and then applies the computation of F * from F on the output, then do tracing on this D F * , applying also the public transformation to the messages.

Our Inner-Product Functional Encryption

We will describe concretely a traceable functional encryption for inner product scheme (T -FE) for n users. Let G be a bilinear group of large prime of order q. Additionally, let e : G 1 ×G 2 → G T denote a bilinear map, where G 1 , G 2 and G T are cyclic groups of order q, written multiplicatively.

Setup(1 λ , 1 k ): This algorithm generates a bilinear setting G = (G 1 , G 2 , G T , q, e) for sufficiently large prime order q and g 1 , g 2 respectively are generators of the groups G 1 and G 2 . The bilinear map e over G 1 , G 2 can be calculated efficiently.

-

Randomly choose t 1 , . . . , t k $ ← Z q , set t = (t 1 , . . . , t k ) and b 1 = g t 1 1 , . . . , b k = g t k 1 . -For each i ∈ {1, . . . , k}, randomly choose s i $ ← Z q . We set s = (s 1 , . . . , s k ) and set G = e(g 1 , g 2 ) ∈ G T and H i = G s i ∈ G T for all i = 1, . . . , k.
-We consider a linear code Γ over the alphabet Z q with n codewords Γ = {θ 1 , . . . , θ n }, corresponding to n users in our system. Each codeword has the length k.

-The public key is PK = G, Γ, g 1 , g 2 , G, H 1 , . . . , H k , b 1 , . . . , b k .
-The master secret key is MSK = {s, t}. Extract(ID, MSK, x): Takes as input an identity ID, the master secret key MSK and a characteristic vector x = (x 1 , . . . , x k ) ∈ Z k q . Choose a (new) vector (codeword)

θ ID = (θ 1 , . . . , θ k ) ∈ Γ. A secret key is an element g tk x,ID 2 ∈ G 2 such that tk x,ID • θ ID is a representation of g s,x 1 in the basis of (b 1 , b 2 , . . . , b k ). That is g s,x 1 = k i=1 b tk x,ID θ i i = b tk x,ID θ 1 1 • • • b tk x,ID θ k k
. Concretely, set tk x,ID = s, x t, θ ID and define sk x,ID = g tk x,ID 2 for θ ID .

Encrypt(PK, y): Takes as input the public key PK and a message y = (y 1 , . . . , y k ) ∈ Z k q . To encrypt y, sample r $ ← Z q and compute

CT = (H r 1 G y 1 , . . . , H r k G y k , b r 1 , . . . , b r k ).
Decrypt(PK, sk x,ID , CT): Takes as input the public key PK, the secret key sk x,ID = g tk x,ID 2 for θ ID = (θ 1 , . . . , θ k ) and a ciphertext CT, the algorithm computes

E = H r 1 G y 1 x 1 • • • H r k G y k x k e b r 1 θ 1 • • • b r k θ k , g tk x,ID 2 .
Finally, it returns the discrete logarithm of E in basis G = e(g 1 , g 2 ).

Correctness: For all (PK, MSK) ← Setup(1 λ , 1 k ), all y ∈ Z k q and x ∈ Z k p , for sk x,ID = (g tk x,ID 2 , θ ID ) ← Extract(ID, MSK, x) and CT ← Encrypt(PK, y), we have that

H r 1 G y 1 x 1 • • • H r k G y k x k e b r 1 θ 1 • • • b r k θ k , g tk x,ID 2 = G x,y • G x 1 s 1 +•••+x k s k r e g t 1 rθ 1 1 • • • g t k rθ k 1 , g s,x t,θ ID 2 = G x,y • G r s,x
e(g 1 , g 2 ) r s,x G x,y = e(g 1 , g 2 ) x,y .

Theorem 7. The above T -FE achieves the selective security (sel-IND-CPA) under the BDDH assumption

Proof. We assume that there exists an adversary A can distinguish distributions of ciphertexts in the real game with non-negligible advantage. We build a simulator B that solves the BDDH problem. It means that B takes as input a tuple g a 1 , g b 1 , g a 2 , g c 2 , T ∈ G 2 1 × G 2 2 × G T , it must decide whether the input is BDDH tuple where T = e (g 1 , g 2 ) abc or random tuple where T = e (g 1 , g 2 ) z . We set

D 0 = g a 1 , g b 1 , g a 2 , g c 2 , e (g 1 , g 2 ) abc |a, b, c $ ← Z q D 1 = g a 1 , g b 1 , g a 2 , g c 2 , e (g 1 , g 2 ) z |a, b, c, z $ ← Z q .
The algorithm B progresses as follows:

-Firstly, B is provided two distinct messages y 0 and y 1 .

-B chooses Γ = {θ 1 , . . . , θ n } is a linear code of size n and length k, as well as t 1 , . . . , t k $ ← Z q . Set t = (t 1 , . . . , t k ) and b i = g t i 1 , for i = 1 to k. -B finds a (k -1)-basis of subspace (y 0 -y 1 ) ⊥ because the adversary A can only ask secret keys for vectors x in (y 0 -y 1 ) ⊥ . We denote this basis by (z 1 , . . . , z k-1 ).

For i = 1, . . . , k -1, B randomly chooses u i $ ← Z q .
-We consider the canonical basis (e 1 , . . . , e k ) of Z k q . A linear transformation from basis (z 1 , . . . , z k-1 , (y 0 -y 1 )) to (e 1 , . . . , e k ) is given by: e i = α i (y 0 -y 1 ) + k-1 j=1 λ i,j z j , where the coefficients α i , λ i,j can be found efficiently by B. Note that e i , y 0 -y 1 = α i ×||y 0 -y 1 || 2 . Then α = i α i e i = 1/||y 0 -y 1 || 2 × i e i , y 0 -y 1 e i = 1/||y 0 -y 1 || 2 × (y 0 -y 1 ).

-From the challenge tuple, and random scalars u 1 , . . . , u k-1

$ ← Z q , set G = e(g 1 , g c 2 )
and

H i = e (g a 1 ) α i • g k-1 j=1 u j λ i,j 1 , g c 2 = e(g 1 , g c 2 ) aα i + k-1 j=1 u j λ i,j = G aα i + k-1 j=1 u j λ i,j
for i = 1, . . . , k, which implicitly defines

s i = aα i + k-1 j=1 u j λ i,j . The public key is set to PK = G, Γ, g 1 , g 2 , H 1 , . . . , H k , b 1 , . . . , b k .
-For any vector x = (x 1 , . . . , x k ) ∈ (y 0 -y 1 ) ⊥ , B computes κ x = s, x = k-1 j=1 k i=1 x i u j λ i,j and, for identities ID, sk x,ID = g tk x,ID 2

, where tk x,ID = κ x t, θ ID . It sends the value g tk x,ID 2 to A.

Vector θ ID is a codeword in Γ. -The challenger randomly picks β $ ← {0, 1} and, from the challenge tuple where T is the last element in G T , gives A a ciphertext CT = (ct 1 , . . . , ct 2k ), where

ct j = T α j • e g b 1 k-i i=1 u i λ j,i , g c 2 • G y β,j and ct j+k = g b 1 t j , for j = 1, . . . , k.
-At the end, the adversary outputs his guess β for β. If β = β then B returns 1 for "BDDH tuple". Otherwise returns 0 for "random tuple". We will show that B can break BDDH assumption. To do so, we need to prove that the difference below is negligible

Pr[B(D 0 ) = 1] -Pr[B(D 1 ) = 1] = Pr[β = β | T = e (g 1 , g 2 ) abc ] -Pr[β = β | T = e (g 1 , g 2 ) z ] .
We find that:

1. When T = e (g 1 , g 2 ) abc then we have

ct j = T α j • e g b 1 k-1 i=1 u i λ j,i , g c 2 • G y β,j = H b j G y β,j , for j = 1, . . . , k. Therefore CT = H b 1 G y β,1 , . . . , H b k G y β,k , b b 1 , . . . , b b k .
It implies that B perfectly simulates the real game. Since A can break the semantic security with non-negligible probability, we have Pr[β = β | T = e (g 1 , g 2 ) abc ] = Adv(A) + 1/2. 2. When T = e(g 1 , g 2 ) z = G v is random element, the challenger will send A the ciphertext of message y β + vα = y β + v/||y 0 -y 1 || 2 × (y 0 -y 1 ) = µy 0 + (1 -µ)y 1 , for some random µ ∈ Z q . This makes β perfectly unpredictable:

Pr[β = β | T = e (g 1 , g 2 ) z ] = 1/2.
We conclude the advantage is non-negligible as

Pr[β = β | T = e (g 1 , g 2 ) abc ] -Pr[β = β | T = e (g 1 , g 2 ) z ] = Adv(A) + 1 2 - 1 2 = Adv(A).

Black-Box Confirmation Traitor-Tracing

This section will be devoted to present a black-box confirmation traitor-tracing algorithm. The purpose of this algorithm is to verify sets of secret keys which are suspected by a Tracer. The tracing algorithm takes as input the master secret key MSK and it can access the table T (see the Tracing security game) to take a set of secret keys for which it wants to check its suspicion. We will use the scalar form tk x,ID of the secret keys instead of the group element form sk x,ID . But as we only consider possible legitimate secrete keys in this form, the scalars are known to the authority.

Notations

Suppose that Tracer is provided a set of t secret keys (for the suspected traitors), say K suspect = {tk 1 , . . . , tk t } which are derived from a fixed vector x = (x 1 , . . . , x k ). Here, we have slightly abused the notation, as we are in the one-target security. When the vector x is explicit, we use the notation {tk 1 , . . . , tk t } instead of {tk x,1 , . . . , tk x,t }, the pirate decoder D x is replaced by D and we use integers to represent identities of users. A codeword will be θ i which is attached to a user with identity i. The goal of the Tracer is to verify whether there is any traitor in K suspect .

Before go further we need to define some notations.

-Set K i = {tk 1 , . . . , tk i } ⊆ K suspect , for all i ∈ [t] and K 0 = ∅.

-We define spaces of tracing signals (ciphertexts) Tr 0 , Tr 1 , . . . , Tr t such that each signal from Tr i can be decrypted successfully by any secret key in K i . More concretely, for each i from 0 to t, the tracing signal for a message y = (y 1 , . . . , y k ) is taken from the distribution Tr x i (y) (or Tr i (y) for simplicity, when x is explicit) that is defined as follows

H a 1 G y 1 , . . . , H a k G y k , g z 1 1 , . . . , g z k 1 a $ ← Z q , z $ ← Z k q , z, tk j θ j = a s, x , ∀j ∈ [i]
,

where z = (z 1 , . . . , z k ). G, H 1 , . . . , H k are group elements of G T and belong to the public key PK. Set Q(a) = e(g 1 , g 2 ) a s,x , as s and x are fixed. -Every user j with secret key in K i can output the same

(H a 1 G y 1 ) x 1 • • • (H a k G y k ) x k e(g z,θ j 1 , g tk j 2 ) = P(y, a) Q(a)
,

where P(y, a) = (H a 1 G y 1 ) x 1 • • • (H a k G y k ) x k = Q(a) × G y,x .
-Define distribution of normal ciphertext for a message y = (y 1 , . . . , y k ), denoted Norm(y):

randomly draw r $ ← Z q and output ciphertext (H r 1 G y 1 , . . . , H r k G y k , b r 1 , . . . , b r k ). -For i = 0, . . . , t, we set p i = Pr[D(CT) = b | b $ ← {0, 1}, CT ← Tr i (y b )]
, where y 0 , y 1 are chosen by D. When i = 0, in Tr i (y b ), a and z are perfectly independent, and so under the DDH assumption, the H a i hides the y b,i . So we have p 0 = 1/2 + negl(λ). Definition 8. A tracing traitor algorithm is black-box confirmation if it satisfies:

1. Confirmation: If suspected set of users actually contains the entire set of traitors then output of Tracing algorithm always returns at least an identity i such that tk i ∈ K suspect is guilty. Formally, with the condition K D ⊆ K suspect , the Tracing algorithm returns at least an identity i such that the secret key tk i ∈ K suspect as guilty. We denote by K D a set of secret keys used to build the pirate decoder D. 2. Soundness: The honest users will never be accused if the Tracing algorithm outputs an identity as guilty; it is impossible for traitors to deceive Tracing algorithm to blame innocent users. Said differently if Tracing algorithm outputs an identity i such that tk i is guilty then

tk i ∈ K D .

Tracing Algorithm

Tracing algorithm needs to use following lemmas.

Lemma 9. Under the DDH assumption in G 1 , no adversary corruping t users 1, . . . , t can distinguish the distribution of tracing signals Tr t (y) with the distribution of normal ciphertexts Norm(y), for any adversarially chosen y.

Proof. Suppose that an adversary A can distinguish the distribution of tracing signals Tr t (y) with the distribution of normal ciphertexts Norm. We will build a simulator B breaks the DDH assumption in G 1 . The simulator has inputs: 4-tuples (g 1 , g 2 , u 1 , u 2 ) ∈ G 4 1 , where g 2 = g c 1 and c is unknown. It decides whether this is a DDH tuple or a random tuple:

1. Take randomly t codewords θ 1 , . . . , θ t from the code Γ. 2. Take randomly A from Z q such that g A 1 g 2 = 1. 3. Take randomly a = (a 1 , . . . , a k ), e = (e 1 , . . . , e k ) $ ← Z k q such that θ i , a -Ae = 0, for all i = 1, . . . , t.

Set b

i = g a i 1 g e i 2
, for all i = 1, . . . , k. 5. Take randomly α = (α 1 , . . . , α k ) $ ← Z k q such that α, a -Ae = 0. Take randomly g 2 $ ← G 2 and it sets g 1 = g A 1 g 2 , G = e(g 1 , g 2 ). We set

H i = e(u A 1 u 2 , g 2 ) α i for all i ∈ [k]. The public key is PK = (G, Γ, g 1 , g 2 , G, H 1 , . . . , H k , b 1 , . . . , b k ),
where G is a bilinear group.

6. The simulator B calculates secret key for queries (x, i), tk x,i = α, x θ i , e , for i ∈ [t] and functions x then gives all g tk x,i 2

to the adversary A. It is clear that tk x,i θ i is a representation of (g A 1 g 2 ) α,x in the base (b 1 , . . . , b k ) . 7. Take randomly a $ ← Z q . The simulator constructs the ciphertext for a message y as below

CT = (H a 1 G y 1 , . . . , H a k G y k , (u a 1 1 u e 1 2 ) a , . . . , (u a k 1 u e k 2 ) a ),
where y = (y 1 , . . . , y k ). 8. Send the ciphertext CT to the adversary A. If A decides the ciphertext comes from normal distribution (i.e. A returns 1) then B returns "DDH tuple", else returns "random tuple".

We first show that the public key PK which is generated by the simulator B is indistinguishable from the corresponding public key in the real algorithm.

-We will prove that distribution of tuples

(b 1 , . . . , b k ) ∈ G k 1 is uniform. Indeed, , write b i = g t i 1
then, for each (t + k)-tuple (0, t 1 , . . . , t k ) where t 1 , . . . , t k $ ← Z q and 0 = (0, . . . , 0) ∈ Z t q the below system of equations has a solution

         . . .
        × a e =      0 t 1 . . . t k     
.

We denote by Γ 0 a matrix with its rows are vectors θ 1 , . . . , θ t . The rank of this matrix is t. Indeed, it is equivalent that

Γ 0 -AΓ 0 I k cI k × a e = 0 t
has solutions. Here I k is the (k × k)-unit matrix. We set

Ω = Γ 0 -AΓ 0 I k cI k .
Since A is chosen such that 1 = g A 1 g 2 = g A+c 1 , ((t + k) × 2k)-matrix Ω has rank k + t. Therefore, dim ImΩ = rank Ω and the dimension of KerΩ = 2k -(k + t) = k -t. Therefore, the above system of linear equations with unkowns (a, e) exists a solution. It implies that

(b 1 , . . . , b k ) is uniform over G k 1 .
-Concerning H i , in the real game H i = e(g 1 , g 2 ) α i for randomly chosen but known g 1 , g 2 while in the simulation game, H i = e(u A 1 u 2 , g 2 ) α i for randomly chosen A and (α i ) i in a span of dimension k -1. Under the DDH in the G 1 , u A 1 u 2 is indistinguishable from random, and thus H i follows from a correct distribution in the computational sense.

We now show that, for any adversarially chosen y, if (g 1 , g 2 , u 1 , u 2 ) ∈ G 4 1 is a DDH tuplee then the ciphertext is a normal ciphertext of y and when it is a random tuple then the ciphertext comes from Tr t (y). Therefore, if the adversary can distinguish these two distributions then B can break the DDH assumption in G

1 : |Pr[B(D 0 ) = 1] -Pr[B(D 1 ) = 1]| is non-negligible. By definition, it is equivalent to Pr[A(CT) = 1 | (g 1 , g 2 , u 1 , u 2 ) $ ← D 0 ] -Pr[A(CT) = 1 | (g 1 , g 2 , u 1 , u 2 ) $ ← D 1 ]
is non-negligible. Here, CT is a ciphertext generated as in Step 7. We find that:

1. When (g 1 , g 2 , u 1 , u 2 ) $ ← D 0 , we will prove that Pr[A(CT) = 1 | (g 1 , g 2 , u 1 , u 2 ) $ ← D 0 ] = Pr[A(CT) = 1 | CT $ ← Norm]. Indeed, suppose that (g 1 , g 2 , u 1 , u 2 ) = (g 1 , g 2 , g z 1 , g z 2 )
, where z is unknown. The ciphertexts in Step 7 is then:

CT = H a 1 G y 1 , . . . , H a k G y k , (u a 1 1 u e 1 2 ) a , . . . , (u a k 1 u e k 2 ) a = H a 1 G y 1 , . . . , H a k G y k , (g za 1 1 g ze 1 2 ) a , . . . , (g za k 1 g ze k 2 ) a = H a 1 G y 1 , . . . , H a k G y k , (g a 1 1 g e 1 2 ) z•a , . . . , (g a k 1 g e k 2 ) z•a = H a 1 G y 1 , . . . , H a k G y k , b z•a 1 , . . . , b z•a k ,
which is in the space of normal ciphertext. It is sufficient thus to show that, with the decryption with the secret key tk x,i , the decryption will gives G x,y . Indeed,

E = H a 1 G y 1 x 1 • • • H a k G y k x k e u a 1 1 u e 1 2 aθ 1 • • • u a k 1 u e k 2 aθ k , g tk x,i 2 = G x,y • e(u A 1 u 2 , g 2 ) ax 1 α 1 • • • e(u A 1 u 2 , g 2 ) ax k α k e g A 1 g 2 za e,θ , g x,α θ,e 2 = G x,y • e(g A 1 g 2 , g 2 ) azx 1 α 1 • • • e(g A 1 g 2 , g 2 ) azx k α k e g A 1 g 2 za e,θ , g x,α θ,e 2 = G x,y • e(g A 1 g 2 , g 2 ) az x,α e g A 1 g 2 za e,θ , g x,α θ,e 2 = G x,y . 2. When (g 1 , g 2 , u 1 , u 2 ) $ ← D 1 , we will prove that Pr[A(CT) = 1 | (g 1 , g 2 , u 1 , u 2 ) $ ← D 1 ] = Pr[A(CT) = 1 | CT $ ← Tr t ]. Indeed, suppose that (g 1 , g 2 , u 1 , u 2 ) = (g 1 , g 2 , g γ 1 1 , g γ 2 2
), where γ 1 = γ 2 and g 2 = g c 1 . The ciphertexts in Step 7 is then:

CT = H a 1 G y 1 , . . . , H a k G y k , (u a 1 1 u e 1 2 ) a , . . . , (u a k 1 u e k 2 ) a = H a 1 G y 1 , . . . , H a k G y k , (g γ 1 a 1 1 g γ 2 e 1 2 ) a , . . . , (g γ 1 a k 1 g γ 2 e k 2 ) a = H a 1 G y 1 , . . . , H a k G y k , g a(γ 1 a 1 +cγ 2 e 1 ) 1 , . . . , g a(γ 1 a k +cγ 2 e k ) 1 = H a 1 G y 1 , . . . , H a k G y k , g z 1 1 , . . . , g z k 1 ,
where

z i = a(γ 1 a k + cγ 2 e k ) for all i ∈ [k].
We show that for any traitor with the key tk x,i , i = 1 to t, it decrypts to the same message.

Indeed:

E = H a 1 G y 1 x 1 • • • H a k G y k x k e g γ 1 a 1 1 g γ 2 e 1 2 aθ 1 • • • g γ 1 a k 1 g γ 2 e k 2 aθ k , g tk x,i 2 = G x,y • e(u A 1 u 2 , g 2 ) ax 1 α 1 • • • e(u A 1 u 2 , g 2 ) ax k α k e g a,θ aγ 1 1 g e,θ aγ 2 2 , g x,α θ,e 2 = G x,y • e(g Aγ 1 1 g γ 2 2 , g 2 ) ax 1 α 1 • • • e(g Aγ 1 1 g γ 2 2 , g 2 ) ax k α k e g e,θ aAγ 1 1 g e,θ aγ 2 2 , g x,α θ,e 2 = G x,y • e(g Aγ 1 1 g γ 2 2 , g 2 ) a x,α e g Aγ 1 1 g γ 2 2 a e,θ , g x,α θ,e 2 = G x,y • e(g Aγ 1 1 g γ 2 2 , g 2 ) a x,α e g Aγ 1 1 g γ 2 2 , g 2 a x,α = G x,y .
Here θ i = (θ 1 , . . . , θ k ).

Finally, we will prove that the distribution of ciphertext CT is uniform over the space of signals Tr t . It requires that the system of equations has full rank (i.e. rank = 2k). Indeed, This is straightforward because the last 2k rows of the above matrix are linear independent due to γ 1 = γ 2 .

  Γ 0 -AΓ 0 I k cI k aγ 1 I k acγ 2 I k   × a e = γ is consistent,
We conclude that Lemma 10 (Hybrid Lemma). Considering the one-target security for an adversarially chosen target function x. Under the DDH assumption over group G 1 , for all 1 ≤ i 0 ≤ t, no adversary can distinguish the distribution of tracing signals Tr i 0 (y) with the distribution of Tr i 0 -1 (y) unless it owns the secret key sk i 0 .

Below, we present the tracing algorithm in more details. We note that y 0 , y 1 are vectors which are chosen by the pirate distinguisher D.

For i = t downto 0, do the following: 1. Let cnt ← 0. 2. For j = 1 to N = 8λt 2 /µ, do the following: Output identities i such that |p i -pi-1 | ≥ µ(λ) 4t .

Below, we state and prove confirmation and soundness property of our Tracing algorithm.

Lemma 11 (Confirmation property). The Tracing algorithm has the confirmation property under the DDH assumption in G 1 .

Proof. We want to prove that in the case of that all the traitors are in the set of suspected users, i.e. K D ⊆ K suspect , the Tracing algorithm always returns the identity of a guilty. It means that the output of Tracing algorithm is not empty with high probability. We denote A an adversary who used the secret keys in K D to output the pirate distinguisher D. Since the adversary A can create a µ-useful pirate distinguisher D, it implies that p Norm -1 2 ≥ µ(λ), where We denote S the set of indices i ∈ [t] such that |p i -p i-1 | > µ(λ)/4t. The set S is well defined in the sense that S = ∅. Indeed, as we know that p 0 is negligibly close to 1/2, and Lemma 9 showed that no adversary A can distinguish the distribution Norm from Tr t , then |p t -p 0 | ≥ µ(λ) -negl(λ) > µ(λ)/2. Then, there exists an index i such that |p i -p i-1 | > µ(λ)/2t. Thus S is a non empty set. Applying Chernoff bound for all i ∈ S, we have on experimental probabilities

Pr |p i -pi-1 | < µ(λ) 4t ≤ negl(λ),
Therefore, with overwhelming probability, there exists an index i such that

|p i -pi-1 | ≥ µ(λ) 4t .
The latter is thus returned with overwhelming probability.

Lemma 12 (Soundness property). The Tracing algorithm has the soundness property under the DDH assumption in G 1 .

←

  Pr [ B(D 0 ) = 1] -Pr[B(D 1 ) = 1] = | Pr[A(CT) = 1 | CT $ ← Normal] -Pr[A(CT) = 1 | CT $ Tr t ]| = Adv(A),which is non-negligible.

←

  Tr i (y b ). iii. Send CT to D. If D(CT) = b then cnt ← cnt + 1.3. End for. 4. Let pi be the fraction of times that D did the correct guess. We have pi = cnt/N . End for.

  b ) = b : (MSK, PK) ← Setup(•) {sk i ← Extract(i, MSK, x)} i∈[n] (D, y 0 , y 1 ) ← A(PK, {sk i } i∈[t] ) st. x, y 0 = x, y 1 b $ ← {0, 1}, CT b ← Norm(PK, y b )

  θ 1 . . . . . . -Aθ 1 . . .

						
	. . .	. . .	. . .	. . .	. . .	. . .
	. . . θ t . . . . . . -Aθ t . . .
	1 . . . 0 c . . . 0
	. . .	. . .	. . .	. . .	. . .	. . .
	0 . . . 1 0 . . . c

  . . . θ 1 . . . . . . -Aθ 1 . . .

	matrix				
		              	. . . 1 . . . 0 c . . . . . . . . . . . . . . . . . . . . . 0 . . . 1 0 aγ 1 . . . 0 acγ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 0 . . . c 0 . . .	              
			0 . . . aγ 1 0	. . . acγ 2

where γ is a fixed vector in Z t+2k q . It is equivalent that the below (t + 2k, 2k)-. . . θ t . . . . . . -Aθ t . . .

Acknowledgments

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud) and the ANR ALAMBIC (ANR16-CE39-0006).

Proof. Suppose that an adversary A can distinguish the distribution of tracing signals Tr i 0 with Tr i 0 -1 . We build a simulator B that breaks DDH assumption. The simulator has input a 4-tuple (g 1 , g 2 , u 1 , u 2 ) ∈ G 4 1 , where g 2 = g c 1 and c is unknown. It must output "DDH tuple" or "random tuple".

1. Take randomly t codewords θ 1 , . . . , θ t from the code Γ corresponding to t traitors and also take t codewords θ (s) 1 , . . . , θ

t from the code Γ corresponding to t suspected users. We are considering the adversary A does not know the secret key sk i 0 or the pirate decoder does not contain sk x,i 0 in itself. 2. Take randomly A from Z q such that g A 1 g 2 = 1. 3. Take randomly a = (a 1 , . . . , a k ), e = (e 1 , . . . , e k )

q such that α, a -Ae = 0 and α, v = 0. 6. When B receives a target function x from A. It calculates τ i = α, x θ i , e , for i = 1, . . . , t and then give all g τ i 2 to the adversary A to create a Pirate Decoder D x . Moreover, τ

where y = (y 1 , . . . , y k ). It then sends the ciphertext to the adversary A. If A returns the ciphertext comes from Tr i 0 (y) distribution then B returns DDH tuple, else returns random tuple.

By the similar argument as in Lemma 9, the ciphertext CT in Step 7 of the algorithm B comes from the distribution Tr i 0 (y) if the input of B is actually DDH tuples and from the distribution Tr i 0 -1 (y) otherwise.

Based on the lemmas 9 and 10, we can design a tracing algorithm that relies on the linear technique tracing:

-Initial step: Tracer constructs distributions of tracing signal Tr t , . . . , Tr 0 .

-Do experiments on the pirate distinguisher D finitely many times. We start testing D by taking tracing signals CT from the distribution Tr t . We measure the rate that D outputs correctly his guess, denoted by pt . Experiments can be done because we can prove that the pirate distinguisher cannot distinguish distributions Tr t and Norm (see Lemma 9). -At step i, for i = t -1, . . . , 0. We do experiment on the pirate distinguisher D with tracing signals taken from Tr i . From Lemma 10, the pirate distinguisher cannot see any change from previous step i + 1 to this step i unless it holds the secret key tk i+1 . More formally, we also measure the rate pi that D outputs correctly his guess and show that if D does not contain tk i+1 then there is no significant difference between pi+1 and pi . -At the final step, D will be tested with tracing signals taken from Tr 0 . D answers correctly only negligibly close to 1/2. -We output the traitor i such that the gap between pi and pi-1 is the largest value among all indices i.

Proof. We now prove the soundness property of Tracing algorithm. Suppose that the Tracing algorithm outputs an identity j, where tk j ∈ K suspect , we will prove that tk j ∈ K D . According to Chernoff bound, thanks to N = 8λt 2 /µ(λ) to calculate pi , for all i, we have

Therefore, with high probability we have |p i -p i | ≤ µ(λ)/16t, for all i = 0, . . . , t. By definition, whenever the Tracing algorithm outputs j as a guilty, we have |p j -pj-1 | ≥ µ(λ)/4t, and thus |p j -p j-1 | ≥ µ(λ)/8t. In other words, the pirate distinguisher can distinguish the two tracing signals Tr j and Tr j-1 with advantage at least µ(λ)/8t. It implies that D contains the secret key tk j , tk j ∈ D. This follows from the fact that if D does not know the secret key tk j , tk j ∈ D, the two tracing signals Tr j and Tr j-1 are indistinguishable. More concretely, under the hardness of the DDH problem in group G 1 , it is impossible for the pirate to distinguish Tr j and Tr j-1 without tk j . This is stated and proved in Lemma 10.

Theorem 13. Under the DDH assumption, our tracing scheme is one-target security in blackbox confirmation model.

Proof. We recall that in the black-box confirmation model we will verify a set suspected secret keys K suspect = {tk 1 , . . . , tk t } which are also derived from the vector x. We will prove that Tracing algorithm always outputs an identity of a traitor whenever K D ∩ K suspect = ∅. It means that Tracer always wins in the game with the pirate distinguisher D. Indeed, we consider the following two cases:

-In the first case K D ⊆ K suspect . It means that all traitors are in suspicious set K suspect .

Tracing algorithm will output a guilty identity i by the confirmation property. According to soundness property, the identity is a traitor (tk i ∈ K D ). -In case K D ⊆ K suspect and K D ∩ K suspect = ∅. Because K D ∩ K suspect = ∅, tracing algorithm will output an identity i so that sk i ∈ K suspect . It implies i is a traitor (tk i ∈ K D ) by the soundness property.