Paola De Perthuis

David Pointcheval

Two-Client Inner-Product Functional Encryption with an Application to Money-Laundering Detection

In this paper, we extend Inner-Product Functional Encryption (IPFE), where there is just a vector in the key and a vector in the single sender's ciphertext, to two-client ciphertexts. More precisely, in our two-client functional encryption scheme, there are two data providers who can independently encrypt vectors x and y for a data consumer who can, from a functional decryption key associated to a vector α, compute αixiyi = x • Diag(α) • y ⊤ . Ciphertexts are linear in the dimension of the vectors, whereas the functional decryption keys are of constant size. We study two interesting particular cases:

-2-party Inner-Product Functional Encryption, with α = (1, . . . , 1). There is a unique functional decryption key, which enables the computation of x • y ⊤ by a third party, where x and y are provided by two independent clients; -Inner-Product Functional Encryption with a Selector, with x = x0∥x1 and y = bn ∥b n ∈ {1 n ∥0 n , 0 n ∥1 n }, for some bit b, on the public coefficients α = α0∥α1, in the functional decryption key, so that one gets x b • α ⊤ b , where x and b are provided by two independent clients. This result is based on the fundamental Product-Preserving Lemma, which is of independent interest. It exploits Dual Pairing Vector Spaces (DPVS), with security proofs under the SXDH assumption. We provide two practical applications: to medical diagnosis for the latter IPFE with a selector, and to money-laundering detection for the former 2-party IPFE, both with strong privacy properties, adaptative security and the use of labels granting a Multi-Client Functional Encryption (MCFE) security for the scheme, thus enabling its use in practical situations.

Introduction

Let us consider the following practical use-case: two distinct data providers (DP 1 and DP 2 ) with private and sensitive pieces of information want to combine them to allow a data consumer (DC) to get a result from a calculation on them. For instance, DP 1 could be a hospital with a patient's biological monitoring data on which a diagnosis depends, but being also be affected by a private piece of information relative to the patient's personal historic, owned by DP 2 . We want to grant an efficient result calculation by DC based on associated data from both data providers and public coefficients, which after the initialization phase would allow both data providers to send their encrypted data to the data consumer indefinitely without further interaction. This can be formally written as DP 1 owning a vector x ∈ Z n q , and DP 2 owning a vector y ∈ Z n q , and having DC wanting to get x • D(α) • y ⊤ , where D(α) is the diagonal matrix with α ∈ Z n q on the diagonal, i.e. i α i x i y i . This is a particular case of quadratic evaluation, as recently studied in [AGT21], where the quadratic function is diagonal. But the multi-client aspect with labels has many interesting applications. For example, in the above medical use-case, we can even have a more specific setting, where DC wants to get either x 0 • α ⊤ 0 or x 1 • α ⊤ 1 according to a bit b encoded in y, which can inform about particular medical predispositions:

x = (x 0 , x 1 ) ∈ Z 2n q y = ( b • 1, b • 1) ∈ Z 2n q α = (α 0 , α 1 ) ∈ Z 2n
q so that in the end, the obtained result is x b • α ⊤ b = ⟨α b , x b ⟩. This is a particular case of innerproduct, with a selector b. And thanks to the labels associated to each vectors x and y, and hence to x 0 , x 1 , and b, computations are restricted between values encrypted under the same labels.

Another application could be money-laundering detection: following [SNY + 16], we can consider a graph of transactions between bank accounts during short windows of time: nodes are the account numbers and the oriented edges are the amounts transferred between accounts; w u,v is the amount of the transactions from u to v in that time-period. When there is no edge, or no transaction, w u,v is set to 0. If one maps all the bank accounts to [[1; N ]], one can write, for all vertices v, the vectors of the incoming transactions w v,in = (w 1,v , . . . , w N,v ) and of the outgoing transactions w v,out = (w v,1 , . . . , w v,N ). The index of similarity between two accounts u and v is calculated as: (u, v) where, using the norm L 2 :

σ(u, v) = σ in (u, v) × σ out
σ in (u, v) =
x w x,u w x,v

x w 2

x,u

x w 2

x,v

= ⟨ w u,in ||w u,in || , w v,in ||w v,in || ⟩ σ out (u, v) = x w u,x w v,x x w 2 u,x x w 2 v,x = ⟨ w u,out ||w u,out || , w v,out ||w v,out || ⟩
If we denote w = w/||w|| the normalized vector, this is

σ in (u, v) = ⟨w u,in , w v,in ⟩ σ out (u, v) = ⟨w u,out , w v,out ⟩
As explained in [SNY + 16], we can compare all the pairs of accounts to detect similar behaviors that are potentially involved in money-laundering activities. One can then identify clusters of suspicious nodes, and a human investigation will draw conclusions on these. We will select accounts with a similarity index above a threshold θ for a given time period.

σ(u, v) = ⟨w u,in , w v,in ⟩ × ⟨w u,out , w v,out ⟩ is the product of two inner-products on vectors generated by two independent banks: these inner-products are a particular case of our general description with α = (1, . . . , 1). More detail, with specific optimisations about these two applications, is provided later. We first present our generic protocol to allow the DC to compute x • D(α) • y ⊤ = i α i x i y i . We stress that in this paper, we consider row vectors.

Functional Encryption

Functional Encryption (FE), first introduced in [O'N10,BSW11], enables the construction of protocols in which the encrypted secret information x can be partially decrypted by a party with a decryption key sk f , with f a function, that will allow them to learn f (x) and nothing else about x. The multi-client functional encryption (MCFE) generalization [CDG + 18] allows the plaintext x = (x 1 , . . . , x n ) to be owned and encrypted by multiple independent clients. But all the clients agree on a common label so that only those inputs can be combined into the same vector on which the functional decryption applies.

In recent years, efficient constructions for particular cases of functional encryption were studied, and first for linear functionalities: given a vector x encrypted by a party and given the functional key sk y , for a vector y, one can compute the inner-product ⟨x, y⟩ [ABDP15,ALS16], with extensions to the multi-client setting, when x = (x 1 , . . . , x n ), and each component is encrypted by a different client [CDG + 18,CDSG + 20]. Quadratic functions have also been dealt, but in the multi-input setting [AGT21], which differs with the multi-client setting by the absence of label. And so, all the contributions of any encryptor can be combined together into the ciphertext of x so that, given the functional key sk A , for a matrix A, one can compute the quadratic relation xAx ⊤ . We are interested in the two-client quadratic functional encryption, where client 1 encrypts x and client 2 encrypts y, under a common label so that, given the functional key sk A , for a matrix A, one can compute the quadratic relation xAy ⊤ . Our construction is limited to diagonal matrices A = D(α), but we will show that this also presents interesting practical applications.

MIFE and MCFE

In [DOT18], a Multi-Input Functional Encryption (MIFE) for Inner Product has already been presented, and [TT18] proposes an Inner-Product FE, both using a similar approach to ours with Dual Pairing Vector Spaces (DPVS). However, the latter paper provides a proof specific to the scheme (without multiple users), whereas we present below a generic Product-Preserving Lemma, that can be applied in several contexts. And the former paper only addresses MIFE.

While in both MIFE and MCFE, there are multiple users that can independently encrypt the multiple inputs, we here stress the main difference: MCFE allows labels, whereas MIFE does not. Hence, MCFE with a constant label reduces to MIFE. But from the security point of view, MCFE allows each client to encrypt multiple inputs with different labels. Only inputs under the same labels will be combined into a vector on which the functional decryption key will apply. In MIFE, if a client encrypts two inputs, they both can be combined with all the other clients' inputs leading to multiple vectors on which the functional decryption key can apply. This leaks so much information that all the individual inputs can be revealed. Such a leakage is not a weakness of a specific MIFE scheme, but of the functionality: this must be considered in the security model, which results in a very weak level of security. With MCFE, the security model excludes any leakage between inputs encrypted under different labels, so the actionable scheme must guarantee that, which is much more difficult to achieve. This is the main goal of this paper: whereas [AGT21] proposed an MIFE scheme that allowed the computation of xAx T from encryptions of the coordinates of vectors x by different users without labels, and a decryption key specific to the matrix A, we offer a two-client FE scheme that provides the result of xAy T from encryptions of vectors x and y from two independent clients, and a decryption key specific to the matrix A. Even if we only manage to deal with diagonal matrices, this finds applications.

Contributions

In the above money-laundering detection application, [GGJ + 20] suggested using MPC with oblivious comparisons to calculate the similarity coefficients between accounts held by different banks. This means a highly interactive and synchronous protocol whereas our goal is to have an asynchronous setting where a neutral law enforcement third party receives the private data and computes the similarity coefficients.

Our main contribution is thus a two-client functional encryption scheme where client 1 owns and encrypts a vector x ∈ Z n q , client 2 owns and encrypts a vector y ∈ Z n q , while a third party knowing a functional decryption key dk α can compute x • D(α) • y ⊤ , where D(α) is the diagonal matrix with public vector α ∈ Z n q on the diagonal: i α i x i y i . We stress again that we are in the multi-client setting, and not just the multi-input, with independent x and y from the two clients, but associated to a common label to allow the application of the functional decryption key, and to give access to the value i α i x i y i . No information leaks if different labels are used.

To this aim, we use dual pairing vector spaces (DPVS) [OT10,OT12a] so that from ciphertexts in each of the two DPVS associated bases, the desired scalar product can be calculated, adding the public coefficients as exponents and using the associated decryption key.

More precisely, we prove and use the Product-Preserving Lemma, that essentially states that no adversary can see the difference, for each component, between the ciphertexts on x i and y i and the ciphertexts on 1 and x i y i , as the product is preserved. This Product-Preserving Lemma is of independent interest for other security proofs where one wants to exploit a product invariant. We provide several examples below. We now stress that our computation x•D(α)•y ⊤ , from two independent inputs x and y can be seen as a particular case from [AGT21], as they allow to compute zAz T which could be used with

z = x||y A = 0 0 D(α) 0
But first, this would result in an MIFE scheme, and not 2-client FE scheme as [AGT21] does not handle labels, and furthermore our functional decryption key is constant-size while theirs is linear in the size of the matrix. Eventually, their security analysis only deals with selective adversaries, who have to commit on the challenge messages before asking functional decryption keys, and ours grants adaptative security.

Dual Pairing Vector Spaces

Dual Pairing Vector Spaces (DPVS) have been proposed for efficient constructions with adaptive security [OT10,OT12a]. We will use them here for their orthogonality properties, and the hard subspace membership problem under the SXDH assumption.

Pairing Vector Spaces

Let us be given any cyclic group (G = ⟨G⟩, +) of prime order q, denoted additively. We can define the n-dimension Z q -vector space

G n = {X = x • G def = (X 1 = x 1 • G, . . . , X n = x n • G) | x ∈ Z n q },
with the following laws:

x • G + y • G def = (x + y) • G a • (x • G) def = (a • x) • G
where x + y and a • x are the usual internal and external laws of the vector space Z n q . For the sake of clarity, vectors will be row-vectors.

In a pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), with a bilinear map e from G 1 × G 2 into G t , where G 1 (resp. G 2 ) is a generator of G 1 (resp. G 2 ), we can have an additional law between elements in G n 1 and G n 2 :

(x • G 1 ) × (y • G 2 ) = X × Y = i e(X i , Y i ) = i e(x i • G 1 , y i • G 2 ) = i g x i •y i t = g x•y ⊤ t = g ⟨x,y⟩ t
where g t = e(G 1 , G 2 ) and ⟨x, y⟩ is the inner product between vectors x and y.

Dual Pairing Vector Spaces

We define E = (e i ) i the canonical basis of the n-dimensional vector space Z n q , where e i = (e i,1 , . . . , e i,n ), and e i,j = δ i,j : δ i,j = 1 if i = j and δ i,j = 0 otherwise, for i, j ∈ {1, . . . , n}. We can also define E = (E i ) i the canonical basis of G n , where

E i = e i • G = (δ i,j • G) j . The above notation x • G will thus be denoted (x) E = i x i • E i = x • E. More generally, given any basis B = (b i ) i of Z n q , we can define the basis B = (B i ) i of G n , where B i = b i • G. Choosing a random basis B of G n is equivalent to a random choice of an invertible matrix B $ ← GL n (Z q ), such that B = B • E. In this case, we can now have (x) B = x • B = x • B • E = (x • B) E .
In case of pairing-friendly setting, for a dimension n, we will denote E = (E i ) i and

E * = (E * i ) i the canonical bases of G n 1 and G n 2 , respectively: E×E * = (g ⟨e i ,e j ⟩ t ) i,j = (g δ i,j t ) i,j = Id n . The same way, if we denote B = (B i ) i = B • E the basis of G n
1 associated to a matrix B, and

B * = (B * i ) i = B * • E * the basis of G n 2 associated to the matrix B * = (B -1 ) ⊤ , as B • B * ⊤ = I n , B × B * = Id n .
B and B * are called Dual Orthogonal Bases. When (B, B * ) are associated to a random matrix B $ ← GL n (Z q ), they are called Random Dual Orthogonal Bases. A pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), with such dual orthogonal bases, is called a Dual Pairing Vector Space.

For avoiding ambiguous notations, we used bold letters x for vectors in Z q , underlined letters A for matrices in Z q , and capital bold letters E for vectors in G. More precisely, in general, B is a vector in G 1 and B * is a vector in G 2 . Then, B and B * are for bases (sets of independent vectors) in G 1 and G 2 respectively.

Useful Transformations

As detailed in [DGP22], we can describe several transformations that are indistinguishable, either in a perfect way or in a computational way under the Decisional Diffie-Hellman Problem:

Definition 1 (Decisional Diffie-Hellman Assumption). The DDH assumption in G, of prime order q with generator G, states that no algorithm can efficiently distinguish the two distributions

D 0 = {(a • G, b • G, ab • G), a, b $ ← Z q } D 1 = {(a • G, b • G, c • G), a, b, c $ ← Z q }
And we will denote by Adv ddh G (t) the best advantage an algorithm can get in distinguishing the two distributions within time bounded by t.

As we will use pairing-friendly setting, we might alternate with modifications in G 1 and G 2 . We will thus make the more general assumption:

Definition 2 (Symmetric eXternal Diffie-Hellman Assumption). The SXDH assumption in (G 1 , G 2 , G t , e, G 1 , G 2 , q) makes the DDH assumptions in both G 1 and G 2 .

Then, we define

