Xavier Bultel
email: xavier.bultel@irisa.fr

Radu Ciucanu
email: radu.ciucanu@insa-cvl.fr

Matthieu Giraud
email: matthieu.giraud@uca.fr

Pascal Lafourcade
email: pascal.lafourcade@uca.fr

Lihua Ye

Secure Joins with MapReduce

Keywords: Database Query, MapReduce, Security, Natural Joins

MapReduce is one of the most popular programming paradigms that allows a user to process Big data sets. Our goal is to add privacy guarantees to the two standard algorithms of join computation for MapReduce: the cascade algorithm and the hypercube algorithm. We assume that the data is externalized in an honest-but-curious server and a user is allowed to query the join result. We design, implement, and prove the security of two approaches: (i) Secure-Private, assuming that the public cloud and the user do not collude, (ii) Collision-Resistant-Secure-Private, which resists to collusions between the public cloud and the user i.e., when the public cloud knows the secret key of the user.

Introduction

With the advent of Big data, new techniques have been developed to process parallel computation on a large cluster. One of them is the MapReduce programming paradigm [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF], which allows a user to keep data in public clouds and to perform computations on it. A MapReduce program uses two functions (map and reduce) that are executed on a large cluster of machines in parallel. The popularity of the MapReduce paradigm comes from the fact that the programmer does not need to handle aspects such as the partitioning of the data, scheduling the program's execution across the machines, handling machine failures, and managing the communication between different machines.

MapReduce users often rent storage and computing resources from a public cloud provider (e.g., Google Cloud Platform, Amazon Web Services, Microsoft Azure). External storage and computations with a public cloud make the Big data processing accessible to users that can not afford building their own clusters. Yet, outsourcing data and computations to a public cloud involves inherent security and privacy concerns. Since the data is externalized, it can be communicated over an untrustworthy network and processed on some untrustworthy machines, where malicious public cloud users may learn private data. We address the fundamental problem of computing relational joins between an arbitrary number of relations in a privacy-preserving manner using MapReduce. We assume that the data is externalized in the cloud by the data owner and there is a user that is allowed to query it as shown in Fig. 1. This standard model has been used recently by Dolev et al. [START_REF] Dolev | Private and secure secret shared mapreduce[END_REF].

We next present via a running example the concept of relational joins. Then, we present MapReduce computations, our problem statement, and illustrate the privacy issues related to joins computation with MapReduce.

Example 1. The data owner is a hospital storing relations R 1 , R 2 , R 3 cf. Fig. 2. The (natural) join of these relations, denoted R 1 ' R 2 ' R 3 , is the relation whose tuples are composed of tuples of R 1 , R 2 and R 3 that agree on shared attributes. In our case, the attribute Name is shared between R 1 and R 2 . Moreover, the attribute Disease is shared between intermediate join result (R 1 ' R 2 ) and relation R 3 . In Fig. 2, we give both the intermediate result pR 1 ' R 2 q and the final result pR 1 ' R 2 q ' R 3 . We observe that tuple pAlice, NYCq from relation R 1 , tuple pBob, Diabetesq from relation R 2 , and tuple pBob, London, Diabetesq from relation R 1 ' R 2 do not participate to the final result.

Joins with MapReduce

Two algorithms for computing relational joins with MapReduce are presented in the literature: the Cascade algorithm (i.e., a generalization of the binary join from Chapter 2 of [START_REF] Leskovec | Mining of Massive Datasets[END_REF]) and the Hypercube algorithm [START_REF] Afrati | Optimizing Joins in a MapReduce Environment[END_REF][START_REF] Chu | From theory to practice: Efficient join query evaluation in a parallel database system[END_REF]. In the following, a reducer refers to the application of the reduce function to a single key.

Cascade Algorithm. To compute an n-ary join (n ě 2), the cascade algorithm uses n ´1 MapReduce rounds i.e., a sequence of n ´1 binary joins. A binary We illustrate this process in Fig. 3.

Example 1 continued. To compute pR 1 ' R 2 q ' R 3 with MapReduce following the cascade algorithm, we start by joining R 1 and R 2 . Relations R 1 and R 2 share attribute Name. Hence from R 1 , the map produces the following key-value pairs: (Alice, (R 1 , NYC)), (Bob, (R 1 , London)), and (Eve, (R 1 , Tokyo)). These key-value pairs are sent to three different reducers depending on the key value. From relation R 2 , the map produces key-value pairs (Bob, (R 2 , Diabetes)), (Bob, (R 2 , AIDS)), and (Eve, (R 2 , Cancer)). We stress that values of pairs (Bob, (R 2 , Diabetes)) and (Bob, (R 2 , AIDS)) are sent to the same reducer as the pair (Bob, (R 1 , London)) since all these pairs have the same key. Similarly, (Eve, (R 2 , Cancer)) and (Eve, (R 1 , Tokyo)) are sent to the same reducer. The pair (Alice, (R 1 , NYC)) does not participate in the join result since no other pair shares the same key. Then, from values (R 1 , London), (R 2 , Diabetes), and (R 2 , AIDS) present on the reducer associated to the key Bob, the reduce creates all possible tuples with values coming from different relations i.e., (Bob, London, Diabetes) and (Bob, London, AIDS). Similarly, the reducer associated to the key Eve produces (Eve, Tokyo, Cancer). These tuples correspond to the relation pR 1 ' R 2 q cf. Fig. 2. We apply the map and the reduce functions on relations pR 1 ' R 2 q and R 3 sharing the attribute Disease. From pR 1 ' R 2 q, the map function produces key-value pairs: (Diabetes, (R 1 ' R 2 , Bob, London)), (AIDS, (R 1 ' R 2 , Bob, London)), and (Cancer, (R 1 ' R 2 , Eve, Tokyo)). From R 3 , the map produces: (AIDS, (R 3 , Hopkins)), and (Cancer, (R 3 , Jude)). From relation R1:

-t1 " pAlice, NYCq -t2 " pBob, Londonq -t3 " pEve, Tokyoq From relation R2:

-t4 " pBob, Diabetesq -t5 " pBob, AIDSq -t6 " pEve, Cancerq From relation R3:

-t7 " pAIDS, Hopkinsq -t8 " pCancer, Judeq Fig. 4: Running example with hypercube algorithm. Underlined tuples correspond to tuples that participate to the final join result. reduce step produces tuples (Bob, London, AIDS, Hopkins) and (Eve, Tokyo, Cancer, Jude) corresponding to relation pR 1 ' R 2 q ' R 3 cf. Fig. 2.

Hypercube Algorithm. Contrarily to cascade, the hypercube computes the join of all n relations in only one MapReduce round. The hypercube has dimension d (where d is the number of join attributes). There are p " ś 1ďjďd α j reducers denoted H i (for 1 ď i ď p), where α j is the number of buckets associated with the j th attribute. Hence, each reducer H i can be uniquely identified by a point in the hypercube. For each relation R i spread over a set of nodes R i , the map function computes the image of all tuples on the d dimensions of the hypercube to decide to which reducers H i the tuple should be sent. Then, each reducer computes all possible combinations of input tuples that agree on shared attributes, only if all n relations are represented on the same reducer. All these combinations correspond to the final result of the n-ary join.

Example 1 continued. We have two join attributes (Name and Disease), hence two hash functions h N and h D for attributes Name and Disease, respectively. For instance, assume 4 reducers establishing a 2 ˆ2 square cf. Fig. 4, where h N pEveq=0, h N pAliceq=h N pBobq=1, h D pDiabetesq=h D pAIDSq=0, and h D (Cancer)=1. For each tuple of each relation, we compute the value of the Name component (if there exists) with the hash function h N and the value of the Disease component (if there exists) with the hash function h D . For instance, the tuple t 6 " pEve, Cancerq of the relation R 2 is sent to the reducer of coordinates p0, 1q since h N pEveq " 0 and h D pCancerq " 1 (cf. Fig. 4). If one of these two attributes is missing in a tuple, then the tuple is replicated over all reducers associated to the different values of the missing attributes of the tuple. For example, tuple t 1 " pAlice, NYCq of relation R 1 has no attribute Disease, and consequently, is sent to reducers p1, 0q and p1, 1q. In such a situation we may write p1, ‹q to simplify presentation. Finally, each reducer performs all possible combinations over tuples that agree on join attributes of the three relations R 1 , R 2 , and R 3 . We obviously obtain the same final result as for cascade algorithm.

Problem statement

We assume three participants: the data owner, the public cloud, and the user (cf. Fig. 1). The data owner externalizes n relations R 1ďiďn to the public cloud. We assume that the public cloud is honest-but-curious i.e., it executes dutifully the computation tasks but tries to learn the maximum of information on tuples of each relation. In order to preserve privacy of data owner and to allow the join computation between relations, we want that the cloud learns nothing about input data or join result. Moreover, we want that the user who queries the join result learns nothing else than the final join result i.e., she does not learn information on tuples of relations that do not participate to the final result.

