André Chailloux
email: andre.chailloux@inria.fr

Simona Etinski
email: simona.etinksi@cwi.nl

On the (In)security of optimized Stern-like signature schemes

Stern's signature scheme is a historically important code-based signature scheme. A crucial optimization of this scheme is to generate pseudo-random vectors and permutation instead of random ones, and most proposals that are based on Stern's signature use this optimization. However, its security has not been properly analyzed, especially when we use deterministic commitments. In this article, we study the security of this optimization. We first show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time O(2 λ 2 ) while the claimed security is λ bits. This impacts in particular the recent Quasy-cyclic Stern signature scheme [BGKS22]. Our second result shows that there is an efficient fix to this attack. By adding a string salt ∈ {0, 1} 2λ to the scheme, and changing slightly how the pseudorandom strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves λ bits of security, and this fix increases the total signature size by only 2λ bits. We apply this construction to other optimizations on Stern's signature scheme, such as the use of Lee's metric or the use of hash trees, and we show how these optimizations improve the signature length of Stern's signature scheme.

Pr ∃i, j st. A queries

with |B| ≈ |A|.

Putting the 2 inequalities together, we have |Pr[A wins Game:2] -Pr[A wins Game:1]| ≤ Adv SD (|A|) + Θ( t 2 2 l salt

).

Introduction

As the NIST standardization process [NIS17] for post-quantum cryptography advances, the challenge of building efficient and secure post-quantum signature schemes becomes increasingly demanding. Though lattice-based schemes seem as the most promising candidates, their wellstudied alternatives from code-based cryptography are gaining more attention recently. The lack of efficiency of code-based signature schemes, as their major drawback, is addressed in the work of many cryptographers, and different techniques that aim to circumvent this problem were proposed. For some of these techniques, however, it remained unclear if the schemes stayed secure after decreasing the signature size, i.e. if the security reduction still holds in that case.

In this article, we focus on the signature schemes derived from the identification protocol originally proposed by Jacques Stern [Ste94]. Its security is based on the hardness of the syndrome decoding problem [BMvT78] and the Fiat-Shamir transform [FS87], which is wellanalyzed with respect to classical and quantum adversaries. The main drawback of Stern's signature scheme in its original form, the same as of the other code-based schemes, is large signature size (order of a few hundreds kilobytes). Different variants of the scheme are thus proposed to mitigate this problem. Some of them, for example, reduce the signature sizes by reducing the cost of each round of the underlying identification protocol. Some versions use the cut and choose technique or even modify the underlying syndrome decoding problem ([Vér97],

[AGS11], [CVE11], [GRSZ14], [Beu20], [BBC + 20]

, [BGKS22], [FJR21], [FJR22]).

The goal of this article is to study several variants of optimized Stern's signature scheme and to assess their security. We first discuss here two features that appear in Stern's signature and other schemes that use the Fiat-Shamir transform.

Random seeds for constructing pseudo-random strings. In the original Stern's scheme, the signer must generate random vectors y i as well as a random permutations π i . In the signature, some of these have to be revealed and for others, we only have the commitment to these values. Revealing all these values is very costly and makes the signature very long. The idea is to replace these random strings by pseudo-random strings. For example, if we want to construct a vector y ∈ F n q , we use a function E : {0, 1} l seed → F n q , generate a random seed ∈ {0, 1} l seed and set y = E(seed). When one wants to reveal y, it is enough to reveal the seed which is much shorter.

This idea has been used in several proposals but has never been properly proven and we don't even know to what extent this optimization remains secure. In order to maintain λ bits of security1 should we have l seed = 2λ in order to avoid any collision between the seeds, or can we take l seed = λ which ensures that y has λ bits of randomness? As we will see, many designs use seeds of size λ which seems at first sight to be enough.

Using commitment from hash functions The following textbook construction builds a commitment scheme from a hash function H : in order to commit to a string s, pick a random string ρ ∈ {0, 1} 2λ and send as a commitment c = H (s, ρ) ∈ {0, 1} 2λ . In order to reveal s, one also reveals the random value ρ. This commitment scheme has λ bits of security against collision attacks, and also has a strong hiding property. For example, in MQDSS [CHR + 20] , we can read (where k is the security parameter):

In particular the commitment functions now take an additional argument -a random string of length 2k. The reason for this change is that with this additional input it can be shown that the commitment function used in MQDSS is computationally hiding -a property needed to show the EU-CMA security of MQDSS.

The string they refer to is exactly the string ρ. However, in many proposer schemes, this randomization ρ is omitted from the commitment scheme. Indeed, if one has to reveal a string ρ of size 2λ for each opening, this can greatly increase the size of the signature scheme constructed from this commitment. We will call a commitment with ρ a randomized commitment and a commitment without this ρ a deterministic commitment. So what it the correct thing to do? Is it necessary to use randomized commitments or can we use deterministic commitments?

Strikingly, each proposal that uses these 2 ingredients doesn't give the same answers to these questions, some are quite conservative while others take the maximum amount of risk. For instance -[BGKS22] in an optimized Stern's signature scheme, uses seeds of size λ and deterministic commitments. -[BBC + 20] relies on restricted syndrome decoding, uses seeds of size 2λ and deterministic commitments. -As we said, the MQDSS signature scheme uses seeds of size λ bits and commitments of size 2λ. However, the commitments are probabilistic so our attack doesn't work but this is makes the scheme quite inefficient.

Contributions

Our contributions can be divided in 3 parts:

1. First we show that one has indeed to be careful with some optimizations. In Stern's signature scheme, if one adds seeds of size λ and deterministic commitments, then we only achieve 2 λ/2 bits of security instead of λ bits. We show an attack in O(2 λ/2 ) that recovers the secret key in this setting. This directly attacks the scheme presented in [BGKS22]. 2. We present the salt + index construction for commitments in order to circumvent the attack by adding a minimal amount of randomness in the commitment scheme. We show that with this addition, Stern's signature scheme has λ bits of security and the cost in terms of signature size is minimal (a total increase of 2λ bits to be precise). 3. We look at other optimizations of Stern's signature scheme: for example by using Lee's metric or by adding Merkle trees, how to improve even more the size of Stern's signature scheme.

We now elaborate each of these contributions.

Showing the insecurity of some optimized Stern's signature schemes.

Our first contribution is the following Theorem 1. If we use seeds of size λ and deterministic commitments in Stern's signature scheme, then there is an attack that recovers the secret key in time O(2 λ/2 ).

In other words, the choice of [BGKS22] for instance gives only λ/2 bits of security and not λ as claimed. We present here the main idea behind our attack, which is quite simple. Assume you construct a pseudo-random string y using a randomseed st. E(seed) = y and that you commit to y using a deterministic commitment c = H (y). If you perform such a commitment many times, which happens when you perform many calls to the signing oracle, then you will arrive at a collision wp. O(2 λ/2 ) (at least each time there is a collision in the seeds) and an adversary can exploit such a collision. Indeed, if for one signature, this commitment is opened and for another signature it isn't opened, the adversary will be able to guess the committed value for this second signature which will break the scheme.

Mitigating the attack: the salt+ index construction

On multi-HVZK advantage. Before we discuss the way to circumvent the above attack, let's discuss on how come the attack we present exists? Stern's signature scheme is constructed by applying the Fiat-Shamir transform to an identification scheme and this transformation is supposed to be secure. An identification scheme is required to be honest-verifier zero-knowledge and the identification scheme used for instance by [BGKS22] is HVZK. So where is the issue? Actually, if one wants to prove that a signature scheme constructed from an identification scheme is EUF-CMA, we require the identification scheme to be multi-HVZK meaning that it is honest-verifier zero-knowledge even when seeing many transcripts arising from the identification scheme. Normally, this is not a big issue and the HVZK property will imply the multi-HVZK but this needn't be always the case. In [GHHM21], where the authors argue about the security of the Fiat-Shamir transform, they write "In our security proofs, we will have to argue that collections of honestly generated transcripts are indistinguishable from collections of simulated ones. Since it is not always clear whether computational HVZK implies computational HVZK for multiple transcripts, we extend our definition, accordingly: In the multi-HVZK game, the adversary obtains a collection of transcripts (rather than a single one)."

Here, we are exactly in a setting where this subtlety matters. If we consider one call of Stern's optimized identification scheme, then one can construct a simulator st. any adversary that wants to distinguish the real transcript from a simulated transcript needs average time O(2 λ ). However, there is an adversary that runs in time O(2 λ/2 ) which can recover the secret key with overwhelming probability if he is given Ω(2 λ/2 ) independent transcripts. In order words, the t-HVZK property breaks for t = 2 λ/2 . The salt + index construction. The above attack can be circumvented if we use a different hash function H each time we perform a commitment. This is exactly the role of the string ρ in the randomized commitment scheme. In theory, we could have a counter i and use as a commitment H (s, i) the i th time we perform a commitment. However, since we run the signing oracle several times, we would need to remember this counter between different signatures and that would make the scheme stateful. There ie however an idea along these lines that will work:

-Each time you sign, pick a random string salt ∈ {0, 1} 2λ that will act as a randomization string. What is important is that this string is the same for all the commitments used in the signature scheme so we will have to reveal only one such string. -Within each signature: add a counter (which we call index) to ensure that within the same call to the signing oracle, we don't call the same function twice.

Since salt is the same throughout the signature, the whole signature is increased only by l salt = 2λ bits. One can see that our attack will not work. Even if there are collisions in the seeds, the hashed values will be with different salts or different indices, and this negates our attack. Moreover, we show that the resulting scheme is mutli-HVZK, which ensures that no other attacks of this type exist.

Theorem 2. The optimized Stern's signature scheme with salt + index has

Adv t-HV ZK (A) = Adv SD (|A|) + O( t 2 2 l salt ) + O( t 2 l seed
).

The way to read this theorem is the following: it is essentially as hard to break the t-HVZK property than to break the syndrome decoding problem (which is the hard computational problem underlying the whole scheme), as long as l salt ≥ t 2 and l seed ≥ t. t here actually corresponds to the number of calls allowed to the signing oracle, which is often taken to be 2 λ . This motivates the choice l salt = 2λ and l seed = λ. Using existing results on the security of the Fiat-Shamir transform, we have the following (informal) corollary.

Corollary 1. Stern's optimized signature scheme with salt + index is EUF-CMA secure Let us discuss the technical difficulties we had to overcome in order to prove our theorem. It seems at first strange that the advantage of solving the syndrome decoding problem appears in the statement of our theorem but we will make this clear. We want to construct a simulator that will output transcripts computationally indistinguishable from real transcripts. In the identification scheme, the prover commits to some strings and reveals some of them. How should we simulate the committed values comm = H (s, salt, index)? The natural solution is to simulate this with a random string. Indeed, we model H as a random function in the random oracle model so the commitment is a random string. This reasoning is not entirely correct. Since salt and index are publicly known (salt is revealed most often by another opening) it suffices for an adversary to guess s in order to distinguish c from a random string. This shows the difficulty of such zero-knowledge proofs with deterministic commitment, even without pseudorandom strings and seeds. As we mentioned earlier, if we use probabilistic commitments, this problem disappears and we can show that the commitment is statistically indistinguishable from a random string.

Going back to our case, we said that comm = H (z, salt, index) can be distinguished from a random string if we can guess z. This will actually be the only way to distinguish comm from a random string, even in the t-HVZK setting, as long as each salt is different (which happens wp. O( t 2 2 l salt )). Stern's identification scheme consists of many repetitions of an identification scheme where the prover commits to 3 strings z 1 , z 2 , z 3 and reveals 2 out of the 3 depending on the verifier's challenge. In this context, guessing the string z means guessing the string that has not been revealed. But we show that if the adversary can guess this string, then he can recover the secret key, meaning he can solve the underlying syndrome decoding problem. Regarding seeds, we show that if we have salts, the only way to distinguish the random strings from the pseudo-random strings is to guess a seed value, which happens wp. 2 -l seed = 2 -λ so with the salt + index construction, seeds of size λ suffice.