Adv sxdh (t) = max{Adv ddh G 1 (t), Adv ddh G 2 (t)}. Subspace Indistinguishability. Let us consider a triple (a • G 1 , b • G 1 , c • G 1 )
, for c = ab + τ mod q, that is either a Diffie-Hellman tuple (i.e., τ = 0 mod q) or a random tuple (i.e., τ $ ← Z q ). For any random dual orthogonal bases U and U * of dimension 2, associated to the matrices U and U * = (U -1 ) ⊤ , respectively, we can set

B = 1 a 0 1 B * = 1 0 -a 1 B = B • U B * = B * • U *
Note that we can compute B = (B i ) i , as we know a • G 1 and all the scalars in U :

B 1 = U 1 + a • U 2 B 2 = U 2
This is the same for B * , excepted for the vector B * 2 as a • G 2 is missing:

B * 1 = U * 1 B * 2 = -a • U * 1 + U * 2 One can thus publish {B 1 , B 2 } and {B * 1 }, but not B * 2 . As already remarked, (x) B = (x • B) U , so (x) U = (x • B -1 ) B . Note that B -1 = B * ⊤ . In particular (b, c) U = (b, c -ab) B = (b, τ ) B
where τ can be either 0 or random: the vector is thus either in the subspace spanned by B 1 or in the full space spanned by B 1 and B 2 .

Whereas we cannot compute B * 2 , this does not exclude this second component in the vectors:

(y) U * = (y • B * -1 ) B * = (y • B ⊤ ) B * . So, in particular (y 1 , y 2 ) U * = (y 1 + ay 2 , y 2 ) B * . And when y 2 = 0, (y 1 , 0) U * = (y 1 , 0) B * .
Theorem 3 (Subspace Indistinguishability). Under the DDH assumption in G 1 , for random dual orthogonal bases B and B * , once having seen B and B * \{B * 2 }, and any vector (y 1 , 0) B * , for any y 1 ∈ Z q , one cannot distinguish the vectors (x 1 , 0) B and (x 1 , x 2 ) B , for unknown random x 1 , x 2 $ ← Z q . More precisely, the best advantage one can get is bounded by 2 × Adv ddh G 1 (t).

Balancing Indistinguishability. With a transformation of the bases, it is possible to alter two components in a vector when there is twice the same value in the other vector, using

B =   1 -a a 0 1 0 0 0 1   B ′ =   1 0 0 a 1 0 -a 0 1  
Lemma 4 (Balancing Indistinguishability). Under the DDH assumption in G 1 , for random dual orthogonal bases B and B * , once having seen B and B * \{B * 2 , B * 3 } and any vector (y 1 , y 2 , y 2 ) B * , for any y 1 , y 2 ∈ Z q , one cannot distinguish the vectors (x 1 , 0, 0) B and (x 1 , -x 2 , x 2 ) B , for unknown random x 1 , x 2 $ ← Z q . More precisely, the best advantage one can get is bounded by Adv ddh G 1 (t).

Swapping Indistinguishability. Applying twice the above Balancing Indistinguishability Lemma 4, with a chosen shift x 2 on B 2 first, with indistinguishability between (x 1 , x 2 , 0) B and (x 1 , x 2 -θ, θ) B , and thus (x 1 , θ ′ , θ) B with θ + θ ′ = x 2 , and then a second chosen shift x 2 on B 3 , with indistinguishability between (x 1 , 0, x 2 ) B and (x 1 , -θ, x 2 + θ) B , and thus again (x 1 , θ ′ , θ) B with θ + θ ′ = x 2 :

Theorem 5 (Swapping Indistinguishability). Under the DDH assumption in G 1 , for random dual orthogonal bases B and B * , once having seen B and B * \{B * 2 , B * 3 } and any vector (y 1 , y 2 , y 2 ) B * , for any y 1 , y 2 ∈ Z q , one cannot distinguish the vectors (x 1 , x 2 , 0) B and (x 1 , 0, x 2 ) B , for an unknown random x 1 $ ← Z q , but chosen x 2 ∈ Z q . More precisely, the best advantage one can get is bounded by 2 × Adv ddh G 1 (t).

Indexing Indistinguishability. We will make use of the major transformation introduced in [OT12b], with orthogonal indices that allow alterations of many components at once, in an indistinguishable way, if labels λ and λ ′ differ using

B = 1 λ ′ -λ   λ ′ -λ aλ ′ -1 1 -a 0 0 λ ′ -λ   B ′ =   1 1 0 λ λ ′ 0 -a 0 1  
Theorem 6 (Indexing Indistinguishability). Under the DDH assumption in G 1 , for fixed distinct labels λ, λ ′ ∈ Z q , random dual orthogonal bases B and B * , once having seen B and B * \{B * 3 } and any vector (π • (λ ′ , -1), y) B * , for any y ∈ Z q but an unknown random π $ ← Z q , one cannot distinguish the vectors (µ • (1, λ), 0) B and (µ • (1, λ), x) B , for any x ∈ Z q but an unknown random µ $ ← Z q . More precisely, the best advantage one can get is bounded by 2 × Adv ddh G 1 (t).

Replication Indistinguishability. Eventually, we will have to replicate some components, in order to prepare a balance or swap transformation on the other vector. In this case, this is perfectly indistinguishable using

B = 1 -1 0 1 B ′ = 1 0 1 1
Lemma 7 (Replication Indistinguishability). For random dual orthogonal bases B and B * , once having seen B\{B 1 }, B * \{B * 2 }, one cannot distinguish the vectors (x 1 , x 2 ) B , (y 1 , y 2 ) B * and (x 1 , x 1 + x 2 ) B , (y 1 -y 2 , y 2 ) B * , for any x 1 , x 2 , y 1 , y 2 ∈ Z q .

We stress that for the above theorem, B 1 and B * 2 must not be shown to the adversary, and then with just B 2 = U 2 and B * 1 = U * 1 , the adversary cannot know whether one is using (U, U * ) or (B, B * ).

Product-Preserving Lemma

We start with a lemma that will be the basis of our results and applications, using several times the above indistinguishability theorems. This lemma is our main contribution. It is of independent interest, with various applications.

Lemma 8 (Product-Preserving Lemma). For two random dual orthogonal bases B and B * , of length 5, unknown to the adversary A, given a list of indexed vectors, for any

(x i , y i , a i , b i ), fixed indices λ i among Q possible values, but random unknown π i , µ i , for i = [[1; N ]]: C i =(π i (1, λ i ), x i , a i , 0) B D i =(µ i (λ i , -1), y i , b i , 0) B *
A cannot distinguish between the two cases, for fixed λ * ̸ = λ i , and any x * , y * , but unknown random π * , µ * :

(0) C * =(π * (1, λ * ), x * , 0, 0) B D * =(µ * (λ * , -1), y * , 0, 0) B * (1) C * =(π * (1, λ * ), 0, 1, 0) B D * =(µ * (λ * , -1), 0, x * y * , 0) B *
with an advantage greater than 4

• (N Q + 1) • (Adv ddh G 1 (t) + Adv ddh G 2 (t))
, and thus greater than 8

• (N Q + 1) • Adv sxdh (t).
In Figure 1, we present the sequence of games of the security proof of the above lemma, where the π i 's and the µ i 's are used when unknown randomness is required to apply swapping indistinguishability. Grey cells highlight the modified values, and the various transformations of bases are precised in the left column. We stress that the indices (λ i ) i and λ * have to be known in advance, to be able to enumerate them deterministically, and apply the indexing indistinguishability several taimes. We thus bound their number by Q (which will be the number of hash queries in our applications). The full proof can be found in appendix A.

2-Client Inner-Product Functional Encryption

In this section, we first recall the general protocol we want to instantiate, and then we provide and prove a concrete construction.

G0 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | x * 0 | 0 ) D * = ( µ * (λ * , -1) | y * 0 | 0 ) G1 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Replication Di = ( µi(λi, -1) | yi bi | yi ) C * = ( π * (1, λ * ) | x * 0 | 0 ) D * = ( µ * (λ * , -1) | y * 0 | y * ) G2 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Swapping Di = ( µi(λi, -1) | yi bi | yi ) C * = ( π * (1, λ * ) | 0 0 | x * ) D * = ( µ * (λ * , -1) | y * 0 | y * ) G3 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Indexing Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 0 | x * ) D * = ( µ * (λ * , -1) | y * 0 | y * ) G4 ∀i Ci = ( πi(1, λi) | xi ai | xi ) Replication Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 0 | x * ) D * = ( µ * (λ * , -1) | 0 0 | y * ) G5 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Indexing Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 0 | x * ) D * = ( µ * (λ * , -1) | 0 0 | y * ) G6 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Quotient Di = ( µi(λi, -1) | yi bi | 0 ) for x * ̸ = 0 C * = ( π * (1, λ * ) | 0 0 | 1 ) D * = ( µ * (λ * , -1) | 0 0 | x * y * ) G7 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Subspace Di = ( µi(λi, -1) | yi bi | 0 ) for x * = 0 C * = ( π * (1, λ * ) | 0 0 | 1 ) D * = ( µ * (λ * , -1) | 0 0 | 0 ) G8 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Replication Di = ( µi(λi, -1) | yi bi | -bi ) C * = ( π * (1, λ * ) | 0 1 | 1 ) D * = ( µ * (λ * , -1) | 0 0 | x * y * ) G9 ∀i Ci = ( πi(1, λi) | xi ai | ai ) Indexing Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 1 | 1 ) D * = ( µ * (λ * , -1) | 0 0 | x * y * ) G10 ∀i Ci = ( πi(1, λi) | xi ai | ai ) Swapping Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 1 | 1 ) D * = ( µ * (λ * , -1) | 0 x * y * | 0 ) G11 ∀i Ci = ( πi(1, λi) | xi ai | 0 ) Replication Di = ( µi(λi, -1) | yi bi | 0 ) C * = ( π * (1, λ * ) | 0 1 | 0 ) D * = ( µ * (λ * , -1) | 0 x * y * | 0 )
Fig. 1. Sequence of Games for the Product-Preserving Lemma

General Protocol Description

Two data providers DP 1 and DP 2 send ciphertexts based on their data x and y ∈ Z n q respectively to a data consumer DC. DC has a functional decryption key dk

A for A = Diag((α i ) i∈[[1;n]] ) ∈ Z n×n q
enabling them to learn xAy T = i α i x i y i and nothing else about x nor y. This is defined using four algorithms:

Setup(1 κ ). This algorithm generates the encryption keys ek 1 and ek 2 for DP 1 and DP 2 respectively, and the secret key sk; KeyGen(sk, A).

For A = Diag((α i ) i∈[[1;n]] ) ∈ Z n×n q
, using the secret key sk, one generates the functional decryption key dk A ; Encrypt(λ, ek, z). Given the label λ and (ek, z), either equal to (ek 1 , x) or (ek 2 , y), the corresponding data provider returns the ciphertext E; Decrypt(dk α , C, D). Where C is a ciphertext obtained from DP 1 and D from DP 2 under labels λ 1 and λ 2 respectively, returns xAy

T = i α i x i y i if λ 1 = λ 2 .

Our 2-Client Inner-Product Functional Encryption

We provide a construction for the general protocol described in section 4.1 hereafter, using ciphertexts made of vectors of elements in two groups G 1 and G 2 used for pairings, with the first data provider DP 1 using elements from G 1 and the second, DP 2 , from G 2 . We take advantage of dual pairing vector spaces, ciphertext group exponents being components of an element of GL 12 (Z q ) decomposed into one of its bases B for DP 1 , or in its dual base B * for DP 2 . As such, when a pairing is performed between ciphertexts from the two data providers, the exponent of the new target group element is the scalar product of the vectors of exponents in both data providers' ciphertexts, and this will procure the expected result, with additional enforcement of identical labels in both ciphertexts, and randomness and additional components to ensure privacy.

Combining the above product-preserving lemma together with IPFE scheme from [ALS16], we can obtain a secure construction, even against adaptive adversaries. However, since we will have two IPFE in G 1 and G 2 , we will need secret keys S = (s i ) i and T = (t i ) i of dimension 3. To this aim we will use 4 times the above Product-Preserving Lemma 8, on the values (x ℓ , y ℓ ) = (x ℓ,i , y ℓ,i ) i , for all the labels ℓ, and on the three pairs of randomness (σ ℓ,j s i,j , τ ℓ,j t i,j ), for j = 1, 2, 3, for all ℓ, i, to lead to unique vectors z ℓ = (z ℓ,i = x ℓ,i y ℓ,i ) i , the unique secret key R = (r i = (r i,j = s i,j t i,j ) j ) i , as well as global randomnesses ρ ℓ = (ρ ℓ,j = σ ℓ,j τ ℓ,j ) j .

We use a Dual Pairing Vector Space of dimension 12, in a pairing-friendly setting

(G 1 , G 2 , G t , e, G 1 , G 2 , q): Setup(1 κ ). From a pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q) of
appropriate size with respect to the security parameter κ, one chooses random dual orthogonal matrices

B = (b i ) i $ ← GL 12 (Z q ) and B * = (b * i ) i ← (B -1 ) ⊤ , which define the bases (B, B * ). One also generates se- cret vectors S = (s i ) i , T = (t i ) i $ ← (Z 3 q ) n .
The encryption key ek 1 of DP 1 is set to (B, S), while the encryption key ek 2 of DP 2 is set to (B * , T). The secret key is sk = (S, T). The public parameters are just PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q), together with a collision-resistant hash function H into Z q ; KeyGen(sk, α). For a vector α ∈ Z n q , one generates the functional decryption key

dk α ← d = α i (s i,1 t i,1 , s i,2 t i,2 , s i,3 t i,3 ) ∈ Z 3
q ; Encrypt(λ, ek, z), for a label λ, where ek is either ek 1 or ek 2 , and z is either x or y, one derives

λ i = H(λ, i) ∈ Z q , for i ∈ [[1; n]]: -To encrypt x with ek 1 = (B, S), one generates σ $ ← (Z * q ) 3 , random π i $ ← Z q , and sets C ← (λ, C 0 , (C i ) i )
, where C 0,j = σ j • G 1 , for j = 1, 2, 3, and for i = 1 . . . , n, ,0,0,σ 1 s i,1 ,0,σ 2 s i,2 ,0,σ 3 s i,3 ,0,0) for j = 1, 2, 3, andfor i = 1