Sets of nodes of type R, Q, and H are honest-but-curious. We denote by R i the set of attributes of a relation R i , for 1 ď i ď n. In the case of the cascade algorithm, we denote by Q i the set of attributes of relation

Q i for 1 ď i ď n, where R 1 " Q 1 .
Finally we denote by X the set of shared attributes between the

n relations i.e., X " | Y 1ďi‰jďn R i X R j |.
We expect the following security properties:

1. Neither a set of nodes R i nor data owner learn final result data. 2. A set of nodes Q i (resp. H i ) cannot learn owner's data and final result.

3. The user learns nothing else than result R 1 ' ¨¨¨' R n i.e., he does not learn tuples from the input relation that do not participate in the result.

Example 1 continued. Looking at the three security properties of the problem statement, we see that the cascade and the hypercube algorithms do not respect properties (1), (2), and (3). In fact, both algorithms reveal to the public cloud all tuples of relations R 1 , R 2 and R 3 since they are not encrypted. Moreover, if the user colludes with the intermediate set of nodes R 1 ' R 2 , then he learns tuples that he should not, in this case the tuple pBob, London, Diabetesq (Fig. 2).

Contributions. We propose two approaches that extend the two aforementioned join algorithms while ensuring the desired security properties, and remaining efficient from both computational and communication points of view.

• The Secure-Private (SP) approach assumes that the public cloud and the user do not collude. We encrypt all values of each tuple using a public key encryption scheme with the user public key pk u . To be able to perform the equality joins between relations we rely on pseudo-random functions. • The Collision-Resistant-Secure-Private (CRSP) approach assumes that the public cloud and the user collude, that means the public cloud knows the private key sk u of the user. In this case, we cannot encrypt all tuples using simply a public encryption scheme since the public cloud can decrypt all these encrypted tuples using the secret key of the user. To avoid this problem, we introduce a proxy such that the data owner also uses the public key of the proxy pk t to encrypt ciphers of tuple values. Thus, we avoid that the public cloud decrypts tuples values received from the data owner even if the public cloud has the secret key sk u of the user. • We give experimental results of our SP and CRSP approaches for the cascade and the hypercube algorithms using Apache Hadoop [START_REF]Apache Hadoop[END_REF] open-source MapReduce implementation and a real-world Twitter dataset [START_REF]Higgs Twitter Dataset[END_REF]. • We prove that our SP and CRSP approaches satisfy the security properties using the random oracle model. We also notice a limitation regarding learning repetitions between pseudo-random values which seems to us inherent because we need to perform equi-joins. Details of proofs are given in the technical report available online [START_REF]Secure Joins with MapReduce[END_REF]. • We quantify the computational and communication overhead of our two secure approaches. We observe that the overhead is linear. Due to lack of space, we include this discussion only in our technical report [START_REF]Secure Joins with MapReduce[END_REF].

Related work. Since the seminal MapReduce paper [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF], different protocols have been proposed to perform operations in a privacy-preserving manner [START_REF] Derbeko | Security and privacy aspects in mapreduce on clouds: A survey[END_REF] such as search [START_REF] Blass | PRISM -privacy-preserving search in mapreduce[END_REF] [20], count [START_REF] Vo-Huu | Epic: Efficient privacy-preserving counting for mapreduce[END_REF], matrix multiplication [START_REF] Bultel | Secure matrix multiplication with mapreduce[END_REF] or joins [START_REF] Dolev | Private and secure secret shared mapreduce[END_REF]. Chapter 2 of [START_REF] Leskovec | Mining of Massive Datasets[END_REF] presents an introduction to the MapReduce paradigm. In particular, it includes the MapReduce algorithm for cascade joins that we enhance with privacy guarantees. Very few approaches address the privacy preserving execution of relational joins in MapReduce and have different assumptions than we do. For instance, Emekçi et al. [START_REF] Emekçi | Privacy preserving query processing using third parties[END_REF] proposed protocols to perform joins in a privacy-preserving manner using the Shamir's secret sharing [START_REF] Shamir | How to share a secret[END_REF]. Contrary to us, they do not consider the MapReduce paradigm and their approach cannot be trivially adopted in MapReduce because values of shared attributes are encrypted in a non-deterministic way. Laur et al. [START_REF] Laur | From oblivious AES to efficient and secure database join in the multiparty setting[END_REF] also proposed a protocol to compute joins using secret sharing but do not consider the MapReduce paradigm and their approach is limited to two relations. Chow et al. [START_REF] Chow | Two-party computation model for privacy-preserving queries over distributed databases[END_REF] introduced a generic model that uses two non-colluding servers to perform join computation between n relations in a privacy-preserving manner but do not consider the MapReduce paradigm. On the other hand, we assume a more general setting where the public cloud servers collude. Dolev et al. [START_REF] Dolev | Private and secure secret shared mapreduce[END_REF] proposed a technique for executing MapReduce computations in the public cloud while preserving privacy using the Shamir's secret sharing [START_REF] Shamir | How to share a secret[END_REF] and accumulating-automata [START_REF] Dolev | Accumulating automata and cascaded equations automata for communicationless information theoretically secure multi-party computation: Extended abstract[END_REF]. Join computation is executed on secret-shares in the public cloud and at the end, the user performs the interpolation on the outputs. Contrary to us, authors assume that the different cloud nodes do not collude, otherwise they can construct the secret from shares. Moreover in our setting, we externalized entirely the computation in the cloud and the user has only to decrypt the join result, contrary to the need of doing interpolations in [START_REF] Dolev | Private and secure secret shared mapreduce[END_REF]. Finally, none of the aforementioned approaches propose a secure approach for the hypercube algorithm with MapReduce. Finally, the system that is most closely related to our work is Popa et al.'s CryptDB [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF][START_REF] Popa | Cryptographic Treatment of CryptDB's Adjustable Join[END_REF]. CryptDB provides practical and provable confidentiality in the face of curious server for applications backed by SQL databases. It works by executing SQL queries over encrypted data using a collection of efficient SQL-aware encryption schemes. However, they do not consider the MapReduce paradigm.

To the best of our knowledge, we are the first to propose two secure approaches of join computation for the cascade and the hypercube MapReduce algorithms, where the user has only to decrypt the result received from the cloud.

Outline. We present the cascade and hypercube algorithms for the n-ary join computation with MapReduce in Section 2. We present our SP and CRSP approaches for both algorithms in Section 3. In Section 4, we compare experimentally the performance of our approaches vs the insecure algorithms. Then, we prove the security of the SP and CRSP approaches in Section 5. Finally, we outline conclusion and future work in Section 6.

n-ary Joins with MapReduce

We formally present the standard algorithms for computing n-ary joins Q " R 1 ' ¨¨¨' R n with MapReduce: cascade i.e., a sequence of n ´1 rounds of binary joins [START_REF] Leskovec | Mining of Massive Datasets[END_REF] and hypercube [START_REF] Afrati | Optimizing Joins in a MapReduce Environment[END_REF] i.e., a single round doing all the n ´1 joins. We have already presented examples for both algorithms in Section 1.1. Fig. 5: BinaryJoin algorithm for natural join with MapReduce between Q and R.

Cascade Algorithm

