Magali Bardet
email: magali.bardet@univ-rouen.fr

Julia Chaulet
email: julia.chaulet@inria.fr

Vlad Dragoi
email: vlad.dragoi1@univ-rouen.fr

Ayoub Otmani
email: ayoub.otmani@univ-rouen.fr

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

Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes

Polar codes discovered by Arikan form a very powerful family of codes attaining many information theoretic limits in the fields of error correction and source coding. They have in particular much better decoding capabilities than Goppa codes which places them as a serious alternative in the design of both a public-key encryption scheme à la McEliece and a very efficient signature scheme. Shrestha and Kim proposed in 2014 to use them in order to come up with a new code-based public key cryptosystem. We present a key-recovery attack that makes it possible to recover a description of the permuted polar code providing all the information required for decrypting any message.

Introduction

The concept of post-quantum cryptography appeared after Peter Shor showed in [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]that all cryptosystems which base their security on the hardness of the factoring problem or the discrete logarithm problem can be attacked in polynomial time with a quantum computer (see [START_REF]Post-Quantum Cryptography[END_REF] for an extensive report). This threatens most if not all public-key cryptosystems deployed in practice, such as RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] or DSA [START_REF] Kravitz | Digital signature algorithm[END_REF]. Cryptography based on the difficulty of decoding a linear code, on the other hand, is believed to resist quantum attacks and is therefore considered as a viable replacement for those schemes in future applications. Yet, independently of their so-called "post-quantum" nature, codebased cryptosystems offer other benefits even for present-day applications due to their excellent algorithmic efficiency.

The first code-based cryptosystem is the McEliece cryptosystem [START_REF] Mceliece | A Public-Key System Based on Algebraic Coding Theory[END_REF], originally proposed using binary Goppa codes. Afterwards, several code families have been suggested to replace them: generalized Reed-Solomon codes (GRS) [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF] or subcodes of them [START_REF] Thierry | How to mask the structure of codes for a cryptographic use[END_REF], Reed-Muller codes [START_REF] Michilovich | A public-key cryptosytem based on Reed-Muller codes[END_REF], algebraic geometry codes [START_REF] Janwa | McEliece public key cryptosystems using algebraic-geometric codes[END_REF], LDPC codes [START_REF] Baldi | Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes[END_REF][START_REF] Baldi | A new analysis of the TMcEliece cryptosystem based on QC-LDPC codes[END_REF], a certain kind of non binary Goppa codes (called wild Goppa codes or wild Goppa codes incognito) [START_REF] Daniel | Wild McEliece[END_REF][START_REF] Daniel | Wild McEliece Incognito[END_REF], MDPC codes [START_REF] Misoczki | MDPC-McEliece: New McEliece variants from moderate density parity-check codes[END_REF], convolutional codes [START_REF] Löndahl | A new version of McEliece PKC based on convolutional codes[END_REF], and more recently polar codes [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF] or subcodes of them [START_REF] Hooshmand | Reducing the key length of McEliece cryptosystem using polar codes[END_REF]. Some of these schemes allow to reduce the public key size compared to the original McEliece cryptosystem while presumably keeping the same level of security against generic decoding algorithms.

However, for many of the aforementioned schemes it has been shown that a description of the underlying code suitable for decoding can be obtained which breaks the corresponding scheme. This has been achieved for GRS codes in [START_REF] Michilovich | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF], subcodes of GRS codes in [START_REF] Wieschebrink | Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes[END_REF], Reed-Muller codes in [START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF]. Algebraic geometry codes based on (very) low genus hyperelliptic curves were broken in [START_REF] Faure | Cryptanalysis of the McEliece cryptosystem over hyperelliptic curves[END_REF], whereas the general case was broken in [START_REF] Couvreur | A polynomial time attack against algebraic geometry code based public key cryptosystems[END_REF]. A first version of the scheme based on LDPC codes proposed in [START_REF] Baldi | Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes[END_REF] has been successfully attacked in [START_REF] Otmani | Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes[END_REF] (but the new scheme proposed in [START_REF] Baldi | A new analysis of the TMcEliece cryptosystem based on QC-LDPC codes[END_REF] seems to be immune to this kind of attack). Some of the parameters that can be found in [START_REF] Daniel | Wild McEliece[END_REF][START_REF] Daniel | Wild McEliece Incognito[END_REF] have been successfully cryptanalyzed with a polynomial time attack in [START_REF] Couvreur | Polynomial time attack on wild McEliece over quadratic extensions[END_REF] or with an exponential time attack in [START_REF] Faugère | Algebraic attack against variants of McEliece with Goppa polynomial of a special form[END_REF], and finally the convolutional scheme of [START_REF] Löndahl | A new version of McEliece PKC based on convolutional codes[END_REF] was successfully cryptanalyzed in [START_REF] Landais | An efficient attack of a McEliece cryptosystem variant based on convolutional codes[END_REF].

All of these attacks (with the exception of [START_REF] Landais | An efficient attack of a McEliece cryptosystem variant based on convolutional codes[END_REF]) pinpoint algebraic properties of the codes which raises the issue of looking for alternative code families with little or no algebraic structure. In this respect the proposals of [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF][START_REF] Hooshmand | Reducing the key length of McEliece cryptosystem using polar codes[END_REF] might be very attractive. Moreover, polar codes enjoy another feature that only few other codes have: they enjoy a decoding algorithm that can also be used to produce for any binary word a codeword that is essentially as close as possible as announced by the information theoretic upper bounds [CT91, Th.13.2.1,Th.13.3.1] (see [START_REF] Satish | Polar codes are optimal for lossy source coding[END_REF] for a proof of this result). This would make such codes perfect candidates in a signature scheme [START_REF] Otmani | On the Design of Code-Based Signatures[END_REF] based on the Niederreiter scheme [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF]. In particular, this would give a much more efficient signature than the CFS scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF].

A McEliece scheme based on (binary) polar codes also raises some other interesting issues. There is basically no large choice for such codes and there is essentially only one polar code (up to permutation of the coordinates) of a given rate. Generally it is advocated that one should take a large code family in the McEliece cryptosystem, because if there is only one code up to permutation of the coordinates, then attacking the scheme amounts to solve the code equivalence problem [START_REF] Petrank | Is code equivalence easy to decide?[END_REF]. For most codes, this is generally easy to do by using the support splitting algorithm [START_REF] Sendrier | Finding the permutation between equivalent linear codes: The support splitting algorithm[END_REF]. However, this algorithm requires in a crucial way that the code has a small hull (which is the intersection of the code with its dual) and a small permutation group, both of them being precisely the opposite for polar codes. Interestingly enough, polar codes are known to be related to the Reed-Muller code family [START_REF] Arıkan | Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels[END_REF]. These two code families behave exactly in the same way with respect to these properties: they have very large hull and permutation group and there is also only one (or zero) Reed-Muller code for a given rate. Note that when a McEliece scheme based on Reed-Muller codes was proposed in [START_REF] Michilovich | A public-key cryptosytem based on Reed-Muller codes[END_REF], its security relied precisely on the assumption that it could be possible in theory to use a single code (up to permutation of the coordinates) by using codes with a large hull and a large permutation group that would defeat attacks based on the support splitting algorithm. It took thirteen years [START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF] to break this McEliece scheme and the attack used many algebraic properties of the Reed-Muller codes, that are presumably absent for polar codes.

However, we will show that despite the fact that polar codes seem to be immune against a plain use of the support splitting algorithm, it can nevertheless be cryptanalyzed successfully. We will show here how to recover from the public generator matrix a description of the code that is suitable for decoding. Our attack uses several ingredients: (i) polar codes have rather low weight codewords which can be found by standard low weight codeword searching algorithms [START_REF] Stern | A method for finding codewords of small weight[END_REF][START_REF] Dumer | On minimum distance decoding of linear codes[END_REF]; (ii) shortening the code with respect to these low weight codewords and taking the dual also gives a code with low weight codewords which can be recovered with the aforementioned algorithms; (iii) by characterizing the permutation group of polar codes together with the low-weight codewords found in Step (ii), it is possible to find among the codewords found in Step (i) a subset of codewords which up to equivalence by the permutation group can be considered as codewords whose support are very specific affine spaces; (iv) Puncturing the code with respect to the support of an element of minimum weight in this last subset of codewords gives a code of small length (typically 16 or 32) whose structure is known up to code equivalence. The code equivalence problem is then solved in this case and is used to recover step by step the underlying polar codes.

Steps (i) and (ii) are directly inspired from the Minder-Shokrollahi attack [START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF] on the McEliece cryptosystem based on Reed-Muller codes, however Steps (iii) and (iv) are new and very specific to polar codes. Basically, the fact that the whole affine group is the permutation group of Reed-Muller code simplifies a great deal the attack of [START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF]. This is not the case anymore for polar codes and the crux for being able to mount this attack is to understand which subgroup of the affine group is part of the permutation group of a polar code and then to use this structure in a relevant way. Amazingly enough, it turns out that a rather large subgroup is the answer to this problem and that polar codes are much more symmetric than could be guessed from their definition. This result is of independent interest and might be used to improve the decoding algorithms of polar codes.

In a general way, in order to understand the structure of polar codes for breaking this cryptosystem we have introduced here new concepts. In particular we suggest here a new code construction, that we call decreasing monomial codes which contains both the Reed-Muller code family and the polar code family and which has a large subgroup of the affine group as permutation group. This construction explains why polar codes have such a large permutation group, but again this new code construction could be of independent interest in coding theory. We also introduce in Step (iv) a novel iterative way of solving the code equivalence problem that could be interesting for solving the code equivalence problem for codes obtained from the (u|u + v) construction.