Adding other optimizations Now that we have theoretic foundations that show the security of our optimized Stern's signature scheme. We propose some instantiations where we also add optimizations.

Changing the metric. Stern's identification scheme was originally constructed based on the hardness of the binary syndrome decoding problem but actually, Shamir already proposed a similar scheme based on the permuted kernel problem, which can be seen as a generalization of the binary syndrome decoding. Several variants of this problem: ternary syndrome decoding with large weight [DST19], restricted syndrome decoding, syndrome decoding with Lee's weight [CDE21,WKH + 22,HTW21] have been proposed and studied. In [CDE21], the current authors and Thomas Debris-Alazard presented a cryptanalysis of syndrome decoding using Lee's metric with the idea of proposing Stern's signature scheme Similar schemes but with different optimizations) have also been proposed. Here, we show that Stern's optimized scheme with Lee's metric gives better results than Stern's original scheme.

Hash trees. Once we allow ourselves seeds, there are actually many ways to combine seeds. Here, we show an optimization which is a good compromise between performance and space gain: we regroup 4 rounds of the identification scheme together and we construct the seeds and commitments according to a Merkle tree. We show that this can also lead to some gains.

Hard Problems in Code-Based Cryptography

In this work, we focus on two hard problems in code-based cryptography: the Syndrome Decoding (SD) problem and the Permuted Kernel Problem(PKP). The two have many properties in common, namely, both of them are known to be NP-complete [BMvT78,GJ90] and they are believed to be hard on average once the instance of the problem is taken from the appropriate distribution.

Syndrome Decoding (SD) problem

The canonical hard problem used in code-based cryptography is the syndrome decoding problem, defined as follows.

Problem 1 (Syndrome Decoding, SD(n, k, w)).

Input:

A matrix H ∈ F (n-k)×n q
, n, k ∈ N, a column vector (the syndrome) s ∈ F n-k q , a weight function wt(•) : F n q → N, and a weight w ∈ N. Goal: Find a column vector e ∈ F n q that satisfies He = s and wt(e) = w.

We call q the alphabet size of the problem. The original version of the problem, which we refer to as the binary syndrome decoding problem, corresponds to the case where q = 2 and the weight function is Hamming weight, defined as: wt H (e) = |{i : e i ̸ = 0}|. The decision version of this problem, asking whether there exists a vector e of Hamming weight w satisfying He = s, is proven to be NP complete[BMvT78]. This is problem is also believed to be hard on average, as summarized by the following conjecture.

Conjecture 1 (Average-case hardness of syndrome decoding).

For suitable choices of R = k n = Θ(1) and ω = w n = Θ(1), SD(n, k, w) defined over the Hamming weight wt(•) is hard on average when the input (H, s) is sampled from the distribution D n,k,w given as:

D n,k,w : H $ ← -F (n-k)×n q , e $ ← -S w , return (H, s = He).
(

) 1
where S w is the set of vectors of weight w.

Moreover, the hardness holds even in the presence of quantum computers. One has to be careful with the choice of parameters. Indeed, for constant values 0 < R, ω < 1, this problem can be solved in time poly(n) using Prange's algorithm [Pra62]

for ω ∈ [(1 -R) q-1 q , 1 - (1 -R) q-1 q ]
, while the problem is believed to be exponentially hard outside this zone even for quantum computers, see for instance [KT17].

Permuted Kernel Problem (PKP)

The Permuted Kernel Problem was introduced by Shamir [Sha89], and has the same linear algebra flavor as the syndrome decoding problem. The main difference is that the weight constraint is replaced with a combinatorical constraint, which seemingly removes the connection with decoding linear codes, while preserving the NP-completeness of the problem. The problem is defined as follows.

Problem 2 (Permuted Kernel Problem PKP(n, k, v)).

Input:

A matrix H ∈ F (n-k)×n q , n, k ∈ N, a column vector s ∈ F n-k q , a column vector v ∈ F n q . Goal: Find a permutation σ acting on [n] that satisfies Hσ(v) = s.
As in the case of the syndrome decoding problem, it is believed that the permuted kernel problem is hard on average for suitable choices of v, i.e. given the instances of the problem is sampled from the distribution D n,k (v) sampled as follows:

D n,k (v) : H $ ← -F (n-k)×n q , σ $ ← -P erm [n] , return (H, s = σ(v), v).
One can see that the permuted kernel problem is similar to the syndrome decoding one in many respects. In fact, if we observe the binary syndrome decoding problem over the Hamming weight, and the corresponding permuted kernel problem over the binary field, we can easily show that the two are equivalent.2 For other weight functions, however, they are not equivalent as the set of potential solutions of the syndrome decoding problem is generally wider than the set of potential solutions of the permuted kernel problem3 . Nevertheless, it can be shown that for the properly chosen parameters, finding a solution of the permuted kernel problem yields a solution to the syndrome decoding problem, as summarized in the following proposition.

Reduction from SD to PKP

Other versions of syndrome decoding problem, namely those with a weight function other than the Hamming weight and an alphabet size greater than 2, start to attract more attention of the cryptographic community in the recent years as they yield potentially harder computational problems and hence more efficient code-based schemes. One example of a weight function that is known from coding theory and that recently gained more attention in cryptography is the Lee weight wt L , defined as: ∀e = (e 0 , ..., e n-1 ) ∈ F n q , wt L (e) = n-1 i=0 min(e i , q -e i ). The hardness of SD(n, k, w) using Lee's weight has been studied against classical adversaries as well as the quantum ones [CDE21,WKH + 22] in the Information Set Decoding framework and it is shown that problem is computationally hard in both cases.

Definition 1 (Weight function from distance function). We say that a weight function wt :

F n q → N is constructed from a distance function is there exists a distance function d : F q ×F q → N st. ∀e = (e 0 , . . . , e n-1 ) ∈ F n q , wt(e) = n-1 i=0 d(e i , 0). (2)
This definition allows us to generalize the syndrome decoding problem over different metric spaces with potentially better security and/or better efficiency.

Definition 2 (Vector decomposition). Let x ∈ F n q . The decomposition of x is a q-tuple c = (c 0 , c 1 , . . . , c q-1 ) in which c 0 counts the number of zeros in x, c 1 counts the number of ones, ..., and c q-1 counts the number of q -1 elements in x. In other words:

c i = |{j ∈ {0, . . . , n -1} : x j = i}|.
Lemma 1 ([Bog83]). The number of vectors in F n q having the same decomposition c = (c 0 , c 1 , . . . , c q-1 ) is given by the multinomial coefficient

n c = n c0,c1,...,cq-1 def = n! c0!c1!•••cq-1! .
We now prove what is essentially a reduction from the SD problem to the PKP problem.

Proposition 1 (Reduction from SD to PKP). Take a constant alphabet size q. Assume we have an algorithm A that can solve the P KP (n, k, v) problem in time t. Then, we can use this algorithm to solve randomly chosen instance (H, s) ← D n,k,wt(v) in time t wp. ≥ Ω( 1 poly(q) ). This is true for any weight function wt() satisfying Definition 1.

Proof. Let us fix an instance (H, s) of the syndrome decoding problem sampled from D n,k,w , and let e ∈ S w be the random vector st. He = s sampled when constructing (H, s), as it is done in D n,k,w . Recall that S w def = {x ∈ F n q : wt(x) = w}. Let also C w be the set of all decompositions of the elements from S w , namely:

C w def = {c = (c 0 , • • • , c q-1 ) ∈ N q : ∀i ∈ {0, . . . , q -1}, q-1 i=0 c i = n and q-1 i=0 c i d(0, i) = w}.
The size of S w can now be calculated as the number of vectors having a decomposition in C w , summing over c ∈ C w . Using 1, we get

|S w | = c∈Cw n c .
Now, let C be the set of all decompositions, namely

C def = {c = (c 0 , • • • , c q-1 ) ∈ N q : ∀i ∈ {0, . . . , q -1}, q-1 i=0 c i = n}.
The size of this set C is known to be

n+q-1 q-1 [Bog83]. Moreover, we have C = w C w hence |C w | ≤ |C| for each w. This implies |S w | = c∈Cw n c ≤ n + q -1 q -1 max c∈Cw n c . Let c st. max c∈Cw n c = n c
, and let ṽ be a vector that has the decomposition given by c. We then fix an instance of the permuted kernel problem, PKP(n, k, v), for which the parity check matrix, and the syndrome are the same as for the syndrome decoding instance.

We run our algorithm A to find a solution of this PKP instance we constructed. A solution to this problem will directly yield a solution to our original SD problem, but it is possible that there is no solution to this PKP problem. Notice however that if the error vector e (given by the SD(n, k, w) instance) has the decomposition c, then our P KP (n, k) instance will have a solution. Given that e is sampled uniformly at random from the set S w , this probability is then given by:

n c |S w | ≥ n c n+q-1 q-1 n c = 1 n+q-1 q-1 ≥ 1 (n + q -1) q-1 = Ω 1 poly(n) ,
3 Identification and digital signature schemes

Identification schemes

First definitions In this article, we study 3-round identification schemes, also known as Σprotocols, defined as follows.

Definition 3 (3-round identification scheme). A 3-round identification scheme is an interactive protocol consisting of the following 3 algorithms, which should be efficient with respect to some security parameter λ:

a key generation algorithm Keygen(1 λ ) → (pk, sk), the prover's algorithms P = (P 1 , P 2 ) satisfying P 1 (sk) → (x, St) and P 2 (sk, x, c, St) → z, where x is the first message, St is some internal state, c is the challenge from the verifier and z ∈ R the prover's response (i.e. second message), the verifier's algorithm V (pk, x, c, z) that outputs 1 if the verifier accepts the interaction and 0 otherwise.

We describe below the main steps of an identification scheme.

Identification scheme IS Initialization. Let (pk, sk) ← Keygen(1 λ ). The prover gets (pk, sk) and the verifier gets pk.

Interaction.

1. The prover generates (x, St) ← P 1 (sk) and sends x to the verifier. 2. The verifier picks a uniform c from the challenge set C and sends c to the prover.

3. The prover generates z ← P 2 (sk, x, c, St) and sends z to the verifier.

Verification. The verifier accepts iff. V (pk, x, c, z) = 1.

A transcript consists of the messages exchanged between the prover and the verifier when running IS. In our setting, a transcript is described by (x, c, z). We now define different distribution sof transcripts.

Definition 4 (Distributions of transcripts, honest behavior). For an identification scheme IS, trans IS (pk, sk), is the distribution of transcripts when both the prover and the verifier are honest. This distribution is sampled as follows:

trans IS (pk, sk) : (x, St) ← P 1 (sk), c ← C, z ← P 2 (sk, x, c, St), return(x, c, z).
We also consider transcripts in the case an adversary A who only knows pk tries to impersonate the prover.

Definition 5. For an identification scheme IS and an adversary A(pk), trans A IS (pk), is the distribution of transcripts when an adversary A = (A 1 , A 2 ) that only knows the public key interacts with the verifier.

trans A IS (pk) : (x, St) ← A 1 (pk), c ← C, z ← A 2 (pk, x, c, St), return(x, c, z).
Completeness,soundness and zero-knowledge An identification must satisfy the completeness, soundness and zero-knowledge properties that we describe below.

Definition 6 (Completeness). An identification scheme IS is perfectly complete4 iff.