We recall that the i th round of the cascade algorithm takes action between sets of nodes Q i and R i`1 , with 1 ď i ď n ´1 and that relation R

1 is denoted Q 1 .
The term chunk refers to a fragment of information. Moreover, R denotes the schema of the relation R i.e. the set of attributes of the relation R.

Algorithm: CascadeJoinpR1, . . . , Rnq We present in Fig. 5 the binary join with MapReduce between two relations. To compute join between n relations R 1 , . . . , R n , we apply n ´1 times the binary join (Fig. 5) as presented in the cascade algorithm in Fig. 6. The final relation Q n corresponds to R 1 ' ¨¨¨' R n .

for 1 ď i ď n ´1 do Qi`1 Ð BinaryJoinpQi, Ri`1q;

Hypercube Algorithm

We assume that we have an hypercube of dimension d, where Moreover, we assume that we have d (non-cryptographic) hash functions h (where 1 ď ď d) such that h : X Ñ 0, α where α is the number of buckets for the attribute X . Hence, the hypercube is composed of α 1 ¨¨¨α reducers where each reducer is uniquely identified by a dtuple px 1 , . . . , x d q with x P 0, α for 1 ď ď d. In the following, we denote by A i j the j-th attribute of the relation R i where 1 ď i ď n and 1 ď j ď |R i |.

d " |X| " |tX 1 , . . . , X d u| " | Y 1ďi‰jďn R i X R j | i.e.,
We present in Fig. 7 the hypercube algorithm for the join computation with MapReduce between n relations R 1 , . . . , R n . The map function sends the pair to the corresponding reducer of the hypercube associated to the coordinates of the key-value pair's key where the star ‹ in theth coordinate means that we duplicate the tuple t on all the α buckets of the -th dimension of the hypercube. Then, if the same reducer of the hypercube has at least one tuple coming from all the n relations and that these tuples agree on their shared attributes then the reduce function produces all possible key-values pairs of the form pt 1 ' ¨¨¨' t n , t 1 ' ¨¨¨' t n q where t i P R i (with 1 ď i ď n).

Secure n-ary Joins with MapReduce

Before formally presenting our secure algorithms, we present the needed cryptographic tools. We illustrate the intuition of each of our algorithms while relying on our running example from the Introduction.

Cryptographic Tools

We define negligible function, pseudo-random function, and public key encryption cryptosystem.

Definition 1 (Negligible function). A function : N Ñ R is negligible in η if for every positive polynomial pp¨q and sufficiently large η, pηq ă 1{ppηq.

Definition 2 (Pseudo-random function). Let η be a security parameter. A function f : t0, 1u pηq ˆt0, 1u l0 Ñ t0, 1u l1 is a pseudo-random function if it is computable in polynomial time in η and if for all polynomial-size B,

ˇˇPr " B f pk,¨q " 1 : k $ Ð t0, 1u pηq ‰ ´Pr " B gp¨q " 1 : g $ Ð Funcrl 0 , l 1 s ‰ˇˇď pηq
where, p¨q is a polynomial function, Funcrl 0 , l 1 s is the space of functions defined over domain t0, 1u l0 and codomain t0, 1u l1 , p¨q is a negligible function in η and the probabilities are taken over the choice of k and g.

In the rest of the paper, the pseudo-random function f pk, ¨q is denoted f k p¨q.

Definition 3 (Public Key Encryption). Let η be a security parameter. A Public Key Encryption (PKE) scheme Π is defined by three algorithms pG, E, Dq:

Gpηq: it takes the security parameter η and returns a key pair ppk, skq. E pk pmq: it takes a public key pk and a plaintext m and returns the ciphertext c. D sk pcq: it takes a private key sk and a ciphertext c and returns the plaintext m.

Preprocessing and Outsourcing

To prevent the cloud from learning the content of relations, the data owner protects each relation R 1ďiďn before outsourcing. The protected relation obtained from R i is denoted Ri and is sent to the public cloud by the data owner.

The data owner protects relations in two ways. First, it uses a pseudo-random function f k p¨q where k is the data owner secret key. The data owner applies f k p¨q on values of shared attributes of each tuples of relations R 1ďiďn . Since a pseudo-random function is determinist, it allows the cloud to perform equality tests between values of join attributes. On other hand, the data owner encrypts for each user each component of tuples with an indistinguishable under chosen plaintext attack (IND-CPA) public key encryption scheme (e.g., ElGamal [START_REF] Gamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], RSA-OAEP [START_REF] Bellare | Optimal asymmetric encryption[END_REF]) using the public key pk u of the user. Hence the encrypted values of non-shared attributes do not give any information to an adversary. Values of shared attributes are also encrypted using the public scheme encryption since we want the user can decrypt them.

We present the preprocessing algorithm in Fig. 8. The set visited prevents the data owner from (IND-CPA) encrypting several times the same values. We stress that A f and A E are just notations making explicit the correspondences between initial and outsourced data. For instance, if a relation R has one attribute "Name" that is shared with an other relation, then this attribute in the protected relation will be denoted "Name f "; we apply the same way the notation A E . Moreover Ri is the schema of the protected relation Ri . We give an example for the cascade algorithm in Fig. 9 Algorithm: PreProcpR1, . . . , Rnq For both algorithms, we remark that the cloud knows when components of same attribute are equal since a pseudo-random function is deterministic. We see in Fig. 9 that the cloud knows that R2 and R3 share two same values of disease since values 18 and 99 are present in both relations. However, we notice that only the data owner knows the secret key k used by the pseudorandom function.

visited Ð H; for 1 ď i ď n do Ri Ð H; R f i Ð tA f |A P Ri X Xu; R E i Ð tA E |A P Rizvisitedu; Ri Ð R f i Y R E i ; for t P Ri do t f Ð Ś A f PR f i f k pπAptqq; tE Ð Ś A E PR E i pE pk u pπAptqqq; Ri Ð Ri Y tt f ˆtE u; visited Ð visited Y Ri;

SP n-ary Joins with MapReduce

SP Cascade Algorithm. If a relation participating at the i-th round contains an attribute that will participate to the join in a following round, the algorithm must anticipate the pseudo-random values of the shared attribute to perform joins. In the original cascade algorithm presented in Section 2.1, tuples are not encrypted and the anticipation is not necessary since each tuple value is available. In the SP approach, we add in value of pairs the pseudo-random evaluations of all needed pseudo-random values allowing joins in other rounds. This is possible since the preprocessing done by the data owner outsources protected relations containing pseudo-random evaluations of values of join attributes.

Algorithm:

SecBinaryp Qi, Ri`1, iq

Map function

Input: pkey, valueq // key: id of chunk of Qi/ Ri`1 // value: coll. t P Qi or t P Ri`1 if i " 1 then foreach tq P Q1 do emit pπ

Q f 1 XR f 2
ptq, pQ1, tqqq;

foreach tr P Ri`1 do emit pπ Q f i XR f i`1
ptq, pRi`1, trqq.

Reduce function

Input: pkey, valuesq // key: π We present in Fig. 10 the general process of the SP-cascade algorithm while we present the SP approach between relations Qi and Ri`1 participating at the i-th round in Fig. 11, where Qi " Qi´1 ' Ri and Q1 " R1 .