In this section we recall a few facts about the McEliece cryptosystem, polar codes, the code equivalence problem, and code operations like shortening or puncturing.

Polar Codes. Polar codes were discovered by Arikan [START_REF] Arıkan | Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels[END_REF] and form a very powerful family of codes that gave a nice constructive way of attaining many information theoretic limits in error correction and source coding. In particular, they allow to attain the capacity of any symmetric memoryless channel with a low complexity decoding algorithm (namely the successive cancellation decoder of Arikan). Since they have much better decoding capabilities than Goppa codes, it is reasonable to study whether they can be used in a McEliece scheme. Due to their better correction capacity, this allows for instance to decrease the key sizes of the scheme. Decoding such codes is also faster than decoding Goppa codes and this can also be used to speed up the decryption process.

They can be described as codes of length n = 2 m , where m is an arbitrary integer. They may take any dimension between 0 and 2 m . The polar code of length n = 2 m and dimension k is obtained through a generator matrix which picks a specific subset of k rows of the 2 m × 2 m matrix:

G m def = 1 1 0 1 ⊗ • • • ⊗ 1 1 0 1 m times .
Note that we depart here slightly from the usual convention for polar codes which is to use in the Kronecker product the matrix 1 0 1 1 . The two definitions (ours and the standard one) are easily seen to be equivalent, they just amount to order the code positions differently. Our convention presents the advantage of simplifying the polynomial formalism that follows.

The specific choice of rows that are picked depends (a little bit) on the noisy channel for which the code is devised. For a given noise model, there is a way to compute the k rows which are used to define the generator matrix of the code. Roughly speaking these rows are chosen in such a way that it gives good performances for the successive cancellation decoder.

McEliece cryptosystem. The (binary) McEliece public-key scheme [McE78] can be described as follows. The key generation algorithm picks a random k × n generator matrix G of a binary linear code C which is itself randomly picked in a family of codes for which t errors can be efficiently corrected. The secret key is the decoding algorithm D associated to C and the public key is G. To encrypt u ∈ F k 2 , the sender chooses a random vector e in F n 2 of Hamming weight less than or equal to t and computes the ciphertext c = uG + e. The receiver then recovers the plaintext by applying D on c.

Code equivalence problem. In the McEliece scheme based on polar codes [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF], since there is in essence a single (binary) polar code of a given dimension and length, breaking the scheme amounts to find for a permuted version of the polar code a permutation that gives the original polar code. In other words, we face here as for the McEliece scheme based on Reed-Muller codes the code equivalence problem. To give a formal definition of this problem we will use the following notation and definition.

Notation 1 (Permutation of a word and a code). The symmetric group of degree n is denoted by S n . Let x = (x i ) 0 i<n ∈ F n 2 and π be a permutation of {0, 1, . . . , n -1}. We denote by x π = (x π(i) ) 0 i<n the vector x permuted by π and for a binary code C of length n, its permutation by π is defined by

C π def = c π | c ∈ C .
Definition 1 (Permutation group of a code). The permutation group of a code C is the set of permutations π such that C π = C .

The code equivalence problem can be stated as follows:

Problem 1 (Code equivalence search problem). Given C and C π where C is a code of length n and π belongs to S n , find π in S n such that C π = C π .

Note that we do not necessarily have π = π when the permutation group of the code is non trivial. It is namely immediate to prove that: Proposition 1. For any x = (x i ) 0 i<n in F n 2 and all permutations π and π in S n we have

(x π ) π = x ππ .
Let C be a code of length n with permutation group G and π be a permutation of the same length as C (i.e. a permutation in S n ). We have

π ∈ S n | C π = C π = Gπ
If C has permutation group G, then C π has permutation group π -1 Gπ.

Proof. The first part of the proposition can be proved by bringing in x def = x π and observing that: (i) for any i in {0, . . . , n -1} we have

x i = x π -1 (i) since x j = x π(j) for j = π -1 (i). (ii) (x π ) π = x π = (x π (i) ) 0 i<n = (x π -1 (π(π (i))) ) 0 i<n = (x π(π (i)) ) 0 i<n = x ππ .
From this we deduce that for any σ in G, we have

C σπ = (C σ ) π = C π . Conversely if C π = C π , then (C π ) π -1 = C and therefore ππ -1 is in G, meaning that π is in Gπ.
To prove the last part we observe that if γ is a permutation that leaves C invariant, then π -1 γπ is a permutation that leaves

C π invariant, since (C π ) π -1 γπ = C γπ = (C γ ) π = C π . Conversely if γ is a permutation of C π , then the same kind of computation shows that γ def = πγ π -1 is a permutation of C .
What makes the equivalence problem difficult for polar codes is that the standard algorithm for solving it, namely the support splitting algorithm of [START_REF] Sendrier | Finding the permutation between equivalent linear codes: The support splitting algorithm[END_REF] is too complex to be used in this context due to the very large size of the hull of the polar code. What makes the problem even more intricate is the fact that a polar code turns out to have a very large permutation group which complicates the task significantly.

Operations on codes. One of the basic operations used in the support splitting algorithm for solving the code equivalence problem is to consider shortened and punctured codes. For a given code C and a subset J ⊆ {0, . . . , n -1} the punctured code P J (C ) and shortened code S J (C ) are defined as:

P J (C ) def = (c i ) i / ∈J | c ∈ C ; S J (C ) def = (c i ) i / ∈J | ∃c = (c i ) i ∈ C such that ∀i ∈ J , c i = 0 .
Instead of writing P {j} (C ) and S {j} (C ) when J = {j} we rather use the notation P j (C ) and S j (C ). These codes are used in the following way to solve the code equivalence problem: C is punctured in a position i whereas C π is punctured in some position j. If we have a quick way to check that two codes are not equivalent, then we can use this tool to check whether the two punctured codes may be equivalent or not (in the support splitting algorithm this is done by computing the weight enumerator of the hull which is obviously invariant by permutation). If the two punctured codes are not equivalent, then we know for sure that i and j can not correspond to each other via the permutation of position π. The same idea works also for the shortened code.

Decreasing Monomial Codes

The purpose of this section is to introduce a novel algebraic framework that sheds some light about the structure of polar codes. We will in particular give a new class of codes, that we call decreasing monomial codes that contains as a particular case, polar codes and Reed-Muller codes. The dual of a decreasing monomial code is a decreasing monomial code and under a very mild condition, such codes turn out to be weakly self-dual (i.e. the hull of the code is the code itself). We will then prove that this general construction has a very large permutation group and both facts put together will explain why polar codes have such a large permutation group and hull. We will use here the polynomial formalism that is generally used to describe Reed-Muller codes. It turns out that this polynomial formalism is also very handy for describing polar codes.

Reed-Muller codes. It is well known that Reed-Muller codes of length 2 m can be obtained as evaluation codes of polynomials in F 2 [x 0 , . . . , x m-1 ]. Polar codes can also be described through this formalism. Since we are interested in evaluations of such polynomials over entries in F m 2 we will identify

x i with x 2 i and work in the ring R 2 [x 0 , . . . , x m-1 ] = F 2 [x 0 , . . . , x m-1 ]/(x 2 0 -x 0 , . . . , x 2 m-1 - x m-1
). It will be convenient with this formalism to associate to a polynomial g ∈ R 2 [x 0 , . . . , x m-1 ] the binary vector denoted by ev(g) in F n 2 with n = 2 m which is the evaluation of the polynomial in all the binary entries (u 0 , . . . , u m-1 ) ∈ F m 2 . In other words ev(g) = g(u 0 , . . . , u m-1 ) (u0,...,um-1)∈F m 2

With this notation, we will view the indices of a vector as elements of F m 2 . This notation does not specify the order we use for the elements of F m 2 . We actually use the natural order by viewing (u 0 , . . . , u m ) as the integer

m-1 i=0 u i 2 i . With this notation at hand, the Reed-Muller code R(r, m) is defined as R(r, m) def = ev(P ) | deg P r
Obviously this code is generated by the codewords ev(g) where g is a monomial of degree less than or equal to r. Recall that a monomial is any product of variables of the form

x g0 0 • • • x gm-1
m-1 where g 0 , . . . , g m-1 are binary. The set of all monomials is denoted by:

M def = {1, x 0 , . . . , x m-1 , x 0 x 1 , . . . , x 0 • • • x m-1 }.
Reed-Muller codes have a very large permutation group which is isomorphic to the affine group over F m 2 . Indeed, it can be checked immediately that:

(i) any bijective affine transformation A over F m 2 can be viewed as a permutation of the code positions by mapping (u 0 , . . . , u m-1 ) to A(u 0 , . . . , u m-1 );

(ii) this permutation leaves the code invariant since P (A(x 0 , . . . , x m-1 )) is a polynomial of degree at most the degree of P and therefore if ev(P ) ∈ R(r, m) then ev(P • A) ∈ R(r, m).

Monomial codes. It is straightforward to check that the rows of G are all possible evaluations of monomials. This fact is easily proved by induction on m by observing that (1, 1) is the evaluation of the constant monomial 1 and that (0, 1) is the evaluation of the monomial x 0 . From this, we easily see that a polar code is a monomial code, meaning codes generated by evaluations of monomials (see the formal definition below).

It will also be very convenient to introduce the following partial order on monomials Definition 2 (Monomial order). The monomials of the same degree are ordered as x i1 . . . x is x j1 . . . x js if and only if for any ∈ {1, . . . , s}, i j

where we assume that i

1 < • • • < i s and j 1 < • • • < j s .
This order is extended to other monomials through divisibility, namely: f g if and only if there is a divisor g * of g such that f g * .