Pr V (pk, x, c, z) = 1 (pk,sk)←Keygen(1 λ ) (x,c,z)←trans IS (pk,sk) = 1.

For the soundness property, we define the soundness advantage as follows Definition 7 (Soundness Advantage). Let IS be an identification scheme. For any adversary A Adv IS (A) = Pr V (pk, x, c, z) = 1 (pk,sk)←Keygen(1 λ ) (x,c,z)←trans A (pk) .

Notice that we write these definitions in order to perform concrete security statements and not asymptotic statements, where we would only require that an adversary that runs in time poly(λ) has soundness advantage negl(λ).

The zero-knowledge property ensures that the transcripts generated by the identification scheme do not reveal any information, in particular about the secret key. The way the notion of not revealing any information is formalized is through the existence of an efficient simulator Sim(pk) who can output transcripts indistinguishable from real transcripts. For a specified simulator, Adv HV ZK IS (A) corresponds to the probability that an adversary A distinguishes a real transcript from a simulated transcript.

Definition 8 (Honest verifier Zero-knowledge advantage). Let IS be an identification scheme for which we specified a simulator Sim. For any adversary A, we define

Adv HV ZK IS (A) = Pr b = 1 (pk,sk)←Keygen(1 λ ) τ =(x,c,z)←trans IS (pk,sk) b←A(τ,pk) -Pr b = 1 (pk,sk)←Keygen(1 λ ) τ =(x,c,z)←Sim(pk) b←A(τ,pk)
.

As we said in the introduction, an important concept will actually be the notion of multi-HVZK, where we give to an adversary t real or simulated transcripts and we want to consider the distinguishing advantage in this case.

Definition 9 (Multi-Honest verifier Zero-knowledge advantage). Let IS be an identification scheme for which we specified a simulator Sim. For any adversary A, we define (pk,sk)←Keygen(1 λ ) τ1,...,τt←Sim(pk) b=A (τ1,...,τt,pk) .

Parallel repetition of an identification scheme For any identification scheme IS, we define IS ⊗r as the r-fold parallel repetition of IS, which consists of the following:

Identification scheme IS ⊗r

Initialization. Let (pk, sk) ← Keygen(1 λ ). The prover gets (pk, sk) and the verifier gets pk. Interaction.

1. For each i ∈ [r], the prover generates (x i , St i ) ← P 1 (sk) and then sends x = x 1 , . . . , x r to the verifier. 2. The verifier picks a random c = c 1 , . . . , c r for independently randomly chosen challenges and sends c to the prover. 3. The prover generates z = (z 1 , . . . , z r ), where for each i ∈ [r], z i ← P 2 (sk, x i , c i , St i ), and then sends z to the verifier.

Verification. The verifier accepts iff. ∀i ∈ [r], V (pk, x i , c i , z i ) = 1.

Signature schemes

A signature scheme S consists of 3 algorithms (Keygen S , Sign S , Ver S ):

-Keygen S (1 λ ) → (pk, sk) is the generation of the public key pk and the secret key sk from the security parameter λ. -Sign S (m, pk, sk) → σ m : generates the signature σ m of a message m from m, pk, sk.

-Ver S (m, σ, pk) → {0, 1} verifies that σ is a valid signature of m using m, σ, pk. The output 1 corresponds to a valid signature.

We require from our signature schemes correctness and the EUF-CMA property.

Definition 10. A signature scheme is correct iff. when we sample (pk, sk) ← Keygen S (1 λ ), we have for each m Pr[Ver S (m, Sign S (m, pk, sk), pk)] = 1.

We consider the standard EUF-CMA security for signature schemes. To define the advantage of an adversary A, we consider the following EUF-CMA game EUF-CMA game (pk, sk) ← Keygen S (1 λ ).

Run (m * , σ * ) ← A(pk), where A(pk) can perform q sign queries. More precisely, A(pk) constructs m 1 , . . . , m q and receives σ 1 ← Sign S (m 1 , sk, pk), . . . , σ q ← Sign S (m q , sk, pk). Then A performs a procedure to output (m * , σ * ).

A wins the game iff.

Ver S (m * , σ * , pk) = 1 ∧ ∀i ∈ [q], m * ̸ = m i .
The EUF-CMA advantage is defined as follows Definition 11. For a signature scheme S and an adversary A, we define The Fiat-Shamir transform We can directly construct a signature scheme from an identification scheme via the Fiat-Shamir transform [FS87]. From an identification scheme IS = (Keygen, P = (P 1 , P 2 ), V ), we define the following signature scheme S = (Keygen S , Sign S , Ver S ) that uses a random function H :

The Fiat-Shamir transform: constructing S from IS

-Keygen S (1 λ ) = Keygen(1 λ ) -Sign S (m, pk, sk) : (x, St) ← P 1 (pk), c ← H (x, m), z ← P 2 (sk, x, c, St), output σ = (x, z). -Ver S (m, σ = (x, z), pk) = V (pk, x, H (x, m), z).
The transformation is proven to be secure in both classical and quantum random-oracle model, if the identification has good properties. Recently in [GHHM21], the Fiat-Shamir is proven to be secure essentially if the underlying identification scheme has low soundness advantage and low t-HVZK advantage. For Stern's identification scheme, the soundness advantage will be immediate and the main focus of our work will be on the t-HVZK advantage. For instance the attack we present later in the paper uses the fact that one of the proposed variants of Stern's identification has a small HVZK-advantage but a big t-HVZK advantage for t large enough.

Commitment schemes

A commitment scheme consists of 3 algorithms:

-A commit function Commit(s) → (c, St). c is the commitment and St is some internal state (usually some private randomness), used for the opening. -An open function Open(s, St) → o that outputs the opening of the string s.

-A function that verifies the validity of an opening o for a string s and a commitment c:

V er(c, s, o) → {0, 1}.

For a commitment c, (s, o) is valid iff. V er(c, s, o) = 1. Ideally, we want 2 properties from a commitment scheme. First, we want a commitment scheme to be hiding, meaning that any adversary A receiving only the commitment c shouldn't have information about the committed value. More precisely, ∀s, s ′ , we want the following advantage to be as small as possible:

Adv Hiding (A) = Pr b = 1 (c,St)←Commit(s) b←A(s,c) -Pr b = 1 (c,St)←Commit(s ′ ) b←A(s ′ ,c)
Again, we deal with concrete security so we don't specify what condition we want for the hiding advantage. If we dealt with asymptotic security, we would require that for any adversary running in time poly(λ) for some security parameter λ, the above advantage is negligible in λ. The second property we want from a commitment scheme is the binding property, which means that an adversary cannot produce a commitment which can be revealed to 2 different values. We therefore want the following advantage to be as small as possible:

Adv Binding (A) = Pr[V er(c, s, o) = V er(c, s ′ , o ′ ) = 1 ∧ s ̸ = s ′ |(c, s, o, s ′ , o ′ ) ← A() ]
4 Stern's identification scheme

Description of the scheme

In it's original form, the protocol is based on the binary syndrome decoding problem over the Hamming weight, where the instance of the syndrome decoding problem is taken from the distribution D n,k,w defined in the previous section. As mentioned in the introductory part, different variants of the scheme were proposed to mitigate the problem of protocol's high communication cost. The most prominent ones, however, are based on the use of pseudo-random generators, so we focus on them in the next two sections.

We describe the scheme for the case of binary syndrome decoding but our descriptions can be easily extended to the case of PKP with larger alphabet size q. We consider a commitment scheme (Commit, Open, V er) and let P erm n be the set of permutations acting on [n]. Stern's 1 round identification protocol is the following: pk = (H,s). The prover obtains (pk, sk) and the verifier obtains pk.

1 round Stern's identification scheme, generic commitment, IS 1 Stern Initialization. Let (H, e, s = He) $ ← -D n,k,w 1, sk = e,
Interaction.

-The prover picks a random permutation π ∈ P erm n and a random column vector y $ ← -F n q , and then computes t = Hy. The prover computes z 1 = (π, t), z 2 = (π(y)), z 3 = (π(y + e)). For i ∈ {1, 2, 3}, he then constructs (x i , St i ) ← Commit(z i ) and sends each x 1 , x 2 and x 3 to the verifier.

-The verifier sends a random challenge c $ ← -{1, 2, 3} to the prover.

-The prover reveals information so that the verifier can recover z i for each i ∈ {1, 2, 3}\ c. More precisely:

1. if c = 1, the prover computes o 2 = Open(z 2 , St 2 ), o 3 = Open(z 3 , St 3 ) and sends z 2 , z 3 , o 2 , o 3 to the verifier. 2. if c = 2, the prover computes o 1 = Open(z 1 , St 1 ), o 3 = Open(z 3 , St 3 ) and sends z 1 , z 3 , o 1 , o 3 to the verifier. 3. if c = 3, the prover computes o 1 = Open(z 1 , St 1 ), o 2 = Open(z 2 , St 2 ) and sends z 1 , z 2 , o 1 , o 2 to the verifier.
Verification.

1. if c = 1, the verifier checks that |z 2 + z 3 | = w and checks the validity of the commitments z 2 , z 3 so he checks that V er(x 2 , z 2 , o 2 ) = V er(x 3 , z 3 , o 3 ) = 1. 2. if c = 2, the verifier gets z 1 = (π, t) and z 3 = π(y + e). He checks that H(π -1 (z 3 )) = H(y + e) = t + s. He also checks the validity of the commitments z 1 and z 3 . 3. if c = 3, the verifier gets z 1 = (π, t) and z 2 = π(y). He checks that H(π -1 (z 2 )) = H(y) = t. He also checks the validity of the commitments z 1 and z 2 .

Definition 12. Stern's identification scheme IS Stern is the R-fold parallel repetition of (IS 1 Stern ) described above, namely (IS 1 Stern ) ⊗R . When aiming for λ bits of classical security, we take R = λ log 2 (3), and we double the number of rounds R if we want λ bits of quantum security.

Basic properties of Stern's identification scheme

Stern's identification scheme is clearly complete. Soundness and HVZK properties are also known from this scheme and a thorough analysis has been done for instance in [Lei18]. Regarding soundness, we have the following Proposition 2.

Adv IS 1 Stern (A) ≤ 2 3 + Adv Binding (A) + Adv SD (A).
where Adv SD denotes the probability to break the underlying syndrome decoding problem.

Proof. The way this statement is proved actually by using a notion called 3-special soundness.

We show that if an adversary can win the identification scheme simultaneously for the 3 challenges then: or he broke the binding property of the commitment function, or solved the underlying syndrome decoding problem. We refer the reader to [Lei18] for details of this proof.

Moreover, the above scheme is zero-knowledge, if the commitment scheme is hiding Proposition 3.

Adv HV ZK IS 1 Stern (A) ≤ Adv Hiding (A).
Proof. We consider the following simulator:

Simulator

Input. A public key pk = (H, s).

Execution. Pick a random challenge c ← {1, 2, 3}.

-

If c = 1, choose z 2 ← F n q , y ← S w and let z 3 = z 2 + y. For i ∈ {2, 3}, compute (x i , St i ) ← Commit(z i ) and o i = Open(z i , St i ). -If c = 2, choose π ← P erm n , y ← F n q and set t = Hy, z 1 = (π, t) and z 2 = π(y). For i ∈ {1, 3}, compute (x i , St i ) ← Commit(z i ) and o i = Open(z i , St i ). -If c = 3, choose π ← P erm n , y ′ ← F n q and set t = Hy ′ -s, z 1 = (π, t) and z 3 = π(y ′ ). For i ∈ {1, 2}, compute (x i , St i ) ← Commit(z i ) and o i = Open(z i , St i ). Compute (x c , St c ) ← Commit(0) where 0 is the all 0 string. Output. τ = (x 1 , x 2 , x 3 , c, o c ′ , o c ′′ ) where c ′ ̸ = c ′′ and c ′ , c ′′ ̸ = c.
We also rewrite the procedure that generates real transcripts