Q f i XR f i`1 ptq //
ď i ď n do R 1 i Ð Ť pR i ,tqPvalues ttu; for t P R 1 1 ' ¨¨¨' R 1 n do emit pt, tq.
SP Hypercube Algorithm. We present the SP approach for the hypercube algorithm in Fig. 12. The main difference compared to the insecure approach is that the map function receives encrypted tuples from the data owner. As for the cascade algorithm, we add pseudo-random evaluations in value of each pair allowing the reduce function to check correspondences of tuples on join attributes.

CRSP n-ary Joins with MapReduce

We present the Collision-Resistant-Secure-Private (CRSP) approach for cascade and hypercube algorithms to compute joins between n ą 2 relations with MapReduce. We recall that we assume in the CRSP approach that the user and the public cloud collude i.e., the public cloud knows the secret key sk u of the user. Even in this scenario, we want that the security properties are satisfied.

When the public cloud and the user collude, the SP approach does not satisfy anymore the security properties since the public cloud can decrypt all tuples using the user's private key sk u . Hence, the user learns intermediate results that she should not know, and property security (3) is not satisfied. To solve this issue, we introduce a trusted set of nodes as proxy (which do not collude with the public cloud and the user) denoted P. This proxy has a key pair ppk t , sk t q. The public key pk t is used by the data owner in the preprocessing phase. In this case the value of t E is equal to Ś

A E PR E i E pk t pE pk u pπ A ptqqq. In fact, the data owner encrypts (with the proxy public key) each encrypted values obtained with the user public key pk u . This avoids the public cloud to decrypt the encrypted components outsourced in the cloud. Hence, the public cloud does the join computation as usually, and sends the result to the proxy. The proxy uses his secret key sk t and sends the result only encrypted by the user's public key to the user. We illustrate the CRSP approach in Fig. 13.

CRSP Cascade Algorithm. The CRSP approach for the cascade algorithm between n relations uses the same algorithm than the SP approach and is presented in Fig. 10. The difference lies in the preprocessing where the data owner uses the proxy public key pk t to encrypt the encrypted values obtained using the user public key. Hence, the public cloud cannot use the user's secret key sk u to learn information about tuples. We stress that P is a trusted set of nodes i.e., the proxy colludes neither with the public cloud nor the user.

CRSP Hypercube Algorithm. The CRSP approach for the hypercube algorithm between n relations presented in Fig. 12 uses the same algorithm than the SP approach. As for the cascade algorithm in the CRSP approach, the difference lies in a second encryption of values done by the data owner using the proxy public key. This second encryption avoids the public cloud to learn information on relations sent by the data owner, even if the cloud and the user collude.

Experimental Results

We present the experimental results for the insecure, SP and CRSP approaches with the cascade and hypercube algorithms using the Hadoop [1] implementation of MapReduce. We have done all computations on a cluster running on Ubuntu Server 14.04 with Vanilla Hadoop 2.7.1 using Java 1.7.0. The cluster is composed of one master node and of three data nodes. The master node has four CPU cadenced to 2.4GHz, 80Gb of disk, and 8Gb of RAM. The three data nodes have of two CPU cadenced to 2.4GHz, 40Gb of disk, and 4Gb of RAM.

We use the real-world Higgs Twitter Dataset [START_REF]Higgs Twitter Dataset[END_REF] that we denote by relation RpA, Bq where attributes A and B encode followee-follower relation on Twitter. The relation RpA, Bq has 15M tuples. To perform joins with this dataset, we generate two relations SpB, Cq and T pC, Aq that are copies of R. The join query used in our experiments is RpA, Bq ' SpB, Cq ' T pC, Aq, consisting on all directed triangles of the Higgs Twitter Dataset. Using such a dataset and query is a standard practice in the database community literature to evaluate the performance of join query algorithms, as recently done e.g., in [START_REF] Chu | From theory to practice: Efficient join query evaluation in a parallel database system[END_REF]. We use the AES encryption scheme [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] as the pseudo-random function, and the RSA-OAEP encryption scheme [START_REF] Bellare | Optimal asymmetric encryption[END_REF] as the public key encryption scheme.

Scalability. We present in Fig. 14a the running time for the cascade and hypercube algorithms, for each security approach. The different numbers of selected tuples come from the original dataset, where a sample is selected randomly. In the figures presented in Fig. 14, we consider size up to 2, 356, 225 tuples because after such a size, our cluster gives out-of-memory errors hence we cannot compare meaningful results for all approaches. We report average times over five runs. For the hypercube algorithm, we use four buckets for each of the three dimensions defined by attributes A, B, and C, hence a total number of 4 3 " 64 reducers. Without any security, the cascade and hypercube algorithms perform very similarly, although the hypercube seems a bit better for the largest input data sizes. For each of our secure approaches (SP and CRSP), the hypercube algorithm performs better than the cascade, hence the aforementioned trend is visible starting from small input data sizes. Intuitively, this happens because the hypercube avoids computing large intermediate results as may happen in practice when triangle queries are computed with a cascade approach.

Behind the curtain. We look in details at the main parts behind the algorithm execution for SP Cascade (Fig. 14b), SP Hypercube (Fig. 14c), CRSP Cascade (Fig. 14d), and CRSP Hypercube (Fig. 14e). For each of the aforementioned cases, the cryptography is not the dominant cost, which confirms our intuition that the overhead needed to secure standard join algorithms is a constant factor. The communication and the computation dominate the total execution time. transitivity, we prove that it does not exist a polynomial-time algorithm that can distinguish the view generated by real protocols and the view generated by the simulator Sim 2 . Hence, if f is a secure pseudo random function and Π is an IND-CPA public key encryption scheme, then the SP cascade and the SP hypercube algorithms securely computes joins between n relations in ROM in the presence of honest-but-curious adversaries if the cloud and the user do not collude.

Theorem 2. Assume f is a secure pseudo random function and Π is an IND-CPA public key encryption scheme. Then, the CRSP cascade and the CRSP hypercube algorithms securely computes joins between n relations in ROM in the presence of honest-but-curious adversaries even if the public cloud and the user collude.

Proof (Sketch). First, we use the hybrid argument to show that it does not exist a polynomial-time algorithm that is able to distinguish the view of the cloud colluding with the user generated by the real protocols (CRSP cascade and CRSP hypercube) and the view generated by a simulator using inputs and outputs of the cloud and of the user. As in the previous proof, it relies on the secure pseudo random function f and on the IND-CPA public key encryption scheme. In the same way, we prove that we can perfectly simulate the view of the proxy using its input and output. Hence, if f is a secure pseudo random function and Π is an IND-CPA public key encryption scheme, the CRSP cascade and the CRSP hypercube algorithms securely computes joins between n relations in ROM in the presence of honest-but-curious adversaries even if the public cloud and the user collude.

Conclusion

We have presented two efficient approaches for computing joins with MapReduce. The SP approach assumes that the cloud and the user do not collude, whereas the CRSP approach resists to collusions, but needs more resources as it needs to communication with an honest proxy. We have thoroughly compared these two approaches with respect to their privacy guarantees and their practical performance using a standard real-world dataset.

As future work, we plan to integrate our secure join algorithms in a secure query optimizer system based on the MapReduce paradigm. We also aim at designing a protocol that is secure in the standard model and that not depends on a trusted third party.

Fig. 2 :Fig. 1 :

 21 Fig. 2: Joins between relations R 1 , R 2 and R 3 .

Fig. 6 :

 6 Fig. 6: Cascade Algorithm.

Fig. 7 :

 7 Fig. 7: Hypercube algorithm.

Fig. 9 :

 9 Fig.9: Intuition of the SP approach. We denote an IND-CPA public encryption scheme by t¨u, and pseudo-random values by integers.

Fig. 8 :

 8 Fig. 8: Preprocessing of relations.

Fig. 12 : 1 Ð

 121 Fig. 12: SecHypercube algorithm.

Fig. 10 :

 10 Fig. 10: SecCascade algorithm.

Fig. 13 :

 13 Fig. 13: CRSP n-ary joins with MapReduce.

  d is the number of join attributes.

	Algorithm:
	HypercubeJoinpR1, . . . , Rnq
	Map function
	Input: pkey, valueq
	Reduce function
	Input: pkey, valuesq
	// key: px1, . . . , x d q, x P 0, α
	// values: collection of pRi, tq
	for 1 ď i ď n do
	R 1 i Ð	Ť pR i ,tqPvalues ttu;
	for t P R 1 1 ' ¨¨¨' R 1 n do
	emit pt, tq.

// key: id of chunk of R1ďiďn // value: collection of t P Ri foreach t P Ri do for 1 ď ď d do if X P Ri then x Ð h pπX ptqq; else x Ð ‹; emit ppx1, . . . , x d q, pRi, tqq.

  using the running example.

		R1					R1 ' R2
	Name f Name E	City E	Name f Disease f Name E	City E	Disease E
	41 tAliceu tNYCu		23	87	tBobu tLondonu tDiabetesu
	23	tBobu Londonu		23	18	tBobu tLondon	tAIDSu
	36	tEveu tTokyou		36	99	tEveu tTokyou tCanceru
		R2				R3		R1 ' R2 ' R3
	Name f Disease f		Disease E	Disease f Specialist E	Name E	City E	Disease E	Specialist E
	23	87	tDiabetesu	18	tHopkinsu	tBobu tLondonu tAIDSu tHopkinsu
	23	18		tAIDSu	99	tJudeu	tEveu tTokyou tCanceru tJudeu
	36	99		tCanceru

  . . . , x d q, pRi, tqq. Reduce function Input: pkey, valuesq // key: px1, . . . , x d q // values: coll. of pRi, tq for 1

			Algorithm:
			SecHypercubep R1, . . . , Rnq
			Map function
			Input: pkey, valueq
			// key: id of chunk of Ri for
			1 ď i ď n
			// value: collection of t P Ri
			foreach t P Ri do
			for 1 ď ď d do
			if X f P R f i then
			x Ð h pπ X f ptqq;
			else x Ð ‹;
			emit
			ppx1,
	Q	f i`1 XR i`2 f	ptq, tq;
	else
	emit pt, tq.

values: coll. of pQi, tqq and pRi`1, trq for pQ, tqq P values do for pR, trq P values do t " tq ˆtr; if i ‰ n ´1 then emit pπ

Fig. 11: SecBinary algorithm.

Acknowledgements

This research was conducted with the support of the FEDER program of 2014-2020, the region council of Auvergne-Rhône-Alpes, the support of the "Digital Trust" Chair from the University of Auvergne Foundation, the Indo-French Centre for the Promotion of Advanced Research (IFCPAR) and the Center Franco-Indien Pour La Promotion De La Recherche Avancée (CEFIPRA) through the project DST/CNRS 2015-03 under DST-INRIA-CNRS Targeted Programme.

Security Proofs

We present briefly the security proofs of the cascade and the hypercube algorithms in our two approaches considering the Random Oracle Model (ROM).

Complete proofs are given in the technical report available online [START_REF]Secure Joins with MapReduce[END_REF]. We use the standard multi-party computations definition of security against honest-butcurious adversaries. We refer the reader to [START_REF] Lindell | Tutorials on the Foundations of Cryptography[END_REF] for further details.

Theorem 1. Assume f is a secure pseudo random function and Π is an IND-CPA public key encryption scheme. Then, the SP cascade and the SP hypercube algorithms securely computes joins between n relations in ROM in the presence of honest-but-curious adversaries if the cloud and the user do not collude.