Obviously for any monomial f of M the constant polynomial 1 satisfies the inequality 1 f . The interval [f ; h] where f and h are in M with f h is the set of monomials g ∈ M such that f g h. We will also need the following definition Definition 3 (Decreasing set). A set I ⊆ M is decreasing if and only if (f ∈ I and g f ) implies g ∈ I.

With these definitions, we define monomial and decreasing monomial codes as follows.

Definition 4 (Monomial and decreasing monomial codes). Let I be a finite set of multivariate polynomials in m variables and set n def = 2 m . The linear code defined by I is the vector subspace

C (I) ⊆ F n 2 generated by {ev(f ) | f ∈ I}. It is called the polynomial code associated to I. 1. When I ⊆ M, C (I) is called a monomial code. 2. When I ⊆ M is a decreasing set, C (I) is called a decreasing monomial code.
The dimension of monomial codes is easily derived.

Lemma 1. For all I ⊆ M the dimension of the monomial code C (I) is equal to |I|.

Proof. This comes from the linear independence of the monomials in R 2 [x 0 , . . . , x m-1 ].

Example 1. The r-th order Reed-Muller code is the decreasing monomial code defined by the interval [1; x m-r . . . x m-1 ]since:

R(r, m) = C ([1; x m-r . . . x m-1 ]) . The dimension 1 + m + • • • + m r comes directly from Lemma 1.
It turns out that it can be proved, but this is beyond the scope of this article, that polar codes devised for the erasure channel are also decreasing monomial codes. The point is that if we take a row of G m to be a row of the generator matrix (and view this row as a monomial -since as we have explained beforeall these rows correspond to an evaluation of a particular monomial) all the rows that are "smaller" (in the sense of the monomial order defined before) will also be chosen to be part of the generator matrix of the polar code. This fact can be proved by studying the polarization process ( [START_REF] Arıkan | Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels[END_REF]) which is at the heart of choosing the relevant rows of G m . Simple heuristics can be invoked that this also holds for other channel models and we have experimental evidence showing that this seems to hold in particular for polar codes devised for the binary symmetric channel (which are the polar codes used here). This fact can be simply checked for the polar codes that we have attacked here.

Duality and permutation group of decreasing monomial codes. Duals of decreasing monomial codes have a very simple description and it will turn out that under certain very weak conditions, they are weakly self-dual. It is readily seen that the dual of a monomial code is a polynomial code, but it is not necessarily a monomial code. However the dual of a decreasing monomial code turns out to be a decreasing monomial code. To describe this dual we will use the following notion of (multiplicative) complement of a monomial g and denote it by ǧ.

Definition 5 (Complement). For any g ∈ M we define the complement of g as ǧ =

x 0 . . . x m-1 g .

With this notion, we have the following proposition whose proof is in Section A of the appendix.

Proposition 2. Let C (I) be a decreasing monomial code, then its dual is a decreasing monomial code given by

C (I) ⊥ = C (M \ Ǐ).
Notice that this proposition yields the well known result about the dual of a Reed-Muller code RM (r, m) = C ([1; x m-r . . . x m-1 ]) where we have

RM (r, m) ⊥ = C (M \ [x 0 . . . x m-r-1 ; x 0 . . . x m-1 ]) = C ([1; x r+1 . . . x m-1 ]) = R(m -r -1, m).
A straightforward consequence of this is that under some conditions, any decreasing monomial code is weakly self-dual. Polar codes of rate (sufficiently) smaller than 1/2 generally satisfy this assumption and in the case of rate greater than 1 2 it is the dual of the polar code that satisfies this assumption. This can be explained by looking at the polarization process that is used to choose the monomials defining the polar code, but explaining this point is beyond the scope of this article. We just wish to add that this assumption is satisfied for the polar codes used in the McEliece cryptosystem that we have attacked in this article. This corollary explains why such codes are weakly self-dual and why the support splitting is of unreasonable complexity in such a case for recovering the unknown permutation between a known permuted polar code and a polar code.

Polynomial codes and monomial codes may have a trivial permutation group. Applying an affine permutation to a monomial code yields a polynomial code, but it is not necessarily a monomial code. To understand the action of a permutation π which is also an affine transformation on F m 2 we can notice that for any monomial f in R 2 [x 0 , . . . , x m-1 ] we have

ev(f ) π = ev(f • π) (1)
where on the lefthand side we view π as a permutation on the coordinates (viewed as elements of F m 2 ) whereas on the righthand side we view π as an affine permutation. This equation explains why a monomial code may not be a monomial code after applying an affine permutation and it is rather straightforward to come up with examples of monomial codes that have a trivial permutation group. However by considering the subclass of decreasing monomial codes we obtain codes with a very large permutation group which is the lower triangular affine group, that is: Definition 6 (Lower triangular affine group). The lower triangular affine group LTA m on F m 2 is defined as the set of affine transformations over F m 2 of the form x → Ax + b where A is a lower triangular binary matrix with "1"'s on the diagonal and b is arbitrary in F m 2 . Theorem 1. The permutation group of a decreasing monomial code in m variables contains LTA m . This theorem is proved in Section A of the appendix. This theorem explains why polar codes have a large subgroup of the permutation group of Reed-Muller codes as permutation group. This fact is one of the keys for the cryptanalysis which follows.

Minimum distance of decreasing codes. We first recall some well known facts about the minimum distance of Reed-Muller codes (see for instance [MS86, Ch. 13, §4]):

Theorem 2. The minimum distance of the Reed-Muller code R(r, m) is 2 m-r .
There is a one to one correspondance between the affine subspaces of F m 2 of dimension m-r and the minimum codeword of R(r, m): all minimum codewords are obtained as ev(x 0 . . . x r-1 ) where x 0 , . . . , x r-1 are obtained from x 0 , . . . , x r-1 by a bijective affine change of coordinates.

In other words, "up to action of the permutation group there is only one codeword of minimum weight". All these facts have simplified significantly the attack of the McEliece cryptosystem based on Reed-Muller codes in [START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF]. We will see in what follows that polar codes behave differently with this respect.

To understand the minimum distance of a decreasing monomial code, and of a polar code in particular, the following notion is very useful. Definition 7. Let C (I) be a decreasing monomial code over m variables. We let

r -(C (I)) def = max r | R(r, m) ⊆ C (I) r + (C (I)) def = min r | C (I) ⊆ R(r, m)
It is readily checked that another way of defining these quantities is that r -is the largest r for which the monomial x m-r . . . x m-1 is in I. On the other hand r + is the largest integer r for which x 0 . . . x r-1 is in I. These quantities are related to the minimum distance of a decreasing monomial code and its dual through the following result Proposition 3. Let C (I) be a decreasing monomial code over m variables. We have the following properties:

(i) The minimum distance of C (I) is equal to 2 m-r+(C (I)) . (ii) r -(C (I) ⊥ ) and r + (C (I) ⊥ ) satisfy the equalities:

r -(C (I) ⊥ ) = m -1 -r + (C (I)) r + (C (I) ⊥ ) = m -1 -r -(C (I)) (iii) The minimum distance of C (I) ⊥ is equal to 2 r-(C (I))+1
This proposition is proved in appendix Section A. A straightforward corollary of these propositions is that the minimum distance of a polar code is always smaller than or equal to the minimum distance of the Reed-Muller code of the same dimension (if it exists) and this is already a strong indication that this minimum distance is rather small (at most the square root of the length for codes of rate greater than 1 2 for instance). For the polar codes we are interested in in this study, we will be able to find minimum weight codewords in the polar code and its dual with standard algorithms for finding low weight codewords [START_REF] Stern | A method for finding codewords of small weight[END_REF][START_REF] Dumer | On minimum distance decoding of linear codes[END_REF], since both minimum distances turn out to be rather small.

For Reed-Muller codes there is only one orbit of the permutation group inside the set of minimum codewords. The case of decreasing monomial codes is more complicated. However, and this will be very helpful for classifying these codewords, we have: This theorem is proved in Section A of the appendix.

Cryptanalysis

We will explain here how we solve the code equivalence problem for a decreasing monomial code C (I). This can be applied to any polar code and yields an attack that breaks the McEliece scheme based on polar codes proposed in [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF]. In this section, we use the simplified notation r -for r -(C (I)) and r + for r + (C (I)). We also use the notion of signature formalized as follows.

Definition 8 (Signature). Let C be a code of length n. Let G be a subgroup of permutations of C and W be a subset of C globally invariant under G. We say that a function Σ(c, C ) where c belongs to C is a signature for the action of G on W if and only if: Notice here that a signature always takes the same value on an orbit under G since if we take c in W and γ is an element of G, then Σ(c, C ) = Σ(c γ , C γ ) = Σ(c γ , C ) since γ belongs to the permutation group of the code.

(i) Σ(c, C ) = Σ(c π , C π ) for π from S n (i.e. Σ is invariant by permutation), (ii) Σ(c, C ) = Σ(c , C ) if
The algorithm for performing the attack can now be summarized as follows:

Step 1. (Minimum weight codewords searching) Search the non-zero minimum weight vectors of C (I) and C (I) π . We denote these two sets by W min and W π min respectively. Note that

W min = {c ∈ C (I) : |c| = 2 m-r+ }, W π min = {c ∈ C (I) π : |c| = 2 m-r+ } and the codeword c min def = ev(x 0 • • • x r+-1 ) belongs to W min .
Step 2. (Signature of orbits in W min ) Compute the orbits of W min under the lower triangular subgroup LTA m of the affine group and find a signature for these orbits. This signature is based on shortening the dual C (I) ⊥ on the support of c (where c belongs to W min ) and computing the dimension of this code and the number of codewords of minimum weight in it.