Real transcript

Input. A public key pk (H, s). A secret key sk = e. Execution. Pick a random permutation π ∈ P erm n and a random string y ∈ F n q . Let t = Hy and z 1 = (π, t), z 2 = π(y), z 3 = π(y + e). Pick a random challenge c ← {1, 2, 3}.

For i ∈ {1, 2, 3}, let (x i , St i ) ← Commit(z i ) and o i = Open(z i , St i ). Output. τ = (x 1 , x 2 , x 3 , c, o c ′ , o c ′′ ) where c ′ ̸ = c ′′ and c ′ , c ′′ ̸ = c.
We now prove that distinguishing these 2 distributions is equivalent to breaking the hiding property of the commitment scheme. First, notice that c ← {1, 2, 3} in both cases. Now, for each challenge, we look at the distribution of z c ′ , z c ′′ for the 2 values c ′ , c ′′ ∈ {1, 2, 3} which are different from c.

-If c = 1: both for the real and the simulated transcript, z 2 is a random string in F n q and z 3 -z 2 is a random string in S w -If c = 2: both for the real and the simulated transcript, z 3 is a random string in F n q . Regarding z 1 = (π, t), in both cases π is a random permutation in P erm n and t = π -1 (z 2 ) -s.

-If c = 3, both for the real and the simulated transcript, z 2 is a random string in F n q . Regarding z 1 = (π, t), in both cases π is a random permutation in P erm n and t = π -1 (z 2 ).

The same distribution for z c ′ , z c ′′ imply the same distributions for (x c ′ , x c ′′ , o c ′ , o c ′′ ) given c for real and simulated transcripts. Finally, we are left with x c . For real transcripts, it is the commitment of z c and for simulated transcripts, it is the commitment of 0. By definition of the hiding property, if we can distinguish these 2 settings then we can break the hiding property of the commitment scheme.

Optimized schemes

The choice of commitment From a hash function H , it is known how to construct a commitment scheme which is both hiding and binding. We take Commit(s) = (c = H (s||ρ), St = ρ) for a randomly chosen ρ of large enough length, and the opening consists of revealing the value ρ, from which one can verify that the commitment is well formed. However, this implies that in order to reveal s, one has to send this string ρ each time. We will call this commitment a randomized commitment

In the literature regarding Stern's signature scheme, we most often see another choice for commitment, namely Commit(s) = (c = H (s), St = ∅) and the opening is also empty so in order to open s, you can just reveal s and the verification just checks that c = H (s). This improves the communication cost. However, this scheme is not hiding anymore. Indeed, an adversary distinguish Commit(s) from Commit(s ′ ) for fixed (and known) s, s ′ just by recomputing these 2 values (which he couldn't do before because he didn't know ρ). We will call this commitment a deterministic commitment.

We haven't seen the choice of deterministic commitment widely discussed regarding security. It seems that this has been the default choice (except for example in [Lei18] and in MQDSS which is not based on the syndrome decoding problem but for which a similar discussion exists) because of it's higher efficiency and because the lack of hiding property didn't seem to be exploitable. It could be that the hiding property given by randomized commitments is overkill and that deterministic commitments are enough for having a secure scheme. This question is actually at the core of our contributions, where we show that there are security issues regarding deterministic schemes, but that they can be repaired much more efficiently than by using the randomized commitments described above.

Adding seeds Another standard technique for reducing the communication cost of identification protocols is to replace some of the random vectors with pseudo-random ones. We thus consider the following functions, i.e. pseudo-random generators:

0 : {0, 1} l seed → {0, 1} l seed × {0, 1} l seed , E 1 : {0, 1} l seed → P erm n , E 2 : {0, 1} l seed → F n q ,
where l seed ∈ N is the seed size. We present below a state of the art 1 round optimized scheme which uses deterministic commitments and seeds, which is similar to the one presented in [BGKS22]. We denote by H comm the hash function used for the commitment.

Stern's identification scheme (optimized, 1 round), IS 1

Stern,opt

Initialization. Let (H, e, s = He) $ ← -D n,k,w 1, sk = e, pk = (H, s). The prover obtains (pk, sk) and the verifier obtains pk.

Interaction.

-The prover picks a random seed ∈ {0, 1} l seed . Let (seed π , seed y ) = E 0 (seed), π = E 1 (seed π ) and y = (π) -1 (E 2 (seed y )). It then computes t = Hy, z 1 = (π, t), z 2 = π(y), z 3 = π(y + e), and computes for i ∈ {1, 2, 3}, x i = H comm (z i ). He then sends x 1 , x 2 and x 3 to the verifier.

-The verifier sends random challenge c $ ← -{1, 2, 3} to the prover.

-The prover reveals information so that the verifier can recover x i for each i ∈ {1, 2, 3}\ c. More precisely:

1. if c = 1, the prover sends l 1 = (o 2 , o 3 ) with o 2 = seed y , o 3 = π(e). 2. if c = 2, the prover sends l 2 = (o 1 , o 3 ) with o 1 = seed π , o 3 = y + e.
3. if c = 3, the prover sends l 3 = seed.

Verification.

1. if c = 1, the verifier recovers z 2 , z 3 from o 2 , o 3 by taking z 2 = E 2 (o 2 ) and z 3 = z 2 + o 3 .
Then for i ∈ {2, 3} checks that H comm (x i ) = z i and that wt(o 3 ) = w. 2. if c = 2, the verifier computes π = E 1 (o 1 ), z 3 = π(o 3 ) then t = Ho 3 -s and finally z 1 = (π, t). Then for i ∈ {1, 3} checks that H comm (x i ) = z i . 3. if c = 3, the verifier computes (seed π , seed y ) = E 0 (l 3 ), π = E 1 (seed π ) and z 2 = E 2 (seed y ), followed by t = H(π) -1 (z 2 ). From there, he constructs z 1 = (π, t). Then for i ∈ {1, 2} checks that H comm (x i ) = z i .

Notice that with deterministic commitments, there are here other optimizations regarding what the prover sends for each challenge. He doesn't reveal the full strings z c ′ , z c ′′ but the minimal information required to recover them.

Replacing the first message with a global commitment Recall that the full scheme consists of R parallel repetition of the above 1 round schemes. In this case, it is possible to replace the first message by a global commitment of all the x i . This allows to reveal the commitment only of the values not revealed (since they can be recovered from the openings). The scheme becomes the following. Attack on the optimized signature scheme -The adversary performs q s = ⌈ 1 R 2 l seed /2 ⌉ signature queries, with not necessarily distinct messages, to obtain the signatures σ m1 , . . . , σ mq s from the signer, where each σ(m k ) is written as

σ m k = x k , x 1 c1,k , . . . , x R c R ,k , l 1 c1,k , . . . , l R c R ,k ) .
-The adversary tries to find a pair ((i, k), (i ′ , k ′ )) st.

(i, k) ̸ = (i ′ , k ′ ) ∧ x i 2,k = x i ′ 2,k ′ ∧ c i k = 2 ∧ c i ′ k ′ ̸ = 2. (3)
If none are found, return to the first step.

-From such a pair of couples ((i, k), (i ′ , ′ )), the adversary recovers the secret key as follows:

• Since c i k = 2, we have that from l i 2 , the adversary can recover

π i k = E 1 (z i 1,k ) and π i k (y i k + e k ) = π(z i 3,k ). • Since c i ′ k ′ ̸ = 2
, then the adversary obtains either seed i ′ y,k ′ or seed i ′ k ′ from which seed i ′ y,k ′ can be calculated. Moreover, as x i ′ 2,k ′ = x i 2,k , with overwhelming probability seed i y,k = seed i ′ y,k ′ , the adversary learns

π i k (y i k ) = E 2 (seed i ′ y,k ′ ).
-From π i k , π i k (y i k ), π i k (y i k +e), the adversary thus recovers the secret key by computing

e = (π i k ) -1 π i k (y i k + e) -π i k (y i k ) = (π i k ) -1 π i k (e) ,
where (π i k ) -1 is the inverse of (π i k ).

Theorem 3. The attack presented above finds the secret key, e, in time O(2 l seed /2 ) doing O( 1 r 2 l seed /2 ) signature queries. The scheme thus preserves at most l seed 2 bits of security.

Proof. We prove that each iteration of the attack described above finds the secret key with a constant probability. Notice that for q S = ⌈ 1 R 2 l seed /2 ⌉, the signing oracle generates

Rq S = R⌈ 1 R 2 l seed /2 ⌉ ≥ 2 l seed /2 random seeds seed i y,k ∈ {0, 1} l seed , i ∈ [R], k ∈ [q S ].
There is a collision in the seeds, i.e. ∃(i, k),

(i ′ , k ′ ) such that (i, k) ̸ = (i ′ , k ′ ) ∧ seed i y,k = seed i ′ y,k ′ wp. Ω( q 2
S 2 l seed ) and with constant probability, this happens wp. c i k = 2 and c i ′ k ′ ̸ = 2. So we proved that the probability that the adversary finds a pair of couples ((i, k), (i ′ , k ′ )) satisfying Equation 3, which proves our theorem.

As a concrete example, assume we consider the above signature scheme with λ = 128 which is practice the most common choice. This means that there is an adversary performing 1 R 2 64 ≤ 2 58 queries and running in time 2 64 that will break the scheme with constant probability (here something around 1 10 ), while the underlying syndrome decoding problem requires time 2 128 to break. The attack clearly invalidates the claim of 128 bits of security. Notice also that it is quite standard to allow up to 2 64 calls to the signing oracle, this is for example what is requried by the NIST for the standardisation of post-quantum signature schemes so our attack fits these guidelines.

Fortunately, this attack can be mitigated with the methods we present in the next section with a close to zero loss in the efficiency, so optimized Stern's schemes can still be used securly with these mild changes.

The salt + index construction

There are 2 easy ways of mitigating the above attack: by taking l seed = 2λ or by using randomized commitments but both these solutions are very costly in terms of signature size. Here, we present another solution that will very mildly increase the signature size while preserving security: the salt + index construction. The idea is very simple: when running the identification scheme (the full R round scheme), we pick a random salt ∈ {0, 1} 2λ which we use as a randomization for all the commitments and the pseudo-random generators. Since the functions are used several times, we add an index which will be like an internal counter. Each time such a function is used, we increment the index and add it to the input, to ensure that each function used is independent from one another. Putting everything together, we obtain

Adv t-HVZK IS DC,N oS,salt (A) ≤ Adv SD (|A|) + O t 2 2 l salt .
6.2 Zero-knowledge for IS Stern using pseudo-random generators

Here, we show that using pseudo-random strings instead of random strings π, y doesn't change the security of the scheme. Recall that we showed in the previous section that if one isn't careful using seeds of size λ and deterministic commitments, there are attacks on the identification scheme. We show here that our salt + index construction. In the ROM, we have the following:

Proposition 4. Consider a random function E : {0, 1} l seed → I modeled as a random function in the random oracle model, and consider the following distinguishing game:

Game:Indist(E) b ← {0, 1}. If b = 0, seed ← {0, 1} l seed , y = E(seed). If b = 1, y ← I. b ′ ← A(y). The game is won iff. b = b ′ .
Consider an adversary A that performs q queries to E. Then

Pr[A wins Game:Indist(E)] ≤ 1 2 + O( q 2 l seed ).
Moreover, the above proposition is true even if A has some auxiliary information, as long as it is independent of the function E5 .

Proposition 5. Consider the 2 following games Game:0 Real transcript (pk, sk) ← Keygen(1 λ ). ∀i ∈ {1, . . . , t}, τ 1 , . . . , τ t ← trans IS DC,N oS,salt (pk, sk).