Proof (Sketch). We use the hybrid argument. For each protocol (SP cascade and SP hypercube), we first build a simulator Sim 1 where the pseudo random function is simulated by a random oracle. We show that it does not exist a polynomialtime algorithm such that it can distinguish the view of real protocols to the view of Sim 1 since we assume that f is a secure pseudo random function. Values of attributes are encrypted using a public key encryption scheme with the user's public key, hence we build a second simulator Sim 2 working as Sim 1 but where all encryptions are replaced by random values. We show that a distinguer can distinguish an execution of Sim 1 to an execution of Sim 2 only with a negligible probability if the public key encryption scheme is semantically secure. By


Jean-Pierre Tillich
email: jean-pierre.tillich@inria.fr.

The decoding failure probability of MDPC codes

Moderate Density Parity Check (MDPC) codes are defined here as codes which have a parity-check matrix whose row weight is of order the square root of the length n of the code. They can be decoded like LDPC codes but they decode much less errors than LDPC codes: the number of errors they can decode in this case is of order the square root of n. Despite this fact they have been proved very useful in cryptography for devising key exchange mechanisms [BGG + 17]. They have also been proposed in McEliece type cryptosystems. However in this case, the parameters that have been proposed in [MTSB13] were broken in [GJS16]. This attack exploits the fact that the decoding failure probability is non-negligible. We show here that this attack can be thwarted by choosing the parameters in a more conservative way. We first show that such codes can decode with a simple bit-flipping decoder any pattern of

errors. This avoids the previous attack at the cost of significantly increasing the key size of the scheme. We then show that under a very reasonable assumptions the error probability after decoding decays almost exponentially with the codelength with just two iterations of bit-flipping. With an additional assumption it has even been proved that it decays exponentially with an unbounded number of iterations and show that in this case the increase of the key size which is required for resisting to the [GJS16] attack is only moderate.

Introduction

Virtually all the public key cryptography used in practice today can be attacked in polynomial time by a quantum computer [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF]. Even if such a quantum computer does not exist yet, finding viable solutions which would be resistant to a quantum computer is expected to be a lengthy process. This is one of the reasons why the NIST has recently launched a process for standardizing public key cryptographic algorithms that would be safe against a quantum adversary. Code-based cryptography is believed to be quantum resistant and is therefore considered as a viable solution. The McEliece system [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF] based on binary Goppa codes, which is almost as old as RSA, is a public key cryptosystem that falls into this category. It has withstood all cryptanalyses up to now. It is well known to provide extremely fast encryption and fast decryption [START_REF] Biswas | McEliece cryptosystem implementation: theory and practice[END_REF][START_REF] Daniel | Mcbits: Fast constant-time code-based cryptography[END_REF], but has large public keys, about 200 kilobytes for 128 bits of security and slightly less than one megabyte for 256 bits of security [START_REF] Daniel | Attacking and defending the McEliece cryptosystem[END_REF].

There have been many attempts to decrease the key size of this system. They are either based on codes with a better error correction capacity such as generalized Reed-Solomon codes [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF], algebraic geometry codes [START_REF] Janwa | McEliece public key cryptosystems using algebraic-geometric codes[END_REF], a certain kind of non binary Goppa codes (called 1 wild Goppa codes or wild Goppa codes incognito) [START_REF] Daniel | Wild McEliece[END_REF][START_REF] Daniel | Wild McEliece Incognito[END_REF], convolutional codes [START_REF] Löndahl | A new version of McEliece PKC based on convolutional codes[END_REF][START_REF] Gligoroski | McEliece in the world of Escher[END_REF] or polar codes [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF] or on more structured codes, such as codes with a non trivial automorphism group; for instance quasi-cyclic codes [Gab05, BC07, BBC08, BCGO09, MTSB13] or quasi-dyadic and quasi-monoidic Goppa codes [START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF][START_REF] Barreto | Monoidic codes in cryptography[END_REF]. Using codes with better error correction capacity reduces the key size because of the following phenomenon : the size of the public key in a McEliece cryptosystem is generally the size needed to store a systematic generator matrix of the code used in it, that is R(1 -R)n 2 log 2 q bits for a code of rate R and length n over F q . The attacks using generic decoding techniques [START_REF] Stern | A method for finding codewords of small weight[END_REF][START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF] have an exponential complexity which is of the form e α(q,R)t where t is the number of errors that the code can correct. The security of the cryptosystem is generally measured against this attack and a better errorcorrection capacity implies a better dependency of the key size in terms of the complexity of the generic decoding attack. With the second method, the key size is decreased directly because the public generator matrix is a quasi-cyclic code for instance. When the circulant blocks that form the generator matrix of the corresponding code are of size p this allows to decrease the key size by a multiplicative factor p, whereas the best decoding on quasi-cyclic codes have roughly the same complexity as the best generic decoding on unstructured codes.

However, it has turned out that most of the aforementioned schemes allowed key recovery attacks that could not be mounted on the original Goppa codes [SS92, Wie10, MS07, FM08, FOPT10, OTD10, CGG + 14, LT13, CMCP14, COT14, FPdP14, COTG15, BCD + 16]. But some of them remain unbroken by direct key attacks, namely those relying on Moderate Density Parity Check (MDPC) codes [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF] and their cousins [START_REF] Baldi | A new analysis of the McEliece cryptosystem based on QC-LDPC codes[END_REF], the original binary Goppa codes of [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF] and their non-binary variants as proposed in [START_REF] Daniel | Wild McEliece[END_REF][START_REF] Daniel | Wild McEliece Incognito[END_REF]. The family of Moderate Density Parity Check codes (MDPC) codes is particularly interesting since (i) the decryption algorithm is extremely simple and is based on a extremely simple bit flipping decoding algorithm, (ii) direct attacks on key directly really amount to a problem of the same nature as decoding a linear code. This can be used to give a security proof [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF]. However this security proof does not take into account the decoding failure probability. This is not not necessarily a problem in a setting where the scheme is used to devise ephemeral keys [BGG + 17, ABB + 17]. However, in security models where an attacker is allowed to query the decryption oracle many times, this can be a problem as observed by [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] which showed how to attack the parameters proposed in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF]. This attack really exploits the non negligible decoding failure probability of the MDPC codes chosen in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF]. If this probability were as low as 2 -λ where 2 λ is the complexity of the best attack that the scheme has to sustain, then this would not be a problem and the security proof of [BGG + 17] could be used to show the security of the scheme under this stronger attacking model. This raises the issue whether or not the error probability of MDPC codes can be made arbitrarily small.

We tackle this issue by giving several different answers to this issue. We study in depth this question in the regime which is particularly interesting for these cryptographic applications, namely when the weight of the parity-check equations is of order O ( √ n) where n is the length of the MDPC code. We define in the whole article MDPC codes in this way Definition 1 (MDPC code). Let α be a positive real number. An α MDPC code is a binary linear code that admits a parity check matrix whose rows are all of weight ≤ α √ n. When we do not specify α, we implicitly assume that α = 1. In the case where this parity-check matrix have rows of a same weight w and columns of a same weight v, we say that the parity-check matrix is of type (v, w). By some abuse of terminology, we will also call the corresponding code a code of type (v, w).

We will decode these codes with a simple bit-flipping decoding algorithm. One round of decoding is just majority-logic decoding based on a sparse parity-check matrix of the code.

When we perform just one round of bit-flipping we call this decoder a majority-logic decoder. Recall that a majority logic decoder based on a certain parity-check matrix computes for all bits the number u i of parity-checks that involve the bit i that are are unsatisfied. Let n i be the number of parity-checks involving bit i. If for a bit i we have u i > n i /2 (i.e if a strict majority of such parity-checks is violated) the bit gets flipped. We will assume here that the computation of the v i 's so that flipping one bit does not affect the other v j 's. In other words the decoder works as follows when we perform t iterations Usually, majority-logic decoding is performed by taking Algorithm 1 Bit-flipping decoder for all i ∈ {1, . . . , n} do n i ← # {j ∈ {1, . . . , r} : h ji = 1} for a = 1 to t do for all i ∈ {1, . . . , n} do u i ← # {j ∈ {1, . . . , r} :

h ji = 1, h j y = 1 (mod 2)} for all i ∈ {1, . . . , n} do if u i > n i /2 then y i ← 1 -y i
for each bit i a subset of the parity-checks that involve it that do not intersect each other in other positions and perform majority-voting based on this subset. The analysis of the majority-logic decoder is based on this assumption. We proceed differently here by taking into account all parity-checks that involve a given bit. A crucial quantity will play an important role, namely Definition 2 (maximum column intersection). Let H = (h ij ) 1≤i≤r 1≤j≤n be a binary matrix. The intersection number of two different columns j and j of H is equal to the number of rows i for which h ij = h ij = 1. The maximum column intersection of H is equal to the maximum intersection number of two different columns of H.