Step 3. (Computation of orbits in W π min ) Use this signature to decompose W π min into distinct orbits under the group π -1 LTA m π and use it to find the orbit of c π min .

Step 4. (Identification of affine spaces) Without loss of generality, we may take any codeword in the orbit of c π min and declare that it is equal to c π min . Let I be the support of c min , and J be the complementary set (that is the set of position for which c min takes the value 0). Note that with the way we identify positions as elements of F m 2 , I can be viewed as the affine space

x 0 = x 1 = • • • = x r+-1 = 1.
The structure of the orbit of c min is such that the supports of all the codewords in this orbit are affine spaces of the form x 0 = ε 0 , x 1 = ε 1 , . . . , x r+-1 = ε r+-1 , where the ε i 's are arbitrary elements in F 2 . Denote this affine space by A(ε 0 , . . . , ε r+-1 ) and let c min (ε 0 , . . . , ε r+-1 ) be the corresponding codeword. Up to a permutation of C π , we identify all the elements c min (ε 0 , . . . , ε r+-1 ) π . This gives all the affine spaces permuted by π, that is A(ε 0 , . . . , ε r+-1 ) π def = {π -1 (i) | i ∈ A(ε 0 , . . . , ε r+-1 )}.

Step 5. (Equivalence problem for a short code) Let J be the set of positions where c min takes zero values. Notice that the set of positions for which c π min takes zero values is J π . Then we compute the codes D def = P J (C ) and D π def = P J π (C π ). We solve the code equivalence problem for D and D π where π is the restriction of the permutation π to the affine space I. Notice that this problem is solved for much shorter codes than the original system.

Step 6. (Induction step) Let c i = ev(x 0 . . . , x i-1 ) with c 0 being ev(1), that is the all-one codeword. Notice that c min = c r+ , and let J i be the set of positions for which c i takes the value 0. Denote by D i = P J i (C ). Solve for i = r + -1, . . . , 0 the code equivalence problem for the pair (D i , (D i ) π i ) by using the solution to the code equivalence problem (D i+1 , (D i+1 ) π i+1 ) where π i is the restriction of π to the set of positions of D i .

The last code equivalence problem we solve here (namely for i = 0) is just a solution to the original code equivalence problem.

Step 1 -Minimum weight codewords searching.

Finding the codewords of C (I) π can be performed by applying Dumer's algorithm [START_REF] Dumer | On minimum distance decoding of linear codes[END_REF]. The complexity of this algorithm for finding a codeword of weight w in a code of rate R can be estimated as O e -w ln(1-R)(1+o(1)) when w is a sublinear function of the length (see [START_REF] Canto | Analysis of information set decoding for a sub-linear error weight[END_REF] for more details) and the length n of the code goes to infinity. For monomial codes it can be readily checked that codes with rate greater than some constant ε > 0 have minimum distance at most O( √ n) (this comes from straightforward and well known results about the minimum distance of Reed-Muller codes and Proposition 3). This is clearly achievable for the polar codes we have considered in this article.

On the other hand, all the minimum codewords of C (I) are easily obtained by using Theorem 3: W min decomposes into orbits under the action of LTA m where each orbit contains one of the monomials of I of degree r + .

Step 2 -Signature of orbits in W min

To distinguish between the codewords of W min we have first chosen a monomial in each of the orbits under LTA m that decompose W min . For each of such monomials g we have computed the dual of the shortened code D def = S J (C (I)) ⊥ with respect to the support J of ev(g). It has turned out that, for the polar codes we have considered, the pair (number of codewords of weight 2 r-in D, dimension of D) was discriminant enough to yield a signature of the orbit. This critical quantity 2 r-occurs because we have Theorem 4. Let g = x i1 . . . x ir + be a monomial of degree r + in I. Denote by supp(g) the support of ev(g), then the minimum distance of S supp(g) (C (I))

⊥ is equal to 2 r-if and only if there exists a monomial h in M \ Ǐ such that:

(i) the number of variables of h that are also variables of g is r + -1, (ii) the number of variables of h that are also variables of ǧ is m -r --r + .

This theorem is proved in Section B of the appendix.

Step 3 -Computation of orbits in W π min

The signature Σ that has been found in the previous step is now applied to W π min . It gives the orbits of W π min with respect to the conjugate group π -1 Gπ. Indeed, it can be verified that Proposition 4. W π min is invariant by the action of π -1 LTA m π and if Σ is a signature for W min under the action of LTA m , then it is also a signature for the action of π -1 LTA m π on W π min .

We use this signature for finding the orbit of c min . This orbit has a particularly nice structure: Proposition 5. The orbit of c min under LTA m consists of 2 r+ codewords that are of the form c min (ε 0 , . . . , ε r+-1 ) where the ε i 's are arbitrary elements of F 2 . The orbit of c π min under π -1 LTA m π is given by 2 r+ codewords of weight 2 m-r+ that have disjoint supports which are the permuted versions A(ε 0 , . . . , ε r+-1 ) π of the affine spaces A(ε 0 , . . . , ε r+-1 ).

In other words, finding this orbit in W π min and looking at the support of the codewords that we have found in this way allows us to find the support of the permuted versions A(ε 0 , . . . , ε r+-1 ) π of the affine spaces A(ε 0 , . . . , ε r+-1 ).

Step 4 -Identification of affine spaces

There are several ways to identify the permuted versions of the affine spaces we are interested in. One of the simplest way, which worked for the [2048, 614] polar code that we studied, is by computing the dimensions of certain spaces. First we take any codeword in the orbit of c min . Such codeword is of the form c γπ min where γ is a permutation leaving C (I) invariant. In other words, up to applying the permutation group, we can safely declare that this codeword is c π min . Let I 0 be the support of c min = c(1, . . . , 1). We choose I 0 be the support of the codeword c( 1, . . . , 1 (r+-1) times , 0). Notice that I def = I 0 ∪ I 0 is the support of the codeword ev(x 0 . . . x r+-2 ). We compute the dimension of the code P I (C (I)). Now, we let J 0 , . . . , J 2 r + -1 be the supports of the codewords that are in the orbit of c π min , with J 0 being the support of the codeword c γπ min that has been chosen. We compute the dimensions of the codes P J0∪Ji (C (I) π ) for i = 1, . . . , 2 r+ -1. It turns out that there is generally a single space J i such that dim (P J0∪Ji (C (I) π )) = dim (P I (C (I))). We pair these two spaces J 0 and J i together. This process can be used to pair together all the spaces A(ε 0 , . . . , ε r+-2 , 0) γπ and A(ε 0 , . . . , ε r+-2 , 1) γπ by pairing together J i and J j when J j is the only space for a given i such that dim P Ji∪Jj (C (I) π ) = dim (P I (C (I))) .

In such a case, J i and J j necessarily correspond to A(ε 0 , . . . , ε r+-2 , 0) γπ and A(ε 0 , . . . , ε r+-2 , 1) γπ for a certain (ε 0 , . . . , ε r+-2 ) ∈ F r+-1 2

. In other words, we know after this process all the spaces A(ε 0 , . . . , ε r+-2 ) γπ = A(ε 0 , . . . , ε r+-2 , 0) γπ ∪ A(ε 0 , . . . , ε r+-2 , 1) γπ . We can carry on this process with the codeword c = ev(x 0 . . . x r+-1 ) instead of c min and recover all the permuted affines spaces A(1) γπ , A(1, 1) γπ , . . . , A(1, 1, . . . , 1 r+ times ) γπ for some permutation γ leaving C (I) invariant.

Step 5 -Equivalence problem for a short decreasing monomial code

We now have to solve the code equivalence problem for D which is a code of length 2 m-r+ which is much shorter than the original code. It is also straightfor-ward to check that it is a decreasing monomial code. We can for instance carry out the process again that we saw before. For the [2048,614] polar code that we studied, we can even compute the whole permutation group of the code which is much closer to the whole affine group. It is here a code of length 32 that contains R(2, 5) and is contained in R(3, 5). We do not detail this point here, since there are many ways to actually solve the problem.

Step 6 -Induction step

The idea here is to reconstruct the permutation π given that we already know its action on the support of c min . More precisely, the code equivalence problem that we solve here is:

Problem 2 (Code equivalence search problem with side information). Given (C , C π ) and t pairs of code positions (i 0 , j 0 ), (i 1 , j 1 ), . . . , (i t-1 , j t-1 ), find π such that C π = C π and π(i s ) = j s for all s ∈ {0, 1, . . . , t -1}

We use the following algorithm for solving this problem (we let here

I def = {i 0 , . . . , i t-1 } and J def = {j 0 , . . . , j t-1 })
1. we pick a certain number of codewords c(0), . . . , c( -1) of C . 2. Let C (j) the set of codewords of C which coincide with c(j) on the positions belonging to J . We also define C (i) π as the set of codewords of C π that coincide with c(i) π on I. 3. We compute for all i in 0, 1, . . . , -1 and all positions j which are not in J , the number Σ(i, j) which is the number of codewords of minimum weight in P j (C (i)), and similarly for all all positions j that are not in I, the number Σ π (i, j) which is the number of codewords of minimum weight in P j (C (i) π ). 4. We declare for u which is not in I that π(u) = v if there exists a unique v which does not belong to J such that Σ(i, v) = Σ π (i, u) for all i in {0, 1, . . . , -1}.