A wins the game iff. A(τ 1 , . . . , τ t ) = 1.

Notice that this game is exactly Game:0 from Section 6.1. Consider the second game Game:0' Real transcript with seeds (pk, sk) ← Keygen. ∀i ∈ {1, . . . , t}, τ 1 , . . . , τ t ← trans IS Stern,opt (sk).

A wins the game iff. A(τ 1 , . . . , τ t ) = 1.

where IS Stern,opt is the full optimized scheme with seeds and salt described in Section 6. For any adversary performing q queries to E, we have

Pr[A wins Game:0] -Pr[A wins Game:0 ′ ] ≤ O( q 2 l seed ) + O( t 2 2 l salt
).

Proof. The only difference between the 2 games is the way the strings π ij and π ij (y ij ) are Notice that for each i, j we use a different function E as long as the salts are all different (more precisely, we use E( * ||salt i , index) so we actually use the same function but with a different suffix). Take the permutations π ij , the adversary can distinguish a pseudorandom π ij from a random π ij wp. O( q ij 2 l seed ) where q ij is the number of queries done to the function E used to construct π ij . Similarly, let r ij be the number of queries done to the function E used to construct π ij (y ij ). Because each of these functions is different, we have ij q ij + r ij ≤ q where recall that q is the total number of queries done by A. Moreover, we can use Proposition 4 and therefore have

Pr[A wins Game:0]-Pr[A wins Game:0 ′ ] ≤ ij O( q ij + r ij 2 l seed )+O( t 2 2 l salt ) ≤ O( q 2 l seed )+O( t 2 2 l salt
).

7 Reduction of Signature Size using Hash Trees

A common technique for further reducing the signature size is to utilize a technique based upon seeded hash trees -small seed expansions associated to Merkel trees. This technique is used, for example, in [Beu20] and promises to have a huge advantage in efficiency. We show here how this technique can reduce the length of the signatures arising from Stern's signature scheme.

Stern's identification protocol, optimized fusion of 4 rounds For i ∈ {1, 2, 3, 4}, we construct π i = E(seed i 1 ||salt||index) and π i (y i ) = E(seed i 1 ||salt||index). Let t i = Hy i , z i 1 = (π i , t i ). He then construct the commitments x i j = H comm (z i j ||salt||index), and constructs

x 12 j = L((x 1 j , x 2 j )||salt||index)) x 34 j = L((x 3 j , x 4 j )||salt||index)) x 1234 j = L((x 12 j , x 34 j )||salt||index))

Prover calculates random challenges as (c 1 , c 2 , c 3 , c 4 ) = H F SH (x 1234 , m).

The prover and the verifier run a 4 round optimized scheme with the following optimizations:

-For j ∈ {1, 2} If the prover needs to reveal seed 1 j and seed 2 j (resp. seed 3 j and seed 4 j ) he reveals seed 12 j instead (resp. seed 34 j ) and the verifier uses J to recover each seed. If the prover needs to reveal seed 12 j and seed 34 j he reveals seed 1234 j instead and uses J again -For j ∈ {1, 2, 3} If the prover needs to reveal x 1 j and x 2 j (resp. x 3 j and X 4 j ) reveals x 12 j instead (resp. x 34 j ) and the verifier uses L to recover each commitment. If the prover needs to reveal x 12 j and x 34 j he reveals x 1234 j instead and uses L again.

Stern's identification scheme with hash trees consists of 55 parallel repetition of the above scheme (which each has 4 rounds), except that the same salt is used for all the repetition. This gives a total of 220 rounds. Proposition 6. The signature size of the signature scheme constructed from the above identification scheme is (in bits):

SIZE = l salt + 55 2C 1 + 4 1 3 s w + 1 3 n log 2 (q) + 1 3 l comm .
where and s w = log 2 |{x ∈ F n q , wt(x) = w} .

C
Proof. Let us compute the communication cost in this setting. Let C 1 be the communication cost corresponding to j = 1. This means we count here the costs of the revealed seed i 1 as well as x i 1 . For each of the 4 rounds, we have a probability 2 3 of revealing the seed and probability 1 3 of revealing the commitment. Moreover, we use our seed and commitment regrouping. For example, if we reveal the 4 seeds (which happens wp. ( 2 3 ) 4 ), we only have to reveal seed 1234 1 which costs l seed bits. Considering each of these case, we obtain: The same calculation can be done for j = 2. For the final case, we reveal the commitment wp.

C 1 = ( 2
1 3 . If this doesn't happen, we reveal π(e) or π(y+e) which requires respectively s w and n log 2 (q) bits to send. Finally, we have to send also the salt used (the indexes can be recomputed by the verifier). From there, we have that the total size is SIZE = l salt + 55 2C 1 + 4 1 3 s w + 1 3 n log 2 (q) + 1 3 l comm .

Proposal with Lee's metric

We use our scheme with the salt + index construction and with the above hash trees. Wa also consider Lee's metric, defined as follows. For e = (e 1 , . . . , e n ) ∈ F n q , we define wt L (e) = n i=1 min{e i , q -e i }.

The best known algorithms for solving the syndrome decoding problem with this metric were proposed in [CDE21]. Plugging these exponents to our construction, we obtain the following signature sizes.

Conclusion

In this work, we studied the security and insecurity of some optimized Stern's signature schemes. The main takeaway from our work is that one has to be careful when considering deterministic commitments and seeds of size λ that there is a way to make work with minimal deterioration of the efficiency. Similar analysis could be done for other schemes, and we hope to extend this fully to MQDSS. There doesn't seem to be any special difficulty but each scheme has to be studied with care. Moreover, it would be nice to extend this framework to 5 round schemes, which is an optimization that we didn't consider in this work.

  Adv t-HV ZK IS (A) = Pr b = 1 (pk,sk)←Keygen(1 λ ) τ1,...,τt←trans IS (pk,sk) b=A(τ1,...,τt,pk) -Pr b = 1

  Pr[A wins the EUF-CMA game].

  Stern's identification scheme (optimized, R rounds), IS Stern,opt Initialization. Let (H, e, s = He) $ ← -D n,k,w 1, sk = e, pk = (H, s). The prover obtains (pk, sk) and the verifier obtains pk. Interaction. 5 Attack on optimized Stern's signature schemes Here, we show that the combination of deterministic commitment and of seeds with l seed = λ gives only λ/2 bits of security instead of the claimed λ bits of security from [BGKS22].

  Stern's identification scheme (optimized, R rounds), IS Stern,opt Initialization. Let (H, e, s = He) $ ← -D n,k,w 1, sk = e, pk = (H, s). The prover obtains (pk, sk) and the verifier obtains pk.

Finally

  , notice that the τ ij constructed in Game:2 follows exactly the distribution of simtranscripts. This means Adv t-HVZK IS DC,N oS,salt (A) = |Pr[A wins Game:2] -Pr[A wins Game:0]| .

Initialization.

  Keygenerator samples (H, e, s = He) $ ← -D n,k,w 1, sk = e, pk = (H,

When we write maintain λ bits of security, we mean that if the original scheme has λ bits of security then the optimized scheme should also have λ bits of security.

If the weight constraint from the syndrome decoding problem, wtH (e) = w, is replaced with the permutation constraint from the permuted kernel problem, e = σ(v) (where v is given and it satisfies wtH (v) = w), a solution to first problem yields a solution to the second, and vice versa.

The number of non-binary words of weight w, length n, and alphabet of size q is given as the number of permutations of any word of a given weight and length multiplied by the number of compositions of w into n parts taking values in {0, . . . , q -1}. In the binary case, there is only one possible such composition, while in the non-binary case the number of such compositions can be, and in most cases it is, greater than 1.

In this paper, we construct a scheme that is perfectly complete. In general, this condition can be relaxed so that "almost perfectly complete scheme", where the probability above is very close to 1, can also be considered as a proper identification scheme.

This last part is what motivates the use of the salt + index construction for seeds.

-For j from 1 to R: the prover picks random seed j ∈ {0, 1} l seed and lets (seed j π , seed j y ) = E 0 (seed j ), π j = E 1 (seed j π ) and y j = (π j ) -1 (E 2 (seed j y )). It then computes t j = Hy j , z j 1 = (π j , t i ), z 2 = π i (y i ), z i 3 = π i (y i + e), and computes for i ∈ {1, 2, 3}, x j i = H comm (z j i ).

The prover sends x = H comm (x 1 1 , x 1 2 , x 1 3 , . . . , x R 1 , x R 2 , x R 3 ) to the verifier.

-For j from 1 to R: the verifier sends a random challenge c j $ ← -{1, 2, 3} to the prover.

-For j from 1 to R: the prover reveals information so that the verifier can recover x j i for each i ∈ {1, 2, 3} \ c. More precisely:

1. if c j = 1, the prover sends l j 1 = (o j 2 , o j 3 ) with o j 2 = seed y , o j 3 = π j (e) and x j 1 . 2. if c j = 2, the prover sends l j 2 = (o j 1 , o j 3 ) with o j 1 = seed π , o j 3 = y j + e and x j 2 3. if c j = 3, the prover sends l j 3 = seed and x j 3 .

Verification. For j from 1 to R:

1. if c j = 1, recovers z j 2 , z j 3 from o j 2 , o j 3 by taking z j 2 = E 2 (o j 2 ) and z j 3 = z j 2 + o j 3 . Then for i ∈ {2, 3} checks that H comm (x j i ) = z j i and that wt(

) and z j 2 = E 2 (seed j y ), followed by t j = H(π j ) -1 (y j ). From there, he constructs

The verifier also checks that

3 ) is equal to the value x he received.

Here, we described an identification scheme. The resulting signature schemes is constructed using the Fiat-Shamir transform presented in Section 3.2. This means each signature is of the form:

Interaction. The prover picks a random salt ∈ {0, 1} 2λ and initializes index = 0. Each time index is called, increment -For j from 1 to R: the prover picks a random seed j ∈ {0, 1} l seed and lets (seed j π , seed j y ) = E 0 (seed j , salt, index), π j = E 1 (seed j π , salt, index) and y j = (π j ) -1 (E 2 (seed j y ), salt, index). He then computes t j = Hy j , z j 1 = (π j , t i ), z 2 = π i (y i ), z i 3 = π i (y i + e), and computes for i ∈ {1, 2, 3},

The prover sends

to the verifier as well as salt.

-For j from 1 to R: the verifier sends a random challenge c j $ ← -{1, 2, 3} to the prover.

-For j from 1 to R: the prover reveals information so that the verifier can recover x j i for each i ∈ {1, 2, 3} \ c. More precisely: 1. if c j = 1, the prover sends l j 1 = (o j 2 , o j 3 ) with o j 2 = seed y , o j 3 = π j (e) and x j 1 . 2. if c j = 2, the prover sends l j 2 = (o j 1 , o j 3 ) with o j 1 = seed π , o j 3 = y j + e and x j 2 3. if c j = 3, the prover sends l j 3 = seed and x j 3 .

Verification. For j from 1 to R:

The verifier also checks that

) is equal to the value x he received. In each function, is known what index is used by the prover (it doesn't depend on some internal randomness) so the verifier uses for each function the same index as the prover when performing the above.

First, notice that this mitigates the above attack. Indeed, the attack used the fact that collision in the seeds between different signatures led to collisions in the commitments which could be detected and used. Here, with the addition of the salt, this won't happen anymore (and the index ensures that collisions within the same signature cannot be used). Moreover, notice that in terms of communication, a single string salt of size 2λ is added so the increase in the signature size is 2λ.

There could a priori be other attacks on this scheme. We show that this is not the case, by showing that Stern's scheme with the salt + index construction is multi-HVZK. Then, one can use the results of [GHHM21] to prove the EUF-CMA security of the resulting signature scheme.

Zero-knowledge for IS Stern without pseudo-random generators

We first prove a bound on the multi-HVZK advantage when we don't have seeds, but we still have deterministic commitments. We call this scheme IS DC,N oS,salt , which is described as follows:

IS DC,N oS,salt scheme Initialization. Let (H, e, s = He) $ ← -D n,k,w 1, sk = e, pk = (H, The prover obtains (pk, sk) and the verifier obtains pk.

Interaction.

-For j from 1 to R: The prover picks a random permutation π j acting on F n q and a random column vector y j $ ← -F n q , and then computes t j = Hy j . The prover computes z j 1 = (π j , t j ), z j 2 = (π j (y j )), z 3 = (π j (y j + e)), and computes for i ∈ {1, 2, 3},

The prover sends

-For j from 1 to R: the verifier sends a random challenge c j $ ← -{1, 2, 3} to the prover. -For j from 1 to R: the prover reveals information so that the verifier can recover x j i for each i ∈ {1, 2, 3} \ c. More precisely:

1. if c j = 1, the prover sends l j 1 = (o j 2 , o j 3 ) with o j 2 = π j (y j ), o j 3 = π j (e) and x j 1 . 2. if c j = 2, the prover sends l j 2 = (o j 1 , o j 3 ) with o j 1 = π j , o j 3 = y j + e and x j 2 3. if c j = 3, the prover sends l j 3 = (π j , y j ) and x j 3 .

Verification. For j from 1 to R:

The verifier also checks that

) is equal to the value x he received. We prove a tight reduction from the advantage of breaking the t-HVZK condition and the advantage of solving the underlying syndrome decoding problem.

Theorem 4. For any adversary A, there exists a adversary B st.

where Adv SD (B) gives the probability that the adversary breaks the underlying syndrome decoding problem, and the running time of B is the same as the running time of A.

Before presenting a proof of this theorem, let us perform a small discussion on how to interpret this theorem. In the previous section, we started from a signature scheme st. the underlying syndrome decoding problem requires 2 λ time to break, and we presented an adversary A running in time O(2 λ/2 ) that breaks the signature scheme arising from IS Stern,opt with t = O(2 λ/2 ) signature queries. One can also interpret our attack as an adversary A st. running in time O(2 λ/2 ) st. Adv t-HVZK IS Stern,opt (A) is close to 1 with t = 2 λ/2 . Theorem 4 that we will shortly prove, shows that such an attack cannot be possible when in the case where there is salt. Indeed, assume we also had an adversary A running in time 2 λ st. Adv t-HVZK IS Stern,opt (A) is close to 1. Then the above theorem immediately says that there is an adversary B running in time 2 λ/2 that breaks the underlying syndrome decoding problem but we chose the parameters st. such an adversary would require time at least 2 λ hence the contradiction.

We now present the proof of this theorem.

Proof. We will do a game based proof. The first game we consider is Game:0 Real transcript (pk, sk) ← Keygen. ∀i ∈ {1, . . . t} :

-Pick a random salt i ← {0, 1} l salt .

-∀j ∈ {1, . . . , R}:

• Pick a random permutation π ij and a random string

, and compute for k ∈ {1, 2, 3},

Let also

In this game, we construct t transcripts constructed according to trans IS Stern,DC,N oS (pk, sk). The game is won if the adversary outputs 1 given these real transcripts as input.

We now consider another game where we construct the same transcripts but in a different way. For each choice of c ij , it is possible to construct the responses l ij independently of the secret key and to make only the strings x ij c ij dependent of the secret key. Let S w be set the of words of weight w.

Game:1 Real transcript with openings depending only on pk (pk, sk) ← Keygen. ∀i ∈ {1, . . . , t} :

-Pick a random salt i ← {0, 1} l salt .

-∀j ∈ {1, . . . , R}:

• Pick a random challenge c ij ← {1, 2, 3}.

3 ) = e, and let

