# Masking the GLP Lattice-Based Signature Scheme at Any Order

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin

Grégoire, Mélissa Rossi, Mehdi Tibouchi

► To cite this version:

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, et al. Masking the GLP Lattice-Based Signature Scheme at Any Order. Journal of Cryptology, 2024, 37 (1), pp.5. 10.1007/s00145-023-09485-z. hal-04832806

HAL Id: hal-04832806

https://hal.science/hal-04832806v1

Submitted on 12 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Masking the GLP Lattice-Based
Signature Scheme at Any Order

Gilles Barthe¹,², Sonia Belaïd³, Thomas Espitau⁴, Pierre-Alain Fouque⁵, Benjamin Grégoire⁶,
Mélissa Rossi⁷, and Mehdi Tibouchi⁸

¹ MPI-SP

gilles.barthe@mpi-sp.org

² IMDEA Software Institute

³ CryptoExperts

sonia.belaid@cryptoexperts.com

⁴ PQShield SAS

thomas.espitau@pqshield.com

⁵ Université de Rennes

pierre-alain.fouque@univ-rennes1.fr

⁶ Inria Sophia Antipolis

benjamin.gregoire@sophia.inria.fr

⁷ ANSSI

melissa.rossi@ssi.gouv.fr

⁸ NTT Social Informatics Laboratories

mehdi.tibouchi@ntt.com

**Abstract.** Recently, numerous physical attacks have been demonstrated against lattice-based
schemes, often exploiting their unique properties such as the reliance on Gaussian distri-
butions, rejection sampling and FFT-based polynomial multiplication. As the call for con-
crete implementations and deployment of postquantum cryptography becomes more press-
ing, protecting against those attacks is an important problem. However, few countermea-
sures have been proposed so far. In particular, masking has been applied to the decryption
procedure of some lattice-based encryption schemes, but the much more difficult case of
signatures (which are highly non-linear and typically involve randomness) has not been con-
sidered until now.

In this paper, we describe the first masked implementation of a lattice-based signature scheme.
Since masking Gaussian sampling and other procedures involving contrived probability dis-
tributions would be prohibitively inefficient, we focus on the GLP scheme of Güneysu,
Lyubashevsky and Pöppelmann (CHES 2012). We show how to provably mask it in the
Ishai–Sahai–Wagner model (CRYPTO 2003) at any order in a relatively efficient manner,
using extensions of the techniques of Coron et al. for converting between arithmetic and
Boolean masking. Our proof relies on a mild generalization of probing security that sup-
ports the notion of public outputs. We also provide a proof-of-concept implementation to
assess the efficiency of the proposed countermeasure.

**Keywords:** Side-Channel Analysis, Masking, Lattice-Based Cryptography, Fiat–Shamir With Aborts, GLP Signatures
# 1 Introduction

As the demands for practical implementations of postquantum cryptographic schemes get more pressing, as evidenced by the NIST postquantum competition and the recommendations of various agencies, understanding the security of those schemes against physical attacks is of paramount importance. Lattice-based cryptography, in particular, is an attractive option in the postquantum setting, as it allows to design postquantum implementations of a wide range of primitives with strong security guarantees and a level of efficiency comparable to currently deployed RSA and elliptic curve-based schemes. However, it poses new sets of challenges as far as side-channels and other physical attacks are concerned. In particular, the reliance on Gaussian distributions, rejection sampling or the number-theoretic transform for polynomial multiplication have been shown to open the door to new types of physical attacks for which it is not always easy to propose efficient countermeasures.

**Lattice-based signatures and their security.** The issue has in particular been laid bare in a number of recent works for the case of lattice-based signature schemes. Lattice-based signature in the random oracle model can be roughly divided into two families: on the one hand, constructions following Lyubashevsky's "Fiat-Shamir with aborts" paradigm [37], and on the other hand, hash-and-sign signatures relying on lattice trapdoors, as introduced by Gentry, Peikert and Vaikuntanathan [32]. Attempts have been made to implement schemes from both families, but Fiat-Shamir signatures are more common (although their postquantum security is admittedly not as well grounded). The underlying framework is called Fiat-Shamir with aborts because, unlike RSA and discrete logarithm-based constructions, lattice-based constructions involve sampling from sets that do not admit a nice algebraic structure. A naïve sampling algorithm would leak partial key information, in much the same way as it did in early heuristic schemes like GGH and NTRUSign; this is avoided by forcing the output signature to be independent of the secret key using rejection sampling. Many instantiations of the framework have been proposed [37,38,35,26,42], some of them quite efficient: for example, the BLISS signature scheme [26] boasts performance and key and signature sizes roughly comparable to RSA and ECDSA signatures.

However, the picture becomes less rosy once physical attacks are taken into account. For instance, Groot Bruinderink et al. [13] demonstrated a cache attack targeting the Gaussian sampling of the randomness used in BLISS signatures, which recovers the entire secret key from the side-channel leakage of a few thousand signature generations. Fault attacks have also been demonstrated on all kinds of lattice-based signatures [28,10]. In particular, Espitau et al. recover the full BLISS secret key using a single fault on the generation of the randomness (and present a similarly efficient attack on GPV-style signatures). In 2017, ACM CCS featured two papers [29,41] exposing further side-channel attacks on BLISS, its variant BLISS-B, and their implementation in the strongSwan VPN software. They are based on a range of different side channels (cache attacks, simple and correlation electromagnetic analysis, branch tracing, etc.), and some of them target new parts of the signature generation algorithm, such as the rejection sampling.

In order to protect against attacks such as these, one would like to apply powerful countermeasures like masking. However, doing so efficiently on a scheme like BLISS seems hard, as discussed in [29]. Indeed, the sampling of the Gaussian randomness in BLISS signature generation involves either very large lookup tables, which are expensive to mask efficiently, or iterative approaches that are hard to even implement in constant time, let alone mask. Similarly, the rejec-
tion sampling step involves transcendental functions of the secret data that have to be computed to high precision; doing so in masked form seems daunting.

However, there exist other lattice-based signatures that appear to support side-channel countermeasures like masking in a more natural way, because they entirely avoid Gaussians and other contrived distributions. Both the sampling of the randomness and the rejection sampling of signatures target uniform distributions in contiguous intervals. Examples of such schemes include the GLP scheme of Güneysu, Lyubashevsky and Pöppelmann [35], which can be seen as the ancestor of BLISS, and later variants like the Dilithium scheme of Ducas et al. [27] (but not Dilithium-G).

In this paper, we show how to efficiently mask the GLP scheme at any masking order, so as to achieve security against power analysis and related attacks (both simple power analysis and higher-order attacks like differential/correlation power analysis). This is to the best of our knowledge the first time a masking countermeasure has been applied to protect lattice-based signatures.

**Prior work on masking.** Masking is a well-known technique introduced by Chari, Rao and Rohatgi at CHES 2002 [14] and essentially consists in splitting a secret value into $d+1$ values ($d$ is thus the masking order), using a secret sharing scheme. This will force the adversary to read many internal variables if he wants to recover the secret value, and he will gain no information if he observes fewer than $d$ values. The advantage of this splitting is that linear operations cost nothing, but the downside is that non-linear operations (such as the AES S-box) can become quite expensive. Later, Ishai, Sahai and Wagner [36] developed a technique to prove the security of masking schemes in the probing model (ISW), in which the adversary can read off at most $d$ wires in a circuit. Recently, Duc, Dziembowski and Faust [25] proved the equivalence between this probing model and the more realistic noisy model, in which the adversary acquires leakage on all variables, but that leakage is perturbed with some noise distribution, as is the case in practical side-channel attacks. Since the ISW model is much more convenient for designing and proving masking countermeasures, it is thus preferred, as the equivalence results of Duc et al. ultimately ensure that a secure implementation in the ISW model at a sufficiently high masking order is going to be secure against practical side-channel attacks up to a given signal-to-noise ratio.

Prior to this work, masking had been applied to lattice-based encryption schemes [44,43] (as opposed to signatures). However, in these schemes, in most cases, only the decryption procedure needs to be protected, and it usually boils down to computing a scalar product between the secret key and the ciphertext (which is a linear operation in the secret data) followed by a comparison (which is non-linear, but not very difficult to mask). Oder et al. [40] point out a number of issues with those masked decryption algorithms, and describe another one, for a CCA2-secure version of Ring-LWE public-key encryption.

**Our results.** Masking lattice-based signatures, even in the comparatively simple case of GLP, turns out to be surprisingly difficult—possibly more so than any of the previous masking countermeasures considered so far in the literature. The probabilistic nature of signature generation, as well as its reliance on rejection sampling, present challenges (both in terms of design and of proof techniques) that had not occurred in earlier schemes, most of them deterministic. In addition, for performance reasons, we are led to require a stronger security property of the original, unprotected signature scheme itself, which we have to establish separately. More precisely, the following issues arise.

*Conversion between Boolean and mod-$p$ arithmetic masking.* Most steps of the signing algorithm involve linear operations on polynomials in the ring $\mathcal{R} = \mathbb{Z}_p[x]/(x^n + 1)$. They can thus be
masked very cheaply using mod-$p$ arithmetic masking: each coefficient is represented as a sum of $d+1$ additive shares modulo $p$. For some operations, however, this representation is less convenient.

This is in particular the case for the generation of the randomness at the beginning of the algorithm, which consists of two polynomials $y_1, y_2$ with uniformly random coefficients in a subinterval $[-k, k]$ of $\mathbb{Z}_p$. Generating such a random value in masked form is relatively easy with Boolean masking, but seems hard to do efficiently with arithmetic masking. Therefore, we have to carry out a conversion from Boolean masking to mod-$p$ arithmetic masking. Such conversions have been described before [22,18], but only when the modulus $p$ was a power of 2. Adapting them to our settings requires some tweaks.

Similarly, the rejection sampling step amounts to checking whether the polynomials in the signature have their coefficients in another interval $[-k', k']$. Carrying out the corresponding comparison is again more convenient with Boolean masking, and hence we need a conversion algorithm in the other direction, from mod-$p$ arithmetic masking to Boolean masking. We are again led to adapt earlier works on arithmetic-to-Boolean masking conversion [22,21] to the case of a non-prime modulus.

*Security of the signature scheme when revealing the “commitment” value.* One of the operations in signature generation is the computation of a hash function mapping to polynomials in $\mathcal{R}$ of a very special shape. Masking the computation of this hash function would be highly inefficient and difficult to combine with the rest of the algorithm. Indeed, the issue with hashing is not obtaining a masked bit string (which could be done with something like SHA-3), but expanding that bit string into a random-looking polynomial $\tilde{c}$ of fixed, low Hamming weight in masked form. The corresponding operation is really hard to write down as a circuit. Moreover, even if that could be done, it would be terrible for performance because subsequent multiplications by $\tilde{c}$ are no longer products by a known sparse constant, but full-blown ring operations that have to be fully masked.

But more importantly, this masking *should* intuitively be unnecessary. Indeed, when we see the signature scheme as the conversion of an identification protocol under the Fiat–Shamir transform, the hash function computation corresponds to the verifier’s sampling of a random challenge $c$ after it receives the commitment value $r$ from the prover. In particular, the verifier always learns the commitment value $r$ (corresponding to the input of the hash function), so if the identification protocol is “secure”, one should always be able to reveal this value without compromising security. But the security of the signature scheme only offers weak guarantees on the security of the underlying identification protocol, as discussed by Abdalla et al. [1].

In usual Fiat–Shamir signatures, this is never an issue because the commitment value can always be publicly derived from the signature (as it is necessary for signature verification). However, things are more subtle in the Fiat–Shamir with aborts paradigm, since the value $r$ is not normally revealed in executions of the signing algorithm that do not pass the rejection sampling step. In our setting, though, we would like to unmask the value to compute the hash function in all cases, before knowing whether the rejection sampling step will be successful. If we do so, the side-channel attacker can thus learn the pair $(r, c)$ corresponding to rejected executions as well, and this is not covered by the original security proof, nor does security with this additional leakage look reducible to the original security assumption.

However, it is heuristically a hard problem to distinguish those pairs from uniform (an LWE-like problem with a rather unusual distribution), so one possible approach, which requires no change at all to the algorithm itself, is to redo the security proof with an additional, ad hoc hardness assumption. This is the main approach that we suggest in this paper. Although heuristically
safe, it is rather unsatisfactory from a theoretical standpoint, so we additionally propose another approach:<fnref n="9" /> compute the hash function not in terms of $r$ itself, but of $f(r)$ where $f$ is a statistically-hiding commitment scheme whose opening information is added to actual signatures, but not revealed in executions of the algorithm that do not pass the rejection sampling. Using a suitable $f$, $f(r)$ can be efficiently computed in masked form, and only the result needs to be unmasked. It is then clear that the leakage of $(f(r), c)$ is innocuous, and the modified scheme can be proved entirely with no additional hardness assumption. The downside of this approach is of course that the commitment key increases the size of the public key, the opening information increases the size of signatures, and the masked computation of the commitment itself takes a large amount of time. For practical purposes, we therefore recommend the heuristic approach.

*Security of masking schemes with output-dependent probes.* In order to prove the security of our masked implementation we see that we reveal some public value $r$ or a commitment of it. Consequently, we must adapt the notion of security from the probing model to account for public outputs; the idea here is not to state that public outputs do not leak relevant information, but rather that the masked implementation *does not leak more information than the information released through public outputs*. We capture this intuition by letting the simulator depend on the distribution of the public outputs. This extends the usual “non-interference” (NI) security notion to a new, more general notion of “non-interference with public outputs” (NIo).

*Security proofs.* The overall security guarantee for the masked implementation is established by proving the security of individual gadgets and asserting the security of their combination. For some gadgets, one establishes security in the usual probing model, opening the possibility to resort to automated tools such as *maskComp* [5] to generate provably secure masked implementations. For other gadgets, the proofs of security are given by exhibiting a simulator, and checking its correctness manually. Finally, the main theorem is deduced from the proof of correctness and security in the probing model with public outputs for the masked implementation, and from a modified proof of security for the GLP scheme.

**More recent developments.** Since the publication of the conference version of this paper [6] back in 2018, numerous works have relied on, further developed or expanded upon the techniques presented below.

Most directly, our techniques have been applied to mask other lattice-based signature schemes: Migliore et al. used them to mask Dilithium [39], Gérard and Rossi to mask qTESLA [33], Barthe et al. to mask a novel implementation of BLISS [7] and Espitau et al. to describe a masked version of their new proposed hash-and-sign signature scheme Mitaka [30].

Some of the masking techniques we introduce have also been reused in settings other than signature schemes. In particular, the gadgets to convert between prime-modulus arithmetic masking and boolean masking have seen extensive use, and variants have been discussed in later works, particularly by Schneider et al. [46] and Coron et al. [19], who focus on those conversion algorithms and optimize or simplify them. Masked implementations of lattice-based key encapsulation mechanisms (KEMs) and encryption schemes like Kyber [11] and NTRU [20].

The security notions introduced in our masking proof, particularly NIo, have also proved to be of independent interest. They were for example leveraged in Aranha et al.'s masking of the Picnic MPC-in-the-head signature scheme [2] (as well as BLISS [7] and Mitaka [30]).

<footnote n="9">⁹ We are indebted to Vadim Lyubashevsky for suggesting this approach.</footnote>
Outside of masking, our work has also highlighted the difficulties that arise regarding rejected instances in Fiat-Shamir with aborts in distributed settings, and in doing so, has influenced several later works, particularly on lattice-based threshold signatures [31,23,24], that either used an adapted variant of our rejected-DCK assumption or our commitment approach. Very recently, Boschini et al. [12] showed how this issue could be overcome at least in the discrete Gaussian noise setting and for certain ranges of parameters; adapting those techniques to the present work in order to do away with the extra rejected-DCK assumption would be of great interest, though possibly quite challenging.

**Organization of the paper.** In §2, we describe the GLP signature scheme and the security assumption on which its security is based. In §3, we present the new security notions used in our proofs. Then, in §4, we describe how to mask the GLP algorithm at any masking order. Finally, in §5, we describe an implementation of this masking countermeasure, and suggest some possible efficiency improvements. We conclude in §6.

# 2 The GLP signature scheme

## 2.1 Parameters and security

**Notations.** Throughout this paper, we will use the following notations: $n$ is a power of 2, $p$ is a prime number congruent to 1 modulo $2n$, $\mathcal{R}$ is the polynomial ring modulo $x^n + 1$, $\mathcal{R} = \mathbb{Z}_p[x]/(x^n + 1)$. The elements of $\mathcal{R}$ can be represented by polynomials of degree $n-1$ with coefficients in the range $[-\frac{p-1}{2}, \frac{p-1}{2}]$. For an integer $k$ such that $0 < k \le (p-1)/2$, we denote by $\mathcal{R}_k$ the elements of $\mathcal{R}$ with coefficients in the range $[-k, k]$. We write $\stackrel{\$}{\leftarrow} S$ for picking uniformly at random in a set $S$ or $\stackrel{\$}{\leftarrow} \mathcal{D}$ for picking according to some distribution $\mathcal{D}$. Let $\mathcal{D}_\alpha^n$ is the set of polynomials in $\mathcal{R}$ that have all zero coefficients except for at most $\alpha = 32$ coefficients. The key generation algorithm for the GLP signature scheme is as follows:

<caption>**Algorithm 1: GLP key derivation**</caption>

1 $s_1, s_2 \stackrel{\$}{\leftarrow} \mathcal{R}_1 // s_1$ and $s_2$ have coefficients in $\{-1, 0, 1\}$
2 $a \stackrel{\$}{\leftarrow} \mathcal{R}$
3 $t \leftarrow as_1 + s_2$
4 $sk \leftarrow (s_1, s_2)$
5 $pk \leftarrow (a, t)$

Given the verification key $pk = (a, t)$, if an attacker can derive the signing key, he can be used to also solve a DCK$_{p,n}$ problem defined in [35].

**Definition 1** The DCK$_{p,n}$ problem (Decisional Compact Knapsack problem) is the problem of distinguishing between the uniform distribution over $\mathcal{R} \times \mathcal{R}$ and the distribution $(\mathbf{a}, \mathbf{as}_1 + \mathbf{s}_2)$ with $\mathbf{s}_1, \mathbf{s}_2$ uniformly random in $\mathcal{R}_1$.

In the security proof of our variant of the signature scheme, we introduce a new computational problem.
**Definition 2** Let $p, n, q, \alpha$ and $k$ be integer parameters. The $\mathbf{R-DCK}_{p,n}$ problem (Rejected-Decisional Compact Knapsack problem) is the following problem: Given $(\mathbf{a}, \vec{b}_i, \vec{c}_i) \in R_p \times R_p \times \mathcal{D}_\alpha^n$ for $i \in [0, q-1]$, distinguish whether this sample has been drawn from

1. the procedure where

- $\mathbf{a}$ is drawn uniformly in $R_p$;

- the $\vec{b}_i$ are drawn uniformly in $R_p$;

- the $\vec{c}_i$ are drawn uniformly in $\mathcal{D}_\alpha^n$.

2. or the procedure where

- elements $(\mathbf{s}_1, \mathbf{s}_2, \mathbf{a})$ are firstly drawn uniformly in $R_1^2 \times R_p$;

- for each $i$, elements $(\mathbf{c}_i, \mathbf{y}_{1,i}, \mathbf{y}_{2,i})$ are drawn uniformly in $\mathcal{D}_\alpha^n \times R_{p,k}^2$. This step is repeated until $\mathbf{s}_1\mathbf{c}_i + \mathbf{y}_{1,i} \notin R_{p,k-\alpha}$ or $\mathbf{s}_2\mathbf{c}_i + \mathbf{y}_{2,i} \notin R_{p,k-\alpha}$;

- the final samples are $(\mathbf{a}, \vec{b}_i, \vec{c}_i) = (\mathbf{a}, \mathbf{a}\mathbf{y}_{1,i} + \mathbf{y}_{2,i}, \mathbf{c}_i)$.

As shown in Appendix A.3, assuming the hardness of $\mathbf{R-DCK}_{p,n}$ can be avoided entirely by computing the hash value $\vec{c}$ not in terms of $\vec{r} = \vec{a}\vec{y}_1 + \vec{y}_2$, but of a statistically hiding commitment thereof. This approach shows that masking can be done based on the exact same assumptions as the original scheme, but at some non-negligible cost in efficiency.

To obtain a scheme that more directly follows the original one and to keep the overhead reasonable, we propose to use $\mathbf{R-DCK}_{p,n}$ as an extra assumption, which we view as a pragmatic compromise. The assumption is admittedly somewhat artificial, but the same can be said of $\mathbf{DCK}_{p,n}$ itself to begin with, and heuristically, $\mathbf{R-DCK}_{p,n}$ is similar, except that it removes smaller (hence “easier”) instances from the distribution: one expects that this makes distinguishing harder, even though one cannot really write down a reduction to formalize that intuition.

## 2.2 The signature scheme

This part describes the signature scheme introduced in [35]. Additional functions like transform and compress introduced in [35] can be used to shorten the size of the signatures. Note however that for masking purposes, we only need to consider the original, non-compressed algorithm of Güneysu et al., which we describe below. Indeed, signature compression does not affect our masking technique at all, because it only involves unmasked parts of the signature generation algorithm (the input of the hash function and the returned signature itself). As a result, although this paper only discusses the non-compressed scheme, we can directly apply our technique to the compressed GLP scheme with no change, and in fact this is what our proof-of-concept implementation in §5 actually does.

The signature scheme needs a particular cryptographic hash function, $H: \{0,1\}^* \to \mathcal{D}_\alpha^n$. Recall that $\mathcal{D}_\alpha^n$ is the set of polynomials in $\mathcal{R}$ that have all zero coefficients except for at most $\alpha = 32$ coefficients that are in $\{-1, +1\}$ (or $\alpha = 16$ when using the updated parameters presented in [15]).

Let $k$ be a security parameter. Algorithms 2 and 3 respectively describe the GLP signature and verification. Here is the correctness equation for the verification: $\mathbf{az}_1 + \mathbf{z}_2 - \mathbf{tc} = \mathbf{ay}_1 + \mathbf{y}_2$.

The parameter $k$ controls the trade-off between the security and the runtime of the scheme. The smaller $k$ gets, the more secure the scheme becomes and the shorter the signatures get but the time to sign will increase. The authors of the implementation of [35] suggest $k = 2^{14}$, $n = 512$ and $p = 8383489$ for ≈ 100 bits of security and $k = 2^{15}$, $n = 1024$ and $p = 16760833$ for > 256 bits of security.
## 2.3 Security proof of the r-GLP variant

As mentioned above, masking the hash function of the GLP signature directly has a prohibitive cost, and it is thus preferable to unmask the input $\mathbf{r} = \bar{a}\bar{y}_1 + \bar{y}_2$ to compute the hash value $\mathbf{c} = H(\mathbf{r}, \mathbf{m})$. Doing so allows a side-channel attacker to learn the pair $(\mathbf{r}, \mathbf{c})$ corresponding to rejected executions as well, and since that additional information is not available to the adversary in the original setting, we need to show that it does not affect the security of the scheme.