It is straightforward to verify that this algorithm outputs the unique π solving the problem in this case. We have also encountered cases, where even with the knowledge we have on π, we have different solutions. In such a case, we were able to compute how many solutions we had and add to the set of pairs (i s , j s ) an additional pair (or additional pairs) which gives a unique solution.

Implementation of the Attack on a [2048, 614]-Polar Code

We implemented the [2048, 614]-polar code as follows. The Shannon limit for the noise on a binary symmetric channel of crossover probability p that a code of rate 614 2048 is able to sustain is about p = 0.19. We devised the polar code for a slightly smaller error rate of p = 0.17 and chose the 614 best rows of G 11 which give the best performances for the successive cancellation decoder. Such a code is able to correct more than 200 errors with a small error probability-this should be compared to the 130 errors that a Goppa code of the same rate is able to tolerate. In the case of a Goppa code we have about 70 bits of security against message attacks based on generic linear codes decoding algorithms, whereas we have more than 105 bits of security for the polar code.

We first checked that this code C and its dual C ⊥ are both decreasing monomial codes and computed all the minimum weight codewords by using Theorem 3. The conditions of Corollary 1 were met and the code was weakly self-dual C ⊂ C ⊥ . The minimum distance of C turned out to be equal to 32 and there were 42176 codewords of this weight, whereas the minimum distance of C ⊥ was 8 and there were 6912 codewords of this weight in the dual. The same number of codewords were found by Dumer's algorithm in C π and in (C π ) ⊥ . It tooks 27 seconds to find these codewords in C π and 3 seconds to find these codewords in (C π ) ⊥ on a 8-core XEON E3-1240 running at 3.40 GHz.

But the most time consuming part was Step 6 of the attack when we have to compute the various Σ(i, j)'s that are needed. This is done again by using Dumer's algorithm. The difference with obtaining codewords of minimum weight of the polar code is that in the polar case we know beforehand the number of minimum weight codewords by using a counting procedure based on Theorem 3 and we can stop the search procedure once we have the right amount of different codewords. However when we compute Σ(i, j) we do not know beforehand the number of minimum weight codewords in P j (C (i)) and we use a probabilistic procedure based on the coupon collector problem : once we have found n different minimal codewords, where on average we have found each codeword α ln n times we stop the procedure for a certain value of α greater than 1. Here we have taken α to be equal to 3. In this case, to speed up the computation we chose the c(i)'s to be minimum weight codewords of C . More than 80% of the total computation is actually taken for the last step of induction where we recover a permutation for the whole [2048, 614] code from the partial permutation acting on half its positions. This takes about 227 hours and the total computation time is about 280 hours. This part of the attack is very likely to be improved significantly if need be.

Conclusion

Despite the fact that the code equivalence problem for binary polar codes is a hard instance for the Support Splitting Algorithm, we have shown in this paper that it can nevertheless be solved rather efficiently by a more sophisticated algorithm consisting in (i) looking for minimum weight codewords, (ii) classifying them by using our knowledge of the automorphism group of the polar code to find a particular minimum weight codeword, (iii) use this particular codeword to partition the code positions into affine spaces, (iv) puncture the set of positions with respect to all these affine spaces but one, and solve the code equivalence problem on this reduced problem. We use this to solve the code equivalence problem by induction on increasing affine spaces. This allows to break the McEliece cryptosystem for the parameters proposed in [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF]. It is likely that the only way to avoid this kind of attack (or possible improvements on it) is to look for polar code parameters for which we are unable to find minimum weight codewords either in the code or in its dual. This would require to change significantly the parameters proposed in [START_REF] Sujan | New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[END_REF] that would make such polar codes much less attractive for a use in a McEliece cryptosystem.

To obtain this attack we have proposed a new code family, that we call decreasing monomial codes containing as a particular subcase Reed-Muller codes and binary polar codes. These decreasing monomial codes have a very large permutation group that gives some insight about the permutation group of polar codes. This knowledge on the permutation group of polar codes we obtained could also be used in other settings, for instance to improve the decoding performances of polar codes.

This attack can be considered as a first step towards studying the polar code based McEliece scheme proposed in [START_REF] Hooshmand | Reducing the key length of McEliece cryptosystem using polar codes[END_REF]. Our attack does not apply directly to this scheme since it is based on taking a particular kind of random subcode of the polar code. In such a case, the system does not consist in solving the code equivalence problem (or we have to solve as many instances as the number of possible subcodes of this kind which becomes unfeasible in this case). However it seems that some of the tools provided here, and a particular property of polar codes, might also be used to attack such a scheme. Indeed, taking the square of the polar code or the square of its dual (with the definition of a square code given in [CGG + 14]) gives a code which is not the full space in many cases. If the subcode of a polar code was chosen uniformly at random among the spaces of some prescribed codimension inside the code, then the square of such codes would be almost always equal to the square of the polar code when the codimension is large enough. This would give an attack since the square of a polar code which is a decreasing monomial code is readily seen to be a decreasing monomial code itself. From there we can solve the code equivalence problem on the square of this code by using the tools given in this paper. This reveals the secret permutation and breaks the system. With the way the subcodes are chosen in [START_REF] Hooshmand | Reducing the key length of McEliece cryptosystem using polar codes[END_REF] this does not happen, but still the square of the subcode is a very large subcode of the square of the polar code itself and this looks highly suspicious.

g ⇔ ∃ g 1 ∈ M s.t. g = g 1 g 2 with deg g 1 = deg f and f g 1 . From the first case we deduce that f ǧ1 . On the other hand one checks immediately that ǧ1 ǧ. From these two inequalities we deduce f ǧ.

Corollary 2. Let I ⊆ M be a decreasing set then M \ Ǐ is a decreasing set.

Proof. Let h be a monomial that belongs to M \ Ǐ, and let g be a monomial such that g h. If g / ∈ M \ Ǐ then it would mean that there exists f ∈ I such that g = f . This means that f h and by using Lemma 2 we would get ȟ f = f .

Since I is a decreasing set, ȟ ∈ I, that is to say, ȟ = h ∈ Ǐ which contradicts the assumption. Therefore M \ Ǐ is a decreasing set.

These lemmas can now be used to prove Proposition 2 that we recall below.

Proposition. Let C (I) be a decreasing monomial code, then its dual is a decreasing monomial code given by

C (I) ⊥ = C (M \ Ǐ). Proof. As Ǐ = |I|, we have dim C (M \ Ǐ) = |M| -| Ǐ| = |M| -|I| = 2 m - dim C (I) = dim C (I)
⊥ , so we need to prove only one inclusion.

Let f ∈ M \ Ǐ and consider g ∈ I. Notice that < ev(f ), ev(g) >=< ev(f g), ev(1) > where < ., . > stands for the standard inner product in {0, 1} 2 m : < x, y >= i x i y i . Observe now that f g is a monomial and that the only monomial whose evaluation is not orthogonal (with respect to <, >) to the all 1 vector is the "full" monomial x 1 . . . x m . Assume now that we are in such a case: f g = x 1 • • • x m . This means that ǧ is a divisor of f . A divisor of a monomial is always smaller than or equal to this monomial with our definition of order. Therefore ǧ f . From Corollary 2 we know that M \ Ǐ is a decreasing set and that this would imply ǧ ∈ M \ Ǐ. This would imply that ǧ = g would belong to M \ Ǐ = M \ I. This would contradict the assumption that g belongs to I. Therefore we proved by contradiction that C (M \ Ǐ) ⊆ C (I) ⊥ .

A.2 Proof of Theorem 1

Let us recall this theorem:

Theorem. The permutation group of a decreasing monomial code in m variables contains LTA m .

Proof. Let C (I) be a decreasing monomial code and let π be in LTA m . Consider

x in F m 2 . Let x def = π(x).
There exist binary numbers a ij and ε i such that for any i in {0, . . . , m -1} we have

x i = x i + j<i a ij x j + ε i .
An affine permutation π acts also in a natural way on monomials, with its action being defined by π(x i1 . . . x is

) def = x i1 . . . x is .
In other words the action of an affine permutation π on a monomial f is given by f • π. Observe that this action is such that

ev(f ) π = ev(f • π).
Choose now a monomial f in I and use the observation above. We can expand f •π and verify that it is a sum of monomials that are smaller than f with respect to the order that we introduced. Since I is a decreasing set, then all these monomials belong to I as well and therefore we obviously have that ev(f • π) is also in C (I). C (I) is therefore invariant by π.

A.3 Proof of Proposition 3

Let C (I) be a decreasing monomial code. Let us start by proving Point (i), namely that the minimum distance of C (I) is equal to 2 m-r+(C (I)) . This follows on the spot by noticing that r + is also the largest degree of a monomial in I. If we consider the evaluation of this monomial we obtain a codeword of weight 2 m-r+(C (I)) . This implies that the minimum distance of C (I) is smaller than or equal to this quantity. On the other hand, the minimum distance of C (I) is larger than or equal to the minimum distance of R(r + , m) which is equal to 2 m-r+(C (I)) by using Theorem 2. This implies our claim.

Consider now the second point that we recall below

r -(C (I) ⊥ ) = m -1 -r + (C (I)) (5) r + (C (I) ⊥ ) = m -1 -r -(C (I)) (6)
This follows immediately from Proposition 2: C (I) ⊥ = C (M \ Ǐ) and the alternative definitions of r -(C (I) ⊥ ) and of r + (C (I) ⊥ ) which are respectively the largest degree r such that all monomials of degree r are monomials in M \ Ǐ and the largest degree of a monomial that belongs to M \ Ǐ. The third point, namely that the minimum distance of C (I) ⊥ is equal to 2 r-(C (I))+1 is a straightforward of Point(i) applied to the monomial code C (I) ⊥ and by using (6).