Pr[A wins Game:0] = Pr[A wins Game:1].

Proof. This is true since the distribution of each τ i is the same for both games. This can be seen using the same arguments as in Proposition 3, where we proved that the ideal simulator has the same distribution of openings as the real transcript.

We now change Game:1 into Game:2 where we replace the commitments x ij with uniformly random strings. We put the difference between the games in red.

Game:2 Simulated transcript (pk, sk) ← Keygen. ∀i ∈ . . . , t} :

-Pick a random salt i ← {0, 1} l salt .

-∀j ∈ {1, . . . , R}:

• Pick a random challenge c ij ← {1, 2, 3}.

where B is an adversary st. |B| ≈ |A| and Adv SD (B) is the probability that B breaks the underlying syndrome decoding problem.

Proof. Consider an adversary A for Game:2. This adversary can perform queries H comm (•).

The only difference between Game:1 and Game:2 is in the strings x ij c ij . In Game:1, if all the salts seed i salt are pairwise distinct, ).

Moreover, from the openings o ij , the adversary can recover the 2 other strings z ij c ′ , z ij c ′′ for c ′ ̸ = c ′′ and c ′ , c ′′ ̸ = c ij . From the 3 strings z ij 1 , z ij 2 , z ij 3 one can recover in polynomial time the secret key sk using some extraction algorithm (we described how to do this in Section 5 for example). We can therefore construct from A an algorithm B that solves the syndrome decoding problem.


V Biliatto

L Moonens

T Picon
email: picon@ffclrp.usp.br

HAUSDORFF DIMENSION OF REMOVABLE SETS FOR ELLIPTIC AND CANCELING HOMOGENEOUS DIFFERENTIAL OPERATORS IN THE CLASS OF BOUNDED FUNCTIONS

Keywords: 2010 Mathematics Subject Classification. 47F05 35A23 35B45 35J48 28A12 26B20; divergence-measure vector fields, removable sets, Froostman's Lemma, canceling operators

In this note we give an upper bound on the Hausdorff dimension of removable sets for elliptic and canceling homogeneous differential operators with constant coefficients in the class of bounded functions, using a simple extension of Frostman's lemma in Euclidean space with an additional power decay.

INTRODUCTION

Given a linear differential operator P(x, D) with smooth coefficients in R n , n ≥ 2, one calls a closed set S ⊆ R n removable for the equation P(x, D) f = 0 with respect to a space F of locally integrable functions (scalar or vector-valued), provided that for any f ∈ F satisfying (in the sense of distributions) the equation P(x, D) f = 0 outside S, one has P(x, D) f = 0 in R n (in the sense of distributions). The nomenclature "removable" is hence self-explanatory.

The following result dates back to Harvey and Polking [5, Theorem 4.1, (b)], where H s will stand for the s-dimensional Hausdorff (outer) measure in R n . Theorem 1.1. If P(x, D) is a linear differential operator of order m < n with smooth coefficients and if the closed set S ⊆ R n satisfies H n-m (S) = 0, then S is removable for the equation P(x, D) f = 0 with respect to the space L ∞ loc (R n ) of locally (essentially) bounded functions. Removable sets for several linear equations have been studied, and sometimes characterized completely, in the literature. For the scalar Laplace equation, removable sets with respect to Lipschitz functions have been subject of a very deep study; for example, it follows from works by Calderón [START_REF] Calderón | Cauchy integrals on Lipschitz curves and related operators[END_REF], David and Mattila (n = 2) [START_REF] David | Removable sets for Lipschitz harmonic functions in the plane[END_REF] and Nazarov, Tolsa and Volberg (n > 2) [START_REF] Nazarov | The Riesz transform, rectifiability, and removability for Lipschitz harmonic functions[END_REF] that a compact set S ⊆ R n satisfying H n-1 (S) < +∞ is removable for the Laplace equation with respect to Lipschitz functions, if and only if it is purely (n -1)-unrectifiable, i.e. if and only if the intersection of S with any (n -1)-rectifiable set, is H n-1 -negligible; (un)rectifiability hence plays a fundamental role for determining whether or not a set is removable in this context.

The situation is very different for the divergence equation with respect to bounded vector fields, even though the Laplace equation can be written ∆ f = div(∇ f ) = 0 and ∇ f is a bounded vector field for any Lipschitz function f and hence every removable set for the divergence equation with respect to bounded vector fields is removable for the Laplace equation w.r.t. Lipschitz functions.

It was first proven by the second author in [START_REF] Moonens | Removable singularities for the equation div v = 0. Real Anal. Exchange[END_REF] that a compact set S ⊆ R n is removable for the equation div f = 0 with respect to L ∞ (R n , R n ), if and only if one has H n-1 (S) = 0. The proof there used a decomposition of S into Borel subsets S 1 and S 2 , one of which is (n -1)-rectifiable, the other one being purely (n -1)-unrectifiable, relying then on results by Th. De Pauw [START_REF] De | On the exceptional sets of the flux of a bounded vectorfield[END_REF] for purely (n -1)-unrectifiable sets, and on the fact that (n -1)-rectifiable sets of positive (n -1)-dimensional Hausdorff measure are not removable for the Laplace equation w.r.t. Lipschitz functions (and hence also not removable for the divergence equation w.r.t. bounded vector fields, as discussed just above). Obviously, such a proof heavily relies on the fact that one deals with the divergence operator, and cannot be carried out to other differential operators (even of order one).

Shortly after, Phuc and Torres [START_REF] Nguyen | Characterizations of the existence and removable singularities of divergence-measure vector fields[END_REF] obtained, among other results, a new proof of the abovementioned characterization of (compact) removable sets for the divergence equation w.r.t. bounded vector fields, this time relying on a new strategy to prove that a compact set S ⊆ R n with H n-1 (S) > 0, cannot be removable for the divergence equation. Exhibiting first, with use of Frostman's lemma [START_REF] Mattila | Geometry of sets and measures in Euclidean spaces[END_REF]Theorem 8.8], a non-trivial Radon measure µ supported in such a set S enjoying that µ(B[x, r]) ≤ r s for all x ∈ R n and r > 0, and using a boxing inequality together with a co-area formula, they obtain an inequality of the form:

ˆRn ϕ dµ ≤ C ∇ϕ L 1 ,
for smooth test functions ϕ, implying in turn that µ is in the dual space X * of the space X of test functions endowed with the norm ∇ϕ L 1 . Then, since the operator -∇ :

X → L 1 (R n , R n ) is (
obviously) an isometry, it follows that the adjoint operator:

div = (-∇) * : L ∞ (R n , R n ) = L 1 (R n , R n ) * → X *
is surjective, and hence that the equation div

f = µ has a solution in L ∞ (R n , R n ). As a consequence, S cannot be removable for the divergence equation w.r.t. L ∞ since one has div v = 0 outside S (recall that µ is supported in S) but div f = µ = 0 in R n .
The very specific role of the gradient vs divergence, arising through the co-area formula in the latter argument, suggests that it does not adapt easily to obtain removability results for other operators than the divergence operator. Very recently, the first and third authors obtained in [START_REF] Biliatto | A note on lebesgue solvability of elliptic homogeneous linear equations with measure data[END_REF], for a special class of elliptic homogeneous differential operators A(D) : D(R n , E) → D(R n , F) of order 0 < m < n in R n (see the Section 3 for details), sufficient conditions on the Radon measure µ in order to obtain solvability results in Lebesgue spaces for the equation:

(1.1) A * (D) f = µ,
where A * (D) is the (formal) adjoint operator associated to the homogeneous linear differential operator A(D). In particular, the following solvability result in L ∞ for equation (

(1.2) sup r>0 |µ|(B[0, r]) r n-m < +∞,
as well as, uniformly on x ∈ R n :

(1.3) ˆ|x| 2 0 |µ|(B[x, r]) r n-m+1 dr 1, then there exists f ∈ L ∞ (R n , F * ) satisfying the equation (1.1) in R n in the sense of distributions.
Here |µ| denotes the total variation of the vector-valued Radon measure µ. Note also that, in the latter statement:

• The assumption (1.2) is weaker than requiring |µ|(B[x, r]) ≤ Cr n-m for all x ∈ R n and all r > 0, since the supremum only extends, in (1.2), to balls centered at the origin. • Any scalar Radon measure which satisfies, for each x ∈ R n and each 0 < r <

|x| 2 : (1.4) ν(B[x, r]) ≤ C 2 |x| -m r n ,
automatically satisfies (1.3); hence (1.4) is a stronger condition than (1.3). • The integration boundary |x|/2 in (1.3) can be replaced by a|x|, where 0 < a < 1 is any fixed constant -the holding of (1.4) for any x ∈ R n and 0 < r < a|x| then being again stronger that the modified version of (1.3). • An example of measure ν satisfying (1.2) and (1.3) is given by ν

= |x| -m L n for n ≥ 2,
where L n denotes Lebesgue's outer measure in R n . • The canceling property appearing in the statement (and defined precisely below in (3.1))

is due to J. Van Schaftingen (see [START_REF] Van Schaftingen | Limiting sobolev inequalities for vector fields and canceling linear differential operators[END_REF]); it characterizes the validity of an L 1 Sobolev-Gagliardo-Nirenberg inequality for elliptic homogeneous differential operators, recovering several a priori L 1 estimates for divergence-vector fields and chains of complexes. In this note we present a necessary condition for a compact set S ⊆ R n to be removable for the equation A * (D) f = 0 associated to an elliptic and canceling homogeneous differential operator A(D), using Theorem 1.2 and a slightly improved version of Frostman's lemma. Our main result is the following: Theorem A. Assume that A(D) is an elliptic and canceling homogeneous differential operator on R n of order 0 < m < n, from a finite-dimensional vector space E to a finite-dimensional vector space F. If the closed set S ⊆ R n is removable for the equation A * (D) f = 0 in L ∞ (R n , F * ), then S has Hausdorff dimension less than or equal to nm. REMARK 1.1: Since it follows from Harvey and Polking's result (see Theorem 1.1) that if S is H n-m -negligible, then S is removable for the equation A * (D) f = 0 w.r.t. L ∞ , it hence only remains to understand whether or not some sets with Hausdorff dimension nm yet positive (nm)dimensional Hausdorff measure, may be removable in this context.

We shall organize the paper as follows. In Section 2, we shall present a version of Frostman's Lemma with an additional power decay condition. In Section 3, we shall then recall precisely the context of elliptic and canceling operators, before proving our main Theorem A.

A "FROSTMAN'S LEMMA" WITH DECAY

Our goal in this section is to provide a result ensuring at least that, given integers 0 < m < n and a closed set S ⊆ R n satisfying H n-m+α (S) > 0 for some α > 0, there exists a (nonnegative) non-trivial Radon measure supported in S and satisfying conditions (1.2) and (1.3) above. This will result from observing that one can impose, in the statement of Frostman's Lemma, a decay condition; this is what the next result expresses. Lemma 2.1 (Frostman's Lemma with power weight decay). Assume that 0 < α < s < n are fixed and that B ⊆ R n is a Borel set satisfying H s (B) > 0. Then there exists a non-zero scalar Radon measure µ supported in B satisfying:

(2.1) sup r>0 µ(B[0, r]) r s-α < +∞,
and such that, for any x ∈ R n and any 0 < r < 1 2 |x|, one has:

(2.2) µ(B[x, r]) |x| -α r s .
PROOF: Start by using Frostman's Lemma [START_REF] Mattila | Geometry of sets and measures in Euclidean spaces[END_REF]Theorem 8.8] to find a non-zero (nonnegative) Radon measure ν supported in B satisfying ν(B[x, r]) ≤ r s for all x ∈ R n and all r > 0. Now define A k := {x ∈ R n : k ≤ |x| < k + 1} for k ∈ N and introduce the Radon measure µ defined by:

µ := ∞ ∑ k=0 2 -kα ν A k .
Observe first that for 0 < r < 1 one has:

µ(B[0, r]) r s-α = ν(B[0, r]) r s-α ≤ r s r s-α = r α ≤ 1,
while if one has j ≤ r < j + 1 for some j ∈ N * there holds:

µ(B[0, r]) ≤ j-1 ∑ k=0 2 -kα ν(B[0, k + 1]) + 2 -jα ν(B[0, r]) ≤ j-1 ∑ k=0 2 -kα (k + 1) s + 2 -jα r s ,
and hence:

µ(B[0, r]) r s-α ≤ 1 r s-α j-1 ∑ k=0 2 -kα (k + 1) s + 2 -jα r α ≤ j-1 ∑ k=0 2 -kα (k + 1) s + [2 -j ( j + 1)] α ≤ C α,s < +∞, with for example C α,s := 1 + ∑ ∞ k=0 2 -kα (k + 1)
s since one has ( j + 1)2 -j ≤ 1 for all j ∈ N * . This finishes to establish that (2.1) holds.

To prove (2.2), fix x ∈ R n and 0 < r ≤ |x| 2 . Choosing j ∈ N such that one has j ≤ |x| < j + 1, one finds r ≤ j+1 2 and hence also, for y ∈ B[x, r]:

|y| ≥ |x| -|x -y| ≥ j - j + 1 2 = j -1 2 and |y| ≤ |x| + |y -x| < j + 1 + j + 1 2 = 3 2 ( j + 1), so that there holds B[x, r] ∩ A k = / 0 for k < m j := j-1 2
and k > n j := 3 2 ( j + 1) . We can hence compute:

(2.3) µ(B[x, r]) ≤ n j ∑ k=m j 2 -kα ν(B[x, r]) ≤ r s n j ∑ k=m j 2 -kα .
Yet one has:

(2.4)

n j ∑ k=m j 2 -kα = 2 -m j α n j -m j ∑ k=0 2 -kα = 2 -m j α 1 -2 -[1+(n j -m j )]α 1 -2 -α = 2 -m j α -2 -(n j +1)α 1 -2 -α ≤ 1 1 -2 -α 2 -m j α ≤ 1 1 -2 -α 2 -j-1 2 -1 α) = 2 3 2 α 1 -2 -α 2 -j 2 α .
Writing then:

(2.5) 2 -j 2 α = |x| -α |x| 2 j 2 α ≤ |x| -α j + 1 2 j 2 α ≤ 3
µ(B[x, r]) ≤ 2 α 2 • 3 α 1 -2 -α • |x| -α r s ,
which establishes (2.2).

HAUSDORFF DIMENSION OF REMOVABLE SETS FOR ELLIPTIC AND CANCELING HOMOGENEOUS OPERATORS

Let A(D) be a homogeneous linear differential operator on R n of order 0 < m < n, from a finitedimensional complex vector space E to a finite dimensional complex vector space F, i.e. an operator of the form:

A(D) = ∑ |α|=m c α ∂ α : D(R n , E) → D(R n , F),
where c α ∈ L (E, F) is a linear operator from E to F, for each |α| = m. Here, D(R n , X ) stands for the set of all smooth functions with compact support defined on R n with values in a finite dimensional complex vector space X (itself endowed with a fixed norm).

Recall that one associates to A(D) its symbol A(ξ ) : E → F defined by:

A(ξ ) := ∑ |α|=m c α ξ α , ξ ∈ R n .
We then say that A(D) is: (i) elliptic in case its symbol A(ξ ) is injective for any ξ ∈ R n \ {0};

(ii) canceling in case one has:

(3.1)

ξ ∈R n \{0} A(ξ )[E] = {0}.
We also denote by

A * (D) : D(R n , F * ) → D(R n , E * ) the formal adjoint of A.
An important class of operators satisfying (i) and (ii) is given by the gradient operator A(D) = -∇, where E = R and F = R n . Clearly the operator is elliptic, since its symbol is A(ξ ) = ξ , and canceling for n ≥ 2 since one has:

ξ ∈R n \{0} A(ξ )[E] = ξ ∈R n \{0} ξ • R = {0}.
Note that A * (D) = div. Then, for a positive (scalar) measure µ = |µ| satisfying (1.2) and (1.3), Theorem 1.2 gives a solution f ∈ L ∞ (R n , R n ) for the equation (1.1).

We are now ready to prove our main Theorem A.

3.1. The proof of Theorem (A). If the Hausdorff dimension of S were larger than nm, then there would exist α > 0 such that H n-m+α (S) > 0. The above Frostman Lemma with power decay -Lemma 2.1 -applied to B := S and s := nm + α ensures the existence of a non-zero Radon measure supported in S satisfying (1.2) and such that, for any x ∈ R n and any 0 < r < r α-1 dr ≤ 1 2 α α , so that (1.3) is also satisfied uniformly in x ∈ R n , x = 0. Hence it follows from Theorem 1.2 that there exists f ∈ L ∞ (R n , F * ) solving A * (D) f = µwhich implies that S is not removable for the equation A * (D) f = 0, since one has A * (D) f = 0 outside S (in the sense of distributions) but A * (D) f = µ = 0 in R n (in the sense of distributions).

1 2

 2 |x|, one has: µ(B[x, r]) |x| -α r n-m+α . Yet then, if e ∈ E * is fixed, and if one defines µ e (B) := µ(B)e for any B ⊆ R n , there holds: sup r>0 |µ e |(B[0, r]) r n-m = e E * sup r>0 µ(B[0, r]) r n-m < +∞, meaning that (1.2) above is fullfilled.We also get, for any x ∈ R n , x = 0:

  [START_REF] Calderón | Cauchy integrals on Lipschitz curves and related operators[END_REF]

		α
		|x| -α ,
	since one has k+1 2 k 2	≤ 3 2 for any k ∈ N, we finally get, combining (2.3), (2.4) and (2.5):

The first author was supported by Coordenac ¸ão de Aperfeic ¸oamento de Pessoal de Nível Superior (CAPES -grant 88882.441243/2019-01) and the third by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPqgrant 311430/2018-0) and Fundac ¸ão de Amparo à Pesquisa do Estado de São Paulo (FAPESP -grant 18/15484-7). All three authors also acknowledge the support of the Brazilian-French Network in Mathematics (GDRI-RFBM)..


NARRATIVE WRITING ABOUT FICTIONAL ANIMAL EVOLUTION FOLLOWING THE GAME-PLAY DARWINIUM

Keywords: Students' ideas, Games-based learning, biological evolution

The communication is based on the integration of the board game Darwinium in a biology class in lower secondary school in France. The game, designed by a team of researchers and teachers, engages students to observe the evolution of fictional animal populations. It aims to model different ideas of chance in an evolutionary process. Students are engaged in narrative writings after a game-play. From the analyses of these writings we identify student's expression of ideas about chance and evolution and how they connect to the narrative of the game. For some students, there is an understanding of certain important ideas of evolution (variability, chance, environmental pressure).

INTRODUCTION