This stronger security requirement can be modeled as the unforgeability under chosen message attacks of a modified version of the GLP signature scheme in which the pair $(\mathbf{r}, \mathbf{c})$ is made public when a rejection occurs. We call this modified scheme $\bar{r}$-GLP, and describe it as Algorithm 4.

**Remark 1.** Due to the rejection step in line 7, for a full signature procedure, Algorithm 4 will be called repeatedly in order to generate a final, valid signature. Note that in the attacker model that will be presented in §3.4, an attacker can probe at most *d* intermediate values in the general signature algorithm. Thus, the key does not need to be refreshed between executions of Algorithm 4.

The modification means that, in the EUF-CMA security game, the adversary gets access not only to correctly generated GLP signatures, but also to pairs $(\mathbf{r}, \mathbf{c})$ when rejection occurs, which is exactly the setting that arises as a result of unmasking the value $\bar{r}$. The following theorem, proved in Appendix A.2, states that the modified scheme is indeed secure, at least if we are willing to assume the hardness of the additional $\mathbf{DCK}_{p,n}$ assumption.

**Theorem 1.** Let $n, p, \mathcal{R}$ and $\mathcal{D}_\alpha^n$ as defined in §2.1. Assuming the hardness of the $\mathbf{DCK}_{p,n}$ and $\mathbf{R-DCK}_{p,n}$ problems, the signature $\mathbf{r}$-GLP is EUF-CMA secure in the random oracle model.

**Remark 2.** As mentioned previously, we can avoid the non-standard assumption $\mathbf{R-DCK}_{p,n}$ by hashing not $\bar{r}$ but $f(\bar{r})$ for some statistically hiding commitment $f$ (which can itself be constructed under $\mathbf{DCK}_{p,n}$, or standard lattice assumptions). See Appendix A.2 for details. The downside of that approach is that it has a non negligible overhead in terms of key size, signature size, and to a lesser extent signature generation time.

**Remark 3.** One can think that Algorithm 4 is insecure<fnref n="10" /> because the adversary have access to the rejected $\bar{c}$'s and the rejection probability is accessible (by counting the number of rejected

<table><thead><tr><th>Algorithm 2: GLP signature</th><th>Algorithm 3: GLP verification</th></tr></thead><tbody><tr><td><b>Data:</b> m, pk, sk<br><b>Result:</b> Signature σ</td><td><b>Data:</b> m, σ, pk</td></tr><tr><td>1 y<sub>1</sub>, y<sub>2</sub> &larr; <i>R</i><sub>k</sub></td><td>1 if z<sub>1</sub>, z<sub>2</sub> &isin; <i>R</i><sub>k&minus;&alpha;</sub> and<br>c = H(az<sub>1</sub> + z<sub>2</sub> &minus; tc, m) then</td></tr><tr><td>2 c &larr; H(r = ay<sub>1</sub> + y<sub>2</sub>, m)</td><td>2 | accept</td></tr><tr><td>3 z<sub>1</sub> &larr; s<sub>1</sub>c + y<sub>1</sub></td><td>3 else</td></tr><tr><td>4 z<sub>2</sub> &larr; s<sub>2</sub>c + y<sub>2</sub></td><td>4 | reject</td></tr><tr><td>5 if z<sub>1</sub> or z<sub>2</sub> &notin; <i>R</i><sub>k&minus;&alpha;</sub> then</td><td>5 end</td></tr><tr><td>6 | restart</td><td></td></tr><tr><td>7 end</td><td></td></tr><tr><td>8 return σ = (z<sub>1</sub>, z<sub>2</sub>, c)</td><td></td></tr></tbody></table>

<footnote n="10">¹⁰ We thank Damien Stehlé for suggesting this approach.</footnote>
**Algorithm 4:** Tweaked signature with public $r$ (called repeatedly in order to generate a final, valid signature)

**Data:** $m, pk = (a, t)$, $sk = (s_1, s_2)$

**Result:** Signature $\sigma$

1 $y_1 \stackrel{\$}{\leftarrow} \mathcal{R}_k$

2 $y_2 \stackrel{\$}{\leftarrow} \mathcal{R}_k$

3 $r \leftarrow ay_1 + y_2$

4 $c \leftarrow H(r, m)$

5 $z_1 \leftarrow s_1c + y_1$

6 $z_2 \leftarrow s_2c + y_2$

7 **if** $z_1$ or $z_2 \notin \mathcal{R}_{k-\alpha}$ **then**

8 $\mid$ $(z_1, z_2) \leftarrow (\perp, \perp)$

9 **end**

10 **return** $\sigma = (z_1, z_2, c, r)$

signatures over the total number of signature queries). However, the rejection probability is, by construction, independent from $\vec{s}_1$, $\vec{s}_2$ and $\vec{c}$. Thus, even conditioned with smartly chosen $\vec{c}$, the adversary cannot gain any information from this probability. More precisely, the former probability is

$$P [\|\vec{s}_1\vec{c} + \vec{y}_1\|_{\infty} > k - \alpha] = P [\|\vec{s}_2\vec{c} + \vec{y}_2\|_{\infty} > k - \alpha] = \frac{2\alpha}{2k+1}.$$

It can be seen graphically with Figure 1.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Graphical intuition for computing $P[\|\vec{s}_1\vec{c} + \vec{y}_1\|_{\infty} > k - \alpha] = P[\|\vec{s}_2\vec{c} + \vec{y}_2\|_{\infty}]$. Without loss of generality, we only consider $\vec{y}_1$, $\vec{s}_1$, $\vec{z}_1$. To the left, we represent the distribution for the coefficients of $\vec{y}_1$. In the middle, we represent the possible values for the coefficients of $\vec{s}_1\vec{c}$. To the right, the distribution of $\vec{y}_i$ is shifted by $\vec{s}_i\vec{c}$ to obtain the distribution of $\vec{z}_1$. The accepted (resp. rejected) $\vec{z}_1$ are in green (resp. orange.). We see that, no matter the shift of $\vec{s}_i\vec{c}$, the fraction of rejected coefficients will stay $= \frac{2\alpha}{2k+1}$.</figcaption></figure>

# 3 Probing model with public outputs

In this section, we introduce some essential notions to review the definition of the probing model, then we define an extension to accommodate public outputs.

## 3.1 Preliminary Notions

In the following, let $\mathbb{K}$ be a finite field.
An arithmetic circuit is a directed acyclic graph whose vertices are arithmetic gates processing operations over $\mathbb{K}$ and whose edges are wires. A randomized arithmetic circuit is a additionally equipped with random-bit gates of fan-in 0 that outputs a uniformly random bit.

A $d$-sharing of $x \in \mathbb{K}$ equipped with the additive law + is a random tuple $(x_0, x_1, \dots, x_{d-1}) \in \mathbb{K}^d$ satisfying $x = x_0 + x_1 + \dots + x_{d-1}$. The sharing is said to be uniform if, for a given $x$, it is uniformly distributed over the subspace of tuples satisfying this equality. In the following, a $d$-sharing of a given variable $x$ is denoted by $(x_i)_{0 \le i \le d-1}$. We further denote by Enc a probabilistic encoding algorithm that maps $x \in \mathbb{K}$ to a fresh uniform sharing $(x_i)_{0 \le i \le d-1}$.

A $d$-shared circuit $C$ is a randomized circuit working on $d$-shared variables. More specifically, a $d$-shared circuit takes a set of $n$ input shareings $(x_{1,i})_{0 \le i \le d-1}, \dots, (x_{n,i})_{0 \le i \le d-1}$ and computes a set of $m$ output shareings $(y_{1,i})_{0 \le i \le d-1}, \dots, (y_{m,i})_{0 \le i \le d-1}$ such that $(y_1, \dots, y_m) = f(x_1, \dots, x_n)$ for some deterministic function $f$. ($d-1$) is then referred to as the masking order.