A.4 Proof of Proposition 3

Here we want to prove that any minimum weight codeword c in a decreasing monomial code C (I) can be written as c = ev(f ) π where f is a monomial in I and π an element of LTA m .

Note that from Proposition 3 we know that a minimum weight codeword of C (I) is also a minimum codeword of R(r + (C (I)), m). For simplicity we will simply write r + for r + (C (I)) from now on. By using Theorem 2, we know that c can be written as the evaluation of the product of r + independent affine forms x 0 def = ε 0 + j a 0j x j ,• • • , x r+-1 def = ε r+-1 + j a r+-1,j x j where the ε i 's are elements of the binary field F 2 . We claim now that there are r + independent affine forms x" 0 , . . . , x" r+-1 such that:

(i) ev(x 0 . . . x r+-1 ) = ev(x" 0 . . . x" r+-1 ), (ii) for all i ∈ {0, . . . , r + -1} we have that the x" i 's can be written as ε i + j<ϕ(i) a ϕ(i),j x j , where ϕ is some permutation of {0, 1, . . . , m -1} and the ε i 's and a ϕ(i),j are binary. This is easy to check by considering the affine form x i that involves the "largest" variable x j (the one consisting of the largest index j). Let x j0 be this variable. We may assume without loss of generality that this is x 0 . We can check now that ev(x 0 x 1 . . . x r+-1 ) = ev(x 0 x 1 . . . x r+-1 ), where x i = x i -x 0 -1 if x i involves the variable x j0 and x i = x i otherwise. Observe now that the r + -1 affine forms x 1 , . . . , x r+-1 involve only variables x j which are such that j < j 0 . We can carry on this process with these r + -1 (independent) affine forms x"" 1 , . . . , x r+-1 by considering the variable x j which is the largest among the variables that are involved in these affine forms and so on and so forth. We end up with r + affine forms x" 0 , . . . , x" r+-1 which have exactly the aforementioned properties (i) and (ii). Consider the monomial x j0 . . . x jr + -1 which is the product of the "largest" variable x j in each of these x" i 's. This monomial has to belong to I and we obviously have ev(x" 0 . . . x" r+-1 ) = ev(π(x j0 . . . x jr + -1 )) for some π in LTA m . This proves our theorem.

B Proof of the results of Section 4

B.1 Proof of Theorem 4

We will first begin this proof by proving a general result about the dual of shortened monomial codes.

Lemma 3. Let C (I) be a decreasing monomial code and g ∈ I. Let supp(g) be the support of ev(g). We denote by E S supp(g) (C (I))

⊥ the dual of the shortened code in supp(g) that we have extended by zeros in the positions in which we have shortened the code. Then

E S supp(g) (C (I)) ⊥ = {ev((1 + g)f ) : f ∈ M \ Ǐ} Proof. Recall that we have S supp(g) (C (I)) ⊥ = P supp(g) C (I) ⊥
We know that C (I) ⊥ = C (M \ Ǐ). The lemma follows from this and the fact the ev(1 + g) takes value 1 on the complementary of supp(g) and 0 on supp(g).

The following notation turns out to be convenient.

Notation 2. For a monomial g = x i1 . . . x is , its set of indices Ind(g) is given by {i 1 , . . . , i s } and its intersection g ∧ h with a monomial h is given by

g ∧ h def = Π i∈Ind(g)∩Ind(h) x i .
We will also need the following result that is only a slight generalization of [Mn07, Prop. 6, p.69] (and our proof will follow closely the proof of this proposition).

Lemma 4. Let g be some monomial of degree s 1. Denote by supp(g) the support of ev(g), then the minimum distance of S supp(g) (C (I))

⊥ is greater than or equal to 2 r-. If the minimum distance is equal to 2 r-then there exists a monomial h in M \ Ǐ such that (i) the number of variables of h ∧ g is s -1, (ii) the number of variables of h ∧ ǧ is m -r --s.

Proof. Let us take a nonzero codeword of C (I) ⊥ , say that is the evaluation of some polynomial f , which is in this case of degree at most m -1 -r -. Write f = j m j as a sum of monomials. Then f def = j:g mj m j is defined as the polynomial where we have removed from the monomial expression of f all monomials that are divisible by g. Since (S supp(g) (C (I))) ⊥ = P supp(g) C (I) ⊥ , we want to prove that the evaluation of f on {0, 1} m \ supp(g) is either zero or of weight 2 r-. Notice that the evaluation on {0, 1} m \ supp(g) coincides with the evaluation of f .

Let us assume that g = x 0 . . . x s-1 . With this choice, let us pick a monomial of f that has maximum degree in x s , . . . , x m-1 . Let d be this degree (in x s , . . . , x m-1 ). f can be written as f = mu(x 0 , . . . , x s-1 ) + v(x 0 , . . . , x m-1 ), where m is a monomial of degree d in x s , . . . , x m-1 . We take here in the monomials whose sum is equal to f all monomials that are divisible by m and u is just the sum of these monomials divided by m. Let d be the degree of u which is necessarily smaller than s since f does not contain any monomial divisible by g.

Notice that u(x 0 . . . x s-1 ) is non zero in at least 2 s-d -1 entries if we do not count the (1, . . . , 1) entry, since its evaluation is a codeword of R(d , s).

Call a "block" the set of points (x 0 , . . . , x m-1 ) which take a prescribed value on x 0 , . . . , x s-1 . The support supp(g) of g corresponds to the block x 0 = 1, . . . , x s-1 = 1. Notice that the weight of ev( f ) restricted to a block (with the exception of the block x 0 = 1, . . . , x s-1 = 1) is at least 2 m-s-d , since this restriction is a codeword of R(d, m -s). In other words the weight of ev( f (1 + g)) is lower-bounded by This proves the statement about the minimum distance in this case. A quick inspection of this proof shows that the only fact we used on g was that is is different from 1 (the particular form of g was only here to simplify notation), and therefore it also holds for all monomials g different from 1. Assume now that the minimum distance of S supp(g) (C (I))

⊥ is equal to 2 r-. By a quick inspection of this proof this means that deg u = s -1 and deg m = m -r --1 -(s -1) = m -r --s. Write u as a set of monomials u = j m j and choose m as any monomial in this sum that is of degree s -1.

Obviously h def = mm is a monomial of degree s -1 + m -r --s = m -r --1 that appears as a monomial in the sum f = j m j . Therefore h is in M \ Ǐ. Such an h has the aforementioned form.

We will now use this to prove Theorem 4. We recall its statement below.

Theorem. Let g = x i1 . . . x ir + be a monomial of degree r + in I. Denote by supp(g) the support of ev(g), then the minimum distance of S supp(g) (C (I))

⊥ is equal to 2 r-if and only if there exists a monomial h in M \ Ǐ such that:

(i) the number of variables of h that are also variables of g is r + -1, (ii) the number of variables of h that are also variables of ǧ is m -r --r + .

Proof. First of all let us notice that the minimum distance of E S supp(g) (C (I))

⊥ is the same as the minimum distance of S supp(g) (C (I)) ⊥ . From Lemma 3 we know that any codeword in the first code can be written as ev((1 + g)f )) where f is polynomial which is a linear combination of monomials in M \ Ǐ. Consider now that there is a monomial h satisfying the conditions above. Let us prove that the weight of ev((1 + g)h) is equal to 2 r-. Let i 0 be the only index that is in Ind(g) but not in Ind(g ∧ h). Observe now that

(1 + g)h = (1 + x i1 . . . x ir + ) i∈Indg∧h x i i∈Ind(ǧ∧h) By using the lower-bound on the minimum distance coming from Lemma 4 we obtain that the minimum distance of S supp(g) (C (I))

x i = (1 + x i0 )
⊥ is equal to 2 r-.

Assume now that the minimum distance of S supp(g) (C (I))

⊥ is equal to 2 r-, then we can use Lemma 4 and obtain the aforementioned claim.

B.2 Proof of Proposition 4

Proposition. W π min is invariant by the action of π -1 LTA m π and if Σ is a signature for W min under the action of LTA m , then it is also a signature for the action of π -1 LTA m π on W π min .

Proof. The invariance of W π min follows from the fact that (i) LTA m is a subgroup of the permutation group of C (I) by Theorem 1 and (ii) this implies that π -1 LTA m π is a subgroup of the permutation group of C (I) π by Proposition 1. For the second part, it suffices to prove that Σ takes different values on the orbits of W π min under the action of π -1 LTA m π. Consider two elements x π and y π that belong to two different orbits. They are the permuted versions of x and y which belong to different orbits of W min . If this were not the case we would have x = y γ for γ in LTA m . However this would imply that x π = y γπ = y ππ -1 γπ = (y π ) π -1 γπ and this would imply that x π and y π would be in the same orbit under the action of π -1 LTA m π. We finish the proof by observing that

B.3 Proof of Proposition 5

Proposition. The orbit of c min under LTA m consists of 2 r+ codewords that are of the form c min (ε 0 , . . . , ε r+-1 ) where the ε i 's are arbitrary element of F 2 . The orbit of c π min under π -1 LTA m π is given by 2 r+ codewords of weight 2 m-r+ that have disjoint supports which are the permuted versions A(ε 0 , . . . , ε r+-1 ) π of the affine spaces A(ε 0 , . . . , ε r+-1 ).