The point is that it is readily verified (see Subsection 2.1) that Proposition 1. Consider a code with a parity check matrix for which every column has weight at least v and whose maximum column intersection is s. Performing majority-logic decoding based on this matrix (i.e. Algorithm 1 with t = 1) corrects all errors of weight ≤ v 2s . The point is that for MDPC codes the maximum column intersection is really small. We namely prove that for a natural random MDPC code model, the maximum intersection number of the parity-check matrix defining the MDPC code is typically of order Ω log n log log n . Computing the maximum intersection number can obviously be performed in polynomial time and this allows us to give a randomized polynomial time algorithm for constructing MDPC codes of length n and fixed rate R ∈ [0, 1) that correct any pattern of Ω √ n log log n log n errors with the majority-logic decoder decoder.

For these codes we prove here that i. A code that admits a parity-check matrix of type (v, w) and maximum column intersection s corrects at least errors with the majority-logic decoder based on this parity-check matrix.

ii There is a randomized polynomial time algorithm for constructing MDPC codes of length n and fixed rate R ∈ [0, 1) that correct any pattern of Ω √ n log log n log n errors with the majority-logic decoder decoder.

iii. Under a reasonable assumption on the first round of the bit-flipping decoder, the same MDPC codes correct Ω ( √ n) errors with two iterations of a bit-flipping decoder with decoding failure probability of order e -Ω( n log log n log n ) . iv. Under an additional assumption .

It should be noted that under an additional assumption on the subsequent iterations of the bit-flipping decoder, it has been proved in [ABB + 17] that MDPC codes correct Ω ( √ n) errors by performing an unbounded number of bit-flipping iterations with probability of error e -Ω(n) . We also provide some concrete numbers to show that it is possible to construct MDPC codes that avoid completely the [START_REF] Guo | A key recovery attack on MDPC with CCA security using decoding errors[END_REF] attack and for which it is possible to provide a security proof in strong security models with a significant key size overhead when compared to the parameters proposed in [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF] if we want to stay in the no-error scenario, with a reasonable overhead if we make the assumption of the point [iii.] above, and very moderate overhead if we make the assumptions of [iii.] and [iv.]. Notation. We denote by h(x) the entropy (in nats) of a Bernoulli random variable of parameter

x, that is h(x) def = -x ln x -(1 -x) ln(1 -x).

Majority-logic decoding and its performance for MDPC codes

We start this section by proving Proposition 1, then show that for typical MDPC codes the intersection number is small and that this allows to construct efficiently MDPC codes that correct all patterns of O √ n log log n log n errors.

Proof of Proposition 1

Let us first recall this proposition.

Proposition 1. Consider a code with a parity check matrix for which every column has weight at least v and whose maximum column intersection is s. Performing majority-logic decoding based on this matrix (i.e. Algorithm 1 with t = 1) corrects all errors of weight ≤ v 2s . Proof. We denote by H = (h ij ) 1≤i≤r 1≤j≤n the parity-check matrix we use for performing majoritylogic decoding. For i in {1, . . . , r} denote by E i the subset of positions which are in error and in the support of the i-th parity check equation (i.e. h i = 1). We number the parity-check equations of the code from 1 to r. We consider now what happens to y j in the algorithm. There are two cases to consider. Case 1: y j is erroneous. We can upper-bound the number s j of satisfied parity-check equations involving this bit by the number of parity-check equations involving this bit whose support contains at least 2 errors. We consider now the graph G j which is a bipartite graph associated to j which is constructed as follows. Its set of vertices is the union of the set A j of positions different from j which are in error and the set B j of parity-check equations that involve the position j and whose support contains at least 2 errors. There is an edge between a position in A j and parity-check equation i in B j if and only if the parity-check equation involves , that is h i = 1. Let e j be the number of edges of G j and let n j = be the number of parity-check equations involving j. We observe now that

s j ≤ # {i : h ij = 1, |E i | ≥ 2} (1) ≤ e j ≤ s#A j (2) ≤ s(t -1) ≤ s v 2s -1 < v/2.
(1) is just the first observation whereas (2) follows from the fact the degree in G j of any vertex is at most s by the assumption on the maximum intersection number of H. Since v/2 ≤ n j /2 it follows that the majority-logic decoder necessarily flips the bit and therefore corrects the corresponding error.

Case 2: there is no error in position j. We can upper-bound the number u j of unsatisfied positions in a similar way. This time we consider the graph G j whose vertex set is the union of A j which is the set of positions which are in error and B j the set of parity-check equations involving j and whose support contains this time at least one error. We put an edge between a position in A j and parity-check equation i in B j if and only if the parity-check equation involves . Let e j be the number of edges of G j . Similarly to what we did we observe now that

u j ≤ # {i : h ij = 1, |E i | ≥ 1} ≤ e j ≤ s#A j ≤ st ≤ s v 2s (3) ≤ v/2 ≤ n j /2.
In other words we will not flip this bit.

A random model for MDPC codes of type (v, w)

There are several ways to build random MDPC codes of type (v, w). The one which is used in cryptography [BBC08, MTSB13, DGZ17, BGG + 17, ABB + 17, BBC + 17] is to construct them as quasi-cyclic codes. Our proof technique can also be applied to this case, but since there are several different types of construction of this kind, so that we have to adapt our proof technique to each of those, we will consider a more general model here. It is based on Gallager's construction of LDPC codes [START_REF] Robert | Low Density Parity Check Codes[END_REF]. We will construct an r × n random parity-check matrix of type (v, w) by assuming that n is a multiple of w (n = n w), r is a multiple of v (r = r v) and that rw = nv (this condition is necessary in order to obtain a matrix of type (v, w)). Let P n,w be a matrix of size n × n constructed as follows

P n,w = I n ⊗ 1 w =         1 w 0 w . . . . . . 0 w 0 w 1 w 0 w • • • 0 w . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 w 0 w . . . . . . 0 w 1 w        
.

where I n denotes the identity matrix of size n , 1 w a row vector of length w whose entries are all equal to 1, that is

1 w = (1 . . . 1) w times
, 0 w a row vector of length w whose entries are all equal to 0. We then choose v permutations of length n at random and they define a parity-check matrix H(π 1 , . . . , π v ) of size r × n of type (v, w) as

H(π 1 , . . . , π v ) =     P π1 n,w P π2 n,w . . . P πv n,w     ,
where P πi n,w denotes the matrix P n,w whose columns have been permuted with π i . We denote by D r,n,v,w the associated probability distribution of binary matrices of size r × n and type (v, w) we obtain when the π i 's are chosen uniformly at random.

2.3

The maximum intersection number of matrices drawn according to D r,n,v,w

The maximum intersection number of matrices drawn according to D r,n,v,w turns out to be remarkably small when w and v are of order √ n, it is namely typically of order O log n log log n . To prove this claim we first observe that Lemma 1. Consider a matrix H drawn at random according to the distribution D r,n,v,w . Take two arbitrary columns j and j of H and let n jj be the intersection number of j and j . We have for all t ∈ {0, . . . , v}

P(n jj = t) = v t w -1 n -1 t 1 - w -1 n -1 v-t . Proof. Recall that H = (h ij ) 1≤i≤r 1≤j≤n
is of the form