C i = (π i (b 1 + λ i • b 2 ) + x i • b 3 + 3 j=1 σ j s i,j • b 4+2j ) • G 1 = (π i • (1, λ i ), x i
B = (π i • (1, λ i ), x i , 0, 0, (σ j s i,j , 0) j , 0) B -To encrypt y with ek 2 = (B * , T), one generates τ $ ← (Z * q ) 3 , random µ i $ ← Z q , and sets D ← (λ, D 0 , (D i ) i ), where D 0,j = τ j • G 2 ,
. . . , n, D i = (µ i (λ i b * 1 -b * 2 ) + y i • b * 3 + 3 j=1 τ j t i,j • b * 4+2j ) • G 2 = (µ i • (λ i , -1), y i , 0, 0, τ 1 t i,1 , 0, τ 2 t i,2 , 0, τ 3 t i,3 , 0, 0) B * = (µ i • (λ i , -1), y i , 0, 0, (τ j t i,j , 0) j , 0) B * Decrypt(dk α , C, D).
Due to the orthogonality of the bases B and B * , with g t = e(G 1 , G 2 ), one has

C i × D i = [π i µ i (λ ′ i -λ i ) + x i y i + 3 j=1 σ j τ j s i,j t i,j ] Gt
If the labels are the same, then

C i × D i = g x i y i t • j (g s i,j t i,j t ) σ j τ j . Then, i (C i × D i ) α i = i g α i x i y i t • j (g α i s i,j t i,j t ) σ j τ j = g i α i x i y i t • j (g d j t ) σ j τ j = g i α i x i y i t • j e(C 0,j , D 0,j ) d j
One can thus get g i α i x i y i t and extract the discrete logarithm i α i x i y i .

Security Model

About the security, it is clear neither DP 1 nor DP 2 are allowed to see each other's inputs: given

C i = (π i • (b 1 + λ i • b 2 ) + x i • b 3 + σ 1 s i,1 • b 6 + σ 2 s i,2 • b 8 + σ 3 s i,3 • b 10 ) • G 1 , DP 2 can compute C i × (b 3 • G 1 ) = g x i t
. This thus completely leaks x i . However, we can expect the Data Consumer not to learn more than i α i x i y i on a pair of inputs. And moreover, multiple pairs of inputs cannot be mixed. We thus define a security game, where the adversary can get multiple functional decryption keys dk α for any vector α of their choice, multiple ciphertexts on (λ, x b , y b ) for (λ, x 0 , x 1 ) and (λ, y 0 , y 1 ) of the adversary's choice, in any order of their choice, but for a random bit b. The adversary wins the game if they have correctly guessed b, without cheating: for all the α for which it got the functional decryption keys, and all the labels λ for which it asked (λ, x 0 , x 1 ) and (λ, y 0 , y 1 ),

α i x 0 i y 0 i = α i x 1 i y 1 i . Otherwise, this is easy to guess b.
The goal of the adversary is to guess b, in this classical indistinguishability game, that we model with a left-or-right game, with many queries: Definition 9 (Indistinguishability). The IND security game is defined as follows:

Initialize: The challenger runs the Setup algorithm and gives the public parameters PK to the adversary. They also draw a random coin b $ ← {0, 1}; OKeyGen(α): this is a KeyGen-query for any vector α. It outputs the functional decryption key dk α ← KeyGen(sk, α); LoREncrypt b (λ, z 0 , z 1 ): this is a Left-or-Right query, on a new label λ for b ∈ {1, 2}, and a pair of vectors (z 0 , z 1 ). It outputs

C * b ← Encrypt(λ, ek b , z b ); Finalize(b ′ ):
The adversary outputs a guess b ′ for b. If for all the α asked to the OKeyGenoracle, and all the pairs (x 0 ℓ , x 1 ℓ ) and (y 0 ℓ , y 1 ℓ ) asked to the LoREncrypt-oracle

α i x 0 ℓ,i y 0 ℓ,i = α i x 1 ℓ,i y 1 ℓ,i
, where we denote (x 0 ℓ , x 1 ℓ ) the pair (z 0 , z 1 ) asked for the ℓ-th label λ ℓ with b = 1 and (y 0 ℓ , y 1 ℓ ) for b = 2. Then one outputs b ′ (for legitimate attacks), otherwise one outputs a random bit (for non-legitimate attacks).

The advantage of an adversary A in this indistinguishability game is defined as Adv

ind (A) = Pr[1|b = 1] -Pr[1|b = 0] = 2 Pr[b ′ = b|legitimate] -1.
We stress that in the above security game, the adversary can ask for OKeyGen and LoREncrypt oracles as many times as they want, and in any order. When we specify a "new label", this means that a label can appear only once for each value of b. If the scheme allows to learn some informations between two vectors encrypted under different labels, this breaks this security level. This would be the case with an MIFE scheme, unable to handle labels.

Definition 10 (Ordered Indistinguishability). The ord-IND security game is exactly the same as the IND game except that for each label λ, LoREncrypt 2 must always be asked before LoREncrypt 1 .

We will need the ord-IND security notion in our second construction to drastically reduce the number of ciphertexts sent by DP 2 in the particular case where this data provider sends information to select one or the other half of DP 1 's vector. In this case, for a given label, DP 2 must send their ciphertext before DP 1 sends ciphertexts with the same label, because if these were received in the opposite order, our security games would not allow us to apply the productpreserving lemma storing the product in DP 1 's ciphertext vector. This is a constraint coming from our proof: we cannot think of any practical attack if ciphertexts were sent in the opposite order, but we would then not be able to prove the security. This security level is definitely weaker in theory, as it introduces some constraint for the adversary. However, in practice, one can simply make sure DP 2 first sends all its ciphertexts, and then DP 1 does. This is a similar organizational constraint as not generating two ciphertexts under the same label for each data provider. If these constraints are not satisfied, all the security guarantees are lost.

Security Analysis

Theorem 11. Our above construction from Section 4.2 satisfies IND indistinguishability against adaptive adversaries in time t with:

Adv ind (A) ≤ (32QN (N n + 1) + 3N + 8) • Adv sxdh (t) + 3N/q
where N is the number of different labels the adversary got encryptions for, and Q the number of labels queried to the hash function.

In Figure 2, we present the sequence of games, starting from the real game, where the λ ℓ are all the distinct labels, and λ ℓ,i = H(λ ℓ , i) for i ∈ [[1; n]], for ℓ increased from 1 to N , the total number of distinct labels. We denote L 1 the set of indices ℓ where LoREncrypt 1 is asked first, and L 2 the set of indices where LoREncrypt 2 is asked first. Their sizes are respectively N 1 and N 2 . However, we have to get the possible λ ℓ,i known in advance, in order to enumerate them in the proofs, even if not actually used. We thus program the random oracle for all the Q λ-queries

G0 ∀ℓ ∈ L1, C ℓ,i = ( • • • | x b ℓ,i 0 0 |(σ ℓ,j si,j 0 )j| ) Random b D ℓ,i = ( • • • | y b ℓ,i 0 0 |(τ ℓ,j ti,j 0 )j| ) ∀ℓ ∈ L2, C ℓ,i = ( • • • | x b ℓ,i 0 0 |(σ ℓ,j si,j 0 )j| ) D ℓ,i = ( • • • | y b ℓ,i 0 0 |(τ ℓ,j ti,j 0 )j| ) G1 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |(σ ℓ,j si,j 0 )j| ) Product-Preserving D ℓ,i = ( • • • | 0 x b ℓ,i y b ℓ,i 0 |(τ ℓ,j ti,j 0 )j| ) G2 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 1 )j| ) Product-Preserving D ℓ,i = ( • • • | 0 x b ℓ,i y b ℓ,i 0 |( 0 σ ℓ,j τ ℓ,j si,jti,j )j| ) G3 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 1 )j| ) Formal Renaming D ℓ,i = ( • • • | 0 z b ℓ,i 0 |( 0 ρ ℓ,j si,jti,j )j| ) G4 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 1 )j| ) Random in Span D ℓ,i = ( • • • | 0 z b ℓ,i 0 |( 0 ρ ℓ v1,jsi,jti,j )j| ) G5 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 1 )j| ) Swapping D ℓ,i = ( • • • | 0 c ℓ,i 0 |( 0 0 )j| ) G6 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 0 )j| ) Replication D ℓ,i = ( • • • | 0 c ℓ,i 0 |( 0 0 )j| ) ∀ℓ ∈ L2, C ℓ,i = ( • • • | x b ℓ,i 0 0 |(σ ℓ,j si,j 0 )j| ) D ℓ,i = ( • • • | y b ℓ,i 0 0 |(τ ℓ,j ti,j 0 )j| ) G7 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 0 )j| ) Idem for L 2 D ℓ,i = ( • • • | 0 c ℓ,i 0 |( 0 0 )j| ) ∀ℓ ∈ L2, C ℓ,i = ( • • • | 0 0 c ℓ,i |( 0 0 )j| ) D ℓ,i = ( • • • | 0 0 1 |( 0 0 )j| ) G8 ∀ℓ ∈ L1, C ℓ,i = ( • • • | 0 1 0 |( 0 0 )j| ) b = 0 D ℓ,i = ( • • • | 0 c ′ ℓ,i 0 |( 0 0 )j| ) ∀ℓ ∈ L2, C ℓ,i = ( • • • | 0 0 c ′ ℓ,i |( 0 0 )j| ) D ℓ,i = ( • • • | 0 0 1 |( 0 0 )j| )
The 2 first components of the C ℓ,i and D ℓ,i are always asked to H, anticipating Qn possible indices. K denotes the number of OKeyGen-queries. lls highlight the modified values, and the various transformations of bases are precised in the left column. The full proof is provided in appendix B. Note that under the collision-resistance of H, all the λ ℓ,i are also distinct.

π ℓ,i • (1, λ ℓ,i ) and µ ℓ,i • (λ ℓ,i , -1). For ℓ ∈ L k : c ℓ,i = z b ℓ,i + ρ ℓ j v k,j si,jti,j, and c ′ ℓ,i = z 0 ℓ,i + ρ ℓ j v k,j si,jti,j. C ℓ,0 = σ ℓ • G1, D ℓ,0 = τ ℓ • G2, and ρ ℓ = (σ ℓ,j τ ℓ,j )j, where -From G0 to G3, σ ℓ , τ ℓ $ ← Z 3 q ; -From G4, for ℓ ∈ L1, σ ℓ $ ← (Z * q ) 3 , ρ ℓ ← ρ ℓ • v1, for ρ ℓ $ ← Z * q , τ ℓ ← ρ ℓ • (v1,j/σ ℓ,j )j; -From G7, for ℓ ∈ L2, τ ℓ $ ← (Z * q ) 3 , ρ ℓ ← ρ ℓ • v2, for ρ ℓ $ ← Z * q , σ ℓ ← σ ℓ • (v2,j/τ ℓ,j )j.
5 Inner-Product Functional Encryption with a Selector

The above 2-client IPFE works for all possible inputs from both data providers. However, one may be interested in a very specific sub-case where the second data provider's vector is actually a selector with half of its coefficients equal to one, the other half being zero, i.e., DP 1 's input is

x = x 0 ||x 1 , DP 2 's input y = (1 -b) n ||b n
, with b ∈ {0; 1}, and the functional coefficients are α = α 0 ||α 1 , so that the decryption key dk α helps to decrypt

x b • α ⊤ b .
For such a particular case, the above scheme would lead to a long ciphertext for y, whereas it just contains a bit b. We thus propose a more compact scheme, with a dedicated security result.

Description

Let us first see how the above general scheme can be improved in the specific case of IPFE with a selector:

Setup(1 κ ). From a pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q) of
appropriate size with respect to the security parameter κ, the function chooses random dual orthogonal matrices

B = (b i ) i $ ← GL 9 (Z q ) and B * = (b * i ) i ← (B -1 ) ⊤ , which define the bases (B, B * ). One gener- ates secret vectors S = (s i , s ′ i ) n i=1 $ ← ((Z 2 q ) 2 ) n and T = (t, t ′ ) $ ← (Z 2 q ) 2 .
The encryption key ek 1 of DP 1 is set to (B, S), the encryption key ek 2 of DP 2 is set to (B * , T), and the secret key is set to sk = (S, T). The public parameters are just PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q), together with two collision-resistant hash functions H, H ′ into Z q ; KeyGen(sk, α). For a vector α = (α 0 , α 1 ) ∈ (Z n q ) 2 , DP 1 and DP 2 generate the functional decryption key

dk α ← d = n i=1 α 0,i (s i,1 t 1 , s i,2 t 2 ) + α 1,i (s ′ i,1 t ′ 1 , s ′ i,2 t ′ 2 ) ∈ Z 2 q
Encrypt(ℓ, ek, z), for a label ℓ, where ek is either ek 1 or ek 2 , and z is either

x = (x 0 , x 1 ) ∈ (Z n q ) 2 or b, one derives λ 1 = H(ℓ), λ 2 = H ′ (ℓ) ∈ Z q : -To encrypt x = (x 0 , x 1 ) ∈ (Z n q ) 2 with ek 1 = (B, S), one generates σ $ ← (Z * q ) 2 , random π i , π ′ i $ ← Z q , and returns C ← (ℓ, C 0 , (C i , C ′ i ) i ), where C 0,j = σ j • G 1 , for j = 1, 2, and for i ∈ [[1; n]]: C i = (π i (b 1 + λ 1 • b 2 ) + x 0,i • b 3 + σ 1 s i,1 • b 5 + σ 2 s i,2 • b 7 ) • G 1 = (π i • (1, λ 1 ), x 0,i , 0, σ 1 s i,1 , 0, σ 2 s i,2 , 0, 0) B = (π i • (1, λ 1 ), x 0,i , 0, (σ j s i,j , 0) j , 0) B C ′ i = (π ′ i • (1, λ 2 ), x 1,i , 0, (σ j s ′ i,j , 0) j , 0) B -To encrypt b ∈ {0, 1} with ek 2 = (B * , T), one generates τ $ ← Z 2 q , random µ 1 , µ 2 $ ← Z q , and returns D ← (ℓ, D 0 , D 1 , D 2 )
, where D 0,j = τ j • G 2 , for j = 1, 2, and:

D 1 = (µ 1 (λ 1 b * 1 -b * 2 ) + (1 -b) • b * 3 + τ 1 t 1 • b * 5 + τ 2 t 2 • b * 7 ) • G 2 = (µ 1 • (λ 1 , -1), 1 -b, 0, τ 1 t 1 , 0, τ 2 t 2 , 0, 0) B * = (µ 1 • (λ 1 , -1), 1 -b, 0, (τ j t j , 0) j , 0) B * D 2 = (µ 2 • (λ 2 , -1), b, 0, (τ j t ′ j , 0) j , 0) B * Decrypt(dk α , C, D).
Due to the orthogonality of the bases B and B * , with