This research proposes a study based on a board game integrated into educational resources for lower secondary school. The board game 'Darwinium' was designed by a team of researchers and teachers in the project EGRESS (Educational Game about Randomness and Evolution for Students in Science). The game 'Darwinium' places middle school students in the situation of researchers observing the evolution of fictional experimental animal populations placed in an experimental dome where the environment of the population can be modified by the players. The players also have to report on this evolution in verbal narrative form (written and oral explanation of biological evolution) and graphic form (representation of the population). This project is based on previous work that has highlighted the difficulties in apprehending the theory of evolution of living things and the ideas of chance that are linked to it (Author, 2018;[START_REF] Fiedler | How strongly does statistical reasoning influence knowledge and acceptance of evolution[END_REF]. [START_REF] Gayon | Chance, Explanation, and Causation in Evolutionary Theory[END_REF] identifies "three possible meanings of the word 'chance': 'chance, probability, and contingency with respect to a given theoretical system'" (p. 528). In an evolutionary process, 'chance' is associated with genetic mutations, probability with the mechanism of genetic drift, and contingency with a mechanism combining random events in a historical perspective.

Middle school students' knowledge of the evolution of life seems to be linked to their understanding of chance (Author, 2018). They associate chance with fate, luck or misfortune, inducing a strong finalistic idea of evolution. The students' probabilistic thinking seems to be linked with their evolutionary thinking.

CHANCE AND EVOLUTION IN THE BOARD GAME DARWINIUM

The board game designed for this project particularly focuses on two ideas of chance: random probability and contingency. These ideas feed into the mechanisms explaining evolution at a population level. The game engages students in a fictional scenario of experimental evolution where players study changes occurring in a fictional experimental population in response to conditions imposed by the player but not totally controlled. It engages students with a physical experience of random processes combining a variety of board game artefacts. The game is based on a chaotic game mechanic incorporating random events that disrupt the course of the history of a fictional animal population. A comprehensive description of the game is in the process of being published. For the purpose of this communication, we focus on the specific game mechanics that model different ideas of chance in an evolutionary process.

In the game 'Darwinium', random probability is expressed with different game mechanics. 1) Various tokens, representing various traits of the populations of the game, are thrown in a specially designed dice tower (see fig. 1.a.). The tower allows a random sorting of the pieces. Some are kept by the player, some are discarded, some are trapped in the tower. This step models the fixation or not of traits in the population, which depends on the random distribution of alleles during reproduction. When one of the traits is less advantageous, in a given environment, it is less represented in the population's successive generation and tends to disappear. 2) "Traits" cards are drawn after the "tower" step (see fig. 1.b.). This step models the fixation of new variants in the population, coming from random mutations or from the random expression of recessive alleles. 3) An "event" card is drawn. This step models the possible changes in the environment that could impact the population.

Contingency is convened during the preparation of the number of tokens that are then thrown in the dice tower. The number of tokens is contingent on the type of environment and its resources. If a trait is considered to give an advantage in a given environment, more tokens of that trait are added, increasing the probability of such tokens to be kept after the selection by the tower. This game mechanics models the contingency of the natural selection of certain traits over time according to the adaptive advantages that they confer on the population. Thus, the portion of the population with advantageous traits generates more copies of this traits in the next generation, and vice versa (Fielder et al., 2019). The purpose of this paper is to study the ideas of chance and evolution of students (13-14 years old) expressed after a play activity designed by a team of researchers in science education. The underlying hypothesis that guided the design of the board game is that the various artefacts and game mechanics in the game would engage students to reassess their ideas about chance in an evolutionary process.

METHODS

The proposed methodology is based on the epistemological analysis of the games and the narrative writings produced by middle school students following a game session. This analysis is part of a larger research project that aims to define a comprehensive teaching scenario that integrates the game Darwinium

The data are collected during a debriefing session after a game session of "Darwinium" with 57 students (13-14 years old) conducted in a biology class. 8 games were played in parallel, each with 4 or 3 teams of 2 players.

During a debriefing session, students are asked to write the story of their population, to express their understanding of what happened during the game and how it related to evolution (fig. 2).

The narrative writings are analysed using categories constructed a priori on the basis of previous work in order to identify: 1) ideas of chance in evolutionary processes; 2) the obstacles related to chance in evolutionary processes; 3) types of cultural references in the narrative writing.

Using the elements of the game, explain, in a few lines, how your animal population has changed over the course of the game.

Over the rounds of the game, our population has evolved, by chance. Our population, initially blue, with "pouch -like" beaks and webbed feet, has undergone collective cross-fertilization and has evolved. That is to say that at the time of sexual reproduction of a member of our species and another individual, their reproductive cells mixed and this created new individuals with new physical criteria. Subsequently, when we changed the environment, the individuals with physical criteria adapted to the environment survived, and the others died.

RESULTS

Results highlight that some texts stay close to the context of the game itself and not the story of their population narrated by the game ("we were able to draw cards and the cards allowed us to draw characteristics to have a new population"). When the story of the game is narrated, some texts are descriptive, giving generic characteristics of their population ("our population had red and blue colours, with webbed feet, as well as pouch-like beaks and hook-like beaks"). Some texts introduce the idea of intraspecific variation in their population using percentage to describe the most common traits visible in their population ("half of the individuals had flat beaks"; "50% had pointed beaks and 50% had pouch-like beaks"). Some texts can be linked to a transformist view of evolution ("we have added a hook-like beak to facilitate life in the new environment").

Several texts recognise ideas of chance in the evolutionary process ("chance during reproduction, at the level of genetics, has given the appearance of new traits such as hooves and hook-like beaks which are not, however, adapted to the sea environment").

CONCLUSION

From the analyses, an acceptance of the evolution of populations of living beings appears. For some students, there is an understanding of certain important ideas related to evolution (variability, chance, environmental pressure) in accordance with scientific knowledge. For the other students it will be necessary to go beyond the description of their population to consider the reasons for their evolution. The game seems to allow some pupils to take into consideration the question of chance in the evolutionary process.

Figure 1 .

 1 Figure 1. Overview of parts of the Darwinium board game. (1a. token thrown in the dice tower (left) and selected (right), 1b. a trait card is drawn, 1b. a event card is drawn)

Figure 2 .

 2 Figure 2. Example of a narrative produced by a student after the game (left) and during the game (right). Translation by authors.


Beatriz Menendez

Natalia Perez-Ema

Alessandra Bonazza

Inge Rörigdalgaard

Anna Maria Ferrari

Sergio Gomez Cornelio

Johanna O'byrne

Patricia Quintana

Benjamin Quesada

Beatriz Menéndez

Inge Rörig-Dalgaard

Claudia Garcia-Solis

Sergio Gomez-Cornelio

Susana De La Rosa

Javier Reyes

Maria Pia Riccardi

Luis Valdeon

Sustainable conservation and restoration of built cultural heritage: Introduction to the SCORE project

Keywords:

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

governmental organisationsin order to strengthen collaborative research and innovation in eco-friendly conservation, restoration, and rehabilitation.

Matching cultural heritage requirements with sustainable, economic and social aspects becomes essential and require highly qualified labour for conception, execution and conservation works. The SCORE project objective is to reduce the ecological footprint of the materials and methods employed in built cultural heritage conservation.

• Introduction

Extensive research and innovation efforts have been made worldwide to conserve the Built Cultural Heritage (BCH), but more work must be done to consider the ecological footprint of the materials and methods employed during conservation works. Matching cultural heritage requirements with ecological, economic and social aspects [START_REF] Balliana | Assessing the value of green conservation for cultural heritage: Positive and critical aspects of already available methodologies[END_REF] becomes essential. We should combine the needs of society with the obligation to protect environmental and natural resources while contributing to sustainable future development: circular economy principles.

The SCORE project aims to bring together an intersectoral, international and multidisciplinary group that includes materials scientists, biologists and civil engineering researchers, restores, archaeologists, art historians, Life Cycle Assessment specialists, climatologists, practitioners, consulting companies, training organisations, decisionmakers and non-governmental organisations; in order to strengthen collaborative research and innovation in eco-friendly conservation, restoration, and rehabilitation. It aims to support the development of a series of innovative materials and methods dedicated to BCH conservation, integrating the circular economy concept, climate change and ecological footprint constraints.

•

Objectives and Actions

The SCORE project contributes to the implementation of three objectives:

1. Development of "green" innovations: materials and methods for the conservation of ancient buildings based on a circular economy philosophy. Built heritage conservation materials should meet three criteria: innocuity, compatibility and retractability ( 6), [START_REF]Circular economy and health: opportunities and risks[END_REF]. Even if restoration methods for monuments are subjected to more constraints than vernacular cultural heritage, sustainability aspects must not be neglected. Research on traditional building techniques and new inorganic materials will help to reduce the environmental impact of restoration campaigns. Practitioners and the environment are potentially exposed to risk factors during restoration works; a circular economy model must minimize these risks (8).

Fig. 1. SCORE case studies

The selection of case study (figure 1) sites was based on several criteria: (i) historical and architectonical interest, (ii) geographical proximity and accessibility by research groups, (iii) research groups' previous experience in the material and building techniques employed, (iv) a wide range of climatic conditions. More details about the case studies can be found at www.score-project.net.

To achieve their objectives, the SCORE project implements a designed bespoke methodology which consists in working through "implementation loops", as detailed below and in figure 2 a) Bibliographic review, documentary and "in-situ" study of sites.

b) Laboratory and "in-situ" studies to characterize ancient materials, their conservation degree, composition and physical properties.

• Conclusions

The SCORE project's expected results are:

1. Green restoration and rehabilitation products and methods: new products and methods proposed to practitioners, project managers, public and private owners.

2 .

 2 Two-way assessment of impacts of the environment on materials and of materials on the environment: Climate conditions and atmosphere composition determine BCH materials' behaviour and, at the same time, the BCH conservation impacts greenhouse gases emissions and then climate change. 3. Transfer to society: Training and knowledge transfer on both innovative and traditional materials and methods with a low environmental impact. The research and innovation action is based on two kinds of built cultural heritage in two geographical and climatic vernacular built cultural heritage in Europe and archaeological sites in Yucatan (Mexico). Although different, these two kinds of built heritage use similar materials and construction techniques that can be transmitted and adapted from one to another. In both cases, BCH faces the same environmental constraints: (i) Climate change which threatens the protection of both monuments and vernacular buildings, in the light of current and future climate conditions (3) (4); (ii) The ecological footprint of the restoration (monuments) and rehabilitation (vernacular) materials and methods which must be minimized. The main climate types of the selected areas are extremely different, according to the Köppen-Geiger climate classification (5): equatorial (Aw) in Latin America and several different warm temperate climates (C) in Europe. This allows us to study the behaviour and durability of BCH conservation materials and techniques in different climate conditions, generating different weathering processes such as biological colonisation in climate A, salt crystallisation in climate C, etc., to extend the results obtained to other world regions.

c)

  New materials design: mortars and renders, bricks, consolidants, water repellents, biocides, etc. d) Durability tests in laboratory and "in-situ" to determine the long-term behaviour of ancient and new materials in different environmental conditions. Based on the results obtained, formulations may be reviewed. e) Environmental performance and eco-friendly characteristics of materials and conservation methods. Life Cycle Assessment methodology will be used. The results will be used to review the proposed formulations. f) Durability test results will be used to establish new dose-response functions for different weathering effects under continuous climate changes or extreme events on BCH conservation. g) Past climate data and simulations of climate models for future periods will allow us to know future climate conditions and their from past ones. h) Past, current and future material weathering will be determined using doseresponse functions and climate model "predictions". Formulations will be approved or redesigned based on the results obtained. i) Validation of new materials and methods if they fulfil all the required conditions: compatible with real case materials, eco-friendly and durable in present and future conditions.

Fig. 2 .

 2 Fig. 2. SCORES working methodology.

2 .

 2 Research contributions: a) new dose-response functions to estimate the effect of continuous processes (temperature rise, relative humidity changes, mean rain, etc.), b) critical threshold for extreme events (heatwave, rainstorms, dry seasons, etc.), c) future weathering maps in selected areas based on climate model simulations.

3 .

 3 Training and academic actions, and dissemination of results.4. Development of a large international and multidisciplinary network dedicated to green restoration and rehabilitation projects.

Acknowledgements

This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101007531