Proof. Let f be the monomial x 0 . . . x r+-1 (i.e. c min = ev(f )). Under the action of π in LTA m this monomial is transformed into x 0 . . . x r+-1 where x i = ε i + x i + j<i a ij x j where the ε i 's and the a ij 's are binary. The support of such a monomial is given by the affine space x 0 = 1, . . . , x r+-1 = 1, but this is readily seen to be an affine space of the form x 0 = ε 0 , . . . , x r+-1 = ε r+-1 where the ε i 's are binary. This implies the first claim. The claim on the orbit of c π min follows from the fact that for any γ ∈ LTA m we have (c π min ) π -1 γπ = (c γ min ) π .

Corollary 1 .

 1 Let C (I) be a decreasing monomial code with |I| 1 2 2 m . Then C (I) ⊆ C (I) ⊥ if and only if for any f ∈ I, f ∈ I.

Theorem 3 .

 3 Each orbit under the action of LTA m contained in the set of minimum codewords of the decreasing monomial code C (I) contains a monomial of I.

  c and c both belong to W but are not in the same orbit under G (i.e. Σ takes distinct values for each orbit).

  |ev( f )(1 + g)| 2 m-s-d (2 s-d -1) 2 m-s-d 2 s-d 1 2 = 2 m-d-d -1 .Notice that we have d + d m -r --1 and therefore we finally obtain |ev( f )| 2 m-(m-r--1)-1 = 2 r-.

  x i0 )h. Thus |ev((1 + g)h))| = |(ev((1 + x j0 )h)| = 2 m-(m-r--1+1) = 2 r-.

Σ

  (x π , C (I) π ) = Σ(x, C (I)) Σ(y π , C (I) π ) = Σ(y, C (I))Therefore Σ(x π , C (I) π ) and Σ(y π , C (I) π ) are different since Σ(x, C (I)) and Σ(y, C (I)) are different.

A Proofs of the results of Section 3

A.1 Proof of Proposition 2

In order to prove this result, we first prove a few lemmas about the partial order we introduced.

Lemma 2. For all f and g in M, f g if and only if f ǧ.

Then we have two cases:

if deg f = deg g then by definition of the order we have i j for all j = 1, . . . , s. Consider the -th variable x i in the monomial f and the -th variable x j in the monomial ǧ. Let us define

Observe now that (i) since ϕ(u + 1) is either equal to ϕ(u) or to ϕ(u) + 1 and since ϕ(0) 0, ϕ(m -1) m -1, there exists at least one u such that ϕ(u) = u, (ii) when ϕ(u) = u this means that there exist exactly variables x b for b in {0, 1, . . . , u} that belong to the monomial f . All this implies that i is the smallest index u such that ϕ(u) = u (or what amounts to the same it is the smallest index u such that ϕ(u) u). A similar property holds for j . In other words i = min{u : ϕ(u) u}

(2)

From the fact that j a i a for all a in {1, . . . , s} we have that for all indices u ϕ(u) γ(u)

On the other hand, we know that i = ϕ(i ), where the righthand term is larger than or equal to γ(i ) by using (4). Therefore γ(i ) i , and by using (3) we deduce that j i .


Bertrand Caron
email: bertrand.caron@bnf.fr

Thomas Ledoux
email: thomas.ledoux@bnf.fr

Jean-Philippe Tramoni
email: jean-philippe.tramoni@bnf.fr

Stéphanereecht
email: stephane.reecht@bnf.fr

Experiment, Document & Decide: a Collaborative Approach to Preservation Planning at the BnF

Keywords: Preservation strategies and workflows; innovative practice Preservation planning, decision documentation, community involvement

The National Library of France (BnF) has recently implemented a new module for its Scalable Preservation and Archiving Repository (SPAR) to set up preservation strategies based on formats, agents, workflows, tools and tests, and managed asreference packages in the Archive. This module aims to fulfill an objective: for SPAR to be fully selfdocumented. Formats, agents and workflows are formally described and preserved along with the Information packages in which such elements are involved. Although this was a feature that was included from the beginnings of SPAR, the new Preservation Planning module aims to provide a tool that can more easily build these reference packages and that will more closely involve domain experts and the IT department in the processes of preservation planning. But the main innovation lies in the documentation of decisions that directed their selection as standards in SPAR: test data are now preserved as a new kind of reference package.

INTRODUCTION

Since the operational launch of SPAR in 2010, the BnF has had to face a growing diversity of digital documents (heritage digitization in 2010, third-party archiving in 2011, web archiving in 2013, legal deposit of ebooks planned for 2015). Ingest and preservation of these specific materials led the BnF to implement many different workflows involving characterization, processing and transformation tools.

TheBnF felt the urge to recordthe choices made about these operationsnot only within the system logs but also within the repository itself. From data objects on which tests were performed to results of said tests using a software tool, every step explaining the decisions that led experts to carry out a specific preservation plan has to be preserved.

Following the path initiated by the experimental tool Plato [START_REF] Becker | Plato: a service-oriented decision support system for preservation planning[END_REF] and based on discussions with various communities, the "Preservation planning" module was developed to address this specific need. Although all activities of the Preservation planning OAIS entity werenot taken over, its first version allows experts to develop preservation strategies and standards and keep track of their elaboration.

The module is provided with a user-friendly interface and several levels of authorization; its objective is to foster collaborative work between experts from different departments of the library. Term, even if the original computing environment becomes obsolete."

WHY A PRESERVATION PLANNING MODULE? 2.1 What Does OAIS Say

Monitoring the environment of the archive is achieved through two functions: Monitor Designated Community and Monitor Technology. The former calls for interactions with members of the community in order to track changes in their service requirements or product technologies. The latter requires performing surveillance on emerging standards or technologies. Any changes are reported to the two other functions of this entity which are responsible for defining, developing and validating preservation plans and appropriate tools(see [Figure 1]).

The Develop Preservation Strategies and Standards function "is responsible for developing and recommending strategies and standards, and for assessing risks, to enable the Archive to make informed tradeoffs as it establishes standards, sets policies, and manages its system infrastructure." In response to the reports about identified changes in the environment of the archive, this function will have to estimate possible updates in archive operations, including policies, procedures, standards and tools. This evaluation may require prototyping and testing of these updates such as: SIP/AIP templates, submission requirements, new or modified file formats and tools for identifying and characterizing these formats. This process enables the Develop Preservation Strategies and Standards function to issue recommendations and advice to deal with the incoming changes.

Carrying out these recommendations is the responsibility of the fourth function. The Develop Packaging Designs and Migration Plans function "develops new Information Package designs and detailed migration plans and prototypes, to implement Administration policies and directives." This task will include development of new AIP designs, prototype software, test plans, community review plans and implementation plans for phasing in the new AIPs, and may call on expertise or resources from other functions. After proper testing and validation, the developed elementsplans, AIP designs and templates, softwarewill be sent as a package to be put into production.

Context of SPAR

SPAR (Scalable Preservation and Archiving Repository) is the BnF preservation system, compliant with the OAIS model. Its scope is to manage all entities that can be automatedthrough modules corresponding to the OAIS entities.

Tracks and Channels

In SPAR, sets of documents to be ingested are processed by tracks and channels (sub-tracks), according to their nature (e.g., digitized books, audiovisual files, web archives, administrative records), their legal framework, and the way the BnF plans to manage their life cycle and apply preservation strategies. At the present time, SPAR ingests objects through sixtracks: digitized documents and associated files, audiovisual objects, web legal deposit (ARC or WARC files),negotiated legal deposit (ebooks),administrative records,and third-partyarchiving (various kinds of files, from partners outside the institution); several others are in progress.

Every channel is managed by Service Level Agreements (SLAs), negotiated between the Producer and the Archive. They define the terms of ingest, preservation and dissemination (e.g.,formats accepted, maximum size of packages, availability of service).Each SLA is transcribed in XML files that configure the system.

Reference Packages

SPAR is a self-documented system. It holds and preserves its own reference packages, ingested in a Reference track. These packages describe and identify every component of the preservation policy: formats, agents (software products, modules, processes, and humans), ontologies, classification systems, tracks and channels. SPAR uses them to document every process and, because most of them are machine-actionable, to perform automatic operations (e.g., checks, extractions, transformations). Thus, part of Representation Informationand Preservation Description Information is preserved as well as the Data Objects, allowing reference to common information in every package through links and unique identifiers.This way, the verbosity of the manifests is reduced.

Actors

Many OAIS activities and functions cannot be fully automated and need human actors: administrators, preservation experts, developers, risk managers, collection managers and track managers.The Library hastaken the measureof the challengeand is working onits organization (see [START_REF] Bermès | The Human Face of Digital Preservation: Organizational and Staff Challenges, and Initiatives at the Bibliothèquenationale de France[END_REF], [START_REF] Derrot | Preservation is Knowledge: A community-driven preservation approach[END_REF] and [START_REF] Clatin | Digital curators at work: analyzing emerging professional identities at the Bibliothèquenationale de France (BnF)[END_REF]).

Administrators are members of the IT department. They are responsible for deployment of new software versions, channels, requirements, etc. and, above all, for ensuring the system meets the SLAs in the daily production.

Preservation experts are members of many departments (e.g., from bibliographic information, IT, digitization departments, etc.); their expertise is functional or technical (on formats, storage, technical or bibliographic metadata, etc.). They are involved in standards elaboration. They are the core team that monitors the evolution of technology and the needs.

Track managers are members of departments who receive digital material to be preserved in SPAR: legal deposit, preservation, archiving mission, etc. They monitor a specific producer community and are responsible for ingest and preservation of documents belonging to their track.

The Preservation Planning Module: a Bottom-up Strategy

Up to now, development of SPAR was mainly concentrated on Ingest, Storage, Data management and Administration modules.

Figure 2.SPAR milestones

In 2014, the BnFdecided to develop a module intended to fulfill the functions and activities of another OAIS entity: Preservation Planning.

Building Reference Packages

Formerly, the reference packages were discussed between project stakeholders then coded by developers in XML. Now they can be produced by the interface and modified at any time by a larger community of allowed users. Indeed, the new module is designed to foster collaborative work between administrators, track managers and preservation experts on the reference package elaboration.

In general, some of the benefits expected are:

-Greater speed and reactivity, involving common expertise throughout the library; -Increased trustworthiness, thanks to a validation workflow involving more people; and -Increased visibility of preservation activities.

Documenting Decisions about Standards

Whereas formats, channels and agents had always been preserved in SPAR, the Preservation planning module brings a whole new functionality.The entire decision process, from basic migration or characterization tests to preservation plans on a large scale, is now documented in reference packages ingested in SPAR.

Two major cases are foreseen:

1) Characterization. An upcoming file format has to be preserved in SPAR. What characterization tool will be used? What technical metadata is needed? See use case below, 4.1.