g t = e(G 1 , G 2 ), for i ∈ [[1; n]] one has C i × D 1 = [π i µ 1 (λ * 1 -λ 1 ) + (1 -b)x 0,i + σ 1 τ 1 s i,1 t 1 + σ 2 τ 2 s i,2 t 2 ] Gt C ′ i × D 2 = [π ′ i µ 2 (λ * 2 -λ 2 ) + bx 1,i + σ 1 τ 1 s ′ i,1 t ′ 1 + σ 2 τ 2 s ′ i,2 t ′ 2 ] Gt
If the labels are the same,

C i × D 1 = g (1-b)x 0,i t • j (g s i,j t j t ) σ j τ j and C ′ i × D 2 = g bx 1,i t • j (g s ′ i,j t ′ j t ) σ j τ j . Then, n i=1 (C i × D 1 ) α 0,i × (C ′ i × D 2 ) α 1,i = n i=1 g (1-b)α 0,i x 0,i t • j (g α 0,i s i,j t j t ) σ j τ j • g bα 1,i x 1,i t • j (g α 1,i s ′ i,j t ′ j t ) σ j τ j = g α b •x ⊤ b t • j (g d j t ) σ j τ j = g α b •x ⊤ b t • j e(C 0,j , D 0,j ) d j
One can thus get g

α b •x ⊤ b t
and extract the discrete logarithm

α b • x ⊤ b .
This scheme drastically reduces second data provider's ciphertext sizes, from being linear in n to a small constant size.

Security Analysis

Theorem 12. Our above construction from Section 5.1 satisfies ord-IND indistinguishability against adaptive adversaries in time t with:

Adv ind (A) ≤ (2N • (12Qn(N + 1) + 25) + 4) • Adv sxdh (t) + 3N/q
where N is the number of different labels the adversary got encryptions for, and Q the number of labels queried to the hash function.

We stress that in the ord-IND indistinguishability we assume LoREncrypt 2 is always asked first. The full proof is provided in appendix C.

Privacy-Preserving Money-Laundering Detection

For money-laundering detection, based on the work of [SNY + 16] that presented a method for this detection on cleartexts with no privacy, which we now provide, we consider the graph where the vertices are all the bank accounts, and oriented edges represent transactions between them, with a weight corresponding to the amount of money sent. These can be considered at regular time periods. We can apply our above two-client inner-product functional encryption scheme to calculate the similarity of two nodes u and v belonging to distinct banks, the two data providers DP 1 and DP 2 respectively, over a time-period. One wants to compute:

σ in (u, v) = ⟨w u,in , w v,in ⟩ σ out (u, v) = ⟨w u,out , w v,out ⟩ σ(u, v) = σ in (u, v) × σ out (u, v)
where the vectors w u,in and w u,out are normalized N -vectors that can be generated by DP 1 , and w v,in and w v,out can be generated by DP 2 . Indeed, using the notations introduced in section 1, w u,in is the normalized vector of dimension N , of all the incoming transactions, where N is the total number of possible account numbers, and similarly for the other vectors. One may only focus on the computation of ⟨w u,in , w v,in ⟩, as the same can be done on ⟨w u,out , w v,out ⟩.

While we want all the inner products between all the nodes, our privacy-preserving technique only allows to combine one vector with a unique other vector, both encrypted under the same label. For each pair of nodes (u, v), one thus defines a label λ u,v , then DP 1 and DP 2 encrypt wu,in and wv,in respectively under λ u,v , and the DC can compute the inner-product with the functional decryption key for the Identity matrix. This might look costly, because of the quadratic number of ciphertexts. On the other hand, providing N 2 inner products between N vectors would leak too much information on the inputs, whatever the protocol. One can thus exploit these multiple encryptions of the same vectors to add independent small noise to non-zero components, in the same vein as differential privacy. The level of noise to be introduced is out of the scope of this analysis, but this illustrates the main advantage of labels, and thus of the use of MCFE instead of MIFE, that would not allow the additional protection.

Communication Complexity

Let us evaluate the communication complexity for the banks and the regulation organisation, when DP 1 manages N 1 accounts and DP 2 manages N 2 , among a global number of accounts N , as incoming/outgoing transactions can be with other banks. Our security model indeed requires making ciphertexts for a given label (u, v) to allow combination for the inner-product evaluation. As such, the vector of weights for all incoming and outgoing transactions for each node will have to be encoded differently for each similarity calculation with a new node, meaning DP 1 would have to send 2N 1 N 2 ciphertexts for each vertex u (because both its in and out weight vectors have N components) of their N 1 big set to DC for a comparison with DP 2 's nodes. Symmetrically, DP 2 would have to send 2N 1 N 2 N -long vectors of ciphertexts. In the end, for the comparisons between DP 1 and DP 2 , DC receives 4N N 1 N 2 ciphertexts. We hereafter discuss optimizations to reduce these communication costs when there are many bank accounts and weight vectors are sparse. Another method to reduce these communications can be for each bank to preselect accounts, for instance with a threshold on the amount of transactions transiting through them. Other methods such as the complementary formula growing with a node's amount of transactions and similarity between the amount in its incoming and outgoing transactions presented in [SNY + 16] can also help for this preselection of vertices of interest. The banks should then decide for themselves to which extent it is acceptable to let such a selection of accounts leak to other banks collaborating in the comparison.

Our non-optimized version of the protocol is best for small set sizes or graphs with a big connectivity, as is shown in figure 5, in which we reported [SNY + 16]'s parameter sets for N and n, the number of accounts in the system and their connectivity respectively, and took N 1 = N 2 = N i , the individual bank sizes, to be a fifth of N . The graph hashing method results in a smaller communication size for all their parameter sets.

Reduced Graph with Hashing

Intuition Making similarity calculations in a large graph is by definition an application where the number of comparisons has a quadratic complexity in the number of tested nodes. In money laundering detection, where the graphs considered can be huge, this can become humongous, even though bank infrastructures are considerable. Either a first filtering of nodes of interest can be made, to get reasonable communications, or else we also suggest the following optimization when there are many nodes with a small connectivity (mean number of neighbors a vertex has). The main idea here is to work on much smaller graphs than the original one, even though that means having to consider several ones. To do this we hash the nodes into a smaller space, adding some of them together in common nodes, and perform the similarity calculations on the added weight vectors of nodes landing on the same hash values. We then select nodes where the similarity is in the suspicious range [θ; 1] for at least τ of the hashed graphs, relying on the weight vectors' sparseness. In the following section we detail the probability calculations we made from the supposed sparseness of weight vectors, to deduce the appropriate size of the set nodes should be hashed into, and the corresponding number of hash functions necessary to make the detection accurate.

Building on the idea exposed in presentation [GGJ + 20], similar to Bloom filter techniques, we take r hash functions

H 1 , . . . , H r from [[1; N ]] to [[1; 2 m ]
], and for each function H s we build the corresponding reduced vertices set V s = {H s (v); v ∈ V } from the original N -long set of vertices V , and each vertex v in this new set gets, for the incoming transactions, the sum of the normalized weight vectors of incoming transactions of all the V vertices that H s projected onto v, written w s,v,in . The same goes for the out weight vectors w s,v,out . As we are working with two data providing banks DP 1 and DP 2 , who respectively own N 1 and N 2 nodes, they will only add up vectors of nodes they own in this smaller graph space. We will write V 1 (resp. V 2 ) DP 1 's (resp. DP 2 's) set of vertices, and for each hash function index s, V s,1 (resp. V s,2 ) the set of vertices they are hashed into.

In this version, one makes r computations, one for each hash function reduction, to evaluate to vertices' similarity. In each computation, vectors are still of size N , and if a data provider (a bank) DP 1 wants to compare all their accounts with another bank DP 2 's, they then need to send DC 2r2 2m N ciphertexts, and DP 2 2r2 2m N , so DC should receive r2 2(m+1) N ciphertexts (of constant size, since this is for each component). This thus has to be compared with 4N N 1 N 2 to select the best method.

Parameter calculations We build the following probability model on the bank account data used, in order to set appropriate parameters for the graph hashing technique. We model weight vectors' sparseness with Bernoulli variables, and make sure that for a given inner-product in the original graph, at least σ of the inner-products in the hashed graphs will be with added vectors hashed to the same node that have disjoint supports, so that they do not influence the resulting inner-products. We will select pairs of nodes for which at least τ ≥ σ of the inner-products on hashed graphs gave a result in the detection range [θ; 1] from [SNY + 16]. For σ, we take at least half of the number of hash functions to avoid false positives.

Let (Ω, A, P ) be a probability space, and, to model weight vectors'sparseness, X v,i : Ω → {0; 1}, E → 1 -δ w v,i ,0 , be the random variable taking value 1 if the i-th component of w v from the original graph is non-zero, else 0. X v,i follows a Bernoulli distribution B n N , where n can be seen as the connectivity of the graph (i.e. the number of neighbors of each node) for either in or out transactions. Our optimization will take advantage of having n ≪ N in our use-case.

It will also exploit the random choice of the hash functions that combine totally independent nodes from the original graph. We define the sum X v = N k=1 X v,k , following the binomial distribution B N, n N (as the X v,k are considered be independent), which gives the number of non-zero components in the vector. Let us set: Z v,in,i : Ω → [0; 1], E → w v,i (resp. Z v,out,i ) as the random variable which for v ∈ V takes the value of w v,in (resp. w v,out )'s i-th component, following a law Z. This variable also models weight vectors'sparseness, but instead of taking 0 or 1 values to get the weight vectors' supports, it more precisely takes the transaction amounts inside the weight vectors.

Let:

Y s,v,l : Ω → [[0; N -1]], E → u∈V l u̸ =v
δ Hs(u),Hs(v) be the random variable which gives, for a vertex v ∈ V l (l ∈ {1; 2}), the number of other vertices from V l which H s maps to the same node as v. Y s,v,l

$ ← B N l -1, 1 2 m ,
and is assumed independent of other Y s ′ ,v ′ ,l ′ 's, and from the X and Z above random variables. Let:

X s,v,in,i,l : Ω → {0; 1}, E → 1 -δ x∈V l Hs(x)=Hs(v)
x̸ =v w x,in,i ,0 (or respectively X s,v,out,i,l ) be the boolean random variable which tells whether the i-th component of the sum of the weight vectors added to v's weight vector in hashed graph s, from DP l 's vertex set, x∈V l ,Hs(x)=Hs(v),x̸ =v w x , is null or not. For them not to perturb the inner-product calculation, we will want them to be null on components with transactions on our two original vectors of interest w a and w b , and on the other components, we will want them to be null on one or the other of the destination vectors. We write X s,v,in,l = N i=1 X s,v,in,i,l (and with out respectively), the number of non-null component in the sum of vectors hashed to the same node as v, excluding v.

For Let Z s,v,in,l : Ω → Z N q , E → x∈V l ,Hs(x)=Hs(v),x̸ =v w x,in (respectively Z s,v,out,l : Ω → Z N q , E → x∈V l ,Hs(x)=Hs(v),x̸ =v w x,out ), for all v ∈ V l , be the random variable, which gives the vector of normalized weights from other nodes in the original data owner's graph added with v's normalized weight vector.

a ∈ V 1 , b ∈ V 2 , and s ∈ [[1; r]] such that H s (a) = u ̸ = v = H s (b
It is a sum of Y s,v,l random variables of the original weight vectors following the distribution Z. As such, the probability that a component of Z s,v,in,l (or Z s,v,out,l ) is equal to 0 is

p z,l = P (Z s,v,in,i,l = 0) = 1 - n N N l 2 m -1
.

The expected value of X s,v,in,l is bounded by nN l 2 m , and is equal to

N 1 -1 -n N N l 2 m -1 ,
assuming its components are independent in our model. The same goes for out vectors of course. Also, the probability that Z s,a,in,1 has a separate support from the one of Z s,b,in,2 , meaning ⟨

x∈V 1 Hs(x)=u x̸ =a w x,in ;
x∈V 2 Hs(x)=v x̸ =b w x,in ⟩ would be null, is:

P (∀i ∈ [[1; N ]], z s,a,in,i,1 z s,b,in,i,2 = 0) = (p z,1 + p z,2 -P ((z s,a,in,i,1 = 0) ∩ (z s,b,in,i,2 = 0))) N = 1 - n N N 1 2 m -1 + 1 - n N N 2 2 m -1 -1 - n N N 1 +N 2 2 m -2 N
Similarly, The probability that Z s,a,in,1 and Z s,b,in,2 have disjoint supports, but also Z s,a,in,1 and w b,in , and Z s,b,in,2 and w a,in , resulting in null ⟨w a,in ;

x∈V 2 Hs(x)=v x̸ =b w x,in ⟩ and ⟨w b,in ;

x∈V 1 Hs(x)=u x̸ =a w x,in ⟩, which we will call event A in , is, writing q = 1 -n N , q ′ = 1 -n ′ N , supposing vectors w a,in and w b,in each have n ′ non-zero components, with uniformly distributed indices, knowing that even if H s (a) = H s (b), V 1 and V 2 being disjoint grant the independence of Z s,a,in,1 and Z s,b,in,2 :

P (A in ) = P (∀i ∈ [[1; N ]], (z s,a,in,i,1 z s,b,in,i,2 = 0) ∩ (w b,in,i z s,a,in,i,1 = 0) ∩ (w a,in,i z s,b,in,i,2 = 0)) = q N 1 2 m -1 + q N 2 2 m -1 -q N 1 +N 2 2 m -2 q ′ + q N 1 2 m -1 -q ′ q N 1 2 m -1 q ′ + q N 2 2 m -1 -q ′ q N 2 2 m -1
N again with our independence assumptions. This gives the expected proportion of the r hash functions for which all the vectors hashed to the same value as our two vectors of interest in the original graph are cancelled out in the inner product for a given hash function. Analogously, P (A out ) = P (A in ) = p A . We will be interested in having A in and A out happen for the same hash functions, and approximating in and out vectors' weights as independent, and calling B the event where both A in and A out happen for a given hash function, p B = P (B) = P (A in )P (A out ) = p 2 A . Relating this with the birthday paradox, with the more restrictive expectation that none of the n(N 1 +N 2 ) 2 m draws for all the non-null coordinates of nodes hashed to the same bucket (and approximating one vector's non-null components will not land in the same place), whereas in our case we do not care about some vector components being added together if they get cancelled out with a null component in the inner-product, we give the following lower bound on p A :