H(π 1 , . . . , π v ) =     P π1 n,w P π2 n,w . . . P πv n,w     ,
for some permutations π 1 , π 2 , . . . , π v chosen uniformly at random in S n . A row i of H is called a coincidence if and only if h ij = h ij . There is obviously one coincidence at most in each of the blocks P π n,w . We claim now that the probability of a coincidence in each of these blocks is w-1 n-1 . To verify this consider the row i of block P π n,w which is such that h ij = 1. The probability that there is a coincidence for this block is the probability that h ij = 1 which amounts to the fact that π (j ) takes its values in a subset of w -1 values among n -1 possible values. All of these n -1 are equiprobable. This shows the claim. Since the coincidences that occur in the blocks are all independent (since the π i 's are independent) we obtain the aforementioned formula.

We use this to prove the following result Proposition 2. Let α and β be two constants such that 0 < α < β. Assume we draw a paritycheck matrix H at random according to the distribution D r,n,v,w where we assume that both v and w satisfy α

√ n ≤ v < w ≤ β √ n.
Then for any ε > 0 the the maximum intersection number of H is smaller than (2 + ε) log n log log n with probability 1 -o(1) as n tends to infinity.

Proof. Let is number the columns of H from 1 to n. For i and j in {1, . . . , n} two different columns of H we denote by E i,j,t the event that the intersection number of i and j is ≥ t. Let E t be the probability that the maximum intersection number is larger than or equal to t. By the union bound, and then Lemma 1 we obtain

P(E t ) = P   1≤i<j≤n E i,j,t   ≤ 1≤i<j≤n P(E i,j,t ) ≤ n 2 v s=t v s w -1 n -1 s 1 - w -1 n -1 v-s
From this we deduce

P(E t ) ≤ n 2 v s=t v v s s (v -s) v-s w -1 n -1 s 1 - w -1 n -1 v-s
where we use the well known upper-bound v s ≤ e vh(s/v) = v v s s (v-s) v-s . This allows to write

P(E t ) ≤ n 2 v s=t v v s s (v -s) v-s w n s (4) ≤ n 2 v s=t v v-s (v -s) v-s v • w s • n s ≤ n 2 v s=t 1 + s v -s v-s v • w s • n s ≤ n 2 v s=t e • v • w s • n s ≤ n 2 v s=t eβ 2 s s
Choose now t ≥ (2 + ε) ln n ln ln n for some ε > 0. When n is large enough, we have that eβ 2 t < 1. In such a case we can write

P(E t ) ≤ n 2 v s=t eβ 2 t s ≤ n 2 eβ 2 t t 1 -eβ 2 t ≤ n 2 K t t
for some constant K > 0. This implies that for n large enough, where γ > 0 is some absolute constant.

P(E t ) ≤ n 2 e (2+ε)
Proof. The randomized algorithm is very simple. We choose n to be a square n = w 2 for some integer w and let v def = (1 -R)w and r def = nv w . Then we draw a parity-check matrix H at random according to the distribution D r,n,v,w . The corresponding code has clearly rate ≥ R. We compute the maximum column intersection of H. This can be done in time O wn 2 . If this column intersection is greater than (2 + ε) ln n ln ln n we output the corresponding MDPC code, if not we draw at random H again until finding a suitable matrix H. By Proposition 1 we know that such a code can correct all patterns of at most α √ n ln ln n (4+ε) ln n errors. This implies the corollary.

Analysis of two iterations of bit-flipping

We derived in the previous section a condition ensuring that one round of bit-flipping corrects all the errors. We will now estimate the probability that performing one round of bit-flipping corrects enough errors so that another round of bit-flipping will correct all remaining errors. To analyze the first round of decoding we will model the bit-flipping algorithm by a binomial distribution. More precisely, consider an MDPC code of type (v, w) and length n. The noise model is the following: an error of weight t was chosen uniformly at random and added to the codeword of the MDPC code. For i ∈ {1, . . . , n -t}, let E 0 i be the Bernouilli random variable which is equal to 1 iff the i-th position that was not in error initially is in error after the first round of iterative decoding. We also denote by U 0 i the counter u j associated to the i-th position which was not in error. U 0 i is the sum v j=1 V 0 ij of v Bernouilli random variables V 0 ij associated to the v parity-check equations involving this bit. A Bernoulli-random variable V 0 ij is equal to 1 if and only the corresponding parity-check is equal to 1. Note that by definition of the bit-flipping decoder

E 0 i = 1 {U 0 i >v/2}
Similarly, for i ∈ {1, . . . , t} we denote by E 1 i the Bernoulli random variable that is equal to 1 iff the i-th bit that was in error initially stays in error after the first round of Algorithm 1. We also define the U 1 i 's and the V 1 ij 's similarly. In this case

E 1 i = 1 {U 0 i ≤v/2} . Let us bring in for b ∈ {0, 1}: p b def = P(V b ij = 1). ( 5
)
It is clear that these probabilities do not depend on i and j and that this definition is consistent.

It is (essentially) proved in [ABB

+ 17] that Lemma 2. Assume that w = O ( √ n) and t = O ( √ n). Then p b = 1 2 -(-1) b ε 1 2 + O 1 √ n , (6)
where

ε def = e -2wt n .
We will recall a proof of this statement in the appendix. We will now make the following assumption that simplifies the analysis Assumption 1. When we use Algorithm 1 on an MDPC code of type (v, w), we assume that • for all i ∈ {1, . . . , n -t} the counters U 0 i of Algorithm 1 are distributed like sums of v independent Bernoulli random variables of parameter q 0 at the first iteration and the E 0 i 's are independent;

• for all i ∈ {1, . . . , t} the counters U 1 i of Algorithm 1 are distributed like sums of v independent Bernoulli random variables of parameter q 1 at the first iteration and the E 1 i 's are independent.

To analyze the behavior of Algorithm 1 we will use the following lemma which is just a slight generalization of Lemma 6 in [ABB + 17] Lemma 3. Under Assumption 1 used for an MDPC code of type (v, w) and when the error is chosen uniformly at random among the errors of weight t, we have for all (b, i) ∈ {0}×{1, . . . , n-t} ∪ {1} × {1, . . . , t},

P(E b i = 1) = O (1 -ε 2 ) v/2 √ vε ,
where

ε def = e -2wt n .
Because this quantity does not depend on i we will therefore denote

q b def = P(E b i = 1).
For the ease of reading the proof of this lemma is also recalled in the appendix. We let

S 0 def = E 0 1 + • • • + E 0 n-t S 1 def = E 1 1 + • • • + E 1 t S 0
is the number of errors that were introduced after one round of iterative decoding coming from flipping the n -t bits that were initially correct. Similarly S 1 is the number of errors that are left after one round of iterative decoding coming from not flipping the t bits that were initially incorrect. Let S def = S 0 + S 1 , which represents the total number of errors that are left after the first round of iterative decoding. We quantify the probability that this quantity does not decay enough by the following Theorem which holds under Assumption 1.

Theorem 1. Provided that Assumption 1 holds, we have for an MDPC code of type (v, w) where v = Θ( √ n) and w = Θ( √ n):

P(S ≥ t ) ≤ 1 √ t e t v 4 ln(1-ε 2 )+ t 8 ln(n)+O(t ln(t /t)) .
From this theorem we deduce that Corollary 2. Provided that Assumption 1 holds, we can construct in expected polynomial time arbitrarily for any designed rate R ∈ (0, 1) an MDPC code of rate ≥ R of an arbitrarily large length n and parity-check equations of weight Θ( √ n) large MDPC codes where the probability of error P e after two iterations of bit-flipping is upper-bounded by e -Ω(n ln ln n ln n ) when there are t = Θ( √ n) errors.

Proof. We use the construction given in the proof of Corollary 1 to construct an MDPC code of type (v, w) of length n = w 2 and with v def = (1 -R)w that allows to correct all patterns of errors of size less than γ √ n ln ln n ln n

for n large enough, where γ > 0 is some absolute constant with just one round of the bit-flipping decoder of Algorithm 1. Then we use Theorem 1 to show that with probability upper-bounded by e -Ω(n ln ln n ln n ) there remains at most γ √ n ln ln n ln n errors after one round of Algorithm 1. This proves the corollary.

In [ABB + 17] there is an additional assumption which is made which is that the probability of error is dominated by the probability that the first round of decoding is not able to decrease the number by some mutiplicative factor α. With the notation of thi section, this assumption can be described as follows.

Assumption 2. There exists some constant α > 0 such that the probability of error P err for an unbounded number of iterations of Algorithm 1 is upper-bounded by P(S ≥ αt) where S is the number of errors that are left after the first round of Algorithm 1 and t is the initial number of errors.

With this additional assumption (Assumption 1 is actually also made) it is proven in [ABB + 17] that the probability of errors decays exponentially when t = Θ( √ n). This is actually obtained by a slightly less general version of Theorem 1 (see [ABB + 17, Theorem 1]).

4 Choosing the length in order to have a negligible probability of error A Proof of Lemma 3

Let us first recall this lemma.

Lemma 3. Under Assumption 1 used for an MDPC code of type (v, w) and when the error is chosen uniformly at random among the errors of weight t, we have for all (b, i) ∈ {0}×{1, . . . , n-t} ∪ {1} × {1, . . . , t},

P(E b i = 1) = O (1 -ε 2 ) v/2 √ vε ,
where

ε def = e -2wt n .
To prove this lemma we will use

For the last estimate we proceed as follows

D(x||y) = x ln x y + (1 -x) ln 1 -x 1 -y = x ln x y -(1 -x) -x + y + O x 2 = x ln x y + x -y + O x 2 .
The Kullback-Leibler appears in the computation of large deviation exponents. In our case, we will use the following estimate which is well known and which can be found for instance in [START_REF] Blondeau | Accurate estimates of the data complexity and success probability for various cryptanalyses[END_REF] Lemma 5. Let p be a real number in (0, 1) and X 1 , . . . X n be n independent Bernoulli random variables of parameter p. Then, as n tends to infinity:

P(X 1 + . . . X n ≥ τ n) = (1 -p) √ τ (τ -p) 2πn(1 -τ ) e -nD(τ ||p) (1 + o(1)) for p < τ < 1, (10)
P(X 1 + . . . X n ≤ τ n) = p √ 1 -τ (p -τ ) √ 2πnτ e -nD(τ ||p) (1 + o(1)) for 0 < τ < p. (11)

C Proof of Lemma 2

Recall first this lemma.

Lemma 2. Assume that w = O ( √ n) and t = O ( √ n).
Then

p b = 1 2 -(-1) b ε 1 2 + O 1 √ n , (6)
where ε def = e -2wt n . Before giving the proof of this lemma, observe P(V b ij = 1) can be viewed as the probability that the j-th parity check equation involving a bit i gives an incorrect information about bit i. This is obtained through the following lemma. Lemma 6. Consider a word h ∈ F n 2 of weight w and an error e ∈ F n 2 of weight t chosen uniformly at random. Assume that both w and t are of order

√ n: w = O ( √ n) and t = O ( √ n). We have P e ( h, e = 1) = 1 2 - 1 2 e -2wt n 1 + O 1 √ n .
Remark 1. Note that this probability is in this case of the same order as the probability taken over errors e whose coordinates are drawn independently from a Bernoulli distribution of parameter t/n. In such a case, from the piling-up lemma [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] we have

P e ( h, e = 1) = 1 -1 -2t n w 2 = 1 2 - 1 2 e w ln(1-2t/n) = 1 2 - 1 2 e -2wt n 1 + O 1 √ n .
The proof of this lemma will be done in the following subsection. Lemma 2 is a corollary of this lemma since we have p b = P( h, e = 1|e 1 = b).

C.1 Proof of Lemma 6

The proof involves properties of the Krawtchouk polynomials. We recall that the (binary) Krawtchouk polynomial of degree i and order n (which is an integer), P n i (X) is defined for i ∈ {0, • • • , n} by:

P n i (X) def = (-1) i 2 i i j=0 (-1) j X j n -X i -j where X j def = 1 j! X(X -1) • • • (X -j + 1). ( 13
)
Notice that it follows on the spot from the definition of a Krawtchouk polynomial that

P n k (0) = (-1) k n k 2 k . ( 14
)
Let us define the bias δ by δ def = 1 -2P e ( h, e = 1).

In other words P e ( h, e = 1) = 1 2 (1 -δ). These Krawtchouk polynomials are readily related to δ. We first observe that

To simplify notation we will drop the superscript n in the Krawtchouk polynomial notation. It will be chosen as the length of the MDPC code when will use it in our case. An important lemma that we will need is the following one.

Lemma 7. For all x in {1, . . . , t}, we have

P w (x) P w (x -1) = 1 + O 1 n n -2w + (n -2w) 2 -4w(n -w) 2(n -w) .
Proof. This follows essentially from arguments taken in the proof of [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF][Lemma 36, §7, Ch. 17]. The result we use appears however more explicitly in [START_REF] Kalai | On the distance distribution of codes[END_REF][Sec. IV] where it is proved that if x is in an interval of the form 0, (1 -α) n/2 -w(n -w) for some constant α ∈ [0, 1) independent of x, n and w, then

P w (x + 1) P w (x) = 1 + O 1 n n -2w + (n -2w) 2 -4w(n -w) 2(n -w) .
For our choice of t this condition is met for x and the lemma follows immediately.

We are ready now to prove Lemma 6.

Proof of Lemma 6. We start the proof by using (15) which says that δ = (-2) w n w

P n w (t).

We then observe that (-2)

P n w (0) = (-2) w n w 1 + O 1 n n -2w + (n -2w) 2 -4w(n -w) 2(n -w) t P n w (0) (by Lemma 7) = 1 + O 1 n t n -2w + (n -2w) 2 -4w(n -w) 2(n -w) t (by (14)) = e t ln 1-2ω+ √ (1-2ω) 2 -4ω(1-ω) 2(1-ω) 1 + O t n where ω def = w n = e t ln 1-2ω+1-4ω+O ( ω 2 ) 2(1-ω) 1 + O t n = e t ln 1-3ω+O ( ω 2 ) 1-ω 1 + O t n = e -2tω+O tw 2 n 2 1 + O t n = e -2wt n 1 + O 1 √ n ,
where we used at the last equation that t

= O ( √ n) and w = O ( √ n).

D Proof of Lemma 3

Let us first recall this lemma.

Lemma 3. Under Assumption 1 used for an MDPC code of type (v, w) and when the error is chosen uniformly at random among the errors of weight t, we have for all (b, i) ∈ {0}×{1, . . . , n-t} ∪ {1} × {1, . . . , t},

P(E b i = 1) = O (1 -ε 2 ) v/2 √ vε ,
where ε def = e -2wt n .

Proof. For (b, i) ∈ {0} × {1, . . . , n -t} ∪ {1} × {1, . . . , t}, let X i be independent Bernoulli random variables of parameter p b . From Assumption 1 we have P(E 0 i = 1) = q 0 = P( v i=1 X 0 i > v/2)

P(E 1 i = 1) = q 1 = P( v i=1
X 1 i ≤ v/2).

By using Lemma 5 we obtain for q 0

q 0 ≤ (1 -p 0 ) 1 2 ( 1 2 -p 0 ) 2πv(1 -1 2 ) e -vD( 1 2 ||p0) ≤ (1 -p 0 ) √ 2 √ πvε (1 + O (1/ √ n)) e -vD( 1 2 || 1 2 -1 2 ε(1+O(1/ √ n))) (16)
≤ (1 -p 0 ) √ 2 √ πvε (1 + O (1/ √ n)) e v ln(1-ε 2 )+O 1 √ n 2 (17) ≤ O (1 -ε 2 ) v/2 √ vε (18)
Whereas for q 1 we also obtain

q 1 ≤ p 1 1 2 (p 1 -1 2 ) 2πv 1 2 e -vD( 1 2 ||p1) (19) ≤ O (1 -ε 2 ) v/2 √ vε (20)

E Proof of Theorem 1

We are ready now to prove Theorem 1. We first recall it.

Theorem 1. Provided that Assumption 1 holds, we have for an MDPC code of type (v, w) where v = Θ( √ n) and w = Θ( √ n):

P(S ≥ t ) ≤ 1 √ t e t v
4 ln(1-ε 2 )+ t 8 ln(n)+O(t ln(t /t)) .

Proof.

P(S ≥ t ) ≤ P(S 0 ≥ t /2 ∪ S 1 ≥ t /2) ≤ P(S 0 ≥ t /2) + P(S 1 ≥ t /2)

By Assumption 1, S 0 is the sum of n-t Bernoulli variables of parameter q 0 . By applying Lemma 5 we obtain P(S 0 ≥ t /2) ≤

(1 -q 0 ) t 2(n-t) ( t 2(n-t) -q 0 ) 2π(n -t)(1 -

We observe now that

D t 2(n -t) q 0 ≥ D t 2(n -t) O (1 -ε 2 ) v/2 √ vε ( 22
)
where we used the upper-bound on q 0 coming from Lemma 3 and the fact that D(x||y) ≥ D(x||y ) for 0 < y < y < x < 1. By using this and Lemma 4, we deduce

D
Similarly to what we did above, by using the upper-bound on q 1 of Lemma 3 and D(x||y) ≥ D(x||y ) for 0 < y < y < x < 1, we deduce that

D t 2t q 1 ≥ D t 2t O (1 -ε 2 ) v/2 ε √ v
By using this together with Lemma 4 we obtain

D t 2t q 1 ≥ -h(t /2t) - t 2t ln O (1 -ε 2 ) v/2 ε √ v + O (1 -4ε 2 ) v/2 ε √ v ≥ - t v

= 1 -

 1 2P e ( h, e = 1) = δ.

  ln(1-ε 2 )+ t 8 ln(n)+O(t ln(t /t)) .

	By using this lower-bound in (23), we deduce
	P(S 1 ≥ t /2) ≤	1 √ t	e	t v 4
	4	ln 1 -ε 2 +	t 8t	ln n + O	t t	ln(t /t) .

Part of this work was supported by the Commission of the European Communities through the Horizon 2020 program under project number 645622 PQCRYPTO.

B The Kullback-Leibler divergence

The proofs of the results proved in the appendix use the Kullback-Leibler divergence (see see for instance [START_REF] Cover | Information Theory[END_REF]) and some of its properties what we now recall. Definition 3. Kullback-Leibler divergence Consider two discrete probability distributions p and q defined over a same discrete space X . The Kullback-Leibler divergence between p and q is defined by

We overload this notation by defining for two Bernoulli distributions B(p) and B(q) of respective parameters p and q D(p||q)

We use the convention (based on continuity arguments) that 0 ln 0 p = 0 and p ln p 0 = ∞.

We will need the following approximations/results of the Kullback-Leibler divergence Lemma 4. For any δ ∈ (-1/2, 1/2) we have

For constant α ∈ (0, 1) and δ going to 0 by staying positive, we have

For 0 < y < x and x going to 0 we have

Proof. Let us first prove (7).

To prove (8) we observe that