A probe on $C$ or an intermediate variable of $C$ refers to a wire index (for some given indexing of $C$'s wires)$^{11}$. An evaluation of $C$ on input $[(x_{1,i})_{0 \le i \le d-1}, \dots, (x_{n,i})_{0 \le i \le d-1}$ under a set of probes $P$ refers to the distribution of the tuple of wires pointed by the probes in $P$ when the circuit is evaluated on $(x_{1,i})_{0 \le i \le d-1}, \dots, (x_{n,i})_{0 \le i \le d-1}$, which is denoted by $C((x_{1,i})_{0 \le i \le d-1}, \dots, (x_{n,i})_{0 \le i \le d-1})_P$.

In the following, we focus on a special kind of shared circuits which are composed of gadgets. A $(u, v)$-gadget is a randomized shared circuit as a building block of a shared circuit that performs a given operation on its $u$ input shareings and produces $v$ output shareings.

## 3.2 Probing model

The probing model, introduced by Ishai, Sahai and Wagner in 2003 [36], is one of the most broadly used leakage model. Informally, it states that during the evaluation of a circuit $C$, at most $d$ wires (chosen by the adversary) leak the value they carry. The circuit $C$ is thus claimed to be $d$-probing secure if the exact values of any set of $d$ probes do not reveal any information about its inputs.

**Definition 3 (d-probing security)** A randomized shared arithmetic circuit $C$ equipped with an encoding Enc is $d$-probing secure if there exists a probabilistic simulator $Sim$ which, for any input $x \in \mathbb{K}^\ell$, for every set of probes $P$ such that $|P| \le d$, satisfies

$$ \mathrm{Sim}(C, P) = C(\mathrm{Enc}(x))_P. $$

Since the computation of distributions is expensive, the security proof rather rely on stronger simulation-based properties, introduced by Barthe et al. [5], to demonstrate the independence of the leaking wires from the input secrets. Informally, the idea is to perfectly simulate each possible set of probes with the smallest set of shares for each input. We recall the formal definitions of $d$-non-interference and $d$-strong non-interference hereafter.

**Definition 4 (d-non-interference)** A randomized shared arithmetic circuit $C$ equipped with an encoding Enc is $d$-non-interferent (or $d$-NI) if there exists a deterministic simulator $Sim_1$ and a probabilistic simulator $Sim_2$, such that, for any input $x \in \mathbb{K}^\ell$, for every set of probes $P$ of size $d$,

$$ (\mathcal{I}_1, \mathcal{I}_2, \dots, \mathcal{I}_\ell) \leftarrow \mathrm{Sim}_1(C, P) \quad \text{with } |\mathcal{I}_1|, |\mathcal{I}_2|, \dots, |\mathcal{I}_\ell| \le d \\ \text{and} \quad \mathrm{Sim}_2((x_{1,i})_{i \in \mathcal{I}_1}, (x_{2,i})_{i \in \mathcal{I}_2}, \dots, (x_{\ell,i})_{i \in \mathcal{I}_\ell}) = C(\mathrm{Enc}(x))_P. $$

<footnote>$^{11}$ In this paper, the probes generally correspond to the coefficients (in $\mathbb{K} = \mathbb{Z}_p$) of the polynomials displayed in the algorithms.</footnote>
If the input sharing is uniform, a d-non-interferent randomized arithmetic circuit C is also d-probing secure. One step further, the strong non-interference benefits from stopping the propagation of the probes between the outputs and the input shares and additionally trivially implies d-NI.

**Definition 5 (d-strong non-interference)** A randomized shared arithmetic circuit C equipped with an encoding Enc is d-strong non-interferent (or d-SNI) if there exists a deterministic simulator $Sim_1$ and a probabilistic simulator $Sim_2$, such that, for any input $x \in K^l$, for every set of probes P of size d whose $P_1$ target internal variables and $P_2 = P \setminus P_1$ target the output shares,

$$ (\mathcal{I}_1, \mathcal{I}_2, \dots, \mathcal{I}_l) \leftarrow Sim_1(C, P) \quad \text{with } |\mathcal{I}_1|, |\mathcal{I}_2|, \dots, |\mathcal{I}_l| \le |P_1| \\ \text{and } Sim_2((x_{1,i})_{i \in \mathcal{I}_1}, (x_{2,i})_{i \in \mathcal{I}_2}, \dots, (x_{l,i})_{i \in \mathcal{I}_l}) = C(Enc(x))_P. $$

**The maskComp tool.** For certain proofs, we will use the maskComp tool from Barthe et al. [5]. It uses a type-based information flow analysis with cardinality constraints and ensures that the composition of gadgets is d-NI at arbitrary orders, by inserting *refresh gadgets* when required. The latter are functionally equivalent to the identity function but refresh their input sharing with new random values to break the dependencies between their input and output shareings.

## 3.3 Probing model with public outputs

The security analysis of our masked implementation of GLP requires an adaptation of the standard notion of security in the probing model. Specifically, our implementation does not attempt to mask the computation of $H(\mathbf{r}, \mathbf{m})$ at line 2 of Algorithm 2; instead, it recovers $\mathbf{r}$ from its shares and then computes $H(\mathbf{r}, \mathbf{m})$. This optimization is important for the efficiency of the masked algorithm, in particular because it is not immediately clear whether one can mask the hash function $H$ efficiently—note that this kind of optimization is also reminiscent of the method used to achieve efficient sorting algorithms in multi-party computations.

From a security perspective, recombining $\mathbf{r}$ in the algorithm is equivalent to making $\mathbf{r}$ a public output. In contrast with “return values”, we will refer to “outputs” as values publicly accessible to the adversary during the execution of the masked algorithm. The side-channel attacker can therefore use outputs in attacks. Since the usual notions of NI and SNI security do not account for outputs in that sense, we need to extend those notions of security to support algorithms that provide such outputs. The idea here is not to state that public outputs do not leak relevant information, but rather that the masked implementation does not leak more information than what is released through public outputs. We capture this intuition by letting the simulator depend on the distribution of the public outputs.

**Definition 6** A gadget with public outputs is a gadget together with a distinguished subset of intermediate variables whose values are broadcast during execution.

We now turn to the definition of non-interference for gadgets with public outputs. Informally, a gadget with public outputs $Y$ is d-NIo if and only if every set of at most $d$ intermediate variables can be perfectly simulated with the public outputs and at most $d$ shares of each input.

**Definition 7 (d-non-interference with public outputs (d-NIo))** A randomized shared arithmetic circuit C equipped with an encoding Enc is d-non-interferent with public outputs Y (or d-NIo)
if there exists a deterministic simulator $Sim_1$ and a probabilistic simulator $Sim_2$, such that, for any input $x \in K^l$, for every set of probes $P$ of size $d$,

$$ (\mathcal{I}_1, \mathcal{I}_2, \dots, \mathcal{I}_l) \leftarrow Sim_1(C, P) \quad \text{with } |\mathcal{I}_1|, |\mathcal{I}_2|, \dots, |\mathcal{I}_l| \le d \\ \text{and} \quad Sim_2((x_{1,i})_{i \in \mathcal{I}_1}, (x_{2,i})_{i \in \mathcal{I}_2}, \dots, (x_{l,i})_{i \in \mathcal{I}_l}, Y) = C(Enc(x))_P. $$

Note that the use of public outputs induces a weaker notion of security.

**Lemma 1.** Let $G$ be a $d$-NI-gadget. Then $G$ is $d$-NIo for every subset $X$ of intermediate variables.

Informally, the lemma states that a gadget that does not leak any information also does not leak more information than what is revealed by a subset of its intermediate variables. The lemma is useful when resorting to automated tools for proving NI security of some gadgets used in the masked implementations of GLP. In particular, we will use the maskComp tool.

Since $d$-NIo security is weaker than $d$-NI security, we must justify that it delivers the required security guarantee. This is achieved by combining the proofs of security for the modified version of GLP with public outputs, and the proofs of correctness and security for the masked implementations of GLP.

## 3.4 EUF-CMA-security in the $d$ probing model

GLP is claimed EUF-CMA (existential unforgeability under chosen message attack). While $d$-probing model is universal for all circuits, the EUF-CMA model includes several calls to a signature oracle and thus some internal state management for the secret key is required. In the following, we formalize the notion that combines the EUF-CMA security property and the security in the ISW model. We need to introduce the notion of KeyUpdate algorithm. This algorithm updates the secret key between signature oracle calls. It is executed after each query and is excluded from the given leakage (after each ExecObs, as depicted in Figure 2). We define $\mathcal{O}_{alg}$ as a set of the names of at most $d$ intermediate values inside an algorithm $alg$. In our model, this set is chosen by attacker and the challenger will provide a $d$-uple denoted $\mathcal{L}_{alg}$ that is the leakage corresponding to each of the desired intermediate values.

**Definition 1.** A signature scheme $(KeyGen, Sign, Verify)$ with signing key update algorithm KeyUpdate is EUF-CMA-secure in the $d$-probing model if any PPT adversary has a negligible probability of finishing the exchange presented in Figure 2 with $b = 1$.

**Remark 4.** Definition 1 assumes that the attacker does not get any leakage during the KeyUpdate. In this model, the KeyUpdate is not part of the signing procedure. This model might be seen as somewhat artificial because the secret key refreshing could in practice be attacked by a side-channel adversary. Nevertheless, this paper focuses on the masking of the signature inner content with new masked gadgets. This simplistic model has been introduced to avoid unnecessary complexifications of the analysis that would have been orthogonal to the scope of this paper. It is however possible to adapt the design of the signature with secret key refreshes to fit other more realistic models. For example, an alternative more realistic definition could assume that the attacker also gets leakage during the KeyUpdate. In this alternative definition, the total number of observations should be bounded by $d$. In other words, instead of the condition $\forall i \in \{1, \dots, q\}, |\mathcal{O}_{Sign}^{(i)}| \le d$, one should have $\sum_{i \in \{1, \dots, q\}} |\mathcal{O}_{Sign}^{(i)}| \le d$.
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** *d* probing EUF-CMA game. ExecObs is a universal Turing machine that takes $\mathcal{O}_{alg}$ as input and several other arguments, and returns the output of the algorithm on those arguments, together with $\mathcal{L}_{alg}$. Recall that the notation $\mathcal{O}_{alg}$ corresponds to a set of the names of at most *d* intermediate values inside the algorithm *alg*. This set is chosen by attacker and the challenger provides $\mathcal{L}_{alg}$ that is the leakage corresponding to each of the desired intermediate values.</figcaption></figure>
# 4 Masked algorithm

In this section, the whole GLP scheme is turned into a functionally equivalent scheme secure in the d-probing model with public outputs. Note that it suffices to mask the key derivation in the d-probing model and the signature in the d-probing model with public output $\vec{r}$, since the verification step does not manipulate sensitive data.

*Remark 5.* The masked version of GLP scheme with commitment has also been turned into a functionally equivalent scheme proved secure in the d-probing model with public output $\vec{r}$. Its masked version is a little more complex, it is detailed in Appendix B.

## 4.1 Overall structure

For simplicity, we will show the masking on a single iteration version of the signature. The masking can be generalized by calling the masked signature again if it fails.

To ensure protection against d-th order attacks, we suggest a masking countermeasure with $d+1$ shares for the following sensitive data: $y_1, y_2, s_1$ and $s_2$. All the public variables are $(a, t)$ (i.e., the public key), $m$ (i.e., the message), $rs$ (i.e., the bit corresponding to the success of the rejection sampling), $(z_1, z_2, c)$ (i.e., the signature). As mentioned before, because of the need of $\vec{r}$ recombination, even if $r$ is an intermediate value, it is considered as a public output.

Most operations carried out in the GLP signing algorithm are arithmetic operations modulo $p$, so we would like to use arithmetic masking. It means for example that $y_1$ will be replaced by $y_{1,0}, \dots, y_{1,d} \in \mathcal{R}$ such that

$$y_1 = y_{1,0} + \dots + y_{1,d} \mod p.$$

The issue is that at some points of the algorithm, we need to perform operations that are better expressed using Boolean masking when shares are combined using the exclusive or. Those parts will be extracted from both the key derivation and the signature to be protected individually and then securely composed. The different new blocks to achieve protection against d-th order attacks are depicted hereafter and represented in Figures 3 and 4:

- Generation of the shared data (DG), masked version of line 1 in Algorithm 2 and line 1 in Algorithm 1, is a function to generate shares of $y_1, y_2, s_1$ and $s_2$. It will be described in Algorithm 7, decomposed and proved d-NIo by decomposition.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Composition of mKD (The blue gadgets will be proved d-NIo, the white ones will be proved d-NI)</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Composition of mSign (the blue gadgets will be proved *d*-NIo, the white ones will be proved *d*-NI and the red one won't be protected)</figcaption></figure>

- Rejection Sampling (RS), masked version of line 5 in Algorithm 2, is a test to determine if $z_1$ and $z_2$ belong to the set $\mathcal{R}_{k-\alpha}$. It will be detailed in Algorithm 16 and proved *d*-NI by decomposition.

- Refresh and unmask (FullAdd) is a function that unmasks securely a variable by adding together its shares modulo $p$ without leaking the partial sums. It will be described in Algorithm 17 and proved *d*-NIo and *d*-NI when used at the end.

- $H^1$ and $H^2$ are the elementary parts, masked versions of line 2, 3-4 and then 5-6 in Algorithm 2. $H^1$ is also the masked version of the instruction called in line 3 of the key derivation algorithm (Algorithm 1). They are made of arithmetic computations. They are depicted in Algorithm 18 and 19. They will be proved *d*-NI.

- Hash function, line 2 in Algorithm 2. As mentioned before, it is left unmasked because it manipulates only data that is considered public.

Algorithm 5 shows a high level picture of mSign with all these blocks and Algorithm 6 shows mKD.

The proofs of *d*-NI or *d*-NIo security will be given in the following subsection. Then, the composition will be proved in §4.3 to achieve global security in the *d*-probing model with public outputs. This yields the *d*-NIo security of the masked signature and masked key generation algorithms in Theorems 2 and 3, respectively. By combining these results with the refined analysis of the GLP signature scheme in Theorem 1, one obtains the desired security guarantee, as discussed in § 3.

## 4.2 Masked gadgets

In this section each gadget will be described and proved *d*-NI or *d*-NIo. The difficulty is located in the gadgets containing Boolean/arithmetic conversions. In those gadgets (DG and RS) a detailed motivation and description are given.
**Algorithm 5: mSign**

Data: $m, pk = (\mathbf{a}, \mathbf{t})$, $sk = ((\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{s}_{2,i})_{0\le i\le d})$

Result: Signature $\sigma$

1. $(\mathbf{y}_{1,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$

2. $(\mathbf{y}_{2,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$

3. $(\mathbf{r}_i)_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{a}, (\mathbf{y}_{1,i})_{0\le i\le d}, (\mathbf{y}_{2,i})_{0\le i\le d})$

4. $\mathbf{r} \leftarrow \text{FullAdd}((\mathbf{r}_i)_{0\le i\le d})$

5. $\mathbf{c} \leftarrow \text{hash}(\mathbf{r}, \mathbf{m})$

6. $(\mathbf{z}_{1,i})_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{c}, (\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{y}_{1,i})_{0\le i\le d})$

7. $(\mathbf{z}_{2,i})_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{c}, (\mathbf{s}_{2,i})_{0\le i\le d}, (\mathbf{y}_{2,i})_{0\le i\le d})$

8. $\text{rs} \leftarrow \text{RS}((\mathbf{z}_{1,i})_{0\le i\le d}, (\mathbf{z}_{2,i})_{0\le i\le d}, k - \alpha)$

9. $(\mathbf{z}_{1,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{z}_{1,i})_{0\le i\le d})$

10. $(\mathbf{z}_{2,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{z}_{2,i})_{0\le i\le d})$

11. $\mathbf{z}_1 \leftarrow \text{FullAdd}((\mathbf{z}_{1,i})_{0\le i\le d})$

12. $\mathbf{z}_2 \leftarrow \text{FullAdd}((\mathbf{z}_{2,i})_{0\le i\le d})$

13. $\text{return } \sigma = (\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$

**Algorithm 6: mKD**

Result: Signing key $sk$, verification key $pk$

1. $(\mathbf{s}_{1,i})_{0\le i\le d} \leftarrow \text{DG}(1, d)$

2. $(\mathbf{s}_{2,i})_{0\le i\le d} \leftarrow \text{DG}(1, d)$

3. $\mathbf{a} \xleftarrow{\$} \mathcal{R}$

4. $(\mathbf{t}_i)_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{a}, (\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{s}_{2,i})_{0\le i\le d})$

5. $\mathbf{t} \leftarrow \text{FullAdd}((\mathbf{t}_i)_{0\le i\le d})$

6. $sk \leftarrow ((\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{s}_{2,i})_{0\le i\le d})$

7. $pk \leftarrow (\mathbf{a}, \mathbf{t})$

8. $\text{return as public key} (\mathbf{a}, \mathbf{t})$

9. $\text{return as secret key} ((\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{s}_{2,i})_{0\le i\le d})$

**Data generation (DG).** In the unmasked GLP signing algorithm, the coefficients of the “commitment” polynomials $\mathbf{y}_1, \mathbf{y}_2$ are sampled uniformly and independently from an integer interval of the form $[-k, k]$. In order to mask the signing algorithm, one would like to obtain those values in masked form, using $(d+1)$-arithmetic sharings in $\mathbb{Z}_p$. Note that since all of these coefficients are completely independent, the problem reduces to obtaining a $(d+1)$-arithmetic sharing in $\mathbb{Z}_p$ for a single random integer in $[-k, k]$.

Accordingly, we will first create an algorithm called Random Generation (RG) which generates a $(d+1)$-arithmetic sharing in $\mathbb{Z}_p$ of a single random integer in $[-k, k]$. Next, we will use RG in an algorithm called Data Generation (DG) which generates a sharing of a value in $\mathcal{R}_k$. DG calls RG $n$ times and is described in Algorithm 7. RG is described hereafter and will be given in Algorithm 15.

Let us now build RG. Carrying out this masked random sampling in arithmetic form directly and securely seems difficult. On the other hand, it is relatively easy to generate a Boolean sharing of such a uniformly random value. We can then convert that Boolean sharing to an arithmetic sharing using Coron et al.'s higher-order Boolean-to-arithmetic sharing conversion technique [22].
**Algorithm 7: Data Generation (DG)**

**Data:** $k$ and $d$

**Result:** A uniformly random polynomial $y$ in $\mathbb{R}_k$ in arithmetic masked form $(y_i)_{0 \le i \le d}$.

1. $(y_i)_{0 \le i \le d} \leftarrow \{0\}^d$

2. **for** $j = 0$ to $n-1$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;$(a_i)_{0 \le i \le d} \leftarrow \mathbb{R}_G(k, d)$

4. &nbsp;&nbsp;&nbsp;&nbsp;$(y_i)_{0 \le i \le d} \leftarrow (y_i + a_i x^j)_{0 \le i \le d}$

5. **end**

6. **return** $(y_i)_{0 \le i \le d}$

The technique has to be modified slightly to account for the fact that the modulus $p$ of the arithmetic sharing is not a power of two, but the overall structure of the algorithm remains the same. To obtain a better complexity, we also use the Kogge–Stone adder based addition circuit already considered in [21].

A more precise description of our approach is as follows. Let $K = 2k + 1$, and $w_0$ be the smallest integer such that $2^{w_0} > K$. Denote also by $w$ the bit size of the Boolean sharing we are going to use; we should have $w > w_0 + 1$ and $2^w > 2p$. For GLP masking, a natural choice, particularly on a 32-bit architecture, would be $w = 32$.

Now the first step of the algorithm is to generate $w_0$-bit values $(x_i^0)_{0 \le i \le d}$ uniformly and independently at random, and apply a multiplication-based share refreshing algorithm **Refresh**, as given in Algorithm 8, to obtain a fresh $w$-bit Boolean sharing $(x_i)_{0 \le i \le d}$ of the same value $x$:

$$x = \bigoplus_{i=0}^{d} x_i^0 = \bigoplus_{i=0}^{d} x_i.$$

Note that $x$ is then a uniform integer in $[0, 2^{w_0} - 1]$.

**Algorithm 8: Multiplication-based refresh algorithm for Boolean masking (Refresh)**

**Data:** A $(d+1)$-Boolean sharing $(x_i)_{0 \le i \le d}$ of some value $x$; the bit size $w$ of the returned masks

**Result:** An independent $(d+1)$-Boolean sharing $(x'_i)_{0 \le i \le d}$ of $x$

1. $(x'_i)_{0 \le i \le d} \leftarrow (x_i)_{0 \le i \le d}$

2. **for** $i = 0$ to $d$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = i + 1$ to $d$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick a uniformly random $w$-bit value $r$

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x'_i \leftarrow x'_i \oplus r$

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x'_j \leftarrow x'_j \oplus r$

7. **end**

8. **end**

9. **return** $(x'_i)_{0 \le i \le d}$

We then carry out a rejection sampling on $x$: if $x \ge K$, we restart the algorithm. If this step is passed successfully, $x$ will thus be uniformly distributed in $[0, K - 1] = [0, 2k]$. Of
**Algorithm 9:** Integer addition of Boolean shareings (SecAdd), as generated by the maskComp tool from the Kogge-Stone adder of [21]

**Data:** $(d+1)$-Boolean shareings $(x_i)_{0 \le i \le d}$, $(y_i)_{0 \le i \le d}$ of integers $x, y$; the bit size $w$ of the masks

**Result:** A $(d+1)$-Boolean sharing $(z_i)_{0 \le i \le d}$ of $x+y$

1. $(p_i)_{0 \le i \le d} \leftarrow (x_i \oplus y_i)_{0 \le i \le d}$

2. $(g_i)_{0 \le i \le d} \leftarrow \text{SecAnd}((x_i)_{0 \le i \le d}, (y_i)_{0 \le i \le d}, w)$

3. **for** $j = 1$ **to** $W := \lceil \log_2(w-1) \rceil - 1$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;pow $\leftarrow 2^{j-1}$

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(a_i)_{0 \le i \le d} \leftarrow (g_i \ll \text{pow})_{0 \le i \le d}$

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(a_i)_{0 \le i \le d} \leftarrow \text{SecAnd}((a_i)_{0 \le i \le d}, (p_i)_{0 \le i \le d}, w)$

7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(g_i)_{0 \le i \le d} \leftarrow (g_i \oplus a_i)_{0 \le i \le d}$

8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(a'_i)_{0 \le i \le d} \leftarrow (p_i \ll \text{pow})_{0 \le i \le d}$

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(a'_i)_{0 \le i \le d} \leftarrow \text{Refresh}((a'_i)_{0 \le i \le d}, w)$

10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(p_i)_{0 \le i \le d} \leftarrow \text{SecAnd}((p_i)_{0 \le i \le d}, (a'_i)_{0 \le i \le d}, w)$

11. **end**

12. $(a_i)_{0 \le i \le d} \leftarrow (g_i \ll 2^W)_{0 \le i \le d}$

13. $(a_i)_{0 \le i \le d} \leftarrow \text{SecAnd}((a_i)_{0 \le i \le d}, (p_i)_{0 \le i \le d}, w)$

14. $(g_i)_{0 \le i \le d} \leftarrow (g_i \oplus a_i)_{0 \le i \le d}$

15. $(z_i)_{0 \le i \le d} \leftarrow (x_i \oplus y_i \oplus (g_i \ll 1))_{0 \le i \le d}$

16. **return** $(z_i)_{0 \le i \le d}$

course, the test has to be carried out securely at order $d$. This can be done as follows: compute a random $w$-bit $(d+1)$-Boolean sharing $(k_i)_{0 \le i \le d}$ of the constant $(-K)$ (the two's complement of $K$ over $w$ bits; equivalently, one can use $2^w - K$), and perform the secure addition $\text{SecAdd}((x_i)_{0 \le i \le d}, (k_i)_{0 \le i \le d})$, given in Algorithm 9 (where Refresh denotes the $d$-SNI multiplication-based refresh as proven in [5] and recalled in Algorithm 8). The result is a $(d+1)$-Boolean sharing $(\delta_i)_{0 \le i \le d}$ of the difference $\delta = x - K$ in two's complement form. In particular, the most significant bit $b$ of $\delta$ is 0 if and only if $x \ge K$. Since computing the most significant bit is an $\mathbb{F}_2$-linear operation, we can carry it out component-wise to obtain a $(d+1)$-Boolean sharing $(b_i)_{0 \le i \le d}$ of $b$ with $b_i = \delta_i \gg (w-1)$. The resulting most significant bit $b$ is non-sensitive because it actually corresponds to the number of iterations of the signature algorithm. And this number is statistically independent of any private data by design of the scheme (See [38]). So we can unmask it to check whether to carry out the rejection sampling.

After carrying out these steps, we have obtained a Boolean sharing of a uniformly random integer in $[0, 2k]$. What we want is a *mod-$p$ arithmetic* sharing of a uniformly random integer in the interval $[-k, k]$, which is of the same length as $[0, 2k]$. If we can convert the Boolean sharing to an arithmetic sharing, it then suffices to subtract $k$ from one of the shares and we obtain the desired result. To carry out the Boolean-to-arithmetic conversion itself, we essentially follow the approach of [22, §5], with a few changes to account for the fact that $p$ is not a power of two.

The main change is that we need an algorithm for the secure addition modulo $p$ of two $(d+1)$-Boolean shareings of $y$ and $z$, namely $(y_i)_{0 \le i \le d}$, $(z_i)_{0 \le i \le d}$ (assuming that $y, z \in [0, p)$). Such an algorithm $\text{SecAddModp}$ is easy to construct from $\text{SecAdd}$ (see Algorithm 10 with $\text{SecAnd}$ the $d$-SNI bitwise AND operation from [36,45] and recalled in Algorithm 11) and the com-
<caption>**Algorithm 10: Mod-p addition of Boolean shareings (SecAddModp)**</caption>

**Data:** $(d+1)$-Boolean shareings $(x_i)_{0 \le i \le d}$, $(y_i)_{0 \le i \le d}$ of integers $x, y$; the bit size $w$ of the masks (with $2^w > 2p$)

**Result:** A $(d+1)$-Boolean sharing $(z_i)_{0 \le i \le d}$ of $x + y \bmod p$

1. $(p_i)_{0 \le i \le d} \leftarrow (2^w - p, 0, \dots, 0)$
2. $(s_i)_{0 \le i \le d} \leftarrow \text{SecAdd}((x_i)_{0 \le i \le d}, (y_i)_{0 \le i \le d}, w)$
3. $(s'_i)_{0 \le i \le d} \leftarrow \text{SecAdd}((s_i)_{0 \le i \le d}, (p_i)_{0 \le i \le d}, w)$
4. $(b_i)_{0 \le i \le d} \leftarrow (s'_i \gg (w-1))_{0 \le i \le d}$
5. $(c_i)_{0 \le i \le d} \leftarrow \text{Refresh}((b_i)_{0 \le i \le d}, w)$
6. $(z_i)_{0 \le i \le d} \leftarrow \text{SecAnd}((s_i)_{0 \le i \le d}, (\tilde{c}_i)_{0 \le i \le d}, w)$
7. $(c_i)_{0 \le i \le d} \leftarrow \text{Refresh}((b_i)_{0 \le i \le d}, w)$
8. $(z_i)_{0 \le i \le d} \leftarrow (z_i)_{0 \le i \le d} \oplus \text{SecAnd}((s'_i)_{0 \le i \le d}, (\neg \tilde{c}_i)_{0 \le i \le d}, w)$
9. **return** $(z_i)_{0 \le i \le d}$

parison trick described earlier. More precisely, the approach is to first compute $(s_i)_{0 \le i \le d} = \text{SecAdd}((y_i)_{0 \le i \le d}, (z_i)_{0 \le i \le d})$, which is a Boolean sharing of the sum $s = y + z$ without modular reduction, and then $(s'_i)_{0 \le i \le d} = \text{SecAdd}((s_i)_{0 \le i \le d}, (p_i)_{0 \le i \le d})$ for a Boolean sharing $(p_i)_{0 \le i \le d}$ of the value $-p$ in two's complement form (or equivalently $2^w - p$). The result is a sharing of $s' = s - p$ in two's complement form. In particular, we have $s \ge p$ if and only if the most significant bit $b$ of $s'$ is 0. Denote by $r$ the desired modular addition $y + z \bmod p$. We thus have:

$$r = \begin{cases} s & \text{if } b = 1; \\ s' & \text{if } b = 0. \end{cases}$$

As a result, we can obtain the sharing of $r$ in a secure way as:

$$(r_i)_{0 \le i \le d} = \text{SecAnd}((s_i)_{0 \le i \le d}, (\tilde{b}_i)_{0 \le i \le d}) \oplus \text{SecAnd}((s'_i)_{0 \le i \le d}, (\neg \tilde{b}_i)_{0 \le i \le d}),$$

where we denote by $\tilde{b}$ the extension of the bit $b$ to the entire $w$-bit register (this is again an $\mathbb{F}_2$-linear operation that can be computed component-wise). This concludes the description of **SecAddModp**.

Using **SecAddModp** instead of **SecAdd** in the algorithms of [22, §4], we also immediately obtain an algorithm **SecArithBoolModp** for converting a mod-$p$ arithmetic sharing $a = \sum_{i=0}^{d} a_i \bmod p$ of a value $a \in [0, p)$ into a Boolean sharing $a = \bigoplus_{i=0}^{d} a'_i$ of the same value. The naive way of doing so (see Algorithm 12), which is the counterpart of [22, §4.1], is to simply construct a Boolean sharing of each of the shares $a_i$, and to iteratively apply **SecAddModp** to those masked values. This is simple and secure, but as noted by Coron et al., this approach has cubic complexity in the masking order $d$ (because **SecAdd** and hence **SecAddModp** are quadratic). A more advanced, recursive approach allows to obtain quadratic complexity for the whole conversion: this is described in [22, §4.2], and directly applies to our setting.

With both algorithms **SecAddModp** and **SecArithBoolModp** in hand, we can easily complete the description of our commitment generation algorithm by mimicking [22, Algorithm 6]. To convert the Boolean sharing $(x_i)_{0 \le i \le d}$ of $x$ to a mod-$p$ arithmetic sharing, we first generate random integer shares $a_i \in [0, p)$, $1 \le i \le d$, uniformly at random. We then define $a'_i = -a_i \bmod p = p - a_i$ for $1 \le i \le d$ and $a'_0 = 0$. The tuple $(a'_i)_{0 \le i \le d}$ is thus a mod-$p$
**Algorithm 11:** Bitwise AND of Boolean shareings (SecAnd) from [36,45]

**Data:** $(d+1)$-Boolean shareings $(x_i)_{0 \le i \le d}$, $(y_i)_{0 \le i \le d}$ of integers $x, y$; the bit size $w$ of the masks

**Result:** A $(d+1)$-Boolean sharing $(r_i)_{0 \le i \le d}$ of $x \land y$

$$1 \quad (r_i)_{0 \le i \le d} \leftarrow (x_i \land y_i)_{0 \le i \le d}$$

$$2 \quad \textbf{for } i = 0 \text{ to } d \textbf{ do}$$

$$3 \quad \quad \quad \quad \quad \quad \quad \quad \quad \textbf{for } j = i + 1 \text{ to } d \textbf{ do}$$

$4 \quad \quad \quad \quad \quad \quad \quad \quad \quad \text{pick a uniformly random } w\text{-bit value } z_{ij}$

$5 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad z_{ji} \leftarrow (x_i \land y_j) \oplus z_{ij}$

$6 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad z_{ji} \leftarrow z_{ji} \oplus (x_j \land y_i)$

$7 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad r_i \leftarrow r_i \oplus z_{ij}$

$8 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad r_j \leftarrow r_j \oplus z_{ji}$

$9 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \textbf{end}$

$10 \quad \textbf{end}$

$11 \quad \textbf{return } (r_i)_{0 \le i \le d}$

**Algorithm 12:** Secure conversion from mod-$p$ arithmetic sharing to Boolean sharing (SecArithBoolModp); this is the simple version (cubic in the masking order)

**Data:** $(d+1)$-Arithmetic sharing $(a_i)_{0 \le i \le d}$ modulo $p$ of an integer $a$; the bit size $w$ of the returned masks (with $2^w > 2p$)

**Result:** A $(d+1)$-Boolean sharing $(a'_i)_{0 \le i \le d}$ of $a$

$$1 \quad (a'_i)_{0 \le i \le d} \leftarrow (0, \dots, 0)$$

$$2 \quad \textbf{for } j = 0 \text{ to } d \textbf{ do}$$

$3 \quad \quad \quad \quad \quad \quad \quad \quad \quad \text{(}b_i)_{0 \le i \le d} \leftarrow \text{(}a_j, 0, \dots, 0\text{)}$

$4 \quad \quad \quad \quad \quad \quad \quad \quad \quad \text{(}b_i)_{0 \le i \le d} \leftarrow \text{Refresh}((b_i)_{0 \le i \le d}, w)$

$5 \quad \quad \quad \quad \quad \quad \quad \quad \quad \text{(}a'_i)_{0 \le i \le d} \leftarrow \text{SecAddModp}((a'_i)_{0 \le i \le d}, (b_i)_{0 \le i \le d}, w)$

$6 \quad \textbf{end}$

$7 \quad \textbf{return } (a'_i)_{0 \le i \le d}$

arithmetic sharing of the sum $a' = - \sum_{1 \le i \le d} a_i \mod p$. Using SecArithBoolModp, we convert this arithmetic sharing to a Boolean sharing $(y_i)_{0 \le i \le d}$, so that $\bigoplus_{i=0}^d y_i = a'$. Now, let $(z_i)_{0 \le i \le d} = \text{SecAddModp}((x_i)_{0 \le i \le d}, (y_i)_{0 \le i \le d})$; this is a Boolean sharing of:

$$z = (x + a') \mod p = \left( x - \sum_{i=1}^{d} a_i \right) \mod p.$$

We then securely unmask this value using Coron et al.'s FullXor procedure, recalled in Algorithms 13 and 14, and set $a_0 = z - k \mod p$. Then, we have:

$$\sum_{i=0}^{d} a_i \mod p = z - k + \sum_{i=1}^{d} a_i \mod p = x - k - \sum_{i=1}^{d} a_i + \sum_{i=1}^{d} a_i \mod p = x - k \mod p.$$

Thus, $(a_i)_{0 \le i \le d}$ is a correct mod-$p$ arithmetic sharing of a uniformly random value in $[-k, k]$ as required. The whole procedure is summarized in Algorithm 15 and described in Figure 5
**Algorithm 13:** Refresh-and-unmask algorithm for Boolean masking (FullXor) from [22]

**Data:** A $(d+1)$-Boolean sharing $(x_i)_{0 \le i \le d}$ of some value $x$; the bit size $w$ of the masks

**Result:** The value $x$

1. $(x'_i)_{0 \le i \le d} \leftarrow \text{FullRefresh}((x_i)_{0 \le i \le d}, w)$

2. $x \leftarrow x'_0$

3. **for** $i = 1$ **to** $d$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow x \oplus x'_i$

5. **end**

6. **return** $x$

**Algorithm 14:** Stronger Refresh algorithm for Boolean masking (FullRefresh) from [17, Algorithm 4]

**Data:** A $(d+1)$-Boolean sharing $(x_i)_{0 \le i \le d}$ of some value $x$; the bit size $w$ of the returned masks

**Result:** An independent $(d+1)$-Boolean sharing $(x'_i)_{0 \le i \le d}$ of $x$

1. $(x'_i)_{0 \le i \le d} \leftarrow (x_i)_{0 \le i \le d}$

2. **for** $i = 0$ **to** $d$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp; **for** $j = 1$ **to** $d$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pick a uniformly random $w$-bit value $r$

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x'_0 \leftarrow x'_0 \oplus r$

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x'_j \leftarrow x'_j \oplus r$

7. **end**

8. **end**

9. **return** $(x'_i)_{0 \le i \le d}$

where $xGen$ stands for the generation of $x^0$'s shares, $\text{Refresh}$ for the multiplication-based refreshing from [36,5], $kGen$ for the generation of $k$'s shares, $\gg$ for the right shift of $\delta$'s shares, $\text{FullX}$ for $\text{FullXor}$, $\text{aGen}$ for the generation of $a$'s shares, $\text{SecABM}$ for $\text{SecArithBoolModp}$, and $\text{SecAMp}$ for $\text{SecAddModp}$.

The success probability of the rejection sampling step (the masked comparison to $K$) is $K/2^{w_0}$, and hence is at least $1/2$ by definition of $w_0$. Therefore, the expected number of runs required to complete is at most 2 (and in fact, a judicious choice of $k$, such as one less than a power of two, can make the success probability very close to 1). Since all the algorithms we rely on are at most in the masking order and (when using the masked Kogge-Stone adder of [21]) logarithmic in the size $w$ of the Boolean shares, the overall complexity is thus $O(d^2 \log w)$.

Now that the randomness generation is described, each intermediate gadget will be proven either $d$-NI or $d$-NIo. Then, the global composition is proven $d$-NI as well.

**Lemma 2.** *Gadget SecAdd is $d$-NI.*

*Proof.* Gadget **SecAdd** is built from the Kogge-Stone adder of [21] with secure AND and secure linear functions such as exponentiations and Boolean additions. As to ensure its security with the combination of these atomic masked functions, the tool **maskComp** was used to properly insert
<figure><img src="image_6.png" /><figcaption>**Fig. 5. Randomness Generation RG (The green (resp. white, red) gadgets will be proved d-SNI (resp. d-NI, unmasked))**</figcaption></figure>

**Algorithm 15: Randomness generation (RG)**

**Data:** $k$ and $d$

**Result:** A uniformly random $a$ integer in $[-k, k]$ in mod-$p$ arithmetic masked form
$(a_i)_{0 \le i \le d}$.

1. generate uniformly random $w_0$-bit values $(x_i^0)_{0 \le i \le d}$

2. $(x_i)_{0 \le i \le d} \leftarrow \text{Refresh}((x_i^0)_{0 \le i \le d})$

3. initialize $(k_i)_{0 \le i \le d}$ to a $w$-bit Boolean sharing of the two's complement value
$-K = -2k - 1$

4. $(\delta_i)_{0 \le i \le d} \leftarrow \text{SecAdd}((x_i)_{0 \le i \le d}, (k_i)_{0 \le i \le d})$

5. $(b_i)_{0 \le i \le d} \leftarrow (\delta_i)_{0 \le i \le d} \gg (w - 1)$

6. $b \leftarrow \text{FullXor}((b_i)_{0 \le i \le d})$

7. output $b$

8. **if** $b = 0$ **then**

9. **|** **restart**

10. **end**

11. generate uniform integers $(a_i)_{1 \le i \le d}$ in $[0, p)$

12. $a'_i \leftarrow -a_i \bmod p$ for $i = 1, \dots, d$

13. $a'_0 \leftarrow 0$

14. $(y_i)_{0 \le i \le d} \leftarrow \text{SecArithBoolModp}((a'_i)_{0 \le i \le d})$

15. $(z_i)_{0 \le i \le d} \leftarrow \text{SecAddModp}((x_i)_{0 \le i \le d}, (y_i)_{0 \le i \le d})$

16. $a_0 \leftarrow \text{FullXor}((z_i)_{0 \le i \le d})$

17. **return** $(a_i - k_i)_{0 \le i \le d}$
<figure><img src="image_7.png" /><figcaption>**Fig. 6.** Graphical Representation of **SecArithBoolModp** (The green (resp. white) gadgets will be proved d-SNI (resp. d-NI))</figcaption></figure>

the mandatory *d*-SNI refresh gadgets, denoted as **Refresh** in Algorithm 9. As deeply explained in its original paper, **maskComp** provides a formally proven *d*-NI implementation. □

**Lemma 3.** *Gadget SecAddModp is d-NI.*

*Proof.* Gadget **SecAddModp** is built from the gadget **SecAdd** and **SecAnd** and linear operations (like $⊕$). We use the tool **maskComp** to generate automatically a verified implementation. Note that the tool automatically adds the two refresh gadgets (line 5 and 7) and provides a formally proven *d*-NI implementation. □

**Lemma 4.** *Gadget SecArithBoolModp is d-SNI.*

*Proof.* A graphical representation of **SecArithBoolModp** is in Figure 6. Let $O$ be a set of observations performed by the attacker on the final returned value, let $I_{A_j}$ be the set of internal observations made in step $j$ in the gadget **SecAddModp** (line 5), and $I_{R_j}$ be the set of internal observations made in the step $j$ in the initialization of $b$ (line 3) or in the **Refresh** (line 4). Assuming that $|O| + \sum(|I_{A_j}| + |I_{R_j}|) \le d$, the gadget is *d*-SNI, if we can build a simulator allowing to simulate all the internal and output observations made by the attacker using a set $S$ of shares of $a$ such that $|S| \le \sum(|I_{A_j}| + |I_{R_j}|)$.

At the last iteration (see figure 7), the set of observations $O \cup I_{A_d}$ can be simulated using a set $S_{a'_{d-1}}$ of shares of $a'$ and $S_{b_{d-1}}$ of shares of $b$ with $|S_{a'_{d-1}}| \le |O| + |I_{A_d}|$ and $|S_{b_{d-1}}| \le |O| + |I_{A_d}|$ (because the gadget **SecAddModp** is *d*-NI). Since the **Refresh** is *d*-SNI, the sets $S_{b_{d-1}}$ and $I_{R_d}$
can be simulated using a set $S_{b'_{d-1}}$ of input share with $|S_{b'_{d-1}}| \le |I_{R_d}|$. If $I_{R_d}$ is not empty, then $S_{b'_{d-1}}$ may contain $a_d$, so we add $a_d$ to $S$. For each iteration of the loop this process can be repeated. At the very first iteration, several shares of $a'$ may be necessary to simulate the set of observations. However, there are all initialized to 0, nothing is added to $S$.

<figure><img src="image_8.png" /><figcaption>**Fig. 7.** Last step of **SecArithBoolModp** with probes (The green (resp. white) gadgets will be proved d-SNI (resp. d-NI))**</figcaption></figure>

At the end we can conclude that the full algorithm can be simulated using the set $S$ of input shares. Furthermore we have $|S| \le \sum |I_{R_j}|$ (since $a_j$ is added in $S$ only if $I_{R_j}$ is not empty), so we can conclude that $|S| \le \sum |I_{A_j}| + |I_{R_j}|$ which concludes the proof. $\square$

**Lemma 5.** *Gadget RG is d-NIo with public output b.*

*Proof.* Here we need to ensure that the returned shares of $a$ cannot be revealed to the attacker through a $d$-order side-channel attack. Since $xGen$ and $aGen$ are just random generation of shares, the idea is to prove that any set of $t \le d$ observations on RG including these inputs can be perfectly simulated with at most $t$ shares of $x$ and $t$ shares of $a$.

Gadget RG is built with no cycle. In this case, from the composition results of [5], it is enough to prove that each sub-gadget is $d$-NI to achieve global security. In our case, it is enough to prove that each sub-gadget is $d$-NIo with the knowledge of $b$ to achieve global security.

From Lemmas 2, 4, and 3, **SecAdd**, **SecArithBoolModp**, and **SecAddModp** are $d$-NI. $\gg$ is trivially $d$-NI as well since it applies a linear function, **FullRefresh** is $d$-SNI thus $d$-NI by definition, and **kGen** is generating shares of a non sensitive value.

At this point, both gadgets **FullXor** have to be analyzed to achieve the expected overall security. We start with the gadget computing $b$. After its execution, $b$ is broadcasted. Since $b$ have to be public, its knowledge does not impact the security but because of this output, the security of RG will be $d$-NIo with public output $b$ and not $d$-NI. **FullXor** is composed of a $d$-SNI refresh gadget (made of $d+1$ linear refreshing) of the shares and of a Boolean addition of these resulting shares. The attacker is not able to observe intermediate variable of all the linear refreshings (since he only has $\delta \le d$ available observations), thus we consider that the $i^{th}$ refreshing is left unobserved. As a consequence, all the previous observations involve only one $b$'s share and all the following observations are independent from $b$'s share except for their sum. That is, **FullXor** is $d$-NI. As for its second instance to compute $a_0$, **FullXor** is still $d$-NI but $a_0$ is not revealed after its execution. While the attacker is able to observe its value, it is not returned for free. All the $\delta_0 \le d$ observations made by the attacker of this last instance of **FullXor** can be perfectly simulated with $a_0$ (for the observations performed after the unobserved linear refreshing) and at most $\delta_0 - 1$ shares of $z$ (for the observations made before the unobserved linear refreshing). $\square$
<table><caption>**Algorithm 16: Rejection sampling (RS)**</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>6</td><td>(a'<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecArithBoolModp((a<sup>(j)</sup><sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>7</td><td>(&delta;<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecAdd((a'<sub>i</sub>)<sub>0&le;i&le;d</sub>, (p'<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>8</td><td>(b<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; (&delta;<sub>i</sub>)<sub>0&le;i&le;d</sub> &gg; (w &minus; 1)</td></tr><tr><td>9</td><td>(s<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecAdd((a'<sub>i</sub>)<sub>0&le;i&le;d</sub>, (p<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>10</td><td>(c<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; Refresh((b<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>11</td><td>(a'<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecAnd((a'<sub>i</sub>)<sub>0&le;i&le;d</sub>, (&tilde;c<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>12</td><td>(c<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; Refresh((b<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>13</td><td>(a'<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; (a'<sub>i</sub>)<sub>0&le;i&le;d</sub> &oplus; SecAnd((s<sub>i</sub>)<sub>0&le;i&le;d</sub>, &not;(&tilde;c<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>14</td><td>(&delta;<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecAdd((a'<sub>i</sub>)<sub>0&le;i&le;d</sub>, (k'<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>15</td><td>(b<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; (&delta;<sub>i</sub>)<sub>0&le;i&le;d</sub> &gg; (w &minus; 1)</td></tr><tr><td>16</td><td>(r<sub>i</sub>)<sub>0&le;i&le;d</sub> &larr; SecAnd((r<sub>i</sub>)<sub>0&le;i&le;d</sub>, &not; (b<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>17</td><td>end</td></tr><tr><td>18</td><td>r &larr; FullXor((r<sub>i</sub>)<sub>0&le;i&le;d</sub>)</td></tr><tr><td>19</td><td>return r</td></tr></tbody></table>

**Remark 6.** The knowledge of $b$ (ie. the success of the randomness generation) is not sensitive and we decided to consider it as a public output. To simplify the notation when we report the security on the whole scheme, we will omit $b$ in the public outputs.

**Lemma 6.** *Gadget DG is d-NIo with public output b.*

*Proof.* From Lemma 5, Gadget DG is d-NIo since it only consists in the linear application of Gadget RG to build the polynomial coefficients. □

**Rejection sampling (RS).** Right before the rejection sampling step of the masked signing algorithm, the candidate signature polynomials $z_1$ and $z_2$ have been obtained as sums of $d+1$ shares modulo $p$, and we want to check whether the coefficients in $\mathbb{Z}/p\mathbb{Z}$ represented by those shares are all in the interval $[-k+\alpha, k-\alpha]$. Again, carrying out this check using mod-$p$ arithmetic masking seems difficult, so we again resort to Boolean masking.

For each coefficient $z_{i,j}$ of $z_1$ and $z_2$, one can trivially obtain a mod-$p$ arithmetic masked representation of both $z_{i,j}$ and $-z_{i,j}$, and the goal is to check whether those values, when unmasked modulo $p$ in the interval $[(-p+1)/2, (p-1)/2]$, are all greater than $-k+\alpha$.

Let $a$ be one of those values, and $a = a_0 + \cdots + a_d \mod p$ its masked representation. Using SecArithBoolModp as above, we can convert this mod-$p$ arithmetic sharing to a $w$-bit Boolean
sharing $(a'_i)_{0 \le i \le d}$. From this sharing, we first want to obtain a sharing of the centered representative of $a \bmod p$, i.e. the value $a''$ such that:

$$a'' = \begin{cases} a & \text{if } a \le (p-1)/2, \\ a-p & \text{otherwise.} \end{cases}$$

This can be done using a similar approach as the one taken for randomness generation: compute a $(d+1)$-Boolean sharing $(b_i)_{0 \le i \le d}$ of the most significant bit $a - (p+1)/2$ (which is 1 in the first case and 0 in the second case), and a $(d+1)$-Boolean sharing $(s_i)_{0 \le i \le d}$ of the sum $a-p$. Then, a $(d+1)$-Boolean sharing of $(a''_i)_{0 \le i \le d}$ is obtained as:

$$(a''_i)_{0 \le i \le d} = \text{SecAnd}((a'_i)_{0 \le i \le d}, (\tilde{b}_i)_{0 \le i \le d}) \oplus \text{SecAnd}((s_i)_{0 \le i \le d}, \neg(\tilde{b}_i)_{0 \le i \le d}).$$

Finally, once this $(d+1)$-Boolean sharing is obtained, it suffices to add $k-\omega$ to it and check the most significant bit to obtain the desired test.

We cannot directly unmask that final bit, but we can compute it in masked form for all the $4n$ values to be tested, and apply SecAnd iteratively on all of these values to compute a Boolean masked representation of the bit equal to 1 if all the coefficients are in the required intervals, and 0 otherwise. This bit can be safely unmasked, and is the output of our procedure. The whole algorithm is summarized as Algorithm 16.

Since both SecArithBoolModp and SecAnd have quadratic complexity in the masking order (and SecArithBoolModp has logarithmic complexity in the size $w$ of the Boolean shares), the overall complexity of this algorithm is $O(n^2 \log w)$.

**Lemma 7.** *Gadget RS is d-NI.*

*Proof.* From Lemmas 2 and 4, Gadgets SecArithBoolModp and SecAdd are d-NI. Gadget SecAnd is d-SNI from [45,5] and $\gg$ is linear, thus trivially d-NI as well.

As done for Gadget SecAdd, the tool maskComp was called to generate a d-NI circuit from the initial sequence of gadgets. It inserted Gadgets Refresh (as shown in Algorithm 16) at specific locations so that the overall circuit is formally proven to be d-NI. □

**Refresh and Unmask (FullAdd).** This part provides a computation of the sensitive value as the sum of all its shares. It is a gadget with public output because the final value is returned and also output. This output is useful when FullAdd is used to recombine the intermediate value $r$.

Before summing, the sharing is given as input for FullRefresh [17, Algorithm 4], which is made of a succession of $d+1$ linear refresh operations. Those linear refreshing steps modify the sharing by adding random elements to each share while keeping constant the value of the sum. Their number is strictly superior to $d$ which is useful to consider that any share or strictly partial sum of shares at the output of the final linear refreshing is independent from the original sharing. Then, the following partial sums do not give any information about the original sharing which is dependent of the sensitive values. The whole algorithm, given in Algorithm 17 has a quadratic complexity in $d$.

**Lemma 8.** *Gadget FullAdd is d-NI with public output $r$.*

*Proof.* Let $\delta \le d$ be the number of observations made by the attacker. We use a combination of $d+1$ linear refresh operations. That is, there is at least one of the linear refreshing (we call it the
**Algorithm 17: FullAdd**

Data: $(\mathbf{r}_i)_{0 \le i \le d}$

Result: $\mathbf{r}$

1 if $(\mathbf{r}_i)_{0 \le i \le d} = \perp$ then

2 $\mid \mathbf{r}$ return $\perp$

3 end

4 $(\mathbf{r}_i)_{0 \le i \le d} \leftarrow \text{FullRefresh}((\mathbf{r}_i)_{0 \le i \le d})$

5 $\mathbf{r} \leftarrow (\mathbf{r}_0 + \dots + \mathbf{r}_d)$

6 return $\mathbf{r}$ considered as a public output

**Algorithm 18: H¹**

Data: $\mathbf{a}, (\mathbf{y}_{1,i})_{0 \le i \le d}$

1 for $0 \le i \le d$ do

2 $\mid \mathbf{r}_i \leftarrow \mathbf{a}\mathbf{y}_{1,i} + \mathbf{y}_{2,i}$

3 end

4 return $(\mathbf{r}_i)_{0 \le i \le d}$

**Algorithm 19: H²**

Data: $\mathbf{r}_s, (\mathbf{z}_{1,i})_{0 \le i \le d}$

1 if $\mathbf{r}_s = 0$ then

2 $\mid (\mathbf{z}_{1,i})_{0 \le i \le d} \leftarrow \perp$

3 end

4 return $(\mathbf{z}_{1,i})_{0 \le i \le d}$

$i^{th}$ refreshing) which is not observed by the attacker. For all the $\delta_1 \le \delta$ observations preceding the $i^{th}$ refreshing in FullAdd, they can be perfectly simulated with at most $\delta_1$ shares of $\mathbf{r}$ since each one of them involves at most one $\mathbf{r}_i$. As for the observations performed after the $i^{th}$ refreshing, each one of them is independent from the $\mathbf{r}_i$ inside the refresh mask and each intermediate sum of the unmask part is independent of the $\mathbf{r}_i$ as well with the knowledge of $\mathbf{r}$. Then, during the sum computation, all the $\mathbf{r}_i$ can be simulated with fresh random that sum to $\mathbf{r}$ (the public output). Thus, at most $\delta$ shares of $\mathbf{r}$ and $\mathbf{r}$ itself are enough to simulate further probes. □

*Remark 7.* When FullAdd is used at the very end of the whole algorithm (mKD or mSign), the public outputs are also among the returned values. Then, in those cases, it can be considered as d-NI.

**Transition parts.** The elementary parts $H^1$ and $H^2$ are quite easy to build since they perform only linear operations on the input data. A masked implementation only performs these linear operations on each share to securely compute the returned shares. $H^1$ and $H^2$ are described in Algorithms 18 and 19.

**Lemma 9. Gadgets $H^2$ and $H^1$ are d-NI.**

*Proof.* The straightforward proofs follow.

- d-NI security of $H^1$. Let $\delta \le d$ be the number of observations made by the attacker. The only possible observations are the sensitive values $\mathbf{y}_{1,i}, \mathbf{y}_{2,i}$ and $\mathbf{a}\mathbf{y}_{1,i} + \mathbf{y}_{2,i}$. The proof consists in filling an empty set $\mathbf{I}$ with at most $\delta$ indices in $[0, d]$ such that the distribution of any tuple $(\mathbf{v}_1, \dots, \mathbf{v}_\delta)$ of intermediate variables of the block can be perfectly simulated from the sensitive values. We build the set $\mathbf{I}$ with the index $i$ of each intermediate values in $(\mathbf{v}_1, \dots, \mathbf{v}_\delta)$. After building it, we simulate each one of them with the corresponding share of the inputs. At the end, any set of $\delta \le d$ intermediate variables can be perfectly simulated with at most $\delta$
shares of each sensitive input. This is enough to prove that $H^1$ is $d$-NI.

- $d$-NI security of $H^2$. The proof is very similar to the previous one. Let $\delta \le d$ be the number of observations made by the attacker. The only possible observations are the sensitive values $z_{1,i}$ or on the intermediate value $rs$. So, to simulate $z_{1,i}$ we use the corresponding share of the input. And since $rs$ is a bit showing if the rejection sampling failed, it is public information. $\square$

**Hash function.** The hash function does not manipulate any sensitive data. Thus, it is left unmasked as its inputs are considered accessible by any attacker though public outputs.

## 4.3 Proofs of composition

**Theorem 2.** *The masked GLP sign in Algorithm 5 is $d$-NIo with public output $\{r, b\}$.*

*Proof.* From Lemmas 6,7 and 9, Algorithms DG, RS, $H^1$, and $H^2$ are all $d$-NI. From Lemma 8, FullAdd is $d$-NIo.

Let us assume that an attacker has access to $\delta \le d$ observations on the whole signature scheme. Then, we want to prove that all these $\delta$ observations can be perfectly simulated with at most $\delta$ shares of each secret among $y_1, y_2, s_1$ and $s_2$ and the public variables. With such a result, the signature scheme is then secure in the $d$-probing model since no set of at most $d$ observations would give information on the secret values.

In the following, we consider the following distribution of the attacker's $\delta$ observations: $\delta_1$ (resp. $\delta_2$) on the instance of DG that produces shares of $y_1$ (resp. $\tilde{y}_2$), $\delta_3$ on $H^1$, $\delta_4$ on FullAdd of $\mathbf{r}$, $\delta_5$ (resp. $\delta_6$) on $H^1$ which produces $z_1$ (resp. $z_2$), $\delta_7$ on the instance of RS, $\delta_8$ (resp. $\delta_9$) on $H^2$ applied on $z_1$ (resp. $z_2$), and $\delta_{10}$ (resp. $\delta_{11}$) on FullAdd of $z_1$ (resp. $z_2$). Some other observations can be made on the Hash function, their number won't matter during the proof. Finally, we have $\sum_{i=1}^{11} \delta_i \le \sum_{i=1}^{11} + \delta_{Hash} \le \delta$.

Now, we build the proof from right to left as follows.

Both last FullAdd blocks in the very end of mSign are $d$-NI, then all the observations performed during the execution of FullAdd on $z_1$ (resp. $z_2$) can be perfectly simulated with at most $\delta_{10}$ (resp. $\delta_{11}$) shares of $z_1$ (resp. $z_2$).

$H^2$ is $d$-NI, then all the observations from the call of $H^2$ on $z_1$ (resp. $z_2$) can be perfectly simulated with $\delta_8 + \delta_{10}$ (resp. $\delta_9 + \delta_{11}$) shares of the sensitive input $z_1$ (resp. $z_2$). The inputs $z_1$ and $z_2$ do not come from RS which do not act on them. They are directly taken from the returned values of $H^1$.

RS is $d$-NI and do not return any sensitive element, then all the observations performed in gadget RS can be perfectly simulated with at most $\delta_7$ shares of $z_1$ and $z_2$. So, after $H^1$, the observations can be simulated with $\delta_7 + (\delta_8 + \delta_{10})$ shares of $z_1$ and $\delta_7 + (\delta_9 + \delta_{11})$ shares of $z_2$.

$H^1$ is $d$-NI as well, thus all the observations from the call of $H^1$ on $y_1$ can be perfectly simulated with $\delta_5 + \delta_7 + \delta_8 + \delta_{10} \le \delta$ shares of $y_1$ and $s_1$. Respectively, on $y_2$, the observations can be perfectly simulated from $\delta_6 + \delta_7 + \delta_9 + \delta_{11} \le \delta$ shares of $y_2$ and $s_2$.

The left FullAdd gadget is $d$-NIo and do not return any sensitive element, then all the observations performed in this gadget can be perfectly simulated with at most $\delta_4$ shares of $\mathbf{r}$.

The left $H^1$ gadget is $d$-NI, thus all the observations from its call can be perfectly simulated with at most $\delta_3 + \delta_4$ shares of each one of the inputs $y_1$ and $y_2$.
DG is also d-NI, thus we need to ensure that the number of reported observations does not exceed $\delta$. At the end of DG, the simulation relies on $(\delta_3 + \delta_4) + (\delta_5 + \delta_7 + \delta_8 + \delta_{10}) \le \delta$ shares of $\mathbf{y}_1$ and $(\delta_3 + \delta_4) + (\delta_6 + \delta_7 + \delta_9 + \delta_{11}) \le \delta$ shares of $\mathbf{y}_2$. With the additional $\delta_1$ (resp. $\delta_2$) observations performed on the first (resp. the second) instance of DG, the number of observations remains below $\delta$ which is sufficient to ensure security of the whole scheme in the d-probing model.

□

**Theorem 3.** *The masked GLP key derivation in algorithm 6 is d-NIo with public output b.*

*Proof.* From Lemmas 6 and 9, Algorithms DG, H¹ are all d-NI. From Lemma 8, FullAdd is d-NIo.

Here too, let us assume that an attacker has access to $\delta \le d$ observations on the whole signature scheme. Then, we want to prove that all these $\delta$ observations can be perfectly simulated with at most $\delta$ shares of each secret among $s_1$ and $s_2$.

We now consider the following distribution of the attacker's $\delta$ observations: $\delta_1$ (resp. $\delta_2$) on the instance of DG that produces shares of $s_1$ (resp. $s_2$), $\delta_3$ on H¹, and $\delta_4$ on FullAdd, such that $\sum_{i=1}^4 \delta_i = \delta$.

Now, we build the proof from right to left: FullAdd is used at the very end of mKD, so it is d-NI. Thus, all the observations from the call of FullAdd can be perfectly simulated with $\delta_4 \le \delta$ sensitive shares of the input t.

$H^1$ is d-NI, thus all the observations from its call can be perfectly simulated with at most $\delta_3 + \delta_4 \le \delta$ shares of each one of the inputs $s_1$ and $s_2$.

DG is d-NIo, thus we need to ensure that the number of reported observations does not exceed $\delta$. At the end of DG, the simulation relies on $(\delta_3 + \delta_4) \le \delta$ shares of $s_1$ and $s_2$. With the additional $\delta_1$ (resp. $\delta_2$) observations performed on the first (resp. the second) instance of DG, the number of observations on each block remains below $\delta$. All the observations can thus be perfectly simulated with the only knowledge of the outputs, that is, the key derivation algorithm is this d-NIo.

□

## 4.4 EUF-CMA security in the d-probing model

Let UnmaskedRefresh be the unmasked version of a refreshing gadget.

<caption>**Algorithm 20: UnmaskedRefresh**</caption>

**Data:** $(x_i)_{0 \le i \le d}$
**1** **for** $0 \le i \le d-1$ **do**
    **2** &nbsp;&nbsp;&nbsp;&nbsp; $x'_i \leftarrow \$$
    **3** **end**
**4** $x'_d = \sum_{k=0}^{d} x_k - \sum_{k=0}^{d-1} x'_k$
**5** **return** $(x'_i)_{0 \le i \le d}$

**Theorem 4.** *Assuming the hardness of the DCK$_{p,n}$ and R-DCK$_{p,n}$ problems, the signature scheme r-GLP masked at order d with key update algorithm UnmaskedRefresh is EUF-CMA secure in the d-probing model (see Definition 1) and in the random oracle model.*

*Proof.* Let us show the direction of the proof first. Let $\text{Adv}^{d\text{-probing-EUF-CMA}}$ be the advantage of an adversary $\mathcal{A}$ against the d-probing-EUF-CMA security game for r-GLP masked at order d
with key update algorithm **UnmaskedRefresh**. Remark that $b$ is drawn under a publicly known distribution and is independent of the secret. Hence the advantage of an adversary against the EUF-CMA security game for GLP with the extra knowledge of $b, r$ is exactly $\text{Adv}^{\text{EUF-CMA}}$, the advantage of an adversary against the EUF-CMA security game for $\mathbf{r}$-GLP. This advantage is negligible (see Theorem 1) and has been quantified in Theorem 5.

In the following, we will prove that $\text{Adv}^{d\text{-probing-EUF-CMA}} = \text{Adv}^{\text{EUF-CMA}}$ which is sufficient to conclude the proof. Indeed, thanks to Theorem 5, under the hardness of the $\mathbf{DCK}_{p,n}$ and $\mathbf{R-DCK}_{p,n}$, $\text{Adv}^{\text{EUF-CMA}}$ and so $\text{Adv}^{d\text{-probing-EUF-CMA}}$ will be negligible.

In the $d$-probing-EUF-CMA setting, the signature oracle called $S$ is stateful. Let us define this oracle by the following:

$$S(m, \mathcal{O}_{\text{Sign}}) = (\text{Sign}(m, pk, sk^{(i-1)}), \mathcal{L}_{\text{Sign}})$$

where $i \in [1, q]$ is the state, i.e. the index of the query, and $sk^{(i)} = \text{KeyUpdate}^i(sk)$ (with the convention $sk^0 = sk$).

## Leakage Simulators

- According to Theorem 2, the $d$-Nlo security of GLP Sign implies the $d$-NI security of $\mathbf{r}$-GLP Sign. Indeed, in $\mathbf{r}$-GLP Sign, the output values are actual returned values. One subtlety is that the attacker $\mathcal{A}$ is able to make $d$ observations on each call to the signature oracle but not during the key refreshings.

For any set of at most $d$ observations during the $i^{th}$ call to the signature oracle, the $d$-NI security ensures the existence of a perfectly simulated leakage $\mathcal{L}_{\text{Sign}}^{(i),\text{Sim}}$ that is generated from at most $d$ shares of $sk^{(i-1)}$. Because the attacker is not able to get any observation during the **UnmaskedRefresh**, if $i \neq 1$, the $d$ shares of $sk^{(i-1)}$ can be perfectly simulated by replacing the variables with random values. When $i = 1$, the observations are directly simulated with at most $d$ shares of $sk^{(0)} = sk$. In total, the $q$ leakages $(\mathcal{L}_{\text{Sign}}^{(1),\text{Sim}} \cdots \mathcal{L}_{\text{Sign}}^{(q),\text{Sim}})$ are perfectly simulated from at most $d$ shares of $sk$. Thus, they are independent from the unmasked value of the secret.

- Identically, according to Theorem 3, for any set of at most $d$ observations during the key generation, there exists a perfectly simulated leakage $\mathcal{L}_{\text{KeyGen}}^{\text{Sim}}$ that is independent from the unmasked value of the secret.

Here are the hybrid games involved in the security proof.

**Game $G_0$:** This game is the security game of the EUF-CMA security in the $d$-probing model. We refer to figure 2 for details.

**Game $G_1$:** By probing definition of $\mathbf{r}$-GLP, there exists a variant of ExecObs denoted SimExecObs that takes $\mathcal{O}_{\text{alg}}$ as input and several other arguments, and returns the output of the algorithm on those arguments, together with a simulated leakage $\mathcal{L}_{\text{alg}}^{\text{sim}}$ such that the returned leakage is perfectly indistinguishable than an actual leakage $\mathcal{L}_{\text{alg}}$ returned by ExecObs. The game is detailed in Figure 8. By definition of $d$-probing security for Sign and KeyGen, this game is perfectly indistinguishable from $G_0$.
<figure><img src="image_9.png" /><figcaption>Fig. 8. Game $G_1$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9. Game $G_2$: EUF-CMA security.</figcaption></figure>
**Game G₂:** This game is the security game of the EUF-CMA security. The game is detailed in Figure 9. Since in game G₁, |O<sub>KeyGen</sub>| ≤ d and |O<sub>Sign</sub><sup>(i)</sup>| ≤ d for all i ∈ [1, q], having access to L<sup>Sim</sup> provides no advantage to the attacker by d-probing security. Then, the advantage for G₁ is the same as the advantage for G₂.

$$ \text{Finally } \mathrm{Adv}^{d\text{-probing-EUF-CMA}} = \mathrm{Adv}^{\mathrm{EUF-CMA}}. \quad \square $$

# 5 Implementation of the countermeasure

We have carried out a completely unoptimized implementation of our masking countermeasure based on a recent, public domain implementation of the GLP signature scheme called GLYPH<21>YPH [15,16].

The GLYPH<21>YPH scheme actually features a revised set of parameters supposedly achieving a greater level of security (namely, $n = 1024$, $p = 59393$, $k = 16383$ and $\alpha = 16$), as well as a modified technique for signature compression. We do not claim to vouch for those changes, but stress that, for our purposes, they are essentially irrelevant. Indeed, the overhead of our countermeasure only depends on the masking order $d$, the bit size $w$ of Boolean masks (which should be chosen as $w = 32$ both for GLYPH<21>YPH and the original GLP parameters) and the degree $n$ of the ring $\mathcal{R}$ (which is the same in GLYPH<21>YPH as in the high-security GLP parameters). Therefore, our results on GLYPH<21>YPH should carry over to a more straightforward implementation of GLP as well.

Implementation results on a single core of an Intel Core i7-3770 CPU are provided in Table 1. In particular, we see that the overhead of our countermeasure with 2, 3 and 4 shares (secure in the $d$-probing model for $d = 1, 2, 3$ respectively) is around $15 \times, 30 \times$ and $73 \times$. In view of the complete lack of optimizations of this implementation, we believe that these results are quite promising. The memory overhead is linear in the masking order, so quite reasonable in practice (all masked values are simply represented as a vector of shares).

For future work, we mention several ways in which our implementation could be sped up:

- For simplicity, we use a version of **SecArithBoolModp** with cubic complexity in the masking order, as in [22, §4.1]. Adapting the quadratic algorithm of [22, §4.2] should provide a significant speed-up. Moreover, for small values of $d$, Coron's recent algorithm [18] should be considerably faster. However, the technique from [18] unfortunately has an overhead exponential in the masking order, so it is not suitable for our purpose of masking GLP at any order.

- Several of our algorithms call **SecAdd** on two masked values one of which is actually a public constant. One could use a faster **SecAddConst** procedure that only protects the secret operand instead.

<table><caption>**Table 1.** Implementation results. Timings are provided for 100 executions of the signing and verification algorithms, on one core of an Intel Core i7-3770 CPU-based desktop machine.</caption><thead><tr><th>Number of shares ($d + 1$)</th><th>Unprotected</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>Total CPU time (s)</td><td>0.540</td><td>8.15</td><td>16.4</td><td>39.5</td><td>62.1</td><td>111</td></tr><tr><td>Masking overhead</td><td>—</td><td>×15</td><td>×30</td><td>×73</td><td>×115</td><td>×206</td></tr></tbody></table>
- Our algorithms are generic, and do not take advantage of the special shape of $k$ for example. In the case of GLYPH<1>YPH, a comparison to $k = 2^{14} - 1$ could be greatly simplified.

- Many other more technical improvements are also possible: for example, we have made no attempt to reduce the number of unnecessary array copies.

# 6 Conclusion

In this paper, we have described a provably secure masking of the GLP lattice-based signature scheme, as well as a proof-of-concept implementation thereof. The security proof itself involved a number of new techniques in the realm of masking countermeasures. Our method should apply almost identically to other lattice-based Fiat-Shamir type signature schemes using uniform distributions in intervals (as opposed to Gaussian distributions). This includes the Bai-Galbraith signature scheme [3], as well as the recently proposed Dilithium signature [27].

We have mostly ignored the issue of signature compression, which is an important one in all of these constructions, GLP included. However, it is easy to see that compression can be securely applied completely separately from our countermeasure: this is because it only affects already generated signatures (which are non-sensitive) as well as the input to the hash function (which is already unmasked in our technique).

On the other hand, extending our approach to schemes using Gaussian distributions appears to be far from trivial: neither Boolean masking nor arithmetic masking with uniform masks seems particularly well-suited to address the problem. One way to tackle the problem might be to consider masking with non-uniform noise, and only achieving statistically close instead of perfect simulatability. Developing such a framework, however, is certainly a formidable challenge.

Masking hash-and-sign type signatures using GPV lattice trapdoors is probably even harder, as they involve Gaussian sampling not only in $\mathbb{Z}$ but on arbitrary sub-lattices of $\mathbb{Z}^n$, with variable centers. It seems unlikely that a masked GPV signature scheme can achieve a reasonable level of efficiency.

Finally, while we have used the maskComp tool to securely instantiate the masked versions of some of the gadgets we use in our construction, it would be interesting to leverage recent advances in verification [4] and synthesis [5] of masked implementations in a more systematic way in the lattice-based setting. Even for verification, the sheer size of the algorithms involved poses significant challenges in terms of scalability; however, automated tool support would be invaluable for the further development of masking in the postquantum setting.

**Acknowledgements.** We are indebted to Vadim Lyubashevsky for fruitful discussions, and to the reviewers of EUROCRYPT for their useful comments. We acknowledge the support of the French Programme d'Investissement d'Avenir under national project RISQ. This work is also partially supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701), ONR Grant N000141512750 and by the French FUI-AAP25 VeriSiCC project. This research has been partially funded by ANRT under the programs CIFRE N 2016/1583.

# A Security Proof for rGLP and rGLP with commitment

## A.1 Mathematical preliminaries

Let us delay the security proof for a bit to expose useful probabilistic tools we are going to use.
Concentration bounds for inner product of uniform vectors.

**Proposition 1.** Let $u = (u_1, \dots, u_n)^T \in \mathbb{R}^n$ a fixed vector and $x = (x_1, \dots, x_n)^T$ a random uniform vector of $\{-1, 0, 1\}^n$. Then $\langle u, x \rangle$ satisfies

$$ \mathbf{E} [e^{s \langle x, u \rangle}] \le e^{\frac{\|u\|_2^2 s^2}{2}}, $$

for any $s \in \mathbb{R}$

This first concentration inequality is classical in the probability literature and asserts that the scalar product between a random uniform vector and a fixed vector yields a subgaussian variable. For completeness purpose we expose a short proof of this claim.

*Proof.* Let choose $s \in \mathbb{R}$, then we have by linearity and independence:

$$
\begin{align*}
\mathbf{E} [e^{\langle u, x \rangle}] &= \mathbf{E} [e^{\sum_{i=1}^n u_i x_i}] \\
&= \prod_{i=1}^n \mathbf{E} [e^{s x_i u_i}] \qquad \text{(Independence of the } x_i\text{)} \\
&\le \prod_{i=1}^n e^{\frac{s^2 |u_i|^2}{2}} \qquad \text{(Hoeffding Lemma)} \\
&= e^{\frac{\|u\|_2^2 s^2}{2}}.
\end{align*}
$$

□

**Proposition 2.** Let $u = (u_1, \dots, u_n)^T \in \mathbb{R}^n$ a fixed vector and $x = (x_1, \dots, x_n)^T$ a uniformly random vector of $\{-1, 0, 1\}^n$, with Hamming weight at most $\alpha$,

$$ \mathrm{Pr} \left[ \left| \langle u, x \rangle \right| \ge \sqrt{4\alpha/3} \cdot \|u\|_{\infty} \right] \le \frac{1}{2}. $$

This second concentration bound gives a more precise result in the case where the fixed vector is sparse.

*Proof.* Denote by $I$ the support of $x$. By symmetry of the distribution of $x$, $\mathbf{E}(\langle u, x \rangle) = 0$, but by linearity and independence:

$$ \mathbf{E} [\langle u, x \rangle^2] = \sum_{i \neq j \in I} u_i u_j \mathbf{E}[x_i] \mathbf{E}[x_j] + \sum_{i \in I} u_i^2 \mathbf{E}[x_i^2] \le \frac{2\alpha}{3} \|u\|_{\infty}^2. $$

We then conclude by Bienaymé–Tchebychev inequality.

□

**A reduction from a variant of DCK.** In all of the following, for any finite set $S$, we denote generically by $\mathcal{U}(S)$ the uniform distribution over $S$. Let us fix $\gamma$ a positive integer. Let now $u_\gamma$ be the convolution $\mathcal{U}(\{-1, 0, 1\}) \star \mathcal{U}(\{-\gamma, \dots, \gamma\})$, that is the distribution obtained when summing two independent random variables $U$ and $V$, drawn respectively under $\mathcal{U}(\{-1, 0, 1\})$ and $\mathcal{U}(\{-\gamma, \dots, \gamma\})$ We extend this distribution to $\mathcal{R}_\gamma$ by sampling independently the $n$ coefficients from the distribution $u_\gamma$, and call it $\tilde{\mathcal{U}}_\gamma$
**Lemma 10.** The statistical distance between $\tilde{\mathcal{U}}_{\gamma}$ and $\mathcal{U}(\mathcal{R}_{\gamma})$, is bounded by $\frac{n}{2\gamma} + \frac{n}{\gamma^2}$.

*Proof.* Let $U$ and $V$ be two independent random variables, drawn respectively under $\mathcal{U}(\{1 - \gamma, \dots, \gamma - 1\})$ and $\mathcal{U}(\{-1, 0, 1\})$. We then have directly:

$$ \begin{aligned} \Delta(\tilde{\mathcal{U}}_{\gamma}, \mathcal{U}(\mathcal{R}_{\gamma})) &\le n\Delta(\mathcal{U}_{\gamma}, \mathcal{U}(\{-\gamma, \dots, \gamma\})) \\ &\le n \sum_{t \in \{-\gamma, \dots, \gamma\}} \left| \Pr_{U,V} [U + V = t] - (2\gamma + 1)^{-1} \right| \\ &= n \sum_{t \in \{-\gamma, \dots, \gamma\}} \left| \sum_{v \in \{-1, 0, 1\}} \frac{1}{3} \Pr[U = t - v] - (2\gamma + 1)^{-1} \right| \\ &= n \sum_{t \in \{1-\gamma, \dots, \gamma-1\}} \left| \sum_{v \in \{-1, 0, 1\}} \frac{1}{3} \Pr[U = t - v] - (2\gamma + 1)^{-1} \right| \\ &\quad + n \left| \frac{1}{3} \Pr[U = 1 - \gamma] - (2\gamma + 1)^{-1} \right| + n \left| \frac{1}{3} \Pr[U = \gamma - 1] - (2\gamma + 1)^{-1} \right| \\ &= n \sum_{t \in \{1-\gamma, \dots, \gamma-1\}} \left| (2\gamma - 1)^{-1} - (2\gamma + 1)^{-1} \right| + 2n \left| \frac{1}{3} (2\gamma - 1)^{-1} - (2\gamma + 1)^{-1} \right| \\ &\le n(2\gamma + 1) \left| (2\gamma - 1)^{-1} - (2\gamma + 1)^{-1} \right| \\ &= n \left| \frac{2\gamma + 1}{2\gamma - 1} - 1 \right| \\ &< \frac{n}{2\gamma} + \frac{n}{\gamma^2}, \end{aligned} $$

the final domination being obtained by looking at the Laurent development of $\frac{2\gamma+1}{2\gamma-1}$.

We now introduce a variant of the $\mathbf{DCK}_{p,n}$ problem where the terms $s_1, s_2$ are now sampled from the distribution $\tilde{\mathcal{U}}_{\gamma}$.

**Definition 8** The $\mathbf{S-DCK}_{p,n,\gamma}$ problem (Summed-Decisional Compact Knapsack problem) is the problem of distinguishing between the uniform distribution over $\mathcal{R} \times \mathcal{R}$ and the distribution $(\mathbf{a}, \mathbf{as}_1 + \mathbf{s}_2)$ with $\mathbf{s}_1, \mathbf{s}_2$ independently drawn under $\tilde{\mathcal{U}}_{\gamma}$.

Since the support of $\tilde{\mathcal{U}}_{\gamma}$ is larger than the support originally used in the $\mathbf{DCK}_{p,n}$ problem, it seems natural to suppose that the $\mathbf{DCK}_{p,n}$ is somewhat easier to solve than the introduced $\mathbf{S-DCK}_{p,n,\gamma}$. This intuition is formalized in **Proposition 3**.

**Proposition 3.** The $\mathbf{DCK}_{p,n}$ problem is at most as hard as the $\mathbf{S-DCK}_{p,n,\gamma}$ problem.

*Proof.* Any challenge $(\mathbf{a}, \mathbf{u})$ of the $\mathbf{DCK}_{p,n}$ problem can be transformed in a challenge for $(\mathbf{a}, \mathbf{u}')$ for the $\mathbf{S-DCK}_{p,n,\gamma}$ problem by letting $\mathbf{u}' = \mathbf{u} + \mathbf{au}_1 + \mathbf{u}_2$ with $\mathbf{u}_1, \mathbf{u}_2$ independently drawn under the uniform distribution over $\mathcal{R}_{\gamma-1}$, by definition of $\tilde{\mathcal{U}}_{\gamma}$. Indeed, if $\mathbf{u}$ is of the form $\mathbf{as}_1 + \mathbf{s}_2$ for $\mathbf{s}_1, \mathbf{s}_2$ drawn independently and uniformly in $\mathcal{R}_{\gamma}$, then $\mathbf{u}' = \mathbf{a}(\mathbf{s}_1 + \mathbf{u}_1) + (\mathbf{s}_2 + \mathbf{u}_2)$, with the $(\mathbf{s}_i + \mathbf{u}_i)$ independently drawn under $\tilde{\mathcal{U}}_{\gamma}$. If $\mathbf{u}$ is uniform in $\mathcal{R}$, then $\mathbf{u}'$ remains uniform in $\mathcal{R}$.
Collision probability for linear hashing over $\mathcal{R}$.

**Lemma 11.** Let $0 < \gamma < p$ and $\mathbf{a} \in \mathcal{R}$, then for any $\mathbf{s}_1, \mathbf{s}_2 \in \mathcal{R}_\gamma^2$ drawn under $\tilde{\mathcal{U}}_\gamma$, there exists another pair $\mathbf{s}'_1, \mathbf{s}'_2 \in \mathcal{R}_\gamma^2$ such that $\mathbf{a}\mathbf{s}_1 + \mathbf{s}_2 = \mathbf{a}\mathbf{s}'_1 + \mathbf{s}'_2$ with probability at least
$$1 - \frac{p^n}{(2\gamma+1)^{2n}} - \frac{2n}{\gamma} - \frac{2n}{\gamma^2}.$$

*Proof.* Let $\mathbf{a} \in \mathcal{R}$ and define the linear function $\phi_{\mathbf{a}} : (\mathbf{x}, \mathbf{y}) \mapsto \mathbf{a}\mathbf{x} + \mathbf{y}$. This function maps a set of $p^{2n}$ elements to a set of $p^n$ elements and so any vector in the image of $\phi_{\mathbf{a}}$ admits at most $p^n$ preimages. Then there exists at most $p^n$ pairs $(\mathbf{x}, \mathbf{y})$ in $\mathcal{R}_\gamma^2$ such that $\phi_{\mathbf{a}}(\mathbf{x}, \mathbf{y}) \neq \phi_{\mathbf{a}}(\mathbf{x}', \mathbf{y}')$ for every other $(\mathbf{x}', \mathbf{y}') \in \mathcal{R}_\gamma^2$. Hence the probability of uniformly drawn vector not to have a second preimage through $\phi_{\mathbf{a}}$ is at most

$$\frac{p^n}{(2\gamma + 1)^{2n}}.$$

We then conclude with using the statistical distance between the uniform distribution and $\tilde{\mathcal{U}}_\gamma$. $\square$

## A.2 Security proof for the r-GLP signature scheme

In this section, we present a security proof for our r-GLP signature scheme. The unforgeability property of the scheme under the hardness of both the DCK and R-DCK problems, is captured by the following theorem:

**Theorem 5.** The probability that an adversary $\mathcal{A}$, who makes at most $q_h$ queries to the random oracle $H$ and runs in time $T$ succeeds in forging a signature for the oracle $S_0$ is upper bounded by:

$$\delta \le \sqrt{\frac{\epsilon_{\text{DCK}}(T)}{C} + \epsilon_{\text{R-DCK}}(T) + (1-p_r) \frac{q_h}{p^n} + p_r \frac{q_h}{(2k+1)^n} + 2\epsilon_{\text{DCK}}(T)}$$

with:

$$C = \frac{A_\gamma}{32} \left(1 - \left(\frac{n}{2\gamma}\right)^2\right) \left(1 - \left(\frac{\sqrt{p}}{(2\gamma)}\right)^{-2n} - \frac{n}{(2\gamma)}\right),$$

and

$$A_{\gamma} = \sup_{x} \left[ 1 - 2e^{-x} - 4\sqrt{2}(2k + \gamma\sqrt{16x/3})\sqrt{x + \log n/p} \right], p_r = \left(1 - \frac{2\alpha}{2k+1}\right)^{2n},$$

for $1 \le \gamma \le p$.

Description of the hybrid games involved in the security proof.

**Game $G_0$.** This game is the security game of the existential unforgeability under chosen message attack [34].

1. $(\mathbf{s}_1, \mathbf{s}_2), (\mathbf{a}, \mathbf{t}) \leftarrow \text{KEYGEN()}$

2. $(m^*, \sigma^*) \leftarrow \mathcal{A}^{H,S_0}(\mathbf{s}_1, \mathbf{s}_2)(\mathbf{a}, \mathbf{t})$

3. **return 1** if $(\text{VERIFY}(\mathbf{a}, \mathbf{t}, m^*, \sigma^*) = 1$ and $(m^*, \sigma^*)$ has not been returned by the oracle $S_0$) 0 otherwise.

The signing oracle $S_0$ is described in Algorithm 21.

**Game $G_1$.** This game is the same one as in $G_0$ except that the Signing oracle is replaced by the oracle $S_1$ described in Algorithm 22:

1. $(\mathbf{s}_1, \mathbf{s}_2), (\mathbf{a}, \mathbf{t}) \leftarrow \text{KEYGEN()}$
<table><thead><tr><th>Algorithm 21: Signature oracle S<sub>0</sub></th><th>Algorithm 22: Signature oracle S<sub>1</sub></th></tr></thead><tbody><tr><td><b>Data:</b> m, pk = (a, t), sk = (s<sub>1</sub>, s<sub>2</sub>)<br/><b>Result:</b> Signature σ</td><td><b>Data:</b> m, pk = (a, t), sk = (s<sub>1</sub>, s<sub>2</sub>)<br/><b>Result:</b> Signature σ</td></tr><tr><td>1 y<sub>1</sub> &larr; $R<sub>k</sub></td><td>1 y<sub>1</sub>, y<sub>2</sub> &larr; $R<sub>k</sub></td></tr><tr><td>2 y<sub>2</sub> &larr; $R<sub>k</sub></td><td>2 r &larr; ay<sub>1</sub> + y<sub>2</sub></td></tr><tr><td>3 r &larr; ay<sub>1</sub> + y<sub>2</sub></td><td>3 c &larr; H(r, m)</td></tr><tr><td>4 c &larr; H(r, m)</td><td>4 z<sub>1</sub> &larr; s<sub>1</sub>c + y<sub>1</sub></td></tr><tr><td>5 z<sub>1</sub> &larr; s<sub>1</sub>c + y<sub>1</sub></td><td>5 z<sub>2</sub> &larr; s<sub>2</sub>c + y<sub>2</sub></td></tr><tr><td>6 z<sub>2</sub> &larr; s<sub>2</sub>c + y<sub>2</sub></td><td>6 if z<sub>1</sub> or z<sub>2</sub> &notin; R<sub>k&minus;&alpha;</sub> then</td></tr><tr><td>7 if z<sub>1</sub> or z<sub>2</sub> &notin; R<sub>k&minus;&alpha;</sub> then</td><td>7 r &larr; $R$; Program H(r, m) = c</td></tr><tr><td>8 | return r</td><td>8 return r</td></tr><tr><td>9 end</td><td>9 end</td></tr><tr><td>10 return σ = (z<sub>1</sub>, z<sub>2</sub>, c)</td><td>10 return σ = (z<sub>1</sub>, z<sub>2</sub>, c)</td></tr></tbody></table>

2. $(m^*, \sigma^*) \leftarrow \mathcal{A}^{H,S_1}(s_1, s_2)(a, t)$

3. **return** 1 if $(\text{VERIFY}(a, t, m^*, \sigma^*) = 1$ and $(m^*, \sigma^*)$ has not been returned by the oracle $S_1$) 0 otherwise.

The only difference between the actual signing algorithm and the algorithm in $S_1$ is that in this oracle, when the rejection sampling fails, a fresh commitment value $r$ is generated from the random oracle, independently of the values taken by $y_1$ and $y_2$.

**Game G<sub>2</sub>.** This game is the same one as in $G_1$ except that the Signing oracle is replaced by the oracle $S_2$ described in Algorithm 23:

1. $(s_1, s_2), (a, t) \leftarrow \text{KEYGEN()}$

2. $(m^*, \sigma^*) \leftarrow \mathcal{A}_2^{H,S}(a, t)$

3. **return** 1 if $(\text{VERIFY}(a, t, m^*, \sigma^*) = 1$ and $(m^*, \sigma^*)$ has not been returned by the oracle $S_1$) 0 otherwise.

The difference between $G_1$ and $G_2$ is that the returned values of the random oracle $H$ is now chosen at random from the set $\mathcal{D}_\alpha^n$, so that this oracle does not use the secret key anymore.

**Game G<sub>3</sub>.** The game is now slightly different from the previous one, but the oracle used in this game is still the same, that is $S_2$, described in Algorithm 23. The difference between the these two games mainly lies in the fact that the domain from which the keys are drawn is extended to $\tilde{R}_\gamma$, under the distribution $\tilde{U}_\gamma$. We ultimately want to show that a forger against this game can be used to solve an instance of the **DCK** problem.

INPUT: $(a, t_0)$ challenge of DCK<sub>p,n</sub>

1. $(s_1, s_2) \leftarrow \tilde{U}_\gamma^2$

2. $a \leftarrow \mathcal{R}$

3. $t \leftarrow as_1 + s_2$

4. $(m^*, \sigma^*) \leftarrow \mathcal{A}^{H,S_2}(a, t)$

5. **return** 1 if $(\text{VERIFY}(a, t, m^*, \sigma^*) = 1$ and $(m^*, \sigma^*)$ has not been returned by the oracle $S_1$) 0 otherwise.

**Proof of Theorem 5.** Firstly we establish indistinguishability results between the games $G_0$ and $G_1$, then between $G_1$ and $G_2$ and eventually between $G_2$ and $G_3$. These results are formalized in Lemma 12, Lemma 13 and Lemma 14. In a second time we show in Lemma 15 how we can
**Algorithm 23: Signature oracle $S_2$**

**Data:** $m, pk = (\mathbf{a}, \mathbf{t})$

**Result:** Signature $\sigma$

1. $c \stackrel{\$}{\leftarrow} D_{\alpha}^n$

2. $B \stackrel{\$}{\leftarrow} \text{BERNOULLI} \left( \left( 1 - \frac{2\alpha}{2k+1} \right)^{2n} \right)$

3. **if** $B = 1$ **then**

4. $r \stackrel{\$}{\leftarrow} \mathcal{R}$

5. Program $H(\mathbf{r}, m) = \mathbf{c}$

6. **return** $\mathbf{r}$

7. **else**

8. $\mathbf{z}_1 \stackrel{\$}{\leftarrow} \mathcal{R}_{k-\alpha}$

9. $\mathbf{z}_2 \stackrel{\$}{\leftarrow} \mathcal{R}_{k-\alpha}$

10. $\mathbf{r} \leftarrow \mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c}$

11. **end**

12. Program $H(\mathbf{r}, m) = \mathbf{c}$

13. **return** $\sigma = (\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$

construct a distinguisher for the **DCK** problem from an adversary that is able to win the game $S_3$ with non-negligible probability. The result of **Theorem 5** is then a direct consequence of the triangular inequality.

Before going into the details of these lemmas and since this result will be used multiple time in the proof, we recall that the probability $p_r$ of getting accepted by the rejection sampling in the signature (or equivalently in the oracle $S_0$.

$$p_r = \left(1 - \frac{2\alpha}{2k + 1}\right)^{2n}$$

**Lemma 12 (Computational indistinguishability of $G_0$ and $G_1$).** Let $\mathcal{A}$ be an adversary of time complexity bounded by $T$, having access to either the signing algorithm $S_0$ or the oracle $S_1$, and limited to perform at most $q_h$ queries to the $H$ oracle (this count includes the calls that can be performed while calling the signing oracles too). Its computational advantage in distinguishing the signing algorithm $S_0$ from $S_1$ is bounded by:

$$\epsilon_{\mathbf{R}-\mathbf{DCK}}(T) + (1 - p_r) \frac{q_h}{p^n}.$$

*Proof.* Remark that:

1. There is no statistical difference between the output distribution of the two oracles that are accepted by the rejection sampling (that is so that $\mathbf{z}_1$ or $\mathbf{z}_2$ do not lie in the set $\mathcal{R}_{k-\alpha}$).

2. On the one hand, the distribution of outputs of $S_0$ that are rejected by the rejection sampling is by construction the distribution of $(\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2)$ where $(\mathbf{a}, \mathbf{c}, \mathbf{y}_1, \mathbf{y}_2)$ is uniformly sampled in $\mathcal{R} \times D_{\alpha}^n \times \mathcal{R}_k^2$, conditioned by the event $s_1\mathbf{c} + \mathbf{y}_1 \notin \mathcal{R}_{k-\alpha}$ or $s_2\mathbf{c} + \mathbf{y}_2 \notin \mathcal{R}_{k-\alpha}$. Such a vector along with $\mathbf{a}$ and $\mathbf{c}$ constitutes a sample of the distribution of **R-DCK** by definition.
3. On the other hand the distribution of outputs of $S_1$ that are rejected by the rejection sampling is by construction the uniform distribution over $\mathcal{R}$ conditioned by the event the simulation by the random oracle is perfect and remains coherent. Indeed after yielding the commitment $\mathbf{r}$, the random oracle $H$ is programmed so that $H(\mathbf{r}, m) = \mathbf{c}$ without checking whether the value $\mathbf{r}$ has been already set. But the adversary calls at most $q_h$ times the oracle $H$, at most $q_h$ values can be set by the adversary. Hence this distribution is at distance at most:

$$q_h \left\{ \Pr_{\mathbf{r} \leftarrow \mathcal{R}} [\mathbf{r} \text{ already set by } H] \right\} = q_h p^{-n}$$

from uniform.

Therefore the advantage of $\mathcal{A}$ in distinguishing the two oracle $S_0$ and $S_1$ satisfies by the law of total probability:

$$\begin{align*}
& \left| \Pr[\mathcal{A} \text{ wins } \mathbf{G}_1] - \Pr[\mathcal{A} \text{ wins } \mathbf{G}_0] \right| \\
& \le \epsilon_{\mathbf{R}\text{-DCK}}(T) + (1-p_r)q_h \left\{ \Pr_{\mathbf{r} \leftarrow \mathcal{R}} [\mathbf{r} \text{ already set by } H] \right\} \\
& \le \epsilon_{\mathbf{R}\text{-DCK}}(T) + (1-p_r)q_h \max_{\mathbf{r}' \in \mathcal{R}} \left\{ \Pr_{\mathbf{r} \leftarrow \mathcal{R}} [\mathbf{r} = \mathbf{r}'] \right\} \\
& = \epsilon_{\mathbf{R}\text{-DCK}}(T) + (1-p_r) \frac{q_h}{p^n},
\end{align*}$$

where $\epsilon_{\mathbf{R}\text{-DCK}}(T)$ is an upper bound on the **R-DCK**-advantage of any adversary running in time $T$ (and hence negligible under the **R-DCK** hardness assumption for polynomial $T$). $\square$

**Lemma 13 (Computational indistinguishability of $G_1$ and $G_2$).** Let $\mathcal{A}$ be an adversary of time complexity bounded by $T$, having access to either the signing algorithms $S_1$ or $S_2$, and limited to perform at most $q_h$ queries to the $H$ oracle (this count includes the calls that can be performed while calling the signing oracles too). Its computational advantage of distinguishing the two oracles of hybrid $G_1$ or $G_2$ is bounded by

$$p_r \frac{q_h}{(2k+1)^n}.$$

*Proof.* First remark that the parameter chosen for the Bernoulli is exactly the probability of getting a valid signature when signing honestly with the secret key that is $p_r = (1 - \frac{2\alpha}{2k+1})^{2n}$. Let us then perform a case analysis, depending on the conditioning by the value taken by the variable $B$.

- Case $B = 0$: Let consider the output distribution of $S_2$, conditioned by the event $B = 0$ (that is only considering the executions where the Bernoulli variable $B$ is set to 0). This distribution is by construction statistically indistinguishable from the distribution of the game $S_1$ conditioned by the rejection of the computed signature.

- Case $B = 1$: Let now consider the output distribution of $S_2$, conditioned by the event $B = 1$. This distribution is then by construction statistically indistinguishable from the distribution
of the game $S_1$ conditioned this time by the acceptance of the computed signature as long as the simulation by the random oracle is perfect and remains coherent. Indeed once $\mathbf{z}_1, \mathbf{z}_2$ are sampled, the value of the commitment is set a posteriori to fulfill the equation $\mathbf{r} = \mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c}$ and the random oracle is programmed to the answer to $H(\mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c}, m) = H(\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2, m)$. If the value for $(\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2, m)$ was already set, we abort the simulation. Thus one needs to evaluate the probability that $\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2 = \mathbf{r}$ for a given $\mathbf{r} \in \mathcal{R}$ when $\mathbf{y}_1$ and $\mathbf{y}_2$ are sampled uniformly and independently in $\mathcal{R}_k$:

$$ 
\begin{align*}
\max_{\substack{\mathbf{r} = \mathbf{a}\mathbf{u} + \mathbf{v} \\ \mathbf{u}, \mathbf{v} \in \mathcal{R}_k}} \Pr_{\mathbf{u}, \mathbf{v} \in \mathcal{R}_k} [\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2 = \mathbf{r}] &\le \max_{\mathbf{r} \in \mathcal{R}} \Pr_{\mathbf{y}_1, \mathbf{y}_2} [\mathbf{a}\mathbf{y}_1 + \mathbf{y}_2 = \mathbf{r}] \\
&= \max_{\mathbf{r} \in \mathcal{R}} \Pr_{\mathbf{y}_1, \mathbf{y}_2} [\mathbf{y}_2 = \mathbf{r} - \mathbf{a}\mathbf{y}_1] \\
&= \max_{\substack{\mathbf{r}' \in \mathcal{R} \\ \mathbf{r}' \ne \mathbf{r}}} \Pr_{\mathbf{y}_2} [\mathbf{y}_2 = \mathbf{r}'] \\
&= (2k+1)^{-n}.
\end{align*}
$$

We eventually conclude by the law of total probability:

$$ \left| \Pr[\mathcal{A} \text{ wins } \mathbf{G}_2] - \Pr[\mathcal{A} \text{ wins } \mathbf{G}_1] \right| \le \left(1 - \frac{2\alpha}{2k+1}\right)^{2n} \frac{q_h}{(2k+1)^n}. \quad \square $$

**Lemma 14 (Computational indistinguishability of $\mathbf{G}_2$ and $\mathbf{G}_3$).** Let $\mathcal{A}$ be an adversary of time complexity bounded by $T$, having access to either the signing algorithms $S_2$ or $S_3$. Its computational advantage of distinguishing the two oracles of hybrid $\mathbf{G}_2$ or $\mathbf{G}_3$ is bounded by

$$ 2\epsilon_{\text{DCK}}(T) $$

where $\epsilon_{\text{DCK}}(T)$ is an upper bound on the $\text{DCK}(T)$-advantage of any adversary running in time $T$.

*Proof.* The difference between the games $\mathbf{G}_2$ and $\mathbf{G}_3$ lies in the distribution from which the keys $\mathbf{s}_1, \mathbf{s}_2$ are sampled. In $\mathbf{G}_2$ they are drawn under $\mathcal{U}(\mathcal{R}_1)$, whereas in $\mathbf{G}_3$ they are drawn under the $\tilde{\mathcal{U}}_\gamma$. Hence the advantage of the adversary $\mathcal{A}$ to distinguish these two games when knowing the values of $(\mathbf{a}, \mathbf{a}\mathbf{s}_1 + \mathbf{s}_2)$ is bounded by the advantage it has to distinguish $(\mathbf{a}, \mathbf{a}\mathbf{s}_1 + \mathbf{s}_2)$ from the uniform distribution, that is its advantage in solving either the **DCK** problem or the **S-DCK** problem. Since using **Proposition 3** the advantage in solving the **DCK** problem is smaller than the advantage in solving the **S-DCK** problem, its advantage in distinguishing the two games is bounded by $2\epsilon_{\text{DCK}}(T)$. $\square$

**Lemma 15 (Applying the Forking Lemma to construct a distinguisher for DCK).** Suppose there exists a forger $\mathcal{F}$, that succeeds in forging with probability $\delta$, who is given the verification key and access to the signing oracle $S_3$ in the Hybrid $\mathbf{G}_3$, is limited to at most $q_h$ queries to the random oracle $H$. Then there exists a probabilistic algorithm $\mathfrak{A}$ of same time complexity as $\mathcal{F}$, which, for a given pair $(\mathbf{a}, \mathbf{t}) \in \mathcal{R}^2$ is able to decide whether $(\mathbf{a}, \mathbf{t})$ follows the **R-DCK** distribution or is made from two independent random samples, with probability at least

$$ \frac{1}{32} \left(1 - \left(\frac{n+1}{2\gamma+1}\right)^2\right) (\delta - 3^n) \left(\frac{\delta - \epsilon_\alpha}{q_h} - 3^n\right) \left(1 - (\sqrt{p}(2\gamma+1))^{-2n} - n(2\gamma)^{-1} - n\gamma^{-2}\right) A_\gamma, \text{ where} $$

$$ A_{\gamma} = \sup_{x} \left[ 1 - 2e^{-x} - 4\sqrt{2}(2k + \gamma\sqrt{16x/3})\sqrt{x + \log n/p} \right]. $$
Proof. Let us take $\mathbf{a}, \mathbf{t}_0 \in \mathbb{R}$ the instance of the DCK problem we want to solve.

Let us generate $\mathbf{s}_1, \mathbf{s}_2 \in \mathbb{R}_\gamma^2$ and the corresponding $\mathbf{t} = \mathbf{a}\vec{\mathbf{s}}_1 + \mathbf{s}_2$ public key (note that this key is constructed with the challenge element $\mathbf{a}$).

We now choose random coins $\phi$ and $\psi$ which will be used respectively by the forger and the signer. We also pick the values that will correspond to the responses of the random oracle $\mathbf{c}_1, \dots, \mathbf{c}_{q_h}$. Let define the algorithm $\mathbf{a}$:

INPUT: $(\mathbf{a}, \mathbf{t}, \phi, \psi, \mathbf{c}_1, \dots, \mathbf{c}_{q_h})$

OUTPUT: A couple message, signature $(m, \mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$

1. Initialize $\mathbf{a}$ with $\mathbf{a}, \mathbf{t}, \phi$.

2. Run $\mathcal{F}$.

3. Each time $\mathcal{F}$ requires a signature, $\mathbf{a}$ intercepts the call and runs $\mathbf{S}_2$, using the random coins $\psi$ as entropy to produce a signature.

- During this process, some queries to the random oracle $\mathcal{H}$ are performed (by the signature oracle or by $\mathcal{F}$ itself).

- In such cases the response of $\mathcal{H}$ will be the first $\mathbf{c}_i$ in the list $(\mathbf{c}_1, \dots, \mathbf{c}_{q_h})$ that has not been used yet.

4. As soon as $\mathcal{F}$ finishes running return the forged signature $(m, \mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$.

Let $\epsilon_\alpha = 3^{-\alpha}$ be the probability of sampling a particular element uniformly at random in the range of the random oracle $\mathcal{H}$.

The routine $\mathbf{a}$ outputs, with probability $\delta$, a message $m$ and its signature $(\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$, which by construction satisfies: $\mathbf{c} = \mathcal{H}((\mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c}), m)$. If the random oracle $\mathcal{H}$ was neither queried nor programmed with the specific input $\mathbf{r} = \mathbf{a}\mathbf{z}_1 + \mathbf{z}_2$, then, by choosing at random in the range of $\mathcal{H}$, the forger has probability exactly $\epsilon_\alpha$ of generating $\mathbf{c}$ satisfying the relation $\mathbf{c} = \mathcal{H}(\mathbf{r}, m)$. This implies that with probability $1 - \epsilon_\alpha$, $\mathbf{c}$ belongs to the list $(\mathbf{c}_i)_i$. Hence the probability that $\mathbf{a}$ succeeds in forging a signature $(\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$ so that $\mathbf{c}$ is one of the $(\mathbf{c}_i)_i$ is at least $\delta - \epsilon_\alpha$. Suppose from now on that this is case, and without loss of generality we can assume that this returned values is $\mathbf{c}_1$, by simply reordering the $(\mathbf{c}_i)_i$ beforehand. Following the execution flow of the procedure $\mathbf{a}$, one can remark that two cases can occur:

[R1] Either $\mathbf{c}$ was programmed directly by $\mathcal{F}$ to be the output of $\mathcal{H}$ on a certain pair $(\mathbf{r}', m') = (\mathbf{a}\mathbf{z}'_1 + \mathbf{z}'_2, m')$ when signing the message $m'$. Since $(\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$ is a valid signature returned by the forger, we have:

$$H(\mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c}, m) = H(\mathbf{a}\mathbf{z}'_1 + \mathbf{z}'_2 - \mathbf{t}\mathbf{c}, m').$$

If $m \neq m'$ or $\mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c} \neq \mathbf{a}\mathbf{z}'_1 + \mathbf{z}'_2 - \mathbf{t}\mathbf{c}$ then the forger has found a preimage of $\mathbf{c}_1$ for $\mathcal{H}$. This event occurs with probability exactly $\epsilon_\alpha$. One can thus suppose that $\mathbf{a}\mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t}\mathbf{c} = \mathbf{a}\mathbf{z}'_1 + \mathbf{z}'_2 - \mathbf{t}\mathbf{c}$ with probability $1 - \epsilon_\alpha$. Hence by setting $\mathbf{u}_1 = \mathbf{z}_1 - \mathbf{z}'_1$ and $\mathbf{u}_2 = \mathbf{z}'_2 - \mathbf{z}_2$, we have found two elements of norm bounded by $2k$ such that $\mathbf{a}\mathbf{u}_1 + \mathbf{u}_2 = 0$, which are non-zero otherwise $(\mathbf{z}_1, \mathbf{z}_2, m)$ would be exactly the same as the signature $(\mathbf{z}'_1, \mathbf{z}'_2, m)$.

[R2] Either $\mathbf{c}_1$ results from a call to the signature oracle, we store the forged signature $\mathbf{z}_1, \mathbf{z}_2, \mathbf{c}_1$. Then replay the algorithm $\mathbf{a}$ with the same coins but different and fresh $\mathbf{c}'_1, \dots, \mathbf{c}'_{q_h}$. By the general Forking Lemma [9] the probability so that $\mathbf{c}'_1 \neq \mathbf{c}'_1$ and the forger uses the random oracle response $\mathbf{c}_1$ (and the query associated to it) in the forgery is at least

$$(\delta - \epsilon_\alpha) \left( \frac{\delta - \epsilon_\alpha}{q_h} - \epsilon_\alpha \right).$$
Eventually, we can produce two signatures for the message $m$, denoted by $(\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})$ and $(\mathbf{z}'_1, \mathbf{z}'_2, \mathbf{c}')$, so that the commitment coincides:

$$ \mathbf{a}(\mathbf{z}_1 - \mathbf{s}_1\mathbf{c}) + \mathbf{z}_2 - \mathbf{s}_2\mathbf{c} = \mathbf{a}(\mathbf{z}'_1 - \mathbf{s}_1\mathbf{c}') + \mathbf{z}'_2 - \mathbf{s}_2\mathbf{c}', $$

that is:

$$ \mathbf{a}(\mathbf{z}_1 - \mathbf{s}_1\mathbf{c} - \mathbf{z}'_1 + \mathbf{s}_1\mathbf{c}') + (\mathbf{z}_2 - \mathbf{s}_2\mathbf{c} - \mathbf{z}'_2 + \mathbf{s}_2\mathbf{c}') = 0. $$

Let us set

$$ \begin{cases} \mathbf{u}_1 = \mathbf{z}_1 - \mathbf{s}_1\mathbf{c} - \mathbf{z}'_1 + \mathbf{s}_1\mathbf{c}' \\ \mathbf{u}_2 = \mathbf{z}_2 - \mathbf{s}_2\mathbf{c} - \mathbf{z}'_2 + \mathbf{s}_2\mathbf{c}' \end{cases}. $$

The probability of having $(\mathbf{u}_1, \mathbf{u}_2) \neq (\mathbf{0}, \mathbf{0})$ is at least

$$ \frac{1}{2} p_c \left( 1 - \left( \frac{n+1}{2\gamma+1} \right)^2 \right) $$

with

$$ p_c = 1 - (\sqrt{p}(2\gamma + 1))^{-2n} - n(2\gamma)^{-1} - n\gamma^{-2} \approx 1 - n(2\gamma)^{-1}. $$

Indeed, by Lemma 11, with probability at least $p_c$ there exists another pair $(\mathbf{s}'_1, \mathbf{s}'_2)$ such that $\mathbf{a}\mathbf{s}_1 + \mathbf{s}_2 = \mathbf{a}\mathbf{s}'_1 + \mathbf{s}'_2$. Suppose that $(\mathbf{u}_1, \mathbf{u}_2) = (\mathbf{0}, \mathbf{0})$. Then playing the previous argument (and so using the same randomness) with the $\mathbf{s}'_i$ instead of the $\mathbf{s}_i$ yields another pair $(\mathbf{u}'_1, \mathbf{u}'_2)$. Suppose that this pair is also $(\mathbf{0}, \mathbf{0})$. Then we have:

$$ \mathbf{s}_1(\mathbf{c} - \mathbf{c}') = \mathbf{s}'_1(\mathbf{c} - \mathbf{c}') $$

$$ \mathbf{s}_2(\mathbf{c} - \mathbf{c}') = \mathbf{s}'_2(\mathbf{c} - \mathbf{c}'), $$

meaning that $\mathbf{s}_1\mathcal{R} = \mathbf{s}_2\mathcal{R} = \mathbf{s}'_1\mathcal{R} = \mathbf{s}'_2\mathcal{R} = (\mathbf{c} - \mathbf{c}')\mathcal{R} \neq \{\mathbf{0}\}$, $\mathcal{R}$ (indeed, the $\mathbf{s}_i$ can not be all zero by construction and if $(\mathbf{c} - \mathbf{c}')$ is invertible then we would have $\mathbf{s}_1 = \mathbf{s}'_1$ and $\mathbf{s}_2 = \mathbf{s}'_2$). Hence this event can occurs with probability dominated by

$$ \begin{aligned} \Pr_{\mathbf{s}_1, \mathbf{s}_2} [\mathbf{s}_1 \mathcal{R} = \mathbf{s}_2 \mathcal{R} = (\mathbf{c} - \mathbf{c}') \mathcal{R}] &\le \max_{\mathcal{I} \ne \{\mathbf{0}\}, \mathcal{R}} \Pr_{\mathbf{s}_1, \mathbf{s}_2} [\mathbf{s}_1 \mathcal{R} = \mathbf{s}_2 \mathcal{R} = \mathcal{I}] \\ &\le \max_{\mathcal{I} \ne \{\mathbf{0}\}, \mathcal{R}} \Pr_{\mathbf{s} \in \mathcal{U}(\mathcal{R}, \gamma)} [\mathbf{s} \mathcal{R} = \mathcal{I}]^2 \\ &\le \max_{\mathcal{I} \ne \{\mathbf{0}\}, \mathcal{R}} \left( n(2\gamma)^{-1} + n\gamma^{-2} + \max_{\mathbf{s} \in \mathcal{U}(\mathcal{R}, \gamma)} [\mathbf{s} \mathcal{R} \in \mathcal{I}] \right)^2 \\ &\le \left( n(2\gamma)^{-1} + n\gamma^{-2} + \max_{\mathcal{I} \ne \{\mathbf{0}\}, \mathcal{R}} \Pr_{\mathbf{s} \in \mathcal{U}(\mathcal{R}, \gamma)} [\mathbf{s} \mathcal{R} \in \mathcal{I}] \right)^2 \end{aligned} $$

Hence to estimate $\max_{\mathcal{I} \ne \{\mathbf{0}\}, \mathcal{R}} \Pr_{\mathbf{s} \in \mathcal{U}(\mathcal{R}, \gamma)} [\mathbf{s} \mathcal{R} \in \mathcal{I}]$, we fall back to describing the ideals of $\mathcal{R}$. Classically, since $\mathcal{R} \stackrel{\text{Sim}}{=} (\mathbb{Z}[X]/(X^n + 1))/p$ its ideals are in (antitone) bijection with the divisors of $X^n + 1 \bmod p$. Let then $P$ be a divisor of $X^n + 1 \bmod p$, then the ideal generated by $P$ in $\mathcal{R}$ has cardinality $p^{n-\deg P}$ and the probability that $\mathbf{s} \in (P)$ is at most $(2\gamma + 1)^{-\deg P}$. Indeed, the probability of this event is equal to $\Pr[\mathbf{s} = 0 \bmod P]$, yielding the announced increase since the reduction $\bmod P$ acts as a bijection when fixing the $n - \deg P$ coefficients of highest degrees.
Therefore we get the estimate:

$$ \begin{aligned} \max_{\mathcal{I} \neq \{0\}, \mathcal{R}} \Pr[\mathbf{s} \in \mathcal{I}] &\le \max_{d \in \{1, \dots, n-1\}} (2\gamma + 1)^{-d} \\ &= \max_{d \in \{1, \dots, n-1\}} (2\gamma + 1)^{-2d} = (2\gamma + 1)^{-1}. \end{aligned} $$

The probability of getting once again zero elements $\mathbf{u}_i$ is then dominated by $((n+1)(2\gamma+1))^{-2}$. The forger $\mathcal{F}$ does not get access to these functionally equivalent secret keys. Since it does not use them for simulating the signing oracle, we will get a non-zero answer with probability at least $1/2$, since each key has an equal probability of being chosen by uniformity of the generation.

We then need to estimate the norm of the vectors $\mathbf{u}_1, \mathbf{u}_2$, which with a certain probability is not too big. Indeed, remark that Proposition 2 and union bound ensures that with probability at least $1/16$, the elements $\mathbf{s}_1\mathbf{c}, \mathbf{s}'_1\mathbf{c}, \mathbf{s}_2\mathbf{c}$ and $\mathbf{s}'_2\mathbf{c}$ have their $\ell_\infty$-norm bounded by $\gamma\sqrt{\frac{4\alpha}{3}}$, meaning that $\|\mathbf{u}_i\|_\infty \le 2k + \gamma\sqrt{\frac{16\alpha}{3}}$, for $i = 1, 2$.

All in all, in the case [E1], we can find a couple $(\mathbf{u}_1, \mathbf{u}_2) \ne (0, 0)$ of norm bounded by $2k$ such that $\mathbf{a}\mathbf{u}_1 + \mathbf{u}_2 = 0$ with probability at least $(1 - \epsilon_\alpha)$ and in the case [E2], we can find two $\mathbf{u}_1, \mathbf{u}_2$ of norm bounded by $2k + \gamma\sqrt{\frac{16\alpha}{3}}$ such that $\mathbf{a}\mathbf{u}_1 + \mathbf{u}_2 = 0$ with probability at least

$$ p_0 = \frac{1}{2} p_c \left( 1 - \left( \frac{n+1}{2\gamma+1} \right)^2 \right) \left( \delta - \epsilon_\alpha \right) \left( \frac{\delta - \epsilon_\alpha}{q_h} - \epsilon_\alpha \right) < 1 - \epsilon_\alpha $$

Hence, in any cases, with probability at least $p_0$ one can find such vectors. Now allows us to get a non negligible advantage in solving the DCK instance, acting as a trapdoor for this problem. Indeed, for the trial $(\mathbf{a}, \mathbf{t}_0)$, given as input, two cases can occur:

1. Either the element $\mathbf{t}$ of $\mathcal{R}$ is taken uniformly at random, the probability of $\mathbf{u}_1\mathbf{t}$ to be inside the $\ell_\infty$ ball of radius $2\tau$ is crudely upper bounded by $(4\tau - 1)/(p-1)$ (indeed, at most $p^{n-1}$ elements can vanish under the action of $x \mapsto u_1x$, and for the remaining ones, at most $(4\tau - 1)/(p-1)$ elements per space of dimension 1 minus zero intersects the ball).

2. Either it is of the form $(\mathbf{a}, \mathbf{a}\mathbf{s}_3 + \mathbf{s}_4)$, the multiplication of the latter pair by $\mathbf{u}_1$ yields:

$$ (\mathbf{a}\mathbf{u}_1, \mathbf{a}\mathbf{u}_1\mathbf{s}_3 + \mathbf{u}_1\mathbf{s}_4) = (\mathbf{a}\mathbf{u}_1, -\mathbf{u}_2\mathbf{s}_3 + \mathbf{u}_1\mathbf{s}_4). $$

We can notice that $-\mathbf{u}_2\mathbf{s}_3 + \mathbf{u}_1\mathbf{s}_4$ has infinity norm bounded by $2\tau = 2\sqrt{2}\|\mathbf{u}_i\|_2\sqrt{x + \log n}$ with probability at least $1 - 2e^{-x}$, for a free parameter $x$ which will be used for later optimization. To see this, remark that

$$ \Pr[\mathbf{u}_1\mathbf{s}_2 + \mathbf{u}_2\mathbf{s}_1 \ge 2\tau] \le \Pr[\mathbf{u}_1\mathbf{s}_2 \ge \tau] + \Pr[\mathbf{u}_2\mathbf{s}_1 \ge \tau] $$

by the union bound. But we have for $i = 1, 2, j = 1, 2$ and $s > 0$:
$$
\begin{align*}
\Pr[\mathbf{u}_i \mathbf{s}_j \ge \tau] &\le \Pr\left[\bigvee_{k=1}^n \{[\mathbf{u}_i \mathbf{s}_j]_k \ge \tau\}\right] & \text{Coefficient extraction} \\
&\le n \Pr[[\mathbf{u}_i \mathbf{s}_j]_1 \ge \tau] & \text{Union bound} \\
&\le n \Pr[s[\mathbf{u}_i \mathbf{s}_j]_1 \ge s\tau] & \text{Positivity of s} \\
&\le n \Pr[\exp(s[\mathbf{u}_i \mathbf{s}_j]_1)] \ge \exp(s\tau)] & \text{Monotony of exponential} \\
&\le n \frac{\mathbf{E}[\exp(s[\mathbf{u}_i \mathbf{s}_j]_1)]}{\exp(s\tau)} & \text{Markov's Inequality} \\
&\le \exp\left(\frac{s^2 \|\mathbf{u}_i\|_2^2}{2} - s\tau + \log n\right) & \text{Proposition 1} \\
&\le \exp\left(-\frac{\tau^2}{2\|\mathbf{u}_i\|^2} + \log n\right) \\
&= \exp\left(-\frac{(\sqrt{2}\|\mathbf{u}_i\|_2 \sqrt{x + \log n})^2}{2\|\mathbf{u}_i\|^2} + \log n\right) \\
&= \exp(-(x + \log n) + \log n) \\
&= \exp(-x)
\end{align*}
$$

Therefore the distinguisher constructed by testing if the element $t\mathbf{u}_1$ lies inside the ball of radius $2\tau$ has advantage

$$A_x = \sup_x \left[ 1 - 2e^{-x} - 4\sqrt{2}(2k + \gamma\sqrt{16x/3})\sqrt{x + \log n}/p \right].$$

We define the algorithm $\mathfrak{A}$ to be the algorithm that find the trapdoors elements $\mathbf{u}_1, \mathbf{u}_2$ from the forgery of a valid signature by $\mathcal{F}$ and which answer the DCK challenge with the distinguisher above-mentioned. Its running time is at most twice the running time of the forger $\mathcal{F}$ and its success probability is at least $A_x p_0$, by construction. $\square$

**Remark 8 (Practical considerations).** Assuming the computational hardness of both DCK and R-DCK problems, choosing $\gamma = 1664 \approx 2^{10.70}$ (resp. $\gamma = 2504$) for the small (resp. large) security parameters set ensures a security level of 100 (resp 256) bits.

### A.3 r-GLP signature scheme with commitment

This part describes the GLP signature scheme combined with the commitment procedure introduced in [8]. The public commitment key $ck = \begin{pmatrix} ck_{1,1} & ck_{1,2} & ck_{1,3} \\ ck_{2,1} & ck_{2,2} & ck_{2,3} \end{pmatrix}$ is sampled uniformly at random in $\mathbb{R}^{2 \times 3}$ during the key derivation algorithm. The parameter $k'$ is set accordingly to the estimation of [8], so greater than $2^{2q/3}$. In this variation of the original signature scheme, the value $r$ is hidden through the linear commitment. Hence, even if an attacker learn the committed value $f_1, f_2$ by side channel, the computational indistinguishability of the commitment with an uniform distribution ensures that no secret-dependent information could possibly be extracted from this trace. To formalize this intuition we prove like in the latter section that one round of the signature
<table><thead><tr><th colspan="2">Algorithm 24: GLP signature with commitment</th></tr><tr><th colspan="2">Data: m, pk, sk, ck</th></tr><tr><th colspan="2">Result: Signature σ</th></tr></thead><tbody><tr><td>1</td><td>y<sub>1</sub>, y<sub>2</sub> ←<sup>$</sup> R<sub>k</sub></td></tr><tr><td>2</td><td>u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub> ←<sup>$</sup> R<sub>k'</sub></td></tr><tr><td>3</td><td>r ← ay<sub>1</sub> + y<sub>2</sub></td></tr><tr><td>4</td><td>(f<sub>1</sub>, f<sub>2</sub>) ← (u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>) · ck<sup>T</sup> + (0, r)</td></tr><tr><td>5</td><td>c ← H(f<sub>1</sub>, f<sub>2</sub>, m)</td></tr><tr><td>6</td><td>z<sub>1</sub> ← s<sub>1</sub>c + y<sub>1</sub></td></tr><tr><td>7</td><td>z<sub>2</sub> ← s<sub>2</sub>c + y<sub>2</sub></td></tr><tr><td>8</td><td>if z<sub>1</sub> or z<sub>2</sub> /∈ R<sub>k-α</sub> then</td></tr><tr><td>9</td><td>return (f<sub>1</sub>, f<sub>2</sub>)</td></tr><tr><td>10</td><td>end</td></tr><tr><td>11</td><td>return σ = (z<sub>1</sub>, z<sub>2</sub>, u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>, f<sub>1</sub>, f<sub>2</sub>, c)</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Algorithm 25: GLP verification with commitment</th></tr><tr><th colspan="2">Data: m, σ, pk, ck</th></tr></thead><tbody><tr><td>1</td><td>if z<sub>1</sub> and z<sub>2</sub> ∈ R<sub>k-α</sub> and<br/>c = H((u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>) · ck<sup>T</sup> + (0, az<sub>1</sub> +<br/>z<sub>2</sub> - tc), m) then</td></tr><tr><td>2</td><td>accept</td></tr><tr><td>3</td><td>else</td></tr><tr><td>4</td><td>reject</td></tr><tr><td>5</td><td>end</td></tr></tbody></table>

scheme with return values even in case of a rejection is EUF-CMA. We now sketch the security proof of this modified scheme.

**Game G<sub>0</sub>.** This game is the security game of the existential unforgeability under chosen message attack, where the adversary can ask at most $q_h$ hash queries to the $H$ oracle and $q_s$ sign queries to the Signing oracle $S_0$ given in Algorithm 26.

Notice that the signature includes the random values $u_1, u_2, u_3$ to open the commitment $(f_1, f_2)$ of $r$.

**Game G<sub>1</sub>.** This game is the same as in $G_0$ except that the Signing oracle $S_1$ is given in Algorithm 27. The difference in the signing algorithms is that in the case of a rejection at line 6: the committed variables $f_1, f_2$ are freshly re-sampled, independently from any previous values. This game is computationally indistinguishable from $G_0$ under the *hiding* property of the commitment scheme (see [8]) by choice of the commitment parameters. This property relying on the hardness of the **R-LWE** problem. Notice that the previous argument remains valid as long as the simulation by the random oracle is perfect and remains coherent. Indeed after yielding the commitment $r$, the random oracle $H$ is programmed so that $H(y_1, y_2, m) = c$ without checking whether the value $y_1, y_2$ has been already set. If an adversary $A$ running in time $T$ calls $H$ $q_h$ times, at most $q_h$ values can be set by the adversary and we get:

$$ \left| \Pr[\mathcal{A} \text{ wins } \mathbf{G}_1] - \Pr[\mathcal{A} \text{ wins } \mathbf{G}_0] \right| \le \epsilon_{\text{RLWE}}(T) + (1 - p_r) \frac{q_h}{p^{2n}}, $$

where $\epsilon_{\text{RLWE}}(T)$ is an upper bound on the advantage of any adversary running in time $T$ to solve the **R-LWE** problem. All in all $G_0$ and $G_1$ are thus computationally indistinguishable under the hardness Ring-LWE assumption.

**Game G<sub>2</sub>.** In this game, we replace the Signing oracle by $S_2$ described in Algorithm 10 and take as input a trial of the DCK<sub>p,n</sub> problem. INPUT: $(\mathbf{a}, \mathbf{t})$ trials of DCK<sub>p,n</sub>

1. $(s_1, s_2) \leftarrow \mathcal{R}_{\gamma}^2$

2. $(m^*, \sigma^*) \leftarrow \mathcal{A}^{H,S_2}(\mathbf{a}, \mathbf{t})$
<table><thead><tr><th colspan="2">Algorithm 26: Signature oracle S<sub>0</sub></th><th colspan="2">Algorithm 27: Signature oracle S<sub>1</sub></th></tr><tr><td colspan="2">Data: m, pk = (a, t), sk = (s<sub>1</sub>, s<sub>2</sub>)<br>Result: Signature σ</td><td colspan="2">Data: m, pk = (a, t), sk = (s<sub>1</sub>, s<sub>2</sub>)<br>Result: Signature σ</td></tr></thead><tbody><tr><td>1</td><td>y<sub>1</sub>, y<sub>2</sub> &larr; $R<sub>k</sub></td><td>1</td><td>y<sub>1</sub>, y<sub>2</sub> &larr; $R<sub>k</sub></td></tr><tr><td>2</td><td>u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub> &larr; $R<sub>k'</sub></td><td>2</td><td>u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub> &larr; $R<sub>k'</sub></td></tr><tr><td>3</td><td>r &larr; ay<sub>1</sub> + y<sub>2</sub></td><td>3</td><td>(f<sub>1</sub>, f<sub>2</sub>) &larr; (u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>) &middot; ck<sup>T</sup> + (0, r)</td></tr><tr><td>4</td><td>(f<sub>1</sub>, f<sub>2</sub>) &larr; (u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>) &middot; ck<sup>T</sup> + (0, r)</td><td>4</td><td>c &larr; H(f<sub>1</sub>, f<sub>2</sub>, m)</td></tr><tr><td>5</td><td>c &larr; H(f<sub>1</sub>, f<sub>2</sub>, m)</td><td>5</td><td>z<sub>1</sub> &larr; s<sub>1</sub>c + y<sub>1</sub></td></tr><tr><td>6</td><td>z<sub>1</sub> &larr; s<sub>1</sub>c + y<sub>1</sub></td><td>6</td><td>z<sub>2</sub> &larr; s<sub>2</sub>c + y<sub>2</sub></td></tr><tr><td>7</td><td>z<sub>2</sub> &larr; s<sub>2</sub>c + y<sub>2</sub></td><td>7</td><td>if z<sub>1</sub> or z<sub>2</sub> &notin; R<sub>k-&alpha;</sub> then</td></tr><tr><td>8</td><td>if z<sub>1</sub> or z<sub>2</sub> &notin; R<sub>k-&alpha;</sub> then</td><td>8</td><td>f<sub>1</sub>, f<sub>2</sub> &larr; $R</td></tr><tr><td>9</td><td>return (f<sub>1</sub>, f<sub>2</sub>)</td><td>9</td><td>Program H(f<sub>1</sub>, f<sub>2</sub>, m) = c</td></tr><tr><td>10</td><td>end</td><td>10</td><td>return (f<sub>1</sub>, f<sub>2</sub>)</td></tr><tr><td>11</td><td>return σ = (z<sub>1</sub>, z<sub>2</sub>, u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>, f<sub>1</sub>, f<sub>2</sub>, c)</td><td>11</td><td>end</td></tr><tr><td colspan="2"></td><td>12</td><td>return σ = (z<sub>1</sub>, z<sub>2</sub>, u<sub>1</sub>, u<sub>2</sub>, u<sub>3</sub>, f<sub>1</sub>, f<sub>2</sub>, c)</td></tr></tbody></table>

3. **return** 1 if $(\text{VERIFY}(\mathbf{a}, \mathbf{t}, m^*, \sigma^*) = 1$ and $(m^*, \sigma^*)$ has not been returned by the oracle $S_1$) 0 otherwise.

The difference between $G_1$ and $G_2$ lies in that the latter don't use the secret key anymore. Indeed the returned value of the random oracle $H$ is now chosen at random from the set $D_{\alpha}^n$, and that the acceptance in the rejection sampling is simulated by a Bernoulli trial of parameter $p_r$, that is the exact probability of getting a valid signature when signing honestly with the secret key. In the case of simulating an accepted signature, $z_1, z_2$ are generated at random in the space of accepted signature (i.e. $R_{k-\alpha}$). Then $r$ is recomputed from $z_1, z_2, t, c$ to satisfy the equation $r = az_1 + z_2 - tc = ay_1 + y_2$. From this value a commitment is constructed as in the real signature and the random oracle is programmed accordingly. Exactly like in appendix A.2, we can prove that the games $G_1$ and $G_2$ are then also computationally indistinguishable by the same hybrid argument involving an additional game where the key parameters are stretched. Eventually the exact same forking lemma-based argument concludes the proof by showing how to reduce the adversary to a distinguisher for the DCK problem, concluding the proof.

Under the hardness of both the DCK and R-LWE problems, the advantage of the attacker is therefore negligible. We can indeed show by indistinguishability that the advantage of the attacker in the first game is also negligible and then prove the EUF-CMA property of the signature scheme.

## B Masked r-GLP with commitment

The masking of the key generation remains the same with the additional generation of the public commitment key $ck$. For the signature, the commitment gadget (algorithm 30) is added. It is a matrix multiplication as showed in algorithm 30. The composition is then more complex and have more gadgets. The composition is in Figure 11. The whole signature is described in Algorithm 29.
<figure><img src="image_11.png" /><figcaption>Fig. 10. Signature oracle $S_2$</figcaption></figure>
<caption>**Algorithm 28:** GLP masked signature with commitment</caption>

**Data:** $m, pk = (\mathbf{a}, \mathbf{t})$, $sk = (\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{s}_{2,i})_{0\le i\le d}, ck$
**Result:** Signature $\sigma$
1 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{y}_{1,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$
2 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{y}_{2,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$
3 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{1,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$
4 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{2,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$
5 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{3,i})_{0\le i\le d} \leftarrow \text{DG}(k, d)$
6 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{r}_i)_{0\le i\le d} \leftarrow \text{H}^1(\vec{a}, (\mathbf{y}_{1,i})_{0\le i\le d}, (\mathbf{y}_{2,i})_{0\le i\le d})$
7 &nbsp;&nbsp;&nbsp;&nbsp;$$((\mathbf{f}_{1,i})_{0\le i\le d}, (\mathbf{f}_{2,i})_{0\le i\le d}) \leftarrow \text{Comm}((\mathbf{u}_{1,i})_{0\le i\le d}, (\mathbf{u}_{2,i})_{0\le i\le d}, (\mathbf{u}_{3,i})_{0\le i\le d}, (\mathbf{r}_i)_{0\le i\le d}, ck)$$
8 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{f}_1 \leftarrow \text{FullAdd}((\mathbf{f}_{1,i})_{0\le i\le d})$
9 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{f}_2 \leftarrow \text{FullAdd}((\mathbf{f}_{2,i})_{0\le i\le d})$
10 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{c} \leftarrow \text{hash}(\mathbf{f}_1, \mathbf{f}_2, m)$
11 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{z}_{1,i})_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{c}, (\mathbf{s}_{1,i})_{0\le i\le d}, (\mathbf{y}_{1,i})_{0\le i\le d})$
12 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{z}_{2,i})_{0\le i\le d} \leftarrow \text{H}^1(\mathbf{c}, (\mathbf{s}_{2,i})_{0\le i\le d}, (\mathbf{y}_{2,i})_{0\le i\le d})$
13 &nbsp;&nbsp;&nbsp;&nbsp;$\text{rs} \leftarrow \text{RS}((\mathbf{z}_{1,i})_{0\le i\le d}, (\tilde{\mathbf{z}}_{2,i})_{0\le i\le d}, k - \alpha)$
14 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{z}_{1,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{z}_{1,i})_{0\le i\le d})$
15 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{z}_{2,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{z}_{2,i})_{0\le i\le d})$
16 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{1,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{u}_{1,i})_{0\le i\le d})$
17 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{2,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{u}_{2,i})_{0\le i\le d})$
18 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathbf{u}_{3,i})_{0\le i\le d} \leftarrow \text{H}^2(\text{rs}, (\mathbf{u}_{3,i})_{0\le i\le d})$
19 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{z}_1 \leftarrow \text{FullAdd}((\mathbf{z}_{1,i})_{0\le i\le d})$
20 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{z}_2 \leftarrow \text{FullAdd}((\mathbf{z}_{2,i})_{0\le i\le d})$
21 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{u}_1 \leftarrow \text{FullAdd}((\mathbf{u}_{1,i})_{0\le i\le d})$
22 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{u}_2 \leftarrow \text{FullAdd}((\mathbf{u}_{2,i})_{0\le i\le d})$
23 &nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{u}_3 \leftarrow \text{FullAdd}((\mathbf{u}_{3,i})_{0\le i\le d})$
24 &nbsp;&nbsp;&nbsp;&nbsp;$\text{return } \sigma = (\mathbf{z}_1, \mathbf{z}_2, \mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3, \mathbf{c})$
<figure><img src="image_12.png" /><figcaption>Fig. 11. Composition of commitment GLP Sign</figcaption></figure>
**Algorithm 29: Comm**

**Data:** $(\mathbf{u}_{1,i})_{0\le i\le d}, (\mathbf{u}_{2,i})_{0\le i\le d}, (\mathbf{u}_{3,i})_{0\le i\le d}, (\mathbf{r}_i)_{0\le i\le d}, ck$

**Result:** $(\mathbf{f}_{1,i})_{0\le i\le d}, (\mathbf{f}_{2,i})_{0\le i\le d}$

1. $((\mathbf{f}_{1,i})_{0\le i\le d}, (\mathbf{f}_{2,i})_{0\le i\le d}) \leftarrow 0^{2d}$

2. **for** $i = 0, ..., d+1$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{f}_{1,i} \leftarrow ck_{1,1}\mathbf{u}_{1,i} + ck_{1,2}\mathbf{u}_{2,i} + ck_{1,3}\mathbf{u}_{3,i}$

4. &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{f}_{2,i} \leftarrow ck_{2,1}\mathbf{u}_{1,i} + ck_{2,2}\mathbf{u}_{2,i} + ck_{2,3}\mathbf{u}_{3,i} + \mathbf{r}_i$

5. **end**

6. **return** $(\mathbf{f}_{1,i})_{0\le i\le d}, (\mathbf{f}_{2,i})_{0\le i\le d}$

**Lemma 16.** *The gadget Comm is d-NI.*

*Proof.* Let $\delta \le d$ be the number of observations made by the attacker. The proof consists in filling an empty set $\mathbf{I}$ with at most $\delta$ indices in $[0, d]$ such that the distribution of any tuple $(\mathbf{v}_1, ..., \mathbf{v}_\delta)$ of intermediate variables of the block can be perfectly simulated from the sensitive values

$$ (\mathbf{u}_{1,i}, \mathbf{u}_{2,i}, \mathbf{u}_{3,i}, \mathbf{r}_i)_{i \in \mathbf{I}} \qquad (1) $$

For each observation $\mathbf{v}_h$, $(h \in [0, \delta])$, we add the corresponding index $i$ in $\mathbf{I}$. After having built $\mathbf{I}$, every intermediate value $\mathbf{v}_h$ is simulated by the direct computation from $\mathbf{u}_{1,i}, \mathbf{u}_{2,i}, \mathbf{u}_{3,i}, \mathbf{r}_i$ and the public value $ck$.

At the end, any set of $\delta \le d$ intermediate variables can be perfectly simulated with at most $\delta$ shares of each sensitive input. This is enough to prove that Comm is d-NI.

□

**Theorem 6.** *MASKED-GLP sign with commitment is still d-NI.o.*

*Proof.* From Lemmas 6,7, 9 and 16 Algorithms DG, RS, $H^1$, $H^2$ and Comm are all d-NI. From Lemma 8, FullAdd is d-NI.o.

Let us assume that an attacker has access to $\delta \le d$ observations on the whole signature scheme. Then, we want to prove that all these $\delta$ observations can be perfectly simulated with at most $\delta$ shares of each secret among $\mathbf{y}_1, \mathbf{y}_2, \mathbf{s}_1, \mathbf{s}_2, \mathbf{u}_1, \mathbf{u}_2$ and $\mathbf{u}_3$ and the public values. With such a result, the signature scheme is then secure in the $d$-probing model since no set of at most $d$ observations would give information on the secret values.

In the following, we consider this distribution of the attacker's $\delta$ observations:

- $\delta_1$ (resp. $\delta_2, \delta_3, \delta_4, \delta_5$) on the instance of DG that produces shares of $\mathbf{y}_1$ (resp. $\mathbf{y}_2, \mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3$)

- $\delta_6$ on $H^1$,

- $\delta_7$ on Comm,

- $\delta_8$ (resp. $\delta_9$) on FullAdd of $\mathbf{f}_1$ (resp. $\mathbf{f}_2$),

- $\delta_{10}$ (resp. $\delta_{11}$) on $H^1$ which produces $\mathbf{z}_1$ (resp. $\mathbf{z}_2$),

- $\delta_{12}$ on the instance of RS,

- $\delta_{13}$ (resp. $\delta_{14}, \delta_{15}, \delta_{16}, \delta_{17}$) on $H^2$ applied on $\mathbf{z}_1$ (resp. $\mathbf{z}_2, \mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3$),

- $\delta_{18}$ (resp. $\delta_{19}, \delta_{20}, \delta_{21}, \delta_{22}$) on FullAdd of $\mathbf{z}_1$ (resp. $\mathbf{z}_2, \mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3$)
Some other observations can be made on the *Hash* function, their number won't matter during
the proof. Finally, we have $\sum_{i=1}^{22} \delta_i \le \sum_{i=1}^{22} + \delta_{Hash} \le \delta$.

Now, we build the proof from right to left as follows.

The five last FullAdd blocks are d-NI, then all the observations performed during the execution of FullAdd on z₁ (resp. z₂, u₁,u₂,u₃) can be perfectly simulated with at most δ₁₈ (resp. δ₁₉,δ₂₀,δ₂₁,δ₂₂) shares of z₁ (resp. z₂, u₁,u₂,u₃).

H² is d-NI, then all the observations from the call of H² on z₁ (resp. z₂, u₁,u₂,u₃) can be
perfectly simulated with δ₁₃ + δ₁₈ (resp. δ₁₄ + δ₁₉, δ₁₅ + δ₂₀, δ₁₆ + δ₂₁, δ₁₇ + δ₂₂) shares of the
sensitive input z₁ (resp. z₂, u₁, u₂, u₃).

RS is d-NI and do not return any sensitive element, then all the observations performed in
gadget RS can be perfectly simulated with at most δ₁₂ shares of z₁ and z₂. So, after H¹, the
observations can be simulated with δ₁₂ + (δ₁₃ + δ₁₈) shares of z₁ and δ₁₂ + (δ₁₄ + δ₁₉) shares
of z₂.

H¹ is d-NI as well, thus all the observations from the call of H¹ on y₁ can be perfectly
simulated with δ₁₀+δ₁₂+δ₁₃+δ₁₈ ≤ δ shares of y₁ and s₁. Respectively, on y₂, the observations
can be perfectly simulated from δ₁₁ + δ₁₂ + δ₁₄ + δ₁₉ ≤ δ shares of y₂ and s₂.

Both first left FullAdd gadget are d-NIo and do not return any sensitive element, then all the
observations performed from this gadget can be perfectly simulated with at most δ₈ (resp. δ₉)
shares of f₁ (resp. f₂).

The gadget Comm is also d-NI, then all the observations performed after this gadget can be
perfectly simulated with $\delta_7 + \delta_8 + \delta_9$ shares of $\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3$ and $\mathbf{r}$.

The left H¹ gadget is d-NI, thus all the observations from its call can be perfectly simulated
with at most $\delta_6 + \delta_7 + \delta_8 + \delta_9$ shares of each one of the inputs $y_1$ and $y_2$.

DG is also d-NI, thus we need to ensure that the number of reported observations does not
exceed $\delta$ for $y_1, y_2, u_1, u_2$ and $u_3$.

On one hand, at the end of DG for $y_1, y_2$, the simulation relies on $(\delta_6 + \delta_7 + \delta_8 + \delta_9) + (\delta_{10} + \delta_{12} + \delta_{13} + \delta_{18}) \le \delta$ shares of $y_1$ and $(\delta_6 + \delta_7 + \delta_8 + \delta_9) + (\delta_{11} + \delta_{12} + \delta_{14} + \delta_{19}) \le \delta$ shares of $y_2$.
With the additional $\delta_1$ (resp. $\delta_2$) observations performed on the first (resp. the second) instance of DG, the number of observations remains below $\delta$.

On the other hand, at the end of DG for $u_1, u_2$ and $u_2$, the simulation relies on $(\delta_8 + \delta_9) + (\delta_{15} + \delta_{20}) \le \delta$ shares of $u_1$, $(\delta_8 + \delta_9) + (\delta_{16} + \delta_{21}) \le \delta$ shares of $u_2$ and $(\delta_8 + \delta_9) + (\delta_{17} + \delta_{22}) \le \delta$ shares of $u_3$. With the additional $\delta_3$ (resp. $\delta_4, \delta_5$) observations performed on the DG on $u_1$ (resp. $u_2, u_2$), the number of observations remains below $\delta$ which is sufficient to ensure security of the whole scheme in the d-probing model.

□

References

1. M. Abdalla, J. H. An, M. Bellare, and C. Namprempre. From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security. In L. R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 418–433. Springer, Heidelberg, Apr. / May 2002.

2. D. F. Aranha, S. Berndt, T. Eisenbarth, O. Seker, A. Takahashi, L. Wilke, and G. Zaverucha. Side-channel protections for picnic signatures. IACR TCHES, 2021(4):239–282, 2021. https://tches.iacr.org/index.php/TCHES/article/view/9066.
3. S. Bai and S. D. Galbraith. An improved compression technique for signatures based on learning with errors. In J. Benaloh, editor, *CT-RSA 2014*, volume 8366 of LNCS, pages 28–47. Springer, Heidelberg, Feb. 2014.

4. G. Barthe, S. Belaïd, F. Dupressoir, P.-A. Fouque, B. Grégoire, and P.-Y. Strub. Verified proofs of higher-order masking. In E. Oswald and M. Fischlin, editors, *EUROCRYPT 2015, Part I*, volume 9056 of LNCS, pages 457–485. Springer, Heidelberg, Apr. 2015.

5. G. Barthe, S. Belaïd, F. Dupressoir, P.-A. Fouque, B. Grégoire, P.-Y. Strub, and R. Zucchini. Strong non-interference and type-directed higher-order masking. In E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi, editors, *ACM CCS 2016*, pages 116–129. ACM Press, Oct. 2016.

6. G. Barthe, S. Belaïd, T. Espitau, P.-A. Fouque, B. Grégoire, M. Rossi, and M. Tibouchi. Masking the GLP lattice-based signature scheme at any order. In J. B. Nielsen and V. Rijmen, editors, *EU-ROCRYPT 2018, Part II*, volume 10821 of LNCS, pages 354–384. Springer, Heidelberg, Apr. / May 2018.

7. G. Barthe, S. Belaïd, T. Espitau, P.-A. Fouque, M. Rossi, and M. Tibouchi. GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In L. Cavallaro, J. Kinder, X. Wang, and J. Katz, editors, *ACM CCS 2019*, pages 2147–2164. ACM Press, Nov. 2019.

8. C. Baum, I. Damgård, S. Oechsner, and C. Peikert. Efficient commitments and zero-knowledge protocols from Ring-SIS with applications to lattice-based threshold cryptosystems. Cryptology ePrint Archive, Report 2016/997, 2016. http://eprint.iacr.org/2016/997.

9. M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In A. Juels, R. N. Wright, and S. De Capitani di Vimercati, editors, *ACM CCS 2006*, pages 390–399. ACM Press, Oct. / Nov. 2006.

10. N. Bindel, J. A. Buchmann, and J. Krämer. Lattice-based signature schemes and their sensitivity to fault attacks. In P. Maurine and M. Tunstall, editors, *FDTC 2016*, pages 63–77. IEEE Computer Society, 2016.

11. J. W. Bos, M. Gourjon, J. Renes, T. Schneider, and C. van Vredendaal. Masking kyber: First- and higher-order implementations. *IACR TCHES*, 2021(4):173–214, 2021. https://tches.iacr.org/index.php/TCHES/article/view/9064.

12. C. Boschini, A. Takahashi, and M. Tibouchi. MuSig-L: Lattice-based multi-signature with single-round online phase. Cryptology ePrint Archive, Report 2022/1036, 2022. https://eprint.iacr.org/2022/1036.

13. L. G. Bruinderink, A. Hülsing, T. Lange, and Y. Yarom. Flush, gauss, and reload - A cache attack on the BLISS lattice-based signature scheme. In B. Gierlichs and A. Y. Poschmann, editors, *CHES 2016*, volume 9813 of LNCS, pages 323–345. Springer, Heidelberg, Aug. 2016.

14. S. Chari, J. R. Rao, and P. Rohatgi. Template attacks. In B. S. Kaliski Jr., Çetin Kaya. Koç, and C. Paar, editors, *CHES 2002*, volume 2523 of LNCS, pages 13–28. Springer, Heidelberg, Aug. 2003.

15. A. Chopra. GLYPH<150>A new insantiation of the GLP digital signature scheme. Cryptology ePrint Archive, Report 2017/766, 2017. http://eprint.iacr.org/2017/766.

16. A. Chopra. Software implementation of GLYPH<150>A. GitHub repository, 2017. https://github.com/quantumsafelattices/glyph.

17. J.-S. Coron. Higher order masking of look-up tables. In P. Q. Nguyen and E. Oswald, editors, *EURO-CRYPT 2014*, volume 8441 of LNCS, pages 441–458. Springer, Heidelberg, May 2014.

18. J.-S. Coron. High-order conversion from Boolean to arithmetic masking. Cryptology ePrint Archive, Report 2017/252, 2017. https://eprint.iacr.org/2017/252.

19. J.-S. Coron, F. Gérard, S. Montoya, and R. Zeitoun. High-order table-based conversion algorithms and masking lattice-based encryption. 2022(2):1–40, 2022. https://tches.iacr.org/index.php/TCHES/article/view/9479.

20. J.-S. Coron, F. Gérard, M. Trannoy, and R. Zeitoun. High-order masking of NTRU. Cryptology ePrint Archive, Report 2022/1188, 2022. https://eprint.iacr.org/2022/1188.

21. J.-S. Coron, J. Großschädl, M. Tibouchi, and P. K. Vadnala. Conversion from arithmetic to Boolean masking with logarithmic complexity. In G. Leander, editor, *FSE 2015*, volume 9054 of LNCS, pages 130–149. Springer, Heidelberg, Mar. 2015.
22. J.-S. Coron, J. Großschädl, and P. K. Vadnala. Secure conversion between Boolean and arithmetic masking of any order. In L. Batina and M. Robshaw, editors, CHES 2014, volume 8731 of LNCS, pages 188–205. Springer, Heidelberg, Sept. 2014.

23. I. Damgård, C. Orlandi, A. Takahashi, and M. Tibouchi. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. In J. Garay, editor, PKC 2021, Part I, volume 12710 of LNCS, pages 99–130. Springer, Heidelberg, May 2021.

24. I. Damgård, C. Orlandi, A. Takahashi, and M. Tibouchi. Two-round *n*-out-of-*n* and multi-signatures and trapdoor commitment from lattices. 35(2):14, Apr. 2022.

25. A. Duc, S. Dziembowski, and S. Faust. Unifying leakage models: From probing attacks to noisy leakage. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 423–440. Springer, Heidelberg, May 2014.

26. L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal Gaussians. In R. Canetti and J. A. Garay, editors, CRYPTO 2013, Part 1, volume 8042 of LNCS, pages 40–56. Springer, Heidelberg, Aug. 2013.

27. L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehle. CRYSTALS – Dilithium: Digital signatures from module lattices. Cryptology ePrint Archive, Report 2017/633, 2017. https://eprint.iacr.org/2017/633.

28. T. Espitau, P.-A. Fouque, B. Gérard, and M. Tibouchi. Loop-abort faults on lattice-based Fiat-Shamir and hash-and-sign signatures. In R. Avanzi and H. M. Heys, editors, SAC 2016, volume 10532 of LNCS, pages 140–158. Springer, Heidelberg, Aug. 2016.

29. T. Espitau, P.-A. Fouque, B. Gérard, and M. Tibouchi. Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, ACM CCS 2017, pages 1857–1874. ACM Press, Oct. / Nov. 2017.

30. T. Espitau, P.-A. Fouque, F. Gérard, M. Rossi, A. Takahashi, M. Tibouchi, A. Wallet, and Y. Yu. Mitaka: A simpler, parallelizable, maskable variant of falcon. In O. Dunkelman and S. Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, pages 222–253. Springer, Heidelberg, May / June 2022.

31. M. Fukumitsu and S. Hasegawa. A lattice-based provably secure multisignature scheme in quantum random oracle model. In K. Nguyen, W. Wu, K.-Y. Lam, and H. Wang, editors, ProvSec 2020, volume 12505 of LNCS, pages 45–64. Springer, Heidelberg, Nov. / Dec. 2020.

32. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In R. E. Ladner and C. Dwork, editors, 40th ACM STOC, pages 197–206. ACM Press, May 2008.

33. F. Gérard and M. Rossi. An efficient and provable masked implementation of qtesla. In S. Belaïd and T. Güneysu, editors, Smart Card Research and Advanced Applications - 18th International Conference, CARDIS 2019, Prague, Czech Republic, November 11-13, 2019, Revised Selected Papers, volume 11833 of Lecture Notes in Computer Science, pages 74–91. Springer, 2019.

34. S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281–308, 1988.

35. T. Güneysu, V. Lyubashevsky, and T. Pöppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems. In E. Prouff and P. Schaumont, editors, CHES 2012, volume 7428 of LNCS, pages 530–547. Springer, Heidelberg, Sept. 2012.

36. Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In D. Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 463–481. Springer, Heidelberg, Aug. 2003.

37. V. Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In M. Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 598–616. Springer, Heidelberg, Dec. 2009.

38. V. Lyubashevsky. Lattice signatures without trapdoors. In D. Pointcheval and T. Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 738–755. Springer, Heidelberg, Apr. 2012.
39. V. Migliore, B. Gérard, M. Tibouchi, and P.-A. Fouque. Masking Dilithium - efficient implementation and side-channel evaluation. In R. H. Deng, V. Gauthier-Umaña, M. Ochoa, and M. Yung, editors, *ACNS 19*, volume 11464 of LNCS, pages 344–362. Springer, Heidelberg, June 2019.

40. T. Oder, T. Schneider, T. Pöppelmann, and T. Güneysu. Practical CCA2-secure and masked ring-LWE implementation. *Cryptology ePrint Archive, Report 2016/1109*, 2016. https://eprint.iacr.org/2016/1109.

41. P. Pessl, L. G. Bruinderink, and Y. Yarom. To BLISS-B or not to be: Attacking strongSwan's implementation of post-quantum signatures. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, *ACM CCS 2017*, pages 1843–1855. ACM Press, Oct. / Nov. 2017.

42. T. Pöppelmann, L. Ducas, and T. Güneysu. Enhanced lattice-based signatures on reconfigurable hardware. In L. Batina and M. Robshaw, editors, *CHES 2014*, volume 8731 of LNCS, pages 353–370. Springer, Heidelberg, Sept. 2014.

43. O. Reparaz, R. de Clercq, S. S. Roy, F. Vercauteren, and I. Verbauwhede. Additively homomorphic Ring-LWE masking. In T. Takagi, editor, *PQCrypto 2016*, volume 9606 of LNCS, pages 233–244. Springer, 2016.

44. O. Reparaz, S. S. Roy, F. Vercauteren, and I. Verbauwhede. A masked ring-LWE implementation. In T. Güneysu and H. Handschuh, editors, *CHES 2015*, volume 9293 of LNCS, pages 683–702. Springer, Heidelberg, Sept. 2015.

45. M. Rivain and E. Prouff. Provably secure higher-order masking of AES. In S. Mangard and F.-X. Standaert, editors, *CHES 2010*, volume 6225 of LNCS, pages 413–427. Springer, Heidelberg, Aug. 2010.

46. T. Schneider, C. Paglialonga, T. Oder, and T. Güneysu. Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto. In D. Lin and K. Sako, editors, *PKC 2019, Part II*, volume 11443 of LNCS, pages 534–564. Springer, Heidelberg, Apr. 2019.