p A ≥ e -n 2 (N 1 +N 2 ) 2 2 2m+1 N . So if we want to have p B = p 2 A ≥ 0.95, we can thus take: m ≥ log 2 (n) + log 2 (N 1 + N 2 ) - 1 2 (log 2 (N ) + log 2 (ln( 1 0.95 )) -1)
, and we will take m just above that limit. With n = 0.14, N i = 2000 and N = 10000, we can thus take m = 6. We choose values for m using the birthday paradox approximation and then calculate the exact resulting probabilities p A and p B , with results shown in figure 4. Considering the binomial random variable with probability p B , and r (the number of hash functions) repetitions, the probability of having at least σ ≥ 2 successes (the outcome B) out of the r hash functions (the expected number of successes being rp B ), which we will write 1 -F (σ -1, r, p B ), where F is the cumulative distribution function of the binomial law, is greater than the following Chernoff bound, for σ ≤ rp B + 1:

1 -F (σ -1, r, p B ) ≥ 1 - rp B σ -1 σ-1 e σ-1-rp B (1)
Let c be our lower bound on the confidence interval of having at least σ successes B for one of the r hash functions. We choose the minimal r such that the right member of inequality 1 is greater than c, taking σ = ⌈r/2⌉, meaning we want to be sure to have relevant result on at half of the hash functions, as we will take the majority output and want to avoid having false positives. We show the results in figure 5 (whose Python code is provided in appendix E) for σ = ⌈r/2⌉ , using N and n parameters from [SNY + 16]. #C 0 is the number of ciphertexts to be sent without optimizations and #C H with these optimizations. If event B happens, then:

⟨w a,in + Z s,a,in,1 ; w b,in + Z s,b,in,2 ⟩ × ⟨w a,out + Zs,a,out,1; w b,out + Z s,b,out,2 ⟩ = ⟨w a,in ; w b,in ⟩ × ⟨w a,out ; w b,out ⟩
is in [0; 1], and we will deem a and b suspicious if it is in [θ, 1], where θ was taken equal to 0.2 in [SNY + 16].

To make sure our above theoretical method yielded good results in practice, we compared its results to those from the experiments of [SNY + 16], with their parameter sets and our suggested corresponding r and m from figure 4. Because the theoretical approach was pessimistic when using the birthday paradox approximation, we found that we could lower m to 3 on the first set and still get good results, and recorded these in figure 5. We also empirically adapted the n N m pA pB Ni r c #C0 #CH 0.36 10 3 5 0.99 0.99 200 16 0.95 1.6E+08 6.6E+07 0.11 10 4 5 0.99 0.99 2000 16 0.96 1.6E+11 6.6E+08 0.14 10 4 6 1.0 0.99 2000 16 0.96 1.6E+11 2.6E+09 Fig. 4. parameters and communications comparison with or without the hash functions optimization. n is the average number of other accounts one account has transactions with, N the total number of existing bank accounts, Ni the number of accounts each of the two banks controls, m is the bit size of the space each hash function maps into, pA gives, for one graph hashing and two nodes in the original graph, the probability that their in (or out) scalar product in the hashed graph is equal to its value in the original graph, and pB gives the probability that this both happens for their in and out inner-products. r is the number of hash functions required so that we have a resulting c confidence interval of having this happen for at least half of the hash functions, for a given node in the original graph, and thus of detecting similar nodes. #C0 is the number of ciphertexts in the communication without the hashing strategy, and #CH is this communication with the hashing technique. We took input n and N parameter sets from in [SNY + 16] with Ni = N/5. threshold τ on the number of hash functions we need a positive result from to sort a node as positive, and show the results in the figure, using our script in appendix E. Because of the empirical variations on m, yielding the r parameter, we recorded the resulting communication sizes in figure 6, to see when the graph hashing technique was interesting compared with the standard procedure. False negative rate with h. 0.041 0.018 0.031 Fig. 5. We used a detection threshold θ = 0.2 as in [SNY + 16], and more generally their three parameter sets. We chose τ empirically, above the limit of r/2, and also modified m empirically when we saw the experiments still worked with a less pessimistic bound than the birthday paradox one; it can be adapted depending on the desired sensitivity versus fall-out tradeoff. Sensitivity gives the true positive rate, fall-out the false positive rate. These are given as an average on 50 dataset generations.

n N m pA pB Ni r c #C0 #CH 0.36 10 3 3 0.91 0.83 200 32 0.95 1.6E+08 8.2E+06 Fig. 6. parameters and communications comparison with or without the hash functions optimization from an empirical m on the first set and its corresponding theoretical number of hash functions r, and success probabilities.

Our expermiments confirm that using the hashing technique is interesting on all parameter sets from [SNY + 16]. We show that our hashing parameters from figure 4 give very similar detection rates as the standard method, as showed in figure 5.

Optimization on the number of ciphertexts for null edges would reveal information

One could remark that in the weight vectors for this use-case, many components are set to zero as each bank account will supposedly only communicate with a small portion of all existing bank accounts. One could suggest using similar techniques as in the selector instantiation of our scheme to use only one ciphertext for all these null components. However, as the other data provider in the computation would have to encode all corresponding ciphertexts with the same label, this would leak information about which accounts each one of them is communicating with, which would not work out in this use-case. If public information can cut out groups of bank accounts, the two data providers might as well agree on it together from the start to reduce vector sizes. Game G 7 : In case x * = 0, then, the Subspace Indistinguishability Theorem 3 enables the replacement of the y * coordinate in D * with 0 since the corresponding coordinate in C * is null and the D * 's has random components at the beginning of the vector, and then using the same theorem again we replace the zero in the 5-th coordinate of C * with a 1, using the now null fifth component of D * , and the randomness in one of the first two components of C * . In this case, we have: S 6 -S 7 ≤ 2Adv ddh G 1 (t) + 2Adv ddh G 2 (t). Game G 8 : One now duplicates the 1 from the 5-th component of C * to the 4-th using the Replication Lemma 7. This also negatively adds the 4-th components at the 5-th positions of D i vectors. The two games are perfectly indistinguishable: S 7 = S 8 . Game G 9 : One applies twice the Indexing Lemma 6, between λ * and every possible label λ i ̸ = λ * , iteratively, to first on (B * , B) to replace each -b i in the 5-th components of D i by 0, while all the 5-th components of the C i are 0, and then on (B, B * ) to replace the 0 in the 5-th components of C i by a i , while all the 5-th components of the D i are 0. One gets

S 8 -S 9 ≤ 2QN • (Adv ddh G 1 (t) + Adv ddh G 2 (t)
). Game G 10 : One now swaps the 5-th component x * y * and the 4-th component 0 of D * . This easily works as all the C i and C * vectors have identical 4-th and 5-th components, using the Swapping Lemma 5, with the first two components for randomness: S 9 -S 10 ≤ 2 • Adv ddh G 2 (t). Game G 11 : One then withdraws the 4-th components from the 5-th components in C * and the C i 's, while the null 5-th components of D i 's and D * are added to the 4-th components, using the Replication Lemma 7. This game is perfectly indistinguishable from the previous one: S 10 -S 11 = 0.

The global probability difference is bounded by 0 + 2

• Adv ddh G 1 (t) + 2N Q • Adv ddh G 2 (t) + 0 + 2N Q • Adv ddh G 1 (t) + 2(Adv G 1 (t) + Adv G 2 (t)) + 0 + 2N Q • (Adv ddh G 1 (t) + Adv ddh G 2 (t)) + 2 • Adv ddh G 2 (t) + 0 = 4 • (N Q + 1) • (Adv ddh G 1 (t) + Adv ddh G 2 (t)) ≤ 8 • (N Q + 1) • Adv sxdh (t).
B Proof of Theorem 11 (Indistinguishability of the 2-Client IPFE)

Proof. The security proof follows the sequence of games presented on Figure 2.

Game G 0 : This is the real game with x ℓ and y ℓ encrypted in Encrypt-queries: one starts with a pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), with random dual orthogonal matrices B and B * of dimension 12 that define (B, B * ), and two secret matrices S, T $ ← (Z 3 q ) n . One sets the encryption keys ek 1 ← (B, S) and ek 2 ← (B * , T), and the secret key sk ← (S, T). Then, the public parameters PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q) are provided to the adversary.

-For the query OKeyGen(α k ), with α k ∈ Z n q , one outputs

dk α k ← d k = α k,i (s i,1 t i,1 , s i,2 t i,2 , s i,3 t i,3 ) -For a query LoREncrypt 1 (λ ℓ , x 0 ℓ , x 1 ℓ ), one first derives λ ℓ,i = H(λ ℓ , i) ∈ Z q , for i ∈ [[1; n]], and then outputs C ℓ ← (λ ℓ , C ℓ,0 , (C ℓ,i ) i ) where C ℓ,0,j = σ ℓ •G 1 , for a random σ ℓ $ ← (Z * q ) 3 , and, for random π ℓ,i $ ← Z q , ∀i ∈ [[1; n]], C ℓ,i = (π ℓ,i • (1, λ ℓ,i ), x b ℓ,i , 0, 0, (σ ℓ,j s i,j , 0) j , 0) B -For a query LoREncrypt 2 (λ ℓ , y 0 ℓ , y 1 ℓ ), one first derives λ ℓ,i = H(λ ℓ , i) ∈ Z q , for i ∈ [[1; n]], and then outputs D ℓ ← (λ ℓ , D ℓ,0 , (D ℓ,i ) i ) where D ℓ,0,j = τ ℓ • G 2 , for a random τ ℓ $ ← (Z * q ) 3
, and, for random µ ℓ,i

$ ← Z q , ∀i ∈ [[1; n]], D ℓ,i = (µ ℓ,i • (λ ℓ,i , -1), y b ℓ,i , 0, 0, (τ ℓ,j t i,j , 0) j , 0) B *
Then we consider S 0 = Pr[β = b], where β $ ← {0, 1} if for some α k asked to the OKeyGenoracle and some (x 0 ℓ , x 1 ℓ ), (y 0 ℓ , y 1 ℓ ) asked to the LoREncrypt oracle one has the inequality α k,i x 0 ℓ,i y 0 ℓ,i ̸ = α k,i x 1 ℓ,i y 1 ℓ,i , which is a non-legitimate attack, or β ← b ′ , as this is a legitimate attack. Our goal is to show that S 0 is close to 1/2. In the following games, we alter the simulation of all the LoREncrypt-oracles. We denote N the number of distinct λ ℓ , but anticipate by programming at most Qn values of λ ℓ,i (among a select set), and K the number of OKeyGen-queries. Additionally, we denote L 1 the set of indices ℓ where LoREncrypt 1 is asked first, and L 2 the set of indices where LoREncrypt 2 is asked first. Their sizes are respectively N 1 and N 2 . Game G 1 : We first deal with all the indices ℓ ∈ L 1 such that LoREncrypt 1 (λ ℓ , x 0 ℓ , x 1 ℓ ) is asked first. We apply the Product-Preserving Lemma 8 on the vectors (x ℓ,i , 0) and (y ℓ,i , 0) to replace them into (0, 1) and the preserved product (0, x ℓ,i y ℓ,i ). As we have to do it N 1 times, each with a guess on the correct label:

S 0 -S 1 ≤ 8QN 1 (N n + 1) • Adv sxdh (t).
Game G 2 : We apply again the Product-Preserving Lemma 8 on the vectors (σ ℓ,j s i,j , 0) and (τ ℓ,j t i,j , 0) to replace them into (0, 1) and the preserved product (0, σ ℓ,j τ ℓ,j s i,j t i,j ), successively for j = 1, 2, 3:

S 1 -S 2 ≤ 24QN 1 (N n + 1) • Adv sxdh (t)
. Game G 3 : We now formally replace z ℓ,i ← x ℓ,i y ℓ,i , and τ ℓ,j ← ρ ℓ,j /σ ℓ,j , for j = 1, 2, 3. This makes no difference:

S 2 = S 3 . Game G 4 : We replace the random choice ρ ℓ $ ← Z 3 q by ρ ℓ in the span of v 1 = (v 1,1 , v 1,2 , v 1,3 ), for v 1,1 = 1 but random v 1,2 , v 1,3 $ ← Z q : ρ ℓ = ρ ℓ • v 2 for ρ ℓ $ ← Z q . The simulation of D ℓ,0 = (ρ ℓ,1 /σ ℓ,1 • G 2 , ρ ℓ,2 /σ ℓ,2 • G 2 , ρ ℓ,3 /σ ℓ,3 • G 2 ) does not need to know ρ ℓ , but just ρ ℓ • G 2 , as the vector σ ℓ is known. The simulation of the D ℓ,i do not either, but just ρ ℓ • G 2 too.
Under the DDH assumption in G 2 , this game is indistinguishable from the previous one, after N 1 successive changes. See Lemma 13. Hence, S 4 -S 3 ≤ N 1 • Adv ddh G 2 (t) + N 1 /q. Game G 5 : Since the 4-th, the 7-th and the 9-th components of C ℓ,i vectors are all identical to 1, one can successively swap elements from the 7-th to the 4-th positions, and from the 9-th to the 4-th positions in D ℓ,i to get

c ℓ,i = z b ℓ,i + ρ ℓ j v 1,j s i,j t i,j
Applying the Swapping Lemma 5, one gets S 4 -S 5 ≤ 4 • Adv ddh G 2 (t). Game G 6 : Since the 7-th and the 9-th components of the D ℓ,i vectors are null, we use the Replication Lemma 7 twice to withdraw the 4-th component of the C ℓ,i 's, 1, to their 7-th and then 9-th components, all the while adding zeros to the 4-th component in the D ℓ,i 's. This is perfectly indistinguishable from the previous game: S 5 -S 6 = 0. Game G 7 : We now do the same as the previous sequence, but for the indices ℓ such that LoREncrypt 2 (λ ℓ , x 0 ℓ , x 1 ℓ ) is asked first, where we replace the random choice ρ ℓ

$ ← Z 3 q by ρ ℓ in the span of v 2 = (v 2,1 , v 2,2 , v 2,3 ), for v 2,1 = 1 but random v 2,2 , v 2,3 $ ← Z q : ρ ℓ = ρ ℓ • v 2 for ρ ℓ $ ← Z q .
We can additionally formally replace r i,j ← s i,j t i,j :

∀ℓ ∈ L 1 c ℓ,i = z b ℓ,i + ρ ℓ j v 1,j r i,j = z b ℓ,i + ρ ℓ • r i v ⊤ 1 ∀ℓ ∈ L 2 c ℓ,i = z b ℓ,i + ρ ℓ j v 2,j r i,j = z b ℓ,i + ρ ℓ • r i v ⊤ 2
We thus have the same distance as between G 0 and G 6 , but with at most N 2 labels and opposite groups:

S 6 -S 7 ≤ 32QN 2 (N n + 1) • Adv sxdh (t) + (4 + N 2 ) • Adv ddh G 1 (t) + N 2 /q.
In this game, in the setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), one starts with random dual orthogonal matrices B and B * of dimension 12 that define (B, B * ), two random vectors v 1 and v 2 with v 1,1 = v 2,1 = 1, and a secret matrix R $ ← (Z 3 q ) n . The public parameters PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q) are provided to the adversary.

-For the query OKeyGen(α k ), with α k ∈ Z n q , one outputs

dk α k ← d k = (d k,j = α k,i r i,j ); -For ℓ ∈ L 1 : a query LoREncrypt 1 (λ ℓ , x 0 ℓ , x 1 ℓ ) is first asked for the label λ ℓ . One asks for OEncrypt 1 (λ ℓ ): one first derives λ ℓ,i = H(λ ℓ , i) ∈ Z q , for i ∈ [[1; n]], and outputs C ℓ ← (λ ℓ , C ℓ,0 , (C ℓ,i ) i ), where C ℓ,0 = σ ℓ • G 1 , for random σ ℓ $ ← (Z * q ) 3
, and for i = 1, . . . , n, with random π ℓ,i

$ ← Z q , C ℓ,i = (π ℓ,i • (1, λ ℓ,i ), 0, 1, 0, (0, 0) j , 0) B When LoREncrypt 2 (λ ℓ , y 0 ℓ , y 1 ℓ
) is queried, one asks for OEncrypt 2 (λ ℓ , z ℓ ), where z ℓ = (x ℓ,i y ℓ,i ) i and outputs D ℓ ← (λ ℓ , D ℓ,0 , (D ℓ,i ) i ), where

D ℓ,0 = ρ ℓ • (v 1,1 /σ ℓ,1 , v 1,2 /σ ℓ,2 , v 1,3 /σ ℓ,3 ) • G 2 for random ρ ℓ $ ← Z q , and for i = 1, . . . , n, with random π ℓ,i $ ← Z q , D ℓ,i = (π ℓ,i • (1, λ ℓ,i ), 0, z b ℓ,i + ρ ℓ • r i v ⊤ 1 , 0, (0, 0) j , 0) B * -For ℓ ∈ L 2 : the simulation is symmetrical.
For a legitimate attack, we must have

z 0 ℓ α ⊤ k = α k,i z 0 ℓ,i = α k,i z 1 ℓ,i = z 1 ℓ • α ⊤
k for all the functional key queries α k : all z 0 ℓ -z 1 ℓ are orthogonal to all α k . Game G 8 : We eventually replace z b ℓ by z 0 ℓ in all the encryption:

∀ℓ ∈ L 1 c ′ ℓ,i = z 0 ℓ,i + ρ ℓ • r i v ⊤ 1 ∀ℓ ∈ L 2 c ′ ℓ,i = z 0 ℓ,i + ρ ℓ • r i v ⊤ 2
Since b does not appear anywhere, S 8 = 0. But we also have to prove there is not much difference between G 8 and G 7 : Using Lemma 14, one gets S 8 -S 7 ≤ 2N • Adv sxdh (t) + 2N/q.

We can thus conclude that

S 0 -S 8 ≤ 32QN 1 (N n + 1) • Adv sxdh (t) + (4 + N 1 ) • Adv ddh G 2 (t) + N 1 /q + 32QN 2 (N n + 1) • Adv sxdh (t) + (4 + N 2 ) • Adv ddh G 1 (t) + N 2 /q + 2N • Adv sxdh (t) + 2N/q ≤ (32QN (N n + 1) + 3N + 8) • Adv sxdh (t) + 3N/q Lemma 13. From the view of ρ ℓ • G 2 ∈ G 3
2 , for ℓ = 1, . . . , N , one cannot make the difference between ρ ℓ = ρ ℓ • v, with ρ ℓ $ ← Z q for all ℓ, for some random vector v ∈ Z 3 q with v 1 = 1, and ρ ℓ $ ← Z 3 q for all ℓ, with advantage greater than N • Adv ddh G 2 (t) + N/q.

Proof. For a given ℓ, one can define the hybrid game G ℓ : for some random vector v ∈ Z 3 q with v 1 = 1 -For all indices j ∈ [[1; ℓ]], one chooses a random ρ j $ ← Z * q , and sets

ρ j ← ρ j • v; -For all indices j ∈ [[ℓ + 1; N ]], one chooses ρ j $ ← Z 3 q .
This is clear that in G 0 , all the vectors are random, while in G N , all the vectors are co-linear with v.

Let us consider the following game from some ℓ: from a Decisional Diffie-Hellman instance in

G 2 , U = u • G 2 , V = v • G 2 , and W = w • G 2 , where u, v $ ← Z q and w = uv + δ with either δ $ ← Z q or δ = 0: one chooses random a, b $ ← Z q and set A ← U , B ← a • G 2 + b • U , hence (G 2 , A, B) = v • G 2 with v 1 = 1 v 2 = u v 3 = a + ub
For all indices j < ℓ, one sets, for a random ρ j

$ ← Z * q , ρ j • G 2 = ρ j • (G 2 , A, B) = ρ j • v • G 2
For all indices j > ℓ, one chooses a random ρ j $ ← Z 3 q . For the ℓ-th query, one chooses a random x $ ← Z q and sets

ρ ℓ,1 G 2 ← xG 2 + V = (x + v)G 2 = ρG 2 = ρ ℓ v 1 G 2 ρ ℓ,2 G 2 ← xU + C = (xu + w)G 2 = (ρu -δ)G 2 = (ρ ℓ v 2 -δ)G 2 ρ ℓ,3 G 2 ← axG 2 + bxU + aV + bW = (ax + bxu + av + bw)G 2 = (ρ(a + bu) -δb)G 2 = (ρ ℓ v 3 -δb)G 2 where ρ ℓ = x + v. If δ = 0, ρ ℓ = ρ ℓ • v, for a random ρ ℓ as x $ ← Z q . Then we are in G ℓ , unless x = -v. When δ $ ← Z q , as b $ ← Z q , ρ ℓ is random in Z 3
q . So we are in G ℓ-1 .

Lemma 14. S 7 -S 8 ≤ 2N • Adv sxdh (t) + 2N/q.

Proof. We proceed iteratively on each ℓ, as in [CDG + 18], but in both G 1 and G 2 , which requires a randomness with dimension 3: Game G 7.ℓ.0 This is the previous game, and we deal with the ℓ-th label that is in L b , for the appropriate b, that is learnt from the first query of the adversary.

Game G 7.ℓ.1 We use back ρ ℓ $ ← Z 3 q , instead of the span of v b : c ′ ℓ,i = z b ℓ,i + ρ ℓ • r i v ⊤ b is replaced by c 1 ℓ,i = z b ℓ,i + r i ρ ⊤ ℓ
, with S 7.ℓ.0 -S 7.ℓ.1 ≤ Adv sxdh (t), using the same analysis as in the proof of Lemma 13. Game G 7.ℓ.2 We stop if eventually ρ ℓ is in the plane spanned by v 1 and v 2 : S 7.ℓ.1 -S 7.ℓ.2 ≤ 1/q. Otherwise, denoting v 3 a unitary vector orthogonal to both v 1 and v 2 , we can note ρ ℓ = c 1 v 1 + c 2 v 2 + c 3 v 3 , with c 3 ̸ = 0 mod q. Game G 7.ℓ.3 We replace z b ℓ by z 0 ℓ in the encryption:

c 1 ℓ,i = z b ℓ,i + r i ρ ⊤ ℓ is replaced by c 2 ℓ,i = z 0 ℓ,i + r i ρ ⊤ ℓ .
As in [CDG + 18], we can use the complexity leveraging, by guessing (z 0 ℓ , z 1 ℓ ) to show this makes no difference, by building an adversary that guesses (z 0 ℓ , z 1 ℓ ). We then note S * the success of this new adversary that makes both a correct guess on (z 0 ℓ , z 1 ℓ ) and a correct guess for b with a legitimate attack.

-Step 1: one guesses (z 0 ℓ , z 1 ℓ ), which can either be in (Z q ) 2n or empty if the second encryption query is not asked. There are thus q 2n + 1 possibilities. If the guess is correct, one does not change anything, if this is incorrect, one stops and outputs a random bit. One can note that the advantage in this game is S * 1 = S 7.ℓ.2 /(q 2n + 1), as the good guess is exactly 1/(q 2n + 1), even in case of correct guess of b in a legitimate attack; -Step 2: we can replace r i by

u i = r i + γ(z b ℓ,i -z 0 ℓ,i ) • v 3 , for random γ $ ← Z q , as R = (r i ) i $ ← (Z 3 q ) n
is random and independent of (z 0 ℓ , z 1 ℓ ). We have to check this does not impact the view of the adversary:

• the keys, for all k, are generated as

d k = i α k,i • u i = i α k,i • r i + γ(z b ℓ,i -z 0 ℓ,i ) • v 3 = i α k,i • r i + γ • i α k,i • (z b ℓ,i -z 0 ℓ,i ) • v 3 = i α k,i • r i
as for a legitimate attack, i α k,i (z b ℓ,i -z 0 ℓ,i ) = 0.

• the ciphertexts, for all j ̸ = ℓ are all generated with ρ j = ρ j • v δ , for some δ ∈ {1, 2}. So, with b j = 0, for j < ℓ, and b j = b for j > ℓ:

c j,i = z b j j,i + ρ j • u i • v ⊤ δ = z b j j,i + ρ j • r i + γ(z b ℓ,i -z 0 ℓ,i ) • v 3 • v ⊤ δ = z b j j,i + ρ j • r i • v ⊤ δ • excepted c ℓ,i : c ℓ,i = z b ℓ,i + u i • ρ ⊤ ℓ = z b ℓ,i + u i • ρ ⊤ ℓ + γ(z b ℓ,i -z 0 ℓ,i ) • v 3 • (c 1 v ⊤ 1 + c 2 v ⊤ 2 + c 3 v ⊤ 3 ) = z b ℓ,i + u i • ρ ⊤ ℓ + c 3 γ(z b ℓ,i -z 0 ℓ,i ) • v 3 • v ⊤ 3 = z b ℓ,i + c 3 γ(z b ℓ,i -z 0 ℓ,i ) + u i • ρ ⊤ ℓ = z 0 ℓ,i + u i • ρ ⊤ ℓ if γ = -1/c 3 ,
C i,j =(π i,j (1, λ i ), x i,j , a i,j , 0) B D i =(µ i (λ i , -1), y i , b i , 0) B *
A cannot distinguish between the two cases, for fixed λ * ̸ = λ i , and any x * 1 , . . . , x * n and y * , but unknown random π * 1 , . . . , π * n , µ * :

(0) C * j =(π * j (1, λ * ), x * j , 0, 0) B D * =(µ * (λ * , -1), y * , 0, 0) B * (1) C * j =(π * j (1, λ * ), 0, x * j y * , 0) B D * =(µ * (λ * , -1), 0, 1, 0) B *
with an advantage greater than 2 • (Qn(N + 1) + 3)

• Adv ddh G 1 (t) + 2 • (Qn(N + 1) + 1) • Adv ddh G 2 (t)
), and thus greater than 4 • (Qn(N + 1) + 2) • Adv sxdh (t).

In Figure 7, we present the sequence of games, starting from the real game, where the λ ℓ for ℓ ∈ [[1; N ]] are all the distinct labels, and λ ℓ,1 = H(λ ℓ ), λ ℓ,2 = H ′ (λ ℓ ), with N the total number of distinct labels.

Proof. In this proof we suppose the data consumer DC receives ciphertexts from DP 2 before or at the same time as from DP 1 , to be able to get the product preserving property. The security proof follows the sequence of games presented on Figure 7. In the first game, we rename the vectors in order to simplify the notations in the proof.

Game G 0 : This is the real game with x ℓ and y ℓ encrypted in Encrypt-queries: one starts with a pairing-friendly setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), with random dual orthogonal matrices B and B * of dimension 9 that define (B, B * ), and secret vectors S = (s i ,

s ′ i ) n i=1 = (s i,1 , s i,2 ) 2n i=1 $ ← ((Z 2 q ) 2 ) n and T = (t, t ′ ) = (t k,1 , t k,2 ) 2 k=1 $ ← (Z 2 q ) 2 .
One sets ek 1 ← (B, S), ek 2 ← (B * , T), and sk ← (S, T). Then, the public parameters PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q) are provided to the adversary.

G0 ∀ℓ ∈ [[1; N ]], C ℓ,i = ( • • • | x b ℓ,i 0 |(σ ℓ,j si,j 0 )j| ) D ℓ,k = ( • • • | y b ℓ,k 0 |(τ ℓ,j t k,j 0 )j| ) G1 ∀ℓ, C ℓ,i = ( • • • | 0 x b ℓ,i y b ℓ,⌈i/(2n)⌉ |(σ ℓ,j si,j 0 )j| ) Product-Preserving D ℓ,k = ( • • • | 0 1 |(τ ℓ,j t k,j 0 )j| ) G2 ∀ℓ, C ℓ,i = ( • • • | 0 x b ℓ,i y b ℓ,⌈i/(2n)⌉ |( 0 σ ℓ,j τ ℓ,j si,jt ⌈i/(2n)⌉,j )j| ) Product-Preserving D ℓ,k = ( • • • | 0 1 |( 0 1 )j| ) G3 ∀ℓ, C ℓ,i = ( • • • | 0 z b ℓ,i |( 0 ρ ℓ,j si,jt ⌈i/(2n)⌉,j )j| ) Formal Renaming D ℓ,k = ( • • • | 0 1 |( 0 1 )j| ) G4 ∀ℓ, C ℓ,i = ( • • • | 0 z b ℓ,i |( 0 ρ ℓ vjsi,jt ⌈i/(2n)⌉,j )j| ) Random in Span D ℓ,k = ( • • • | 0 1 |( 0 1 )j| ) G5 ∀ℓ, C ℓ,i = ( • • • | 0 c ℓ,i |( 0 0 )j| ) Swapping D ℓ,k = ( • • • | 0 1 |( 0 1 )j| ) G6 ∀ℓ, C ℓ,i = ( • • • | 0 c ℓ,i |( 0 0 )j| ) Replication D ℓ,k = ( • • • | 0 1 |( 0 0 )j| ) G7 ∀ℓ, C ℓ,i = ( • • • | 0 c ′ ℓ,i |( 0 0 )j| ) b = 0 D ℓ,k = ( • • • | 0 1 |( 0 0 )j| )
The 2 first components of the C ℓ,i and D ℓ,⌈i/(2n)⌉ are always π ℓ,i • (1, λ ℓ,⌈i/(2n)⌉ ) and µ ℓ,⌈i/(2n)⌉ • (λ ℓ,⌈i/(2n)⌉ , -1), for each label ℓ ∈ [[1; N ]], and for i = 1, . . . , 2n. c ℓ,i = z b ℓ,i + ρ ℓ j v k,j si,jt ⌈i/(2n)⌉,j , and In this game, in the setting (G 1 , G 2 , G t , e, G 1 , G 2 , q), one starts with random dual orthogonal matrices B and B * of dimension 9 that define (B, B * ), a random vector v with v 1 = 1, and a secret matrix R $ ← (Z 2 q ) n . We formally replace r i,j ← s i,j t ⌈i/(2n)⌉,j . The public parameters PK ← (G 1 , G 2 , G t , e, G 1 , G 2 , q) are provided to the adversary.