2) Migration. The new file has to be transformed when ingested into another format, preferably an open one.

Which final format will be chosen? Which transformation tool will be used?See use case below, 4.

In the end, such tests will result in a new SLAwith a new definition of ingest settings.

Four package types were defined to document this decision process. First, the Data Objects on which tests are carried out (initial "test data") and, in the case of a migration, the result of said tests (transformed "test data") are preserved. Secondly, characterization of initial and transformed data is preserved in "test metadata" packages referring to the Data Objects processed and to the used tool, described and ingested as an agent in the reference channel.One or more "test campaigns" areperformed out of a significant number of tests leading to a decision that is implemented in a "preservation plan".

Figure 3. General organization of test packages

All this information is meant to be preserved in order to document the performed experiments, to give the material to allow the reproduction of these experiments, and to have a stable decision base in order to come back later and be able to reconsider such decisions.

IMPLEMENTATION CHOICES 3.1 A New Approval Workflow

In order to formalize the decision process, a validation circuit was organized, and several levels of authorization were defined according to it.

The following steps of the process were determined:

1) A specific need is submitted by track managers (e.g. a new file format to be preserved) or by preservation experts (e.g. a risk of obsolescence is identified for a specific format).

2) Tests are carried out locally by preservation experts to solve the issue (e.g. characterization and migration tools are run on sample documents).

3) If there has been a transformation, the transformed files are characterized by suitable software.

4) Sample documents and transformed documents are ingested in the Archive. Results of characterization are ingested as well.

5) A decision is taken about how to address the issue, given the tests results. Note that currently no method is defined to come up with the decision: anything such asmind maps, SWOT analysis or decision matrices can be used.

6) Preservation experts create new

SLAs that take into account the new preservation strategy (the file format will be characterized or transformed into another format by a specific tool when ingested).

General Architecture

The module architecture had to reflect the current organization of SPAR. At the same time the module was developed, a working group raised some important organizational issues about the role and attributions of every human agent related to SPAR. The Preservation planning module reflected these changes.

Managing several levels of authorization was a particularly important point in the module, as it gave direct capacity to SPAR"s settings to agents out of the Administration module.

Track managers have rights limited to definition of channels, whereas administrators can read and modify every type of package. Format experts have no rights on the channel packages but have a key role in the elaboration of formats and agent packages.

As the needs of the actors in SPAR are different and might be conflicting, multiple instances of the system have been installed.

-A validation platform is used by developers and the Quality Assurance (QA) team to build and test new versions of the software and to validate it. -A sandbox platform is used by preservation experts and track managers to elaborate reference packages. This instance is also used for training and is regularly cleaned up.

-

The production platform holds SPAR"s current deployed version.

These instances are used in the approval workflow described above as follows:

1) The reference packages are elaborated collaboratively on the sandbox platform. 2) When ready, they are transferred to the QA team who tests them on the validation platform. 3) In the end, they are activated by the Administration and ingested in the production platform.

Going back to the Preservation Planning OAIS Entity, the SPAR implementation can be summarized as below:

Ergonomics and Functionalities

Technically, the module aims to help building step by step a complete reference SIP and to transfer it into the repository. A previously ingested reference package can be updated with new requirements,thus creating a new version of this package.

Updating or creating a new package from an existing one is now easier: authorized users can ask for retrieval of an entire reference package, copy it, modify only the relevant information and ingest it again. The system delivers into a user-specific folder the manifest and the Data Objects contained in the requested package.

The interface usability was a challenge, as it was meant to bridge a gap between domain experts and IT staff. Vocabulary used in the interfaces had to be clear, consistent, precise and, preferably, agnostic about specific metadata terms.

In order to produce a complete machine-actionable reference package, different interfaces are displayed sequentially and cannot be accessed if the required information is not provided at each step. Compliance checks are carried out when moving from one interface to the next.

Common templates to several types of reference packagesaredefined to associate files, define events occurred before the package ingestion or enter its descriptive metadata.

The information provided by the user is recorded within the SIP manifest or within data files in which channel, software or format significant properties are stated. The preservation policy of the Reference track specifies that every version of the packages ingested by the track must be indefinitely preserved. In this way, one can always refer to requirements in effect at the time any event of package ingestion, preservation or dissemination occurred.

An Example: How to Create a Channel Reference Package?

Every channel in the SPAR repository has its own ingest requirements, preservation strategies and dissemination conditions.

The module allows track managers to create new channels and modify existing ones by updating the Service Level Agreements. This has immediate effects on packages ingest, preservation and dissemination.

The interfaces provide a set of information like patterns for descriptive metadata detection, possible transformations of input files, different files groups and formats allowed for each one, files minimum and maximum size, frequency of fixity checks, storage location, and documentation about the channel.

Figure 5. Channel reference package elaboration sequence

At the end of the process, the reference package contains a METS manifest, a complete description of the channel, and the three SLAs (concerning packages ingest, preservation and dissemination) expressed in XML. Three associated Schematron files are used to check the manifests of every package submitted to the channel during its lifecycle.

SOME REAL USE CASES 4.1 A New Format for Heritage Digitization: JPEG 2000

The BnF"sdigitization program was primarily focused on producing images in uncompressed TIFF v6 format which is the preferential preservation format in this case. Due to the increasing volume of data (more than 1PB), the switch to a compressed format was required by the track manager.

Thanks to the collaboration with other heritage institutions, the choice of the JPEG2000 formatwas appealing [START_REF] Buckley | Using lossy jpeg 2000 compression for archival master files[END_REF]. In order to determine which exact settings the Library should require for such a format, a set of sample TIFF images digitized from a vast diversity of material was assembled in a reference tests package. This package was then transformed using the kakadu tool with various settings and the results were compared in order to define the acceptable compression ratio in a similar fashion as described in [START_REF] Martin | Analysis of the variability in digitised images compared to the distortion introduced by compression[END_REF]. In parallel, we use the jpylyzer tool [START_REF] Tarrant | Jpylyzer: Analysing jp2000 files with a community supported tool[END_REF] and an XSLT transformation to generate the corresponding test metadata package in the MIX format. We then had a way to ensure that the new images kept the significant properties of the images while taking less space.

Once the different settings were selected, the Digitized Program track manager was able to modify the reference package of its channel and the preservation system was able to ingest JPEG2000 files, characterized with the adequate tool.

Transforming Office Documents to PDF

In the course of elaborating the "Administrative Records" track, a need for an additionalpreserved copy in PDF format of all the office documents became apparent.

Once again, a set of files were sampled from our production databases trying to target a large time period as well as to vary the versions of production software. As shown in [Figure 3], various tools to make the transformation were tried.

The question of finding a common format to represent the technical metadata ledBnF to XMP [START_REF]Extensible Metadata Platform (XMP)[END_REF], as the only one applicable for such a diversity of formats. The use of the Tika tool [START_REF]Apache Tika[END_REF] to generate the test metadata packages provides a way to evaluate the well-formedness of the output as well as to compare the different outputs.

Currently, we have discovered that no tool is efficient enough to ensure a perfect transformation to PDF; such a conclusion reinforces the strategy of keeping both representations of the files (the original one and the transformed one) in the Archive.

CONCLUSION

As the module has been implemented recently, the BnF has little feedback from its potential users. Appropriation and community involvement will raise new issues and should be addressed in another paper in the years ahead.

However, using this module to elaborate in common SPAR standards has already shown good results, improving interactionbetween domain experts and IT members, and quality.

But the module is one among other results of the BnF"s will to involve more closely librarians in their digital collections preservation.

Finally, the module is likely to undergo evolution, as preservation planning encompasses many more aspects than only creating reference packages. Among them, being able to perform tests or migrations with tools stored in SPAR directly from the planning preservation module is foreseen.

Figure 1 .

 1 Figure 1. Functions of the 'Preservation planning' entity (source: Reference model for an Open Archival Information System (OAIS) [2])As defined by the OAIS standard, the Preservation Planning Functional Entity "provides the services and functions for monitoring the environment of the OAIS, providing recommendations and preservation plans to ensure that the information stored in the OAIS remains accessible to, and understandable by, the Designated Community over the Long

7 ) 8 )

 78 Programmers develop a technical solution (e.g. implementation of new characterization tools) and test it. When ready, the technical solution is activated by the Administration.

Figure 4 .

 4 Figure 4. SPAR implementation of the Preservation Planning OAIS Entity

ACKNOWLEDGMENTS

The authors would like to thank all the members of the SPAR team for their commitment and their invaluable contributions. The Open Preservation Foundation and all its members were paramount in sharing practices and maturation of ideas.