c ′ ℓ,i = z 0 ℓ,i + ρ ℓ j v k,j si,jt ⌈i/(2n)⌉,j . C ℓ,0 = σ ℓ • G1, D ℓ,0 = τ ℓ • G2, where -From G0 to G3, σ ℓ $ ← (Z * q ) 2 , τ ℓ $ ← Z 2 q , and ρ ℓ = (σ ℓ,j τ ℓ,j )j; -From G4, σ ℓ $ ← (Z * q ) 2 , ρ ℓ ← ρ ℓ • v, for ρ ℓ $ ← Z * q , and τ ℓ ← ρ ℓ • (vj/σ ℓ,j )j.
-For the query OKeyGen(α k ), with α k ∈ Z n q , one outputs dk

α k ← d k = (d k,j = α k,i r i,j ); -For ℓ ∈ [[1; N ]]: a query LoREncrypt 2 (λ ℓ , y 0 ℓ , y 1 ℓ )
is first asked for the label λ ℓ . One asks for OEncrypt 2 (λ ℓ ): one derives λ ℓ,i , for i ∈ [[1; 2]], and outputs

D ℓ ← (λ ℓ , D ℓ,0 , (D ℓ,i ) i ), where D ℓ,0 = σ ℓ • G 2 , for random σ ℓ $ ← Z 2
q , and for i = 1, 2, with random µ ℓ,i

$ ← Z q , D ℓ,i = (µ ℓ,i • (1, λ ℓ,i ), 0, 1, (0, 0) j , 0) B * When LoREncrypt 1 (λ ℓ , x 0 ℓ , x 1 ℓ ) is queried, one asks for OEncrypt 1 (λ ℓ , z ℓ ), where z ℓ = (x ℓ,i y ℓ,⌈i/(2n)⌉ ) i and outputs C ℓ ← (λ ℓ , C ℓ,0 , (C ℓ,i ) i ), where C ℓ,0 = ρ ℓ • (v 1,1 /σ ℓ,1 , v 1,2 /σ ℓ,2 ) • G 1 for random ρ ℓ $ ← Z q , and for i = 1, . . . , 2n, with random π ℓ,i $ ← Z q , C ℓ,i = (π ℓ,i • (1, λ ℓ,⌈i/(2n)⌉ ), 0, z b ℓ,i + ρ ℓ • r i v ⊤ , (0, 0) j , 0) B
For a legitimate attack, we must have

z 0 ℓ α ⊤ k = α k,i z 0 ℓ,i = α k,i z 1 ℓ,i = z 1 ℓ • α ⊤
k for all the functional key queries α k : all z 0 ℓ -z 1 ℓ are orthogonal to all α k . Game G 7 : We eventually replace z b ℓ by z 0 ℓ in all the encryptions:

∀ℓ ∈ [[1; N ]] c ′ ℓ,i = z 0 ℓ,i + ρ ℓ • r i v ⊤
Since b does not appear anywhere, S 7 = 0. But we also have to prove there is not much difference between G 7 and G 6 : Using Lemma 16, one gets S 7 -S 6 ≤ 2N • Adv sxdh (t) + 2N/q.

We can thus conclude that

S 0 -S 7 ≤ 24N • (Qn(N + 1) + 2) • Adv sxdh (t) + 2N • Adv sxdh (t) + 4 • Adv ddh G 1 (t) + 3N/q (2N • (12Qn(N + 1) + 25) + 4) • Adv sxdh (t) + 3N/q Lemma 16. S 6 -S 7 ≤ 2N • Adv sxdh (t) + 2N/q.
Proof. We proceed iteratively on each ℓ, as in [CDG + 18]: Game G 6.ℓ.0 This is the previous game, and we deal with the ℓ-th label.

Game G 6.ℓ.1 We use back ρ ℓ $ ← Z 2 q , instead of the span of v: c ′ ℓ,i = z b ℓ,i + ρ ℓ • r i v ⊤ is replaced by c 1 ℓ,i = z b ℓ,i + r i ρ ⊤ ℓ
, with S 6.ℓ.0 -S 6.ℓ.1 = 0, using the same analysis as in game 4. Game G 6.ℓ.2 We stop if eventually ρ ℓ is colinear to v: S 6.ℓ.1 -S 6.ℓ.2 ≤ 1/q. Otherwise, denoting v ′ a unitary vector orthogonal to v, we can write

ρ ℓ = c 1 v + c 2 v ′ , with c 2 ̸ = 0 mod q. Game G 6.ℓ.3 We replace z b ℓ by z 0 ℓ in the encryption: c 1 ℓ,i = z b ℓ,i + r i ρ ⊤ ℓ is replaced by c 2 ℓ,i = z 0 ℓ,i + r i ρ ⊤ ℓ .
As in [CDG + 18], we can use the complexity leveraging, by guessing (z 0 ℓ , z 1 ℓ ) to show this makes no difference, by building an adversary that guesses (z 0 ℓ , z 1 ℓ ). We then note S * the success of this new adversary that makes both a correct guess on (z 0 ℓ , z 1 ℓ ) and a correct guess for b with a legitimate attack.

-Step 1: one guesses (z 0 ℓ , z 1 ℓ ), which can either be in (Z q ) 2n or empty if the second encryption query is not asked. There are thus q 2n + 1 possibilities. If the guess is correct, one does not change anything, if this is incorrect, one stops and outputs a random bit. One can note that the advantage in this game is S * 1 = S 6.ℓ.2 /(q 2n + 1), as the good guess is exactly 1/(q 2n + 1), even in case of correct guess of b in a legitimate attack;

-Step 2: we can replace r i by u

i = r i + γ(z b ℓ,i -z 0 ℓ,i ) • v 3 , for a random γ $ ← Z q , as R = (r i ) i $ ← (Z 2 q )
n is random and independent of (z 0 ℓ , z 1 ℓ ). We have to check this does not impact the view of the adversary:

• the keys, for all k, are generated as

d k = i α k,i • u i = i α k,i • r i + γ(z b ℓ,i -z 0 ℓ,i ) • v ′ = i α k,i • r i + γ • i α k,i • (z b ℓ,i -z 0 ℓ,i ) • v ′ = i α k,i • r i as for a legitimate attack, i α k,i (z b ℓ,i -z 0 ℓ,i ) = 0.
• the ciphertexts, for all j ̸ = ℓ are all generated with ρ j = ρ j • v. So, with b j = 0, for j < ℓ, and b j = b for j > ℓ:

c j,i = z b j j,i + ρ j • u i • v ⊤ = z b j j,i + ρ j • r i + γ(z b ℓ,i -z 0 ℓ,i ) • v ′ • v ⊤ = z b j j,i + ρ j • r i • v ⊤ • excepted c ℓ,i : c ℓ,i = z b ℓ,i + u i • ρ ⊤ ℓ = z b ℓ,i + u i • ρ ⊤ ℓ + γ(z b ℓ,i -z 0 ℓ,i ) • v ′ • (c 1 v ⊤ + c 2 v ′⊤ ) = z b ℓ,i + u i • ρ ⊤ ℓ + c 2 γ(z b ℓ,i -z 0 ℓ,i ) • v ′ • v ′⊤ = z b ℓ,i + c 2 γ(z b ℓ,i -z 0 ℓ,i ) + u i • ρ ⊤ ℓ = z 0 ℓ,i + u i • ρ ⊤ ℓ if γ = -1/c 2 , as v ′ is a unitary vector. Then S * 2 = S * 1 .
And it is straightforward that S * 2 = S 6.ℓ.3 /(q 2n + 1) . Hence, S 6.ℓ.3 = S 6.ℓ.2 . Game G 6.ℓ.4 After having ignored linear vectors, we force ρ ℓ to be in the span of v: S 6.ℓ.3 -S 6.ℓ.4 ≤ 1/q, as above.

D Proof of Lemma 15

It follows the steps in the proof of general Product-Preserving Lemma, though here, for each label λ, there are n C j ciphertexts and one D ciphertext, hence the steps presented in Figure 8.

Proof. Game G 0 : We start from the original distribution, for random π i,j , µ i

$ ← Z q , but any λ i , x i,j , y i , a i,j , b i , for i ∈ [[1; N ]] and j ∈ [[1; n]]: C i,j = (π i,j • (1, λ i ), x i,j , a i,j , 0) B D i = (µ i • (λ i , -1), y i , b i , 0) B * and
C * j = (π * j (1, λ * ), x * j , 0, 0) B D * = (µ * (λ * , -1), y * , 0, 0) B *
for random π * j , µ * but any λ * , x * j , y * . And we denote S 0 the event that the adversary eventually outputs 1, when distinguishing the distributions of C * j , D * . One can note that in this game, we are with the input distribution (0), where the adversary can choose (λ i , x i,j , y i , a i,j , b i ) for all i, j, and λ * , x * j , y * , but λ * is distinct from each λ i , and all the labels being among Q possible values. Game G 1 : As the 5-th components in the C i,j , C * vectors are all 0, one can duplicate the 3-rd components of D i , D * vectors at the 5-th position, applying the Replication Lemma 7. This is perfectly indistinguishable from the previous game: ))) + "}$ "), "& ", m, " & ", "{:.2}".format(pA), # " & ", # "{:.2}".format(approxpA), " & ", "{:.2}".format(pB), # " & ", # "{:.2}".format(approxpB), (" & $2^{" + str(lNi[k]) + "}$ " if k < 0 else " & " + str(round(2 * * lNi[k])) + " "), # " & $10ˆ{" + str(round(log10(2 * * lNi[k]))) + → "}$ "), "& ", r, " & ", "{:.2}".format(new cfdence), " & ", "{:.1E}".format(C0), " & ", "{:.1E}".format(CH), " \\\\" ) confidence min = 0.95 thres birthday paradox proba = 0.95 nprime = 1 lNi = [ # 25, 25, 19, 16, 10, log2(200), log2(2000), log2( 2000), log2(200), log2(2000), log2(2000)] lN = [ # 30, 30, 20, 20, 15, log2(1000), log2(10000), log2( 10000), log2(1000), log2(10000), log2(10000)] ln = [ # 4, 5, 4, 4, 4, log2(0.36), log2(0.11) = 2000 # [200, 2000, 2000] # Number of nodes owned by bank 2 N2 = N1

S 0 = S 1 . G0 Ci,j = ( πi,j(1, λi) | xi,j ai,j | 0 ) ∀i ∈ [[1; N ]], Di = ( µi(λi, -1) | yi bi | 0 ) j ∈ [[1; n]]: C * j = ( π * j (1, λ * ) | x * j 0 | 0 ) D * = ( µ * (λ * , -1) | y * 0 | 0 ) G1 ∀i, j Ci,j = ( πi,j(1, λi) | xi,j ai,j | 0 ) Replication Di = ( µi(λi, -1) | yi bi | yi ) C * j = ( π * j (1, λ * ) | x * j 0 | 0 ) D * = ( µ * (λ * , -1) | y * 0 | y * ) G2 ∀i, j Ci,j = ( πi,j(1, λi) | xi,j ai,j | 0 ) Swapping Di = ( µi(λi, -1) | yi bi | yi ) C * j = ( π * j (1, λ * ) | 0 0 | x * j ) D * = ( µ * (λ * , -1) | y * 0 | y * ) G3 ∀i, j Ci,j = ( πi,j(1, λi) | xi,j ai,j | 0 ) Indexing Di = ( µi(λi, -1) | yi bi | 0 ) C * j = ( π * j (1, λ * ) | 0 0 | x *
# Total number of transactions patterns # because each standard pattern will lead to two nodes with a transaction and each money laundering pattern to two → transactions between three nodes. nb standard transaction ptns = 200 # [300, 500, 200] nb money laundering trans ptns = 200 # [10, 100, 200] # for a given pair of nodes with a transaction pattern, the number of time a transaction happen between them std trans cnt min = 1 std trans cnt max = 3 monlaun trans cnt min = 6 monlaun trans cnt max = 12 # money laundering number of neighbors for each ML pattern monlaun interm min = 1 monlaun interm max = 5 # nodes average connectivity i. e. mean number of other nodes they are having transactions with, for incoming xor → outgoing edges. n = (nb standard transaction ptns + nb money laundering trans ptns * (monlaun interm max+monlaun interm min)/2 * 2) / N print("n: ", n) # transaction amounts mon laun amount input = 10000 mon laun amount output = 9900 std trans min = 1 std trans max = 5000 # hashing parameters # number of hash functions: nb hash = 16 # [32,30,46] print("r: ", nb hash) # threshold for selection of suspicious node in hash repetitions: tau = 14 # [START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]14,16] print("tau: ", tau) # bit size of the space hashed into: m = 6 # [3, 3, 3] print("m: ", m) # Similarity threshold for detection: theta = 0.2 hash theta = theta print("hash_theta: ", hash theta) # returns the matrix of similarity indexes. sim matrix[i, :] = Parallel(n jobs=10)(delayed(get sim mat coeff)(i, j, in graph mat 1, in graph mat 2, out graph mat 1, out graph mat 2) for j in → range(M2)) return sim matrix

Fig. 2 .

 2 Fig. 2. Sequence of Games for the Indistinguishability Security

Fig. 3 .

 3 Fig. 3. Illustration of banks DP1 and DP2 owning some nodes of the graph of all accounts

Fig. 7 .

 7 Fig. 7. Sequence of Games for the Indistinguishability Security of the IPFE with Selector

Fig. 8 .

 8 Fig. 8. Sequence of Games for the Alternative Product-Preserving Lemma

  def calculate similarity matrix(in graph mat 1, in graph mat 2, out graph mat 1, out graph mat 2): # number of node in first dataset: M1 = np.size(in graph mat 1, 1) # number of node in second dataset: M2 = np.size(in graph mat 2, 1) # number of nodes in original graph: N = np.size(in graph mat 1, 0) # columns: if N != np.size(in graph mat 2, 0) or N != np.size(out graph mat 1, 1) or M1 != np.size(out graph mat 1, 0) or N → != np.size(out graph mat 2, 1) or M2 != np.size(out graph mat 2, 0): "Wrong dimensions!" sim matrix = np.zeros([M1, M2]) # for i in range(M1): # for j in range(M2): # sim matrix[i, j] = np.inner(out graph mat 1[i, :], out graph mat 2[j, :]) * \ # np.inner(in graph mat 1[:, i], # in graph mat 2[:, j]) for i in range(M1):

  ),

	⟨w a,in +	w x,in ; w b,in +
	x∈V 1	x∈V 2
	Hs(x)=u	Hs(x)=v
	x̸ =a	x̸ =b
		w x,in ⟩ + ⟨w b,in ;	w x,in ⟩ + ⟨	w x,in ;	w x,in ⟩.
		x∈V 2	x∈V 1	x∈V 1	x∈V 2
		Hs(x)=v	Hs(x)=u	Hs(x)=u	Hs(x)=v
		x̸ =b	x̸ =a	x̸ =a	x̸ =b

w x,in ⟩ = ⟨w a,in ; w b,in ⟩ + ⟨w a,in ;

  OT12b.Tatsuaki Okamoto and Katsuyuki Takashima. Fully secure unbounded inner-product and attributebased encryption. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS, pages 349-366. Springer, Heidelberg, December 2012. SNY + 16. Reza Soltani, Uyen Trang Nguyen, Yang Yang, Mohammad Reza Faghani, Alaa Yagoub, and Aijun An. A new algorithm for money laundering detection based on structural similarity. In 7th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference, UEMCON 2016,

		New York City, NY, USA, October 20-22, 2016, pages 1-7. IEEE, 2016.
	TT18.	Junichi Tomida and Katsuyuki Takashima. Unbounded inner product functional encryption from
		bilinear maps. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume
		11273 of LNCS, pages 609-639. Springer, Heidelberg, December 2018.

  as v 3 is a unitary vector. Then S * 2 = S * 1 . And this is clear that S * 2 = S 7.ℓ.3 /(q 2n + 1) . Hence, S 7.ℓ.3 = S 7.ℓ.2 . Game G 7.ℓ.4 After having ignored linear vectors, we force ρ ℓ to be in the span of v b : S 7.ℓ.3 -S 7.ℓ.4 ≤ Adv sxdh (t) + 1/q, as above.C Proof of Theorem 12 (Indistinguishability of the IPFE with Selector)As we will have several vectors with the same labels, we first need to propose a variant of the Product-Preserving Lemma 8, whose proof is presented in appendix D:Lemma 15 (Alternative Product-Preserving Lemma). For two orthogonal bases B and B * , of length 5, unknown to the adversary A, given a list of indexed vectors, for any (x i,1 , . . . , x i,n , y i , a i,1 , . . . , a i,n , b i ), fixed indices λ i among Q possible values , but random unknown π i,1 , . . . , π i,n , µ

i , for i = [[1; N ]], j ∈ [[1; n]]:

  Experiments script for the Money-Laundering Application from math import ceil from random import randint, seed import numpy as np from numpy import linalg as LA from joblib import Parallel, delayed from datetime import datetime

	# Number of nodes owned by bank 1
	N1
	, log2(
	0.14), log2(0.36), log2(0.11), log2(0.14)]
	calculate values(confidence min, lNi, lN, ln,
	thres birthday paradox proba, nprime)
	E.2 # parameters.
	# Total number of nodes in the system:
	N = 10000 # [1000, 10000, 10000]

Acknowledgments

This work was supported in part by the European Community's Horizon 2020 Project Crypt-Analytics (Grant Agreement no. 966570) and the French ANR Project Crypto4Graph-AI.

A Proof of the Product-Preserving Lemma 8

Proof. We detail the full proof of Lemma 8, following the sequence of games presented on Figure 1.

Game G 0 : We start from the original distribution, for random π i , µ i $ ← Z q , but any x i , y i , a i , b i , for i ∈ [[1; N ]], and fixed λ i among Q possible values: for random π * , µ * but any λ * , x * , y * . And we denote S 0 the event that the adversary eventually outputs 1, when distinguishing the distributions of C * . One can note that in this game, we are with the input distribution (0), where the adversary can choose (λ i , x i , y i , a i , b i ) for all i, and λ * , x * , y * , but λ * is distinct from any other λ i , and all the labels being among Q possible values. Game G 1 : As the 5-th components in C i and C * vectors are all 0, one can duplicate the 3-rd components of D i and D * vectors at the 5-th position, applying the Replication Lemma 7. This is perfectly indistinguishable: S 0 = S 1 . Game G 2 : Since the 3-rd and 5-th components of D i and D * vectors are all identical, one can swap x * from the 3-rd to the 5-th positions in C * , applying the Swapping Lemma 5 with the first two components for the required randomness: S 1 -S 2 ≤ 2 • Adv ddh G 1 (t). Game G 3 : For any i, the 5-th component of C i is 0. Applying the Indexing Lemma 6, on (B * , B), between λ * and every possible label λ i ̸ = λ * , iteratively, one replaces each y i in the 5-th component of D i by 0. More precisely, at the beginning of each the game (each value of i), one anticipates the Q possible values in which λ * and the λ i are drawn, one makes a guess on λ * , and enumerates all the Q -1 possible values for λ i . When the guess on λ * , one aborts. When the guess is correct (which happens with probability 1/Q):

, as there are N indexing operations to apply for all the useful λ i . Other values have no impact. Hence, S 2 -S 3 ≤ 2N Q • Adv ddh G 2 (t) Game G 4 : One now removes y * from the 3-rd component of D * with the Replication Lemma 7:

replicating negatively the 5-th components at the 3-rd positions of D vectors, one subtracts y * in D * , and 0 in other vectors, but adds the 3-rd component to the 5-th in the C i vectors.

The two games are perfectly indistinguishable: S 3 = S 4 . Game G 5 : For any i, the 5-th component of D i is 0. Applying the Indexing Lemma 6, on (B, B * ), between λ * and every possible label λ i ̸ = λ * , iteratively, one replaces each x i in the 5-th components of C i by 0. More precisely, at the beginning of each the game (each value of i), one anticipates the Q possible values in which λ * and the λ i are drawn, one makes a guess on λ * , and enumerates all the Q -1 possible values for λ i . When the guess on λ * , one aborts. When the guess is correct (which happens with probability 1/Q):

, as there are N indexing operations to apply for all the useful λ i . Other values have no impact. Hence, S 4 -S 5 ≤ 2N Q • Adv ddh G 1 (t). Game G 6 : One replaces the pair (x * , y * ) by (1, x * y * ) in the 5-th coordinates of C * and D * (if x * ̸ = 0). To this aim, one makes a random guess X $ ← Z q on x * , and defines the matrices if X ̸ = 0:

or no change otherwise. If during the execution, x * ̸ = X, one aborts, otherwise the two games are perfectly indistinguishable in case of correct guess: S 5 /q = S 6 /q, hence S 5 = S 6 .

-For the query OKeyGen(α k = (α k,0 , α k,1 )), we rewrite α k = (α k,i ) i ∈ Z 2n q , one outputs

-For a query LoREncrypt 1 (λ ℓ , x 0 ℓ , x 1 ℓ ), one first derives λ ℓ,i , for i ∈ [[1; 2]], and then outputs

, and, for random

and then outputs

q , and, for random

Then we consider S 0 = Pr[β = b], where β $ ← {0, 1} if for some α k asked to the OKeyGenoracle and some (x 0 ℓ , x 1 ℓ ), (y 0 ℓ , y 1 ℓ ) asked to the LoREncrypt oracle one has the inequality

, which is a non-legitimate attack, or β ← b ′ , as this is a legitimate attack. Our goal is to show that S 0 is close to 1/2. In the following games, we alter the simulation of all the LoREncrypt-oracles. We denote N the number of distinct λ ℓ , but anticipate by programming at most 2Q values of λ ℓ,i , and K the number of OKeyGenqueries. Game G 1 : We consider LoREncrypt 2 (λ ℓ , y 0 ℓ , y 1 ℓ ) is always asked first. We apply the Alternative Product-Preserving Lemma 15 on the 3-rd and 4-th components (x ℓ,i , 0) and (y ℓ,⌈i/(2n)⌉ , 0) for each ℓ and ⌈i/(2n)⌉ to replace them into the preserved product (0, x ℓ,i y ℓ,⌈i/(2n)⌉ ) and (0, 1). We thus have S 0 -S 1 ≤ 8N • (Qn(N + 1) + 2) • Adv sxdh (t). Game G 2 : We apply again the Alternative Product-Preserving Lemma 15 on (σ ℓ,j s i,j , 0) and (τ ℓ,j t ⌈i/(2n)⌉,j , 0) to replace them into (0, 1) and the preserved product (0, σ ℓ,j τ ℓ,j s i,j t ⌈i/(2n)⌉,j ), successively for j = 1, 2 and each label: S 1 -S 2 ≤ 16N • (Qn(N + 1) + 2) • Adv sxdh (t). Game G 3 : We now formally replace z ℓ,i ← x ℓ,i y ℓ,⌈i/(2n)⌉ , and τ ℓ,j ← ρ ℓ,j /σ ℓ,j for j = 1, 2. This makes no difference:

does not require knowledge of ρ ℓ , but just ρ ℓ • G 1 , as the vector σ ℓ is known. The simulation of the C ℓ,i does not either, but just ρ ℓ • G 1 too. This game is perfectly indistinguishable from the previous one if ρ ℓ is not colinear with v as v 2 $ ← Z q is random, and applying this transformation for the N indices, we get: S 4 -S 3 ≤ N/q. Game G 5 : Since the 6-th and the 8-th components of D ℓ,k vectors are all identical to 1, one can successively swap elements from the 6-th to the 4-th positions, and from the 8-th to the 4-th positions in C ℓ,i to get

Applying the Swapping Lemma 5, one gets S 4 -S 5 ≤ 4 • Adv ddh G 1 (t). Game G 6 : Since the 6-th and the 8-th components of the C ℓ,i vectors are null, we use the Replication Lemma 7 twice to withdraw the 4-th component of the D ℓ,k 's, 1, to their 6-th and then 8-th components, all the while adding zeros to the 4-th component in the C ℓ,i 's. This is perfectly indistinguishable from the previous game: S 5 -S 6 = 0.

Game G 2 : Since the 3-rd and 5-th components of D i , D * vectors are all identical, one can swap x * j 's from the 3-rd to the 5-th positions in C * j 's, applying the Swapping Lemma 5 with the first two components for the required randomness: S 1 -S 2 ≤ 2 • Adv ddh G 1 (t). Game G 3 : For any i, the 5-th component of the C i,j 's is 0. Applying the Indexing Lemma 6, on (B * , B), between λ * and the λ i ̸ = λ * , iteratively, one replaces each y i in the 5-th component of the D i 's by 0, and gets

. Game G 4 : One now removes y * from the 3-rd component of D * using the Replication Lemma 7:

replicating negatively the 5-th components at the 3-rd positions of D's vectors, one subtracts y * in D * , and 0 in other vectors, but adds the 3-rd component to the 5-th in the C's vectors.

The two games are perfectly indistinguishable: S 3 = S 4 . Game G 5 : For any j, the 5-th component of D j is 0. Applying the Indexing Lemma 6, on (B, B * ), between λ * and the λ j ̸ = λ * , iteratively, one replaces each x i,j in the 5-th components of the C i,j 's by 0, and gets

. Game G 6 : One replaces each pair (x * j , y * ) with (x * j y * , 1) in the 5-th coordinates of C * j and D * . To this aim, one makes a random guess Y ← Z q on y * , and defines the matrices, if Y ̸ = 0:

or no change otherwise. If during the execution, y * ̸ = Y , one aborts, otherwise the two games are perfectly indistinguishable in case of correct guess: S 5 /q = S 6 /q, hence S 5 = S 6 . Game G 7 : In case y * = 0, then one applies the subspace indistinguishability theorem 3 twice, to shift the x * j 's to zero, using the null fifth coordinate of D * and the randomness in the first coordinates of the C * j 's, and then to shift the fifth coordinate of D * to 1 using one C * j 's now null fifth coordinate and the randomness in the first coordinates of D * . In this case:

. Game G 8 : One now duplicates the 1 from the 5-th component of D * to the 4-th using the Replication Lemma 7 (and 0 is added to the 4-th components of the D i 's). This also negatively adds the 4-th components at the 5-th positions of C i,j and C * j vectors. The two games are perfectly indistinguishable: S 7 = S 8 . Game G 9 : One applies twice the Indexing Lemma 6, between λ * and the λ j ̸ = λ * , iteratively, to first replaces each -a i,j in the 5-th components of the C i,j 's by 0, and then the 0 in the 5-th components of the D i 's by b i . One gets S 8 -S 9 ≤ 2QnN Adv ddh G 1 (t) + 2QnAdv ddh G 2 (t). Game G 10 : One now swaps the 5-th components x * j y * and the 4-th components 0 of the C * j 's. This easily works as all the D i and D * vectors have identical 4-th and 5-th components, using the Swapping Lemma 5, with the first two components for randomness: S 9 -S 10 ≤ 2 • Adv ddh G 1 (t). Game G 11 : One then withdraws the 4-th components from the 5-th components in the D j 's and the D * , while the null 5-th components of C i,j 's and C * j 's are added to the 4-th components, using the Replication Lemma 7. This game is perfectly indistinguishable from the previous one: S 10 -S 11 = 0. The global probability difference is bounded by 0 trans cnt = randint(monlaun trans cnt min, monlaun trans cnt max) nb intermediates = randint(monlaun interm min, monlaun interm max) sender = randint(0, N-1) if sender not in money launderers: money launderers.append(sender) interms = [sender for i in range(nb intermediates)] receiver = sender for i in range(nb intermediates): interm = sender while interm in interms or interm == sender: # if k == 0: # we want at least one detectable pattern accross the two banks

E Scripts for the Money-Laundering Detection Application