Raccoon: A Masking-Friendly Signature Proven in the Probing Model

In the past decade, post-quantum cryptography has reached quickly grown from a mostly theoretical field to one with sufficient maturity to be deployed on a wide scale. This is epitomized by NIST’s standardization in 2020 of the hash-based signatures XMSS and LMS, as well as its announcement in 2022 of the future standardization of the lattice-based KEM Kyber, the lattice-based signatures Dilithium and Falcon, and the hash-based signature SPHINCS+. Whilst the efficiency profiles and black-box security of these schemes are well-understood, resistance against side-channel attacks remains a weak spot.

Side-Channel Attacks. In a side-channel attack (SCA), an attacker can learn information about the physical execution of an algorithm, such as its running time or its effect on the power consumption, electromagnetic or acoustic emission of the device running it. This information can then be leveraged to recover sensitive information, for example, cryptographic keys.

SCAs can be devastating against cryptographic implementations, and post-quantum schemes are no exception. See Sect. 1.3 for references of concrete SCAs against Dilithium.

Masking. The main countermeasure against side-channel attacks is masking [27]. It consists of splitting sensitive information in d shares (concretely: \(x = x_0 + \dots + x_{d-1}\)), and performing secure computation using MPC-based techniques. Masking provides a trade-off between efficiency and SCA resistance: the computational efficiency of the implementation is reduced by a polynomial factor in d, but the cost of a side-channel attack is expected to grow exponentially [19, 28].

Unfortunately, lattice-based signatures contain subroutines that are extremely expensive to mask, such as (a) sampling from a small set, (b) bit-decomposition, and (c) rejection sampling. Currently, the best known ways to perform these operations is to rely on mask conversions [13, 26], which convert between arithmetic and boolean masking. This typically incurs an overhead \(O(d^2 \log q)\) [14] or \(O(2^{d/2})\) [11], and quickly becomes the efficiency bottleneck. As an illustration, the only publicly available masked implementation of Dilithium [12] is 53 (resp. 200) times slower than unmasked Dilithium for \(d = 2\) (resp. \(d=4\)).

Masking-Friendly Schemes. In order to overcome these limitations, a natural research direction is to design lattice-based signatures that are naturally amenable to masking. However, this is easier said than done. The few designs that exist have either been shown insecure or lack a formal security proof, see Sect. 1.3 for a more detailed discussion. Thus having a masking-friendly signature with a formal proof has been an elusive goal.

1.1 Our Contributions

We propose Raccoon, a masking-friendly signature, and provide a formal security proof in the t-probing model [27]. While Raccoon is inspired from the similarly named scheme from [17], we have heavily modified its design in order to make it more efficient and provable secure under standard assumptions. The design presented in this paper is exactly the same as the one submitted to the NIST on-ramp standardization campaign [16].

Blueprint. Raccoon is based on the “Lyubashevsky signature without aborts” blueprint, also found in works on threshold signatures [1], and which we recall below. Assume the public key \(\textsf{vk}\) is a Learning With Errors (LWE) sample \(\left( \textbf{A}, \textbf{t} = [\begin{array}{cc}\textbf{A} & \textbf{I}\end{array}] \cdot \textbf{s} \right) \), where \(\textbf{s}\) is a small vector, \(\textbf{I}\) is the identity matrix and \(\textbf{A}\) is a uniform matrix (precise definitions will be provided later in the paper). Signing proceeds as follows:

1. (S1)

   Sample \(\textbf{r}\), compute a commitment \(\textbf{w} = \begin{bmatrix} \textbf{A} & \textbf{I} \end{bmatrix} \cdot \textbf{r}\);

2. (S2)

   Compute a challenge \(c = H(\textbf{w}, \textsf{vk}, \textsf{msg})\);

3. (S3)

   Compute a response \(\textbf{z} = \textbf{s} \cdot c + \textbf{r}\).

The verification procedure checks that \(H(\textbf{A} \cdot \textbf{z} - \textbf{t} \cdot c, \textsf{vk}, \textsf{msg}) = c\) and that \(\textbf{z}\) is short. Using a Rényi divergence argument, we can argue security if the modulus q grows as the square root of the number of queries \({Q_s} \), that is \(q = \Omega ( \sqrt{{Q_s}} )\). By eliminating the need for rejection sampling, this sidesteps the issue of masking it. In addition, unlike in Dilithium, the security argument does not rely on bit-decomposition. This eliminates the need to mask bit-dropping, which we now employ purely for efficiency reasons. We note that our final modulus has 49 bits, which is larger than the standard precision (32-bit or less) on many embedded platforms. We mitigate this by taking \(q = q_1 \cdot q_2\), where \(q_1\) and \(q_2\) are 24-bit and 25-bit NTT-friendly prime moduli.

We note that rejection sampling in Dilithium requires a smaller modulus \(q = \Omega ( \dim ( \textbf{s}))\), in practice \(\log q \approx 23\) in Dilithium. Our design choice entails a trade-off between compactness (Dilithium) and ease of masking (Raccoon).

The Problem with Gaussians. Standard Rényi divergence arguments as in [1] require \(\textbf{r}\) to be sampled from a discrete Gaussian distribution. However, Gaussians are notoriously difficult to generate in a way that is robust to SCA. The most common method for sampling Gaussians in a constant-time manner is via probability distribution tables (PDT), see for example FrodoKEM [35] or Falcon [38]. For signatures, the PDT would require a precision \(p \approx \log ({Q_s})\), for example Falcon takes \(p = 72\). Masking this step would incur a prohibitive overhead \(O(d^2 \log q)\). Similarly, all other existing sampling methods (see e.g. “Related works” in [25]) comprise at least one step that is expensive to mask. We could use Gaussians, and from a purely theoretic perspective the security proof would go through, but from a practical point of view this would show little relevance to the real-world issues that masking is trying to solve in the first place.

Sums of Uniforms. Our solution is to pick a distribution that has Gaussian-style properties, but is easier to sample securely on embedded devices. As it turns out, sampling \(\textbf{r}\) as a sum of uniform variates (over a small set) produces remarkably Gaussian-like distributions, which is unsurprising and a straightforward consequence of the central limit theorem. Unfortunately, standard Rényi divergence arguments fail for these distributions since they have finite support.

We resolve this analytical issue by introducing the smooth Rényi divergence, a more robust generalization of the Rényi divergence that is able to provide cryptographically useful statements about sums of uniform distributions. We define it as a simple combination of the statistical distance and the Rényi divergence. This generalisation achieves the best of both worlds: the robustness of the statistical distance and the power of the Rényi divergence.

Probing-resilient sampling via \(\textsf{AddRepNoise}\). Now that we have identified a suitable distribution (that is, sum of uniforms) for \(\textbf{r}\), the final step is to sample it in a way that is resilient to t-probing adversaries. A naive approach would be to sample in parallel each share \(\textbf{r}_i\) of \(\llbracket \textbf{r} \rrbracket \) as the sum of \(\textsf{rep} \) small uniform variates, so that \(\textbf{r}\) is the sum of \(d \cdot \textsf{rep} \) small uniform variates. However, a probing adversary is allowed to probe \(t \le d - 1\) individual shares \(\textbf{r}_i\). This would reduce the standard deviation of the conditional distribution of \(\textbf{r}\) by a factor \(\sqrt{d}\), and lead to worse parameters.

We resolve this by proposing a new algorithm, called \(\textsf{AddRepNoise}\) , which interleaves (a) parallel generation of individual noises and (b) refreshing the masked vector, and repeats this \(\textsf{rep} \) times. We can formally prove that a t-probing adversary only learns t individual uniform variates, so that the standard deviation of \(\textbf{r}\) conditioned to these variates is the sum of \(d \cdot \textsf{rep}- d + 1\) uniform variates, which allows to prove security with a minimal loss in tightness.

1.2 Overview of the Security Proof

We recall that a high-level description of Raccoon is given in Sect. 1.1. Now, in a masked form, the secret is shared as \(\textbf{s} = \sum _{i \in [d]} \textbf{s}_i\) where the coefficients of the vectors \(\textbf{s}_i\) are sampled in a short interval. This is a deliberate choice of \(\mathsf {\text {Raccoon}}\) that allows good sampling performance.

At first sight, if the \(\textbf{s}_i\) are safely manipulated in the signature algorithm and never recombined, the masking security seems guaranteed as the exact value of \(\textbf{s}\) cannot be recombined. However, if an adversary probes \(d-1\) shares of \(\textbf{s}_i\), say \(\{ \textbf{s}_0, \cdots , \textbf{s}_{d-2} \}\), he can compute \(\textsf{vk} ' = \textsf{vk}- \begin{bmatrix} \textbf{A} & \textbf{I} \end{bmatrix}\sum _{i=0}^{d-2} \cdot \textbf{s}_i = \begin{bmatrix} \textbf{A} & \textbf{I} \end{bmatrix} \textbf{s}_{d-1}\). Key recovery is significantly easier as the updated secret is now from a narrower distribution. Hence, while the exact value of \(\textbf{s}\) is inaccessible, the knowledge of the probes combined with the knowledge of the public key can lead to a simpler key recovery. This aspect makes a link between two families of proofs that are typically separated in other works: the black-box game-based \(\textsf{EUF}\text {-}\textsf{CMA}\) proofs and the simulation proofs of masking. The former quantifies the advantage of a black-box attacker and provides a security statement conditioned to the hardness of well-defined mathematical problems (like LWE). The latter provides a statistical statement showing that any probing attacker limited to \(d-1\) probes have no statistical advantage to recover the sensitive information (Fig. 1).

To prove the security of \(\mathsf {\text {Raccoon}}\), it is important to link these two notions. For that, we detail and formalize the probing security from a game-base perspective, i.e. with well-defined simulators and reuse the notion of probing \(\textsf{EUF}\text {-}\textsf{CMA}\) provided in [5]. Such a notion has been defined but it was not formally used in a game-based proof before. The main contribution of this paper is the proof of the probing \(\textsf{EUF}\text {-}\textsf{CMA}\) security of \(\mathsf {\text {Raccoon}}\). It will consist in several steps.

1. 1.

   Non-uniform masks and sNIU: First, one needs to handle the sensitive small uniforms that are deviating from the classical ISW model [27] and other masking proof techniques [4]. For that, all the small uniforms will not be considered as a sharing of a secret value but as several random coins provided in input. The notion of \(\textsf{sNIU}\) introduced in [20] (detailed later on in the paper) will come handy. That way, we will be able to prove the masking security of the key generation and signature algorithm when the small uniforms are provided as inputs in Sect. 6.

2. 2.

   Reduction from t-probing \(\textsf{EUF}\text {-}\textsf{CMA}\) to standard \(\textsf{EUF}\text {-}\textsf{CMA}\) : Next, we will use this probe simulation property offered by the \(\textsf{NIU}\) model (cf. Lemma 5.2) as part of a game based proof in the probing-\(\textsf{EUF}\text {-}\textsf{CMA}\) security model. Through a sequence of games, we prove that the probing-\(\textsf{EUF}\text {-}\textsf{CMA}\) security of \(\mathsf {\text {Raccoon}}\) reduces on the black-box-\(\textsf{EUF}\text {-}\textsf{CMA}\) of a different version of \(\mathsf {\text {Raccoon}}\) with smaller noise distributions, called small \(\mathsf {\text {Raccoon}}\). This reduction lets us include the probing adversary in the attack and reduce to a standard (non probing) \(\textsf{EUF}\text {-}\textsf{CMA}\) adversary. This proof is presented in Sect. 7.

3. 3.

   Unforgeability and smooth Rényi divergence: Finally, the proof concludes with the black-box security of small \(\mathsf {\text {Raccoon}}\). Such a proof is close to existing \(\textsf{EUF}\text {-}\textsf{CMA}\) proofs of signatures following the Fiat–Shamir with aborts framework with a significative difference. To allow a complete end-to-end proof, we avoid any heuristic assessments and introduce the notion of smooth Rényi divergence for obtaining provable and tighter parameters. This proof is presented in Sect. 7.3.

In Sect. 8, we instantiate the parameters to valid our proof and confirm that the current NIST submission is secure.

1.3 Related Works

SCA Against Dilithium. Several side-channel attacks against post-quantum schemes have been published. For concision, we only mention those related to Dilithium, which shares similarities with Raccoon. Since its initial publication, a string of increasingly practical side-channel attacks have been proposed against unprotected implementations of Dilithium: see for example [8, 9, 22, 29, 32, 39, 40].

Masking Lattice Schemes. The formal study of masking lattice-based signatures has been initiated by Barthe et al. [5], which studied the GLP signature. Since then, BLISS [6] and qTESLA [23] have also been studied from a masking perspective. Masked implementations of Dilithium have been proposed in [3, 12, 34].

Masking-Friendly Signatures. A few masking-friendly signatures have been proposed in the past two years.

• Mitaka. Espitau et al. [21] proposed the Mitaka scheme, a masking-friendly variant of Falcon. A flaw in the security proof of Mitaka, as well as a practical attack in the t-probing model, was later demonstrated by Prest [37].

• IEEE SP Raccoon. At IEEE S&P 2023, del Pino et al. [17] presented a lattice-based masking-friendly signature, also called Raccoon. Our scheme is a conceptual descendent of the scheme from [17], with significant improvements. While both versions of Raccoon are Fiat-Shamir lattice-based signatures, the security proof of [17] relies on several heuristic arguments, and the scheme itself is less compact than ours due to the use of a variant of uniform secret LWR. In comparison, our design is more streamlined, more compact, relies on standard assumptions and has a formal security proof.

• Plover. Since the original publication of Raccoon as a NIST candidate [16], Esgin et al. [20] have proposed Plover, a signature scheme heavily inspired from our scheme, including the use of \(\textsf{AddRepNoise}\). The key insight of Plover is to realize that our techniques are not limited to Fiat-Shamir signatures, and can also be applied in a hash-then-sign setting. Conversely, [20] introduced the \(\textsf{NIU}\) notion, a useful abstraction that we re-use in our analysis.

We provide the minimal set of preparation. We refer the readers to the full version for more details. First, let us prepare some notations. We note \(\mathbb {N}\) the set of non-negative integers, including zero. Given \(n \in \mathbb {N}\), we denote by [n] the set \(\{0, 1, \dots , n - 1 \}\). Let \(f : X \rightarrow Y\) be a function, and \(x \in X\). When f is deterministic, we use the notation \(y\, {:}{=}\,f(x)\) to indicate that we assign the output of f(x) to y. When f is randomized, we instead use the notation \(y \leftarrow f(x)\). From a programming viewpoint, both of these notations indicate an assignment of the result to the variable on the left. Given a probability distribution \(\mathcal {D}\) over Y, we note \(y \leftarrow \mathcal {D}\) to express that \(y \in Y\) is sampled from \(\mathcal {D}\).

2.1 Hardness Assumptions

The security of Raccoon is based on the Module Learning with Errors (\(\textsf{MLWE} \)) and Module Short Integer Solutions (\(\textsf{MSIS} \)) assumptions. More precisely, we rely on the Self Target \(\textsf{MSIS} \) (\(\textsf{SelfTargetMSIS} \)) problem, a variant of the \(\textsf{MSIS} \) problem, where the problem is defined relative to some hash function modeled as a random oracle. This assumption also underlies the security of Dilithium.

2.2 Masking Preliminaries

We consider all operations and variables used in algorithms to be over the scalar ring \(\mathcal {R}_q\) (i.e. we consider that basic operations are done directly on polynomials in \(\mathcal {R}_q\)), this entails that we consider that probes leak full polynomials in \(\mathcal {R}_q\) and not bits or even coefficients (leading to a stronger attacker model). An algorithm is defined as a sequence of gadget calls, each gadget being a sequence of (probabilistic or deterministic) assignments of expressions to local variables.

Well-Formed Gadgets. We say a gadget is well-formed if it is written in SSA (single static assignment) form, i.e. if its scalar variables appear at most once on the left-hand side of an assignment, and if all assignments are three-address code instructions, i.e. of the form \(a=b*c\) with \(*\) an operator. These restrictions ensure that all intermediate values are captured by local variables at some point in the code. An algorithm is well formed if in all gadget calls \(\textbf{b} = G(\textbf{x}_1,\ldots ,\textbf{x}_k)\) the variables \(\textbf{b},\textbf{x}_1,\ldots ,\textbf{x}_k\) are pairwise disjoint. While some algorithms we provide are not well formed (e.g., Algorithms 1 and 2), it is clear that this can be easily remedied by indexing variables and adding new local variables.

We use the notation \(\llbracket \textbf{x} \rrbracket = (\textbf{x}_i)_{i \in [d]}\) to denote a tuple of \(d\) values in \(\mathcal {R}_q\), which implicitly defines the value \(\textbf{x}=\sum _0^{d-1}\textbf{x}_i\in \mathcal {R}_q\). This notation is used to express that the secret value \(\textbf{x}\) is shared as \(d\) additive shares as the encoding \(\llbracket \textbf{x} \rrbracket \).

Variables’ Values and Names. We will distinguish variables (designated by a binary string representing their name) from the values they take (in the scalar ring \(\mathcal {R}_q\)), all objects pertaining to variables (singular variables, vectors, sets, etc.) will have a name with a bar (e.g. \(\bar{x}\in \left\{ 0,1 \right\} ^*\), \({\bar{\mathcal {V}} }\subset \left\{ 0,1 \right\} ^*\)), while the corresponding value will not (e.g. \(x\in \mathcal {R}_q\)).

For a gadget G we define the local variables of G as \({\bar{\mathcal {V}} }_G\subset \left\{ 0,1\right\} ^*\) (noted \({\bar{\mathcal {V}} }\) when the gadget is clear from the context), since all variables are assigned only once we can match the position of a variable with its name. For a program P with input scalar variables \((\bar{a}_1,\ldots ,\bar{a}_N)\) that calls the gadgets \(G_1,\ldots ,G_k\), (with \(N,k\in \mathbb {N}\)), we will consider the set of variables \({\bar{\mathcal {V}} }_P=\left\{ \bar{a}_1,\ldots ,\bar{a}_N\right\} \biguplus {\bar{\mathcal {V}} }_{G_1}\biguplus \ldots \biguplus {\bar{\mathcal {V}} }_{G_k}\) (where the local variables of \(G_i\) are additionally labelled with i to differentiate between gadgets and \(\biguplus \) is the disjoint union). Note that since all gadgets are written in three-address code SSA form, all intermediate computations and output variables are at some point stored locally in a uniquely defined local variable \(\bar{v}\in {\bar{\mathcal {V}} }_P\). We thus define the set of all possible probes as the set \({\bar{\mathcal {V}} }_P\) of all local variables as well as the input variables.

Remark 2.1

We will consider that a program P always outputs all unmasked values it computes even if they are not explicitly returned by P.

Definition 2.1

(Probes). For a well-formed program P with variables \({\bar{\mathcal {V}} }_P\) and input variables \(\bar{a}_1,\ldots ,\bar{a}_N\), a set of probes is a set \({\bar{\mathscr {I}} }\subset {\bar{\mathcal {V}} }_P\). For any set \({\bar{\mathscr {I}} }\subset {\bar{\mathcal {V}} }_P\) and any scalars \(\mathcal {X} = (a_1,\ldots ,a_N)\) we will denote as \(\textsf {ExecObs}(P, {\bar{\mathscr {I}} }, \mathcal {X})\) the joint distribution of the (masked and unmasked) outputs of \(P(a_1,\ldots ,a_N)\) and of all the values taken by the variables in \({\bar{\mathscr {I}} }\). In particular for

\(out_\textrm{masked}\) (resp. \(out_\textrm{unmasked}\)) is the masked (resp. unmasked) output of \(P(a_1,\ldots ,a_N)\) for some internal random coins and \({\mathscr {L}}\) is the value taken by the variables in \({\bar{\mathscr {I}} }\) for these random coins.

Probing Model. We recall standard non-interference results from [4].

Definition 2.2

(Perfect simulatability, reformulation of [4]). Let \({\bar{\mathscr {I}} }\) be a set of probes of a gadget \(\textbf{G}\) with input shares \(\bar{\mathcal {X}}\). We say that the PPT simulator \((\textsf {SimIn},Simout)\) perfectly simulates the probes \({\bar{\mathscr {I}} }\) if and only if for any input values \(\mathcal {X}\), \(\textsf {SimIn}(\textbf{G},{\bar{\mathscr {I}} })\) outputs a subset \(\bar{\mathcal {X}}'\subset \mathcal {X}\) of the input variables of \(\textbf{G}\), and \(\textsf {SimOut}(\textbf{G},\mathcal {X}')\) (where \(\mathcal {X}'\) is the values taken by \(\mathcal {X}\) at indices \(\bar{\mathcal {X}}'\)) outputs a tuple of values such that the marginal distribution of \({\mathscr {L}}\), for \((out_\textrm{masked}, out_\textrm{unmasked}, {\mathscr {L}}) \leftarrow \textsf {ExecObs}(P,{\bar{\mathscr {I}} },\mathcal {X})\), and \(\textsf {SimOut}(\textbf{G},\mathcal {X}')\) are identical.

Definition 2.3

(Non Interference [4]). A gadget is said \((d- 1)\)-non-interfering (written \((d- 1)\)-\(\textsf{NI}\) for short) iff any set of probes \({\bar{\mathscr {I}} }\) such that \(|{\bar{\mathscr {I}} }| \le d- 1\) can be perfectly simulated (See Definition 2.2) by a simulator \((\textsf {SimIn},\textsf {SimOut})\) such that \(\textsf {SimIn}(\textbf{G},{\bar{\mathscr {I}} })\) outputs a set \(\bar{\mathcal {X}}'\) of at most \(d- 1\) shares of each input.

Definition 2.4

(Strong Non Interference [4]). A gadget is said \((d- 1)\)-strongly-non-interfering (written \((d- 1)\)-\(\textsf{sNI}\) for short) iff any set \({\bar{\mathscr {I}} }\) of at most \(d- 1= d_\textrm{int} + d_\textrm{out}\) probes, where \(d_\textrm{int}\) are made on internal data and \(d_\textrm{out}\) are made on the outputs, can be perfectly simulated by a simulator \((\textsf {SimIn},\textsf {SimOut})\) such that \(\textsf {SimIn}(\textbf{G},{\bar{\mathscr {I}} })\) outputs a set \(\bar{\mathcal {X}}'\) of at most \(d_\textrm{int}\) shares of each input.

Lemma 2.1

(Composability of \(\textsf{NI} \) \(\textbf{and}\) \(\textsf{sNI} \) \(\textbf{gadgets}\) [5]). A well-formed algorithm is \(\textsf{NI} \) if all of its gadgets are \(\textsf{NI} \) or \(\textsf{sNI} \) and each sharing is used at most once as input of a non-\(\textsf{sNI} \) gadget. Moreover, a well-formed algorithm is \(\textsf{sNI} \) if it is \(\textsf{NI} \) and its output sharings are issued from a \(\textsf{sNI} \) gadget.

Lastly, in this paper, the masking order is fixed at \(d- 1\) where \(d\) is the number of shares. For simplicity, we omit the \(d- 1\) when referring to \(\textsf{NI}/\textsf{sNI} \) properties.

2.3 Sum of Uniforms

Given a distribution \(\mathcal {D} \) of support included in an additive group, we note \([T] \cdot \mathcal {D} \) the convolution of \(T\) identical copies of \(\mathcal {D} \); in other words, \([T] \cdot \mathcal {D} \) is the distribution of the sum of \(T\) independent random variables, each being sampled from \(\mathcal {D} \). Given integers \(u, T> 0\), and if we note \(\mathcal {U}(S)\) the uniform distribution over a finite S, we note:

The acronym SU stands for “sum of uniforms”. This class of distributions is illustrated in Fig. 2. This distribution is highly desirable for our purposes, since for \(T\ge 4\) it verifies statistical properties in the same way as Gaussians do. However, unlike Gaussians, they are straightforward to sample in constant-time and without requiring tables or elaborate mathematical machinery. This makes them adequate for \(\mathsf {\text {Raccoon}}\). Finally, we note \(\text {RSU}(u,1)\) the distribution over \(\mathcal {R}\) obtained by sampling each integer coefficient of \(a \in \mathcal {R}\) according to \({{\,\textrm{SU}\,}}(u,1) \), and outputting a. More details about sums of uniforms can be found the full version of this paper.

In this section, we present our masking-friendly signature scheme called Raccoon. We describe the key generation (Algorithm 1), signing (Algorithm 2) and verification (Algorithm 3). Key generation and signing are always performed in a masked manner; when \(d = 1\), the algorithmic descriptions remain valid but the algorithms are, in effect, unmasked.

We reference relevant variables and parameters in Table 1.

3.1 Key Generation

Masked key generation process is described by Algorithm 1. At a high-level, \(\textsf{KeyGen}\) generates d-sharings \((\llbracket \textbf{s} \rrbracket , \llbracket \textbf{e} \rrbracket )\) of small errors \((\textbf{s}, \textbf{e})\), computes the verification key as an LWE sample \((\textbf{A}, \textbf{t} = \textbf{A} \cdot \textbf{s} + \textbf{e})\), and rounds \(\textbf{t} \) for efficiency. A key technique is that \(\llbracket \textbf{s} \rrbracket , \llbracket \textbf{e} \rrbracket \) are generated in Lines 4 and 6 using our novel algorithm \(\textsf{AddRepNoise}\) (Algorithm 5).

3.2 Signing Procedure

The masked signing process is described by Algorithm 2. This signing procedure is similar to the “Lyubashevsky’s Signature Without Aborts” in [1]. Again, the use of \(\textsf{AddRepNoise}\) is crucial in this procedure. The challenge computation is divided in two parts, first a \(2\kappa \) bitstring is computed using the hash function \(\textsf{ChalHash}\), then this bitstring is mapped to a ternary polynomial with fixed hamming weight using \(\textsf{ChalPoly}\). As in previous works this distinction is made for ease of implementation and storage.

3.3 Verification Procedure

Algorithm 3 describes the signature verification process. Signature verification is not masked, and its parameters are independent of the number of shares d used when creating the signature. As is usual in lattice signatures, verification performs a bound check and an equality check.

It is easy to check that the equation of line 7 verifies by construction when the signature algorithm is run honestly, we will fix the bounds \(B_{\infty } \) and \(B_2\) such that honest signatures verify with overwhelming probability (this is necessary for the reduction of Sect. 7.2 to go through).

3.4 Helper Algorithms

The following are algorithms used within our key generation (Algorithm 1), signing (Algorithm 2) and verification (Algorithm 3). The algorithm \(\textsf{AddRepNoise}\) (Algorithm 5) is the most interesting one, which we come back later when discussing probing security.

Checking Bounds. The function \(\textsf{CheckBounds}\) (Algorithm 4) is used to check the norm bounds and encoding soundness of signatures by both the verification function (Algorithm 3), but also by the signing function (Algorithm 2). Note that unlike rejection, \(\textsf{CheckBounds}\) is used to enforce the zero-knowledge property, and therefore it does need to be masked. Rather, it detects signatures that are a bit too large. Note that \(\textsf{CheckBounds}\) could be removed entirely at the cost of a slight increase in signature size (and therefore a slight decrease in security).

Error Distributions. \(\textsf{AddRepNoise}\) (Algorithm 5) implements the Sum of Uniforms (SU) distribution \({{\,\textrm{SU}\,}}(u,d \cdot \textsf{rep}) \) (Sect. 2.3) in a masked implementation. \(\textsf{AddRepNoise}\) interleaves noise additions and refresh operations; more precisely, for each (masked) coefficient \(\llbracket a \rrbracket \) of \(\llbracket \textbf{v} \rrbracket \), small uniform noise is added to each share of \(\llbracket a \rrbracket \), then \(\llbracket a \rrbracket \) is refreshed, and this operation is repeated \(\textsf{rep} \) times. The security properties of \(\textsf{AddRepNoise}\) is analyzed in Sect. 6.2.

Challenge Computation. As in Dilithium, the challenge computation is split in two subroutines: \(\textsf{ChalHash}\) computes a hash digest, and \(\textsf{ChalPoly}\) expands it into a challenge polynomial \(c _{\textsf{poly}} \) that is (pseudo-randomly) uniform in the set \(\mathcal {C}= \{c \in \mathcal {R}, \Vert c\Vert _1 = \omega \}\). These functions do not need to be masked.

Refresh and Decoding Gadgets. Lastly, we recall some useful gadgets. \(\textsf{Refresh}\) (Algorithm 7) generates a fresh d-sharing of a value in \(\mathcal {R}_q\), or “refresh” the d-sharing. This operation is important for security against t-probing adversaries. \(\textsf{Refresh}\) uses \(\textsf{ZeroEncoding}\) (Algorithm 8) as a subroutine. Both algorithms perform \(O(d \log d)\) basic operations over \(\mathcal {R}_q\) and require \(O(d \, \log (d) \, \log (q))\) bits of entropy. While we present \(\textsf{ZeroEncoding}\) as a recursive algorithm, one can see that it can be computed in-place and its memory requirement is O(d). Remark that our \(\textsf{ZeroEncoding}\) algorithm entails that the number of shares d is a power of 2, as the rest of our algorithms are agnostic to this property we could use a \(\textsf{ZeroEncoding}\) that produces a more fine-grained number of shares to obtain different parameters (e.g. by using Algorithm 8 and collapsing some of the shares).

We describe in Algorithm 6 a \(\textsf{Decode}\) gadget that takes \(\llbracket \textbf{x} \rrbracket = (\textbf{x}_i)_{i \in [t+1]}\) as input, refreshes it with Algorithm 7, then computes the sum \( \textbf{x}_0 + \cdots +\textbf{x}_{d- 1} \bmod q\). When the decoding gadget is already preceded by a refresh gadget, one of them may be omitted. \(\textsf{Decode}\) is similar to the algorithm “FullAdd” from [5, Alg. 16].

Raccoon’s core design choice is using the sum of uniforms distributions as opposed to the discrete Gaussian distributions. From a practical point of view, the sum of uniforms distribution is a much simpler distribution to mask and implement. On the other hand, from a theoretical point of view, it poses more challenges, as there are far fewer established statistical guarantees usable in cryptography. Notably, since the sum of uniforms distribution only has finite support, a standard proof technique used in lattice-based cryptography relying on the Rényi divergence breaks down. To this end, we generalize the Rényi divergence and prepare useful statistical bounds on the sum of uniforms distribution.

4.1 Smooth Rényi Divergence

The usual Rényi divergence is undefined for distributions P, Q of supports not included in one another. For example, this happens when \(P = {{\,\textrm{SU}\,}}(u,T) \) and \(Q = P + a\), for any \(a \ne 0\). The smooth Rényi divergence (Definition 4.1) addresses these limitations by combining the statistical distance and the Rényi divergence. The statistical distance component captures problematic sets (typically, distribution tails), while the Rényi divergence component benefits from the same efficiency as the usual Rényi divergence over unproblematic parts of the supports.

Definition 4.1

(Smooth Rényi divergence). Let \(\epsilon \ge 0\) and \(1 < \alpha < \infty \). Let P, Q be two distributions of countable supports \(\textrm{Supp}(P) \subseteq \textrm{Supp}(Q) = X\). The smooth Rényi divergence of parameters \((\alpha , \epsilon )\) between P and Q is defined as:

where \(\Delta _{\text { SD}}\) and \(R_\alpha \) denote the statistical distance and the Rényi divergence, respectively:

While [18] has also provided a definition of smooth Rényi divergence, we argue that our definition is more natural. Indeed, it satisfies variations of properties that are expected from classical Rényi divergences. These are listed in Lemma 4.1.

Tools for Smooth Rényi Divergence. We review some basic properties of the smooth Rényi divergence.

Lemma 4.1

The smooth Rényi divergence satisfies the following properties.

1. 1.

   Data processing inequality. Let P, Q be two distributions, let \(\epsilon \ge 0\), and g be a randomized function over (a superset of) \(\textrm{Supp}(P) \cup \textrm{Supp}(Q)\).

   $$\begin{aligned} R_\alpha ^\epsilon (g(P); g(Q)) \le R_\alpha ^\epsilon (P; Q). \end{aligned}$$

   (2)
2. 2.

   Probability preservation. For any event \(E \subseteq \textrm{Supp}(Q)\):

   $$\begin{aligned} P(E) \le (Q(E) + \epsilon )^{(\alpha -1)/\alpha } \cdot R_\alpha ^\epsilon (P; Q) + \epsilon . \end{aligned}$$

   (3)
3. 3.

   Tensorization. Let \((P_i)_{i \in I}, (Q_i)_{i \in I}\) be two finite families of distributions, let \(\epsilon _i \ge 0\) for \(i \in I\), and let \(\epsilon = \sum _{i \in I} \epsilon _i\).

   $$\begin{aligned} R_\alpha ^{\epsilon }\left( \prod _{i \in I} P_i; \prod _{i \in I} Q_i \right) \le \prod _{i \in I} R_\alpha ^{\epsilon _i} (P_i; Q_i). \end{aligned}$$

   (4)

Proof

We recall that \(\Delta _{\text { SD}}\) and \((R_\alpha ^\alpha - 1)\) can be cast as f-divergences, following Csiszár’s terminology [15]. Item 1 follows from the data processing inequality for f-divergences. Item 2 is a special case of Item 1 . Finally, Item 3 follows from tensorization properties of the statistical distance and the Rényi divergence.    \(\square \)

4.2 Useful Bounds on Sum of Uniforms

We bound the smooth Rényi divergence between two sums of uniforms, centered at either 0 or a small offset. This will be a key lemma establishing the hardness of standard \(\textsf{EUF}\text {-}\textsf{CMA}\) security of the small Raccoon (cf. Section 7.3). Due to page limitation, the proof is provided in the full version of this paper.

Lemma 4.2

Let \(T, u, N\in \mathbb {N}\) and \(c \in \mathbb {Z}\) such that \(T\ge 4\) and \(N = 2^u\). Let \(P = {{\,\textrm{SU}\,}}(u,T) \) and Q the distributions corresponding to shifting the support of P by c. Let \(\alpha \ge 2\) and \(\tau > 0, \epsilon > 0\) be such that:

1. 1.

   \(\alpha \, |c| \le \tau = o(N / (T- 1))\) ;

2. 2.

   \(\epsilon = \frac{(\tau + T)^T}{N^T\, T!}\).

Then:

Gap with Practice. In practice, Lemma 4.2 is a bit sub-optimal. Let us note \(\sigma ^2 = \frac{ T(N^2 - 1) }{12}\) the variance of P and \(Tc = o(N)\), which follows from Item 1 above. We also use the notation \(a \lesssim b\) for \(a \le b + o(b)\). Then, Lemma 4.2 essentially tells us that \(\log R_\alpha ^\epsilon (P; Q) \lesssim \frac{\alpha }{2}\left( \frac{Tc}{N}\right) ^2 \sim \frac{\alpha \, c^2 \, T^3}{24 \, \sigma ^2}\). In comparison, [1, Lemma 2.28] tells that if P is instead a Gaussian of parameter \(\sigma \), then \(\log R_\alpha (P; Q) \le \frac{\alpha \, c^2}{2 \, \sigma ^2}\). Thus there is a gap \(O(T^3)\) between Lemma 4.2 and [1, Lemma 2.28].

One could assume that this gap is caused by a fundamental difference between Gaussians and sums of uniforms. However we performed extensive experiments and found that this gap does not exist in practice, i.e., it seems to be an artifact of our proof. For this reason, we put forward the following conjecture which ignores this gap and which we use when setting our concrete parameters. Due to page limitation, we expand upon Conjecture 4.1 in the full version.

Conjecture 4.1

Under the conditions of Lemma 4.2, we have

for a constant . Therefore, for any M-dimensional vector \(\textbf{c}\), \(\mathcal {P} = P^M\) and \(\mathcal {Q} = \textbf{c} + Q^M\), and further assuming \(\alpha = \omega _\textsf{asymp}(1)\) and \(T = o(\alpha | c_i |)\) for all the i-th (\(i \in [M]\)) entry of \(\textbf{c}\), we have:

and where \(\Vert \textbf{c}\Vert _T \le \Vert \textbf{c}\Vert _2\) is the \(L_T\) norm.

We first formally define \(\textsf{NI} \) security against a probing adversary, the security model in which Raccoon will later be prove in. We then argue that existing probing tools/models discussed in Sect. 2.2 are insufficient to prove \(\textsf{EUF}\text {-}\textsf{CMA}\) security and prepare useful tools that may be of independent interest. Our tools build on the recent techniques developed by [20] (cf. Sect. 1.3).

5.1 \(\textsf{EUF}\text {-}\textsf{CMA}\) Security in the Probing Model

We use the definition of [5] that captures the fact that no PPT adversary with access to less than \(d- 1\) probes on \(\textsf{KeyGen}\) and \(\textsf{Sign}\) should be able to break \(\textsf{EUF}\text {-}\textsf{CMA}\) security (i.e., unforgeability). Below, our definition slightly deviates from theirs as we rely on more generalized (and formal) notion of probes captured by the function \(\textsf {ExecObs}\) (cf. Definition 2.1).

Definition 5.1

Let \(d \ge 1\) an integer, \(Q_s \) be a fixed maximum amount of signature queries. A signature scheme \((\textsf{KeyGen},\textsf{Sign},\textsf{Verify})\) with an efficient signing key update algorithm \(\textsf{KeyUpdate}\) is \(\textsf{EUF}\text {-}\textsf{CMA}\)-secure in the \((d- 1)\)-probing model if any probabilistic polynomial time adversary has a negligible probability of winning the game presented in Fig. 3.

As in [5], we assume a \(\textsf{KeyUpdate}\) algorithm that refreshes the secret key between signature queries and cannot be probed by the attacker. This is performed to avoid attackers probing more than \(d- 1\) shares of the secret across different signature queries. See [5, Remark 3] for more details.

Remark 5.1

(Standard \(\textsf{EUF}\text {-}\textsf{CMA}\) security). We note that Definition 5.1 incorporates the standard notion of standard \(\textsf{EUF}\text {-}\textsf{CMA}\) (i.e., 0-probing). For this, we define \(\textsf{KeyUpdate}\) to be the identify function; the restriction that the adversary can only query an empty set for the set of probes is enforced by the winning condition.

5.2 Insufficiency of the \(\textsf{NI} \)/\(\textsf{sNI} \) Models

At first glance, all subroutines of \(\mathsf {\text {Raccoon}}\) can be proven composable in the \(\textsf{NI} \) model. However, careful consideration shows that the \(\textsf{NI} \) model does not capture security when the intermediate values are not uniformly distributed and biased with the knowledge of the public output. Indeed, for example in the \(\textsf{KeyGen}\), the combined knowledge of some shares of \(\llbracket \textbf{s} \rrbracket \) and of the public key \(\textsf{vk}\) allows one to decrease the key-recovery security (decreasing the standard deviation of the short vector in a lattice) as presented in the technical overview in Sect. 1.

The gist of the problem when taking the output of an algorithm into account comes from the fact that the \(\textsf{NI} \) model proves that there exists a simulator that can simulate any set of probes from a subset of the input shared secrets of the algorithm. However, the aforementioned property does not entail that the distribution of the probes can be simulated when taking into account the output. This is clearly apparent in Definition 2.2 where the definition requires \(\textsf {SimOut}(\textbf{G},\mathcal {X}')\) and \({\mathscr {L}}\) to be identically distributed, but not \((out_\textrm{unmasked},\textsf {SimOut}(\textbf{G},\mathcal {X}'))\) and \((out_\textrm{unmasked},{\mathscr {L}})\).

To see that the marginal distributions being identical is insufficient we give a simple example in Fig. 4: both algorithms are trivially \(\textsf{NI} \) since any probe \(\bar{\rho }_j\) or \(\bar{v}_j'\) can be simulated by sampling a small uniform and outputting it or adding it to the corresponding input \(v_j\). However, if we consider the unmasked value w as a public output, a simulator taking as input shares of \(\llbracket \textbf{v} \rrbracket \) cannot output probes that are correlated to w. For example, in gadget \(\textsf{non}\text {-}\textsf{NIU}\), consider the set of probes \({\bar{\mathscr {I}} }= \left\{ \bar{v}_1'\right\} \) which corresponds to the sum of \(v_1\) and \(\rho _1\). A simulator \((\textsf {SimIn},\textsf {SimOut})\) can perfectly simulate \({\bar{\mathscr {I}} }\) by setting \(\textsf {SimIn}(\textsf{non}\text {-}\textsf{NIU},{\bar{\mathscr {I}} })\,{:}{=}\,\bar{v}_1\), and \(\textsf {SimOut}(\textsf{non}\text {-}\textsf{NIU},v_1)\,{:}{=}\,v_1+{{{\,\textrm{RSU}\,}}(u,1)}\). Then the variable \({\mathscr {L}}=v_1'\) being probed has the same distribution as \(\textsf {SimOut}(\textsf{non}\text {-}\textsf{NIU},v_1)\). However the distribution of \(({\mathscr {L}},out_\textrm{unmasked})=(v_1+\rho _1,v+\rho _1+\ldots +\rho _d)\) is clearly not the same as that of \((\textsf {SimOut}(\textsf{non}\text {-}\textsf{NIU},v_1),out_\textrm{unmasked})=(v_1+{{{\,\textrm{RSU}\,}}(u,1)},v+\rho _1+\ldots +\rho _d)\).

5.3 \(\textsf{NI} \)/\(\textsf{sNI} \) with Unshared Inputs

To be able to handle cases where the values being probed are correlated with the public output we will modify the relevant gadgets and consider that any correlated random variables will be considered as inputs. We will formalize this idea with a model named Non-Interference with Unshared Inputs (\(\textsf{NIU} \)) (see Definitions 5.2 and 5.3 below), in which we will consider a variant of the algorithm where all random values that can affect the distribution of the output will be considered as inputs of the algorithm. While this model is stronger than the \(\textsf{NI}\) model, as it can be used to prove security even in the presence of leakage (see Lemma 5.2), we note that once an algorithm P has been modified to have its relevant randomness moved to inputs, the difference with the \(\textsf{NI} \) model becomes mostly syntactical since the new inputs of the algorithm and gadgets can be considered as just an additional shared secret input.

As an example, see the algorithm \(\textsf{NIU}\) in Fig. 4 where we parse the random samples \(\rho _i\) as inputs rather than local variables. \(\textsf{NIU}\) thus takes two tuples of d values as input, and can as before be proven \(\textsf{NI} \) (where we artificially consider the tuple \((\rho _i)_{i\in [d]}\) as a shared input). However this time the \(\textsf{NI} \) proof does entail that the joint distribution of the probes and the output is identical to that of the simulator and output, because the output is a deterministic function of the input. Using the same set of probes \({\bar{\mathscr {I}} }=\bar{v}_1'\) as before, this time the simulator needs to use two input values to simulate the probe: \(\textsf {SimIn}(\textsf{NIU},{\bar{\mathscr {I}} })\,{:}{=}\,\{\bar{v}_1,\bar{\rho }_1\}\) , however since each input variable is in a different shared input this simulator fits the definition of 2-\(\textsf{NI} \) in Definition 2.3, and we can set \(\textsf {SimOut}(\textsf{NIU},\{v_1,\rho _1\})\,{:}{=}\,v_1+\rho _1\) . It is obvious that in this case \(({\mathscr {L}},out_\textrm{unmasked})=(v_1+\rho _1,v+\rho _1+\ldots +\rho _d)=(\textsf {SimOut}(\textsf{NIU},\{v_1,\rho _1\}),out_\textrm{unmasked})\) .

We will now first formalize the \((d- 1)\)-\(\textsf{NIU}\) notion, introduced in [20], in Definitions 5.2 and 5.3. Using the formalism of Sect. 2.2 we can then state and prove composition properties in Lemma 5.1, which are straightforward though never made explicit in [20]. Finally we can prove the core simulatability property of Lemma 5.2 which shows that when passing appropriate random variables as input \(\textsf{NIU}\) is sufficient to simulate the joint distribution of the probes and outputs of an algorithm. While this property was implicitly used in [20], it was actually never proven.

Definition 5.2

(Non Interference with Unshared input [20]). Let G be a gadget taking two types of inputs:

1. 1.

   shared inputs \(\mathcal {X}\), where all elements in \(\mathcal {X}\) are d-tuples of elements in \(\mathcal {R}_q\)

2. 2.

   unshared input \(\mathcal {Y}\), where all elements in \(\mathcal {Y}\) are tuples (not of fixed size) of elements in \(\mathcal {R}_q\)

A gadget \(\textbf{G}\) with shared and unshared inputs is said \((d- 1)\)-non-interfering with unshared inputs (written \((d- 1)\)-\(\textsf{NIU}\) for short) iff any set of probes \({\bar{\mathscr {I}} }\) such that \(|{\bar{\mathscr {I}} }| \le d- 1\) can be perfectly simulated (See Definition 2.2) by a simulator \((\textsf {SimIn},\textsf {SimOut})\) such that \(\textsf {SimIn}(\textbf{G},{\bar{\mathscr {I}} })\) outputs a set \(\bar{\mathcal {X}}' \bigcup \bar{\mathcal {U}}\) of at most \(d- 1\) shares of each shared input (\(\bar{\mathcal {X}}'\)) and each unshared input (\(\bar{\mathcal {U}}\)).

Definition 5.3

(Strong Non Interference with Unshared input [20]). A gadget is said \((d- 1)\)-strongly-non-interfering with unshared inputs(written \((d- 1)\)-\(\textsf{sNIU}\) for short) iff any set \({\bar{\mathscr {I}} }\) of at most \(d- 1= d_\textrm{int} + d_\textrm{out}\) probes where \(d_\textrm{int}\) are made on internal data and \(d_\textrm{out}\) are made on the outputs can be simulated as in Definition 5.2 with \(d_\textrm{int}\) instead of \(d- 1\).

Since unshared inputs only differ from shared inputs by semantics (the distinction comes mostly from the fact that they do not represent a secret being used by the algorithm but internal randomnesses), one can note that if we ignore this distinction, the definitions of \(\textsf{NIU} \) and \(\textsf{NI} \) are identical. The interesting property of \(\textsf{NIU} \) comes from the fact that first transforming the relevant gadgets (namely \(\textsf{AddRepNoise}\) ) to include the randomness as unshared inputs allows \(\textsf{NIU} \) to prove a meaningful statement on the joint distribution of the probes and the output. A key property we use to prove \(\textsf{EUF}\text {-}\textsf{CMA}\) in the probing model.

As argued earlier once the randomness is moved to inputs the definition of \(\textsf{NIU} \) becomes identical to the one of \(\textsf{NI} \) with the difference that inputs are separated in two sets by whether they are shared or unshared. Since this difference is purely syntactical the composition lemma of \(\textsf{NI} \) naturally extends to \(\textsf{NIU} \).

Lemma 5.1

(Composability of \(\textsf{NIU} \) and \(\textsf{sNIU} \) gadgets). A well-formed algorithm is \(\textsf{NIU} \) if all of its gadgets are \(\textsf{NIU} \) or \(\textsf{sNIU} \) and each sharing and each unshared variable is used at most once as input of a non-\(\textsf{sNIU} \) gadget. Moreover, a well-formed algorithm is \(\textsf{sNIU} \) if it is \(\textsf{NIU} \) and its output sharings are issued from an \(\textsf{sNIU} \) gadget.

We now give a core lemma to use \(\textsf{NIU}\). In essence the following lemma states that by passing the relevant randomnesses of a program to inputs, proving \(\textsf{NIU}\) becomes sufficient to prove that probes can be simulated even in the presence of outputs.

Lemma 5.2

Let P be an algorithm with shared inputs \(\mathcal {X}\) and unshared inputs \(\mathcal {U}\). If P is \((d-1)\)-\(\textsf{NIU}\), and the public output of P is a deterministic function of \((\mathcal {X},\mathcal {U})\). Then for any input \(\mathcal {X}\) and any probes \({\bar{\mathscr {I}} }\) (with \(|{\bar{\mathscr {I}} }|\le d-1\)), the distribution of \((out_\textrm{unmasked},\textsf {SimOut}(P,(\mathcal {X}',\mathcal {U}')))\) and \((out_\textrm{unmasked}, {\mathscr {L}})\) over the randomness \(\mathcal {U}\) and the random coins of P and \(\textsf {SimOut}\) are identical, where \((out_\textrm{masked}, out_\textrm{unmasked}, {\mathscr {L}}) \leftarrow \textsf {ExecObs}(P,{\bar{\mathscr {I}} },\mathcal {X})\) and \((\bar{\mathcal {X}}',\bar{\mathcal {U}}')\leftarrow \textsf {SimIn}(P,{\bar{\mathscr {I}} })\).

Proof

We will fix the input \(\mathcal {X}\) and not \(\mathcal {D}\) the distribution from which \(\mathcal {U}\) is sampled. \({\mathscr {L}}\) and \(out_\textrm{unmasked}\) are random variables over the choice of \(\mathcal {U}\) and the random coins of P which we will note \(rc_P\), and \(\textsf {SimOut}(P,(\mathcal {X}',\mathcal {U}')))\) is a random variable over the choice of \(\mathcal {U}\) and the random coins of \(\textsf {SimOut}\) which we will note \(rc_S\) (\(\textsf {SimOut}\) only uses the randomness in \(\mathcal {U}'\subset \mathcal {U}\) but we can consider it as a variable of \(\mathcal {U}\) since \(\mathcal {U}'\) is a marginal of \(\mathcal {U}\)). First we observe that since the definition of \(\textsf{NI}\) and \(\textsf{NIU}\) are identical if we simply consider the extra randomness as another input we have that the marginal distributions of \({\mathscr {L}}\) and \(\textsf {SimOut}(P,(\mathcal {X}',\mathcal {U}'))\) are identical, i.e. for any possible leakage \(\Lambda \) we have:

Since the algorithm P is deterministic when given \((\mathcal {X},\mathcal {U})\), we have that for any possible leakage value \(\Lambda \) and output value \(\theta \):

which is the desired result.    \(\square \)

Before establishing \(\textsf{EUF}\text {-}\textsf{CMA}\) security of Raccoon in the probing model, we prove that the \(\textsf{KeyGen}\) and \(\textsf{Sign}\) algorithms are \(\textsf{NIU} \). Looking ahead, this allows a reduction to simulate the probes \({\mathscr {L}}_{\textsf{KeyGen}}\) and \({\mathscr {L}}_{\textsf{Sign}}^{(i)}\) in the \(\textsf{EUF}\text {-}\textsf{CMA}\) security game in the probing model (cf. Fig. 3).

6.1 Existing Security Properties

Thanks to the composability of the \(\textsf{sNI}/\textsf{NIU} \) models, we can focus on the smaller gadgets comprising the \(\textsf{KeyGen}\) and \(\textsf{Sign}\) algorithms. Table 2 summarizes the security properties of the gadgets used in \(\mathsf {\text {Raccoon}}\), where we can rely on prior works to establish the security of every gadget, except for \(\textsf{AddRepNoise}\) . We refer to the cited papers for more information about the proofs.

6.2 Security Property of the \(\textsf{AddRepNoise}\) Gadget

Let us start with an intuition on the role of the \(\textsf{Refresh}\) operations in \(\textsf{AddRepNoise}\). When considering unmasked coefficients, \(\textsf{AddRepNoise}\) is functionally equivalent to performing \(a \leftarrow a + {{\,\textrm{SU}\,}}(u,T) \) for each coefficient a, for \(T= d \cdot \textsf{rep} \). The internal use of \(\textsf{Refresh}\) operations does not affect this behavior but is meant to offer some resilience to probing adversaries.

Without \(\textsf{Refresh}\), a viable strategy would be to probe individual shares of \(\llbracket a \rrbracket \) at the start and at the end of \(\textsf{AddRepNoise}\) , allowing to learn the sum b of \(\textsf{rep} \cdot (d-1)/2 \) small uniform errors. The conditional distribution of the additive noise (conditioned on the \(d-1\) probed values) is now \(b + {{\,\textrm{SU}\,}}(u,T- (d-1) \cdot \textsf{rep}/ 2) \). With \(\textsf{Refresh}\), this strategy is not possible anymore but a probing adversary can still probe individual errors, which in the end gives out no more than the sum b of \(d -1\) small uniform errors. The conditional distribution of the additive noise (conditioned on the \(d -1\) probed values) is now \(b + {{\,\textrm{SU}\,}}(u,T- (d-1)) \), where the adversary learns b but knows nothing about the realization of \({{\,\textrm{SU}\,}}(u,T-(d-1)) \).

While \(\textsf{AddRepNoise}\) performs operations share by share, the underlying distributions are not uniform. The addition of short noise values are added biases the a posteriori distribution of the final noise. Hence, one cannot prove that this gadget is probing secure. We resolve this issue by moving the short noise values as random coin inputs of the algorithm, introducing \(\textsf{AddRepNoise}_\textsf{ER}\) in Algorithm 9, an instance of \(\textsf{AddRepNoise}\) with explicit randomness (ER) for the small uniforms. Note that the complete set of small uniforms is considered as a single unshared input. We can now formally show in Lemma 6.1 that \(\textsf{AddRepNoise}_\textsf{ER}\) is \(\textsf{sNIU}\). A similar result was proven in [20] but our proof strategy is different and perhaps a bit more formal. Later, these inputs will be handled in the general composition proof.

Lemma 6.1

The \(\textsf{AddRepNoise}_\textsf{ER}\) gadget is (d-1)-\(\textsf{sNIU}\).

Proof

We represent \(\textsf{AddRepNoise}_\textsf{ER}\) as a sequential succession of \(\textsf{MiniAddRepNoise}\) and \(\textsf{Refresh}\) as presented in Fig. 5. To prove the \(\textsf{sNIU} \) property, we exhibit the randomness \(\rho _{i, i_\textsf{rep}, j}\) in the input. Let us remark that the randomness involved in \(\textsf{Refresh}\) (and thus in \(\textsf{ZeroEncoding}\)) are not explicited as the algorithm is already proved \(\textsf{sNI} \). Hence, \(\textsf{AddRepNoise}_\textsf{ER}\) is partially derandomized. Our proof proceeds in two steps; we first study the \(\textsf{MiniAddRepNoise}\) sub-gadget, then \(\textsf{AddRepNoise}_\textsf{ER}\).

Step 1: \(\textsf{MiniAddRepNoise}\). We first show that any probe inside \(\textsf{MiniAddRepNoise}\) can be perfectly simulated (see Definition 2.2) with \(\rho _{i, i_\textsf{rep}, j}\) and the input \(\textbf{v}_{j}\), where \((i, i_\textsf{rep}, j)\) corresponds to the targeted loop. Indeed, let p be a probe inside \(\textsf{MiniAddRepNoise}\). The description of this probe necessarily includes \((i, i_\textsf{rep}, j)\) to specify the involved loop. The intermediate value targeted by p can be

1. 1.

   the randomness \(\rho _{i, i_\textsf{rep}, j}\),

2. 2.

   the value \(v_{j}\) or \(v_{j}'\).

It is easy to conclude that any of these values can be perfectly simulated from \(\rho _{i, i_\textsf{rep}, j}\) and the input \(\textbf{v}_{j}\). The only intermediate value that needs both is \(v_{j}'\) as it needs \(\rho _{i, i_\textsf{rep}, j}\).

Step 2: \(\textsf{AddRepNoise}_\textsf{ER}\). Let us now look at the bigger picture. In this proof, we will perform a composition proof by propagating the dependency of the intermediate variables to shares of \(\rho _{i, i_\textsf{rep}, j}\) and \(\textbf{v}_{j}\). Let \({\bar{\mathscr {I}} }\) be the given set of at most \(d-1\) probes in \(\textsf{AddRepNoise}\) . We decompose \({\bar{\mathscr {I}} }\) as follows.

• Let \(\delta _{\textsf{MiniAddRepNoise}}^{i, i_\textsf{rep}}\) be the number intermediate variables that are probed inside the \(\textsf{MiniAddRepNoise}\) gadget of the loop with indexes \(i, i_\textsf{rep} \).

• Let \(\delta _{\textsf{Refresh}}^{i, i_\textsf{rep}}\) be the number intermediate variables that are probed inside the \(\textsf{Refresh}\) gadget of the loop with indexes \(i, i_\textsf{rep} \).

By definition,

Going from right to left in Fig. 5, we first consider the last \(\textsf{Refresh}\) of the last loop (where \(i=\textsf{len} (\textbf{v})\) and \(i_\textsf{rep} = \textsf{rep} \)). Thanks to the \(\textsf{sNI}\) property of the last \(\textsf{Refresh}\) algorithm, all the \(\delta _{\textsf{Refresh}}^{\textsf{len} (\textbf{v}), \textsf{rep}}\) probes can be perfectly simulated from \(\delta _{\textsf{Refresh}}^{\textsf{len} (\textbf{v}), \textsf{rep}}\) shares of \(\textbf{v}'\), which is also the output of the last \(\textsf{MiniAddRepNoise}\). So, thanks to the above paragraph about \(\textsf{MiniAddRepNoise}\), all the probes from the last \(\textsf{MiniAddRepNoise}\), can be perfectly simulated from two sets of probes:

• \({\bar{\mathscr {I}} }_{\textsf{len} (\textbf{v}), \textsf{rep}}\) defined as the description of at most \(\delta _{\textsf{MiniAddRepNoise}}^{\textsf{len} (\textbf{v}), \textsf{rep}} + \delta _{\textsf{Refresh}}^{\textsf{len} (\textbf{v}), \textsf{rep}}\) values of \(\rho _{\textsf{len} (\textbf{v}), \textsf{rep}, j}\) (with several different j’s),

• \({\bar{\mathscr {I}} }'_{\textsf{len} (\textbf{v}), \textsf{rep}}\) defined as the set of to at most \(\delta _{\textsf{MiniAddRepNoise}}^{\textsf{len} (\textbf{v}), \textsf{rep}} + \delta _{\textsf{Refresh}}^{\textsf{len} (\textbf{v}), \textsf{rep}}\) shares of \(\textbf{v}\), the input of the last \(\textsf{MiniAddRepNoise}\).

The set of \({\bar{\mathscr {I}} }'_{\textsf{len} (\textbf{v}), \textsf{rep}}\) can also be seen as probes of the output of the penultimate \(\textsf{Refresh}\). But, thanks to the \(\textsf{sNI}\) property of the penultimate \(\textsf{Refresh}\) algorithm, they can be simulated independently from the \(\delta _{\textsf{Refresh}}^{\textsf{len} (\textbf{v})-1, \textsf{rep}-1}\) intermediate variables probed inside the penultimate \(\textsf{Refresh}\) algorithm. In conclusion, the \({\bar{\mathscr {I}} }'_{\textsf{len} (\textbf{v}), \textsf{rep}}\) probes can be simulated from uniform random.

Applying the same reasoning for all the subsequent loops, the set of \({\bar{\mathscr {I}} }\) probes can be perfectly simulated from

• \({\bar{\mathscr {I}} }_{i, i_\textsf{rep}}\) defined as the description of at most \(\delta _{\textsf{MiniAddRepNoise}}^{i, i_\textsf{rep}} + \delta _{\textsf{Refresh}}^{i, i_\textsf{rep}}\) values of \(\rho _{i, i_\textsf{rep}, j}\) (with several different j’s),

• \({\bar{\mathscr {I}} }'_{0, 0}\) defined as the set of to at most \(\delta _{\textsf{MiniAddRepNoise}}^{0, 0} + \delta _{\textsf{Refresh}}^{0, 0}\) shares of \(\textbf{v}\), the input of the \(\textsf{AddRepNoise}_\textsf{ER}\).

We define \(\bar{\mathcal {U}} = {\bar{\mathscr {I}} }_{0, 0} \bigcup \cdots \bigcup {\bar{\mathscr {I}} }_{\textsf{len} (\textbf{v}), \textsf{rep}}\) and \(\bar{\mathcal {X}}'= {\bar{\mathscr {I}} }'_{0, 0}\). Thanks to Eq. (9) and Lemma 2.1, we have shown that \(\textsf{AddRepNoise}_\textsf{ER}\) is (d-1)-\(\textsf{sNIU}\).    \(\square \)

6.3 Security Property of \(\textsf{KeyGen}\) and \(\textsf{Sign}\)

Now that \(\textsf{AddRepNoise}_\textsf{ER}\) is proved, one needs to derive the security of the key generation and signature algorithms with a composition proof. Let us first introduce \(\textsf{KeyGen}_\textsf{ER}\) and \(\textsf{Sign}_\textsf{ER}\), simple modifications of \(\textsf{KeyGen}\) and \(\textsf{Sign}\) algorithms where the small uniform randomness is provided as input. \(\textsf{KeyGen}_\textsf{ER}\) is formally described in Algorithm 11. Due to space constraints, the formal description of \(\textsf{Sign}_\textsf{ER}\) is deferred to the full version. We provide a proof of Lemma 6.2 for \(\textsf{KeyGen}_\textsf{ER}\). The proof for \(\textsf{Sign}_\textsf{ER}\) proceeds in a similar fashion and is included in the full version of this paper.

Lemma 6.2

The algorithms \(\textsf{KeyGen}_\textsf{ER}\) and \(\textsf{Sign}_\textsf{ER}\) are \((d-1)\)-\(\textsf{NIU}\).

Proof

(Lemma 6.2). Let us decompose the key generation as a succession of gadgets. The gadgets may be represented as in Fig. 6. We assume the respective \(\textsf{NI}\)/\(\textsf{sNI}\)/\(\textsf{sNIU}\) properties of each gadget as presented in Table 2.

Recall that given a set \({\bar{\mathscr {I}} }\) of at most \(d-1\) probes inside \(\textsf{KeyGen}_\textsf{ER}\), we aim at proving that they can be perfectly simulated with at most \(d-1\) shares of \((\rho ^{(0)}_{i, i_\textsf{rep}, j})\) and \(d- 1\) shares of \((\rho ^{(1)}_{i, i_\textsf{rep}, j})\). In other words we will exhibit two sets \({\bar{\mathscr {I}} }_0\) of at most \(d- 1\) values of \((\rho ^{(0)}_{i, i_\textsf{rep}, j})\), and \({\bar{\mathscr {I}} }_1\) of at most \(d-1\) values of \((\rho ^{(1)}_{i, i_\textsf{rep}, j})\) which will be enough to perfectly simulate \({\bar{\mathscr {I}} }\).

Let us decompose the set \({\bar{\mathscr {I}} }\) of at most \(d-1\) probes in \(\textsf{KeyGen}_\textsf{ER}\) among the different gadgets. By convention, to avoid counting certain probes twice (once as output of a gadget and once as input of the subsequent gadget), we do not count the probes on the outputs. For example, if a probe is made on the output of a gadget \(\textbf{G}\), we will consider that it is actually made on the input of the subsequent gadget. We note:

• \(\delta _0\) the number of intermediate variables probed in Line 6 (final \(\textsf{Decode}\) gadget);

• \(\delta _1\) the number of intermediate variables probed in Line 5 (second \(\textsf{AddRepNoise}_\textsf{ER}\));

• \(\delta _2\) the number of intermediate variables probed in Line 4 (multiplication with \(\textbf{A}\));

• \(\delta _3\) the number of intermediate variables probed in Line 3 (first \(\textsf{AddRepNoise}_\textsf{ER}\));

• \(\delta _4\) the number of intermediate variables probed in Line 2 (\(\textsf{ZeroEncoding}\));

We recall that by definition of \({\bar{\mathscr {I}} }\), \(\sum _{i=0}^4 \delta _i \le d- 1\).

The proof is similar to a standard composition proof. Thanks to the \(\textsf{NI}\) property of the \(\textsf{Decode}\) gadget, all the \(\delta _0\) intermediate variables can be perfectly simulated (see Definition 2.2) with at most \(\delta _0\) shares of \(\llbracket \textbf{t} \rrbracket \). Since the second \(\textsf{AddRepNoise}_\textsf{ER}\) is \(d- 1\)-\(\textsf{sNIU}\), the \(\delta _1 + \delta _0\) intermediate variables observed during \(\textsf{Decode}\) and the last \(\textsf{AddRepNoise}_\textsf{ER}\) may be perfectly simulated with \(\delta _1 \) shares of \(\llbracket t \rrbracket \) (the output of the \(\times \textbf{A}\) operation) and \(\delta _1\) shares of \((\rho ^{(1)}_{i, i_\textsf{rep}})\). We note \({\bar{\mathscr {I}} }_1\) this set. Note that \(\delta _0\) is discarded as it concerns the output of a \(\textsf{sNIU}\) gadget.

With the same reasoning, all the \(\delta _0 + \delta _1 + \delta _2 + \delta _3\) intermediate variables observed after the first \(\textsf{AddRepNoiseER}\) can be perfectly simulated with at most \(\delta _3\) shares of \(\llbracket s \rrbracket \) (which are also the output of \(\textsf{ZeroEncoding}\)) and at most \(\delta _3\) shares of \((\rho ^{(0)}_{i, i_\textsf{rep}})\). We note \({\bar{\mathscr {I}} }_0\) this sets. In addition, the \(\delta _4\) intermediate variables in the \(\textsf{ZeroEncoding}\) gadget may be perfectly simulated from the public parameters as \(\textsf{ZeroEncoding}\) is \(\textsf{NI}\) and does not take any input.

Putting everything together, we have proved that the distribution of the intermediate variables in \({\bar{\mathscr {I}} }\) may be perfectly simulated from:

• the set \({{\bar{\mathscr {I}} }_0}\) containing at most \(\delta _3 \) shares of \((\rho ^{(0)}_{i, i_\textsf{rep}})\)

• the sets \({{\bar{\mathscr {I}} }_1}\) containing at most \(\delta _1 \) shares of \((\rho ^{(1)}_{i, i_\textsf{rep}})\)

Since \(\delta _3 + \delta _1 \le \sum _{i=0}^4 \delta _i \le d- 1\), we have exhibited a ses \(\bar{\mathcal {U}}\) of at most \(d- 1\) of the unshared input which concludes the proof.    \(\square \)

We are finally ready to prove \(\textsf{EUF}\text {-}\textsf{CMA}\) security of Raccoon in the probing model. This is done in two steps. We first reduce \(\textsf{EUF}\text {-}\textsf{CMA}\) security of Raccoon in the probing model to the standard \(\textsf{EUF}\text {-}\textsf{CMA}\) security of small Raccoon, formally defined in Fig. 7. We then establish that this small Raccoon is \(\textsf{EUF}\text {-}\textsf{CMA}\) secure. Technically, the first part relies on the \(\textsf{NIU} \) property of \(\textsf{KeyGen}\) and \(\textsf{Sign}\) (cf. Sect. 6), a purely statistical step claiming that given a small Raccoon key and signature, we can simulate the leakage of Raccoon. The second part relies on the smooth Rényi divergence for the sum of uniform distributions (cf. Sect. 4), and reduces to computational problems.

7.1 Description of a Non-masked Small Raccoon

We first formally define a non-masked and simplified variant of Raccoon, called small Raccoon, depicted in Fig. 7. Notice that there are no more masking or bit-droppings applied. More importantly, it is “small” since the sum of uniform distribution is smaller. We effectively modify the bounds on the signature size to be smaller, using \(\bar{B}_\infty \) and \(\bar{B}_2\), whose formal definition appears in Theorem 7.1.

7.2 \(\textsf{EUF}\text {-}\textsf{CMA}\) Security of Small Raccoon \(\Rightarrow \) Probing \(\textsf{EUF}\text {-}\textsf{CMA}\) Security of Raccoon

This consists of the first step. Once the following theorem is established, we only need to prove standard \(\textsf{EUF}\text {-}\textsf{CMA}\) security of small Raccoon.

Theorem 7.1

Let \(B_{\infty }\) and \(B_2\) satisfying:

• \(\bar{B_{\infty }} \ge B_\infty +\omega \cdot (d-1) \cdot \left( \frac{1}{2}+\frac{2^{3u_t}}{3} \right) \cdot (\kappa +\log (n(k+\ell ))+2^{\nu _\textbf{w}} +\omega \cdot 2^{{\nu _\textbf{t}}}\)

• \(\bar{B}_2 \ge B_2+\omega \cdot \sqrt{n(k+\ell )}\cdot (d-1) \cdot \left( \frac{1}{2}+\frac{2^{3u_t}}{3} \right) \cdot (\kappa +\log (n(k+\ell ))+2^{\nu _\textbf{w}} \cdot \sqrt{nk}+\omega \cdot 2^{{\nu _\textbf{t}}}\cdot \sqrt{nk}\)

Let \(Q_H\) and \(Q_S\) denote the number of random oracle queries and signing queries performed by \(\mathcal A\). For any PPT adversary \(\mathcal A\) against the \(\textsf{EUF}\text {-}\textsf{CMA}\) security on \(\mathsf {\text {Raccoon}}\) in the \((d - 1)\)-probing model with time T and advantage \(\varepsilon \), there exists a PTT adversary \(\mathcal B\) against the \(\textsf{EUF}\text {-}\textsf{CMA}\) security on small \(\mathsf {\text {Raccoon}}\) (cf. Fig. 7) with time O(T) and advantage:

We will use a series of hybrids defined below to prove the theorem.

• \(\textsf{Hybrid}_{0}\): This hybrid corresponds to real the \(\textsf{EUF}\text {-}\textsf{CMA} \) security game in the \((d- 1)\)-probing model (cf. Fig. 3).

• \(\textsf{Hybrid}_{1}\): In this hybrid we replace \(\textsf{KeyGen}\) with \(\textsf{KeyGen}_\textsf{ER}\) and \(\textsf{Sign}\) with \(\textsf{Sign}_\textsf{ER}\), in which all randomnesses are sampled prior to running the algorithm. Since the algorithms are functionally identical the advantage is unchanged.

• \(\textsf{Hybrid}_{2}\): This hybrid corresponds to Fig. 8, in which all the probes queried by the adversary during either key generation or signature are mapped to probes that target only the randomness used in the \(\textsf{AddRepNoise}\) gadgets. We prove that the values output by these probes can be used to perfectly simulate the output queried by the adversary in Lemma 6.2. More precisely there is a first PPT simulator \((\textsf {SimIn}_{\textsf{KeyGen}}, \textsf {SimOut}_{\textsf{KeyGen}})\) such that for any probe set \(|{\bar{\mathscr {I}} }_{\textsf{KeyGen}}|\le t\) in \(\textsf{KeyGen}(1^\kappa )\), all probes in \({\bar{\mathscr {I}} }'\,{:}{=}\,({\bar{\mathscr {I}} }_\textbf{s}', {\bar{\mathscr {I}} }_{\textbf{e}}')\,{:}{=}\,\textsf {SimIn}_{\textsf{KeyGen}}({\bar{\mathscr {I}} }_{\textsf{KeyGen}})\) are of the form \(\bar{\rho }_{\textbf{s}, i, i_\textsf{rep}, j}\in {\bar{\mathscr {I}} }_\textbf{s}'\) for some \((i, i_\textsf{rep}, j)\in [\ell , \textsf{rep}, d]\), and \(\bar{\rho }_{\textbf{e}, i, i_\textsf{rep}, j}\in {\bar{\mathscr {I}} }_\textbf{e}'\) for some \((i, i_\textsf{rep}, j)\in [k, \textsf{rep}, d]\) (note that the variable names \(\bar{\rho }\) are also indexed by the \(\textsf{AddRepNoise}\) gadget to which they belong to ensure unique namings), and \(\max (|{\bar{\mathscr {I}} }_s'|,|{\bar{\mathscr {I}} }_e'|)\le d-1\). Using Lemma 5.2 we have that \((\textsf{vk},\textsf {SimOut}(\textsf{KeyGen}_\textsf{ER},\mathscr {I}'))\) follows the same distribution as \((\textsf{vk},{\mathscr {L}})\), where \((\textsf{sk},\textsf{vk},{\mathscr {L}})\leftarrow \textsf {ExecObs}({\bar{\mathscr {I}} }_{\textsf{KeyGen}}, \textsf{KeyGen}_\textsf{ER}, 1^\lambda )\). Similarly there is a second PPT simulator \((\textsf {SimIn}_{\textsf{Sign}}, \textsf {SimOut}_{\textsf{Sign}})\) such that for any message \(\textsf{msg} \), masked secret key \(\llbracket \textsf{sk} \rrbracket \), and probe set \(|{\bar{\mathscr {I}} }_{\textsf{Sign}}|\le t\) in \(\textsf{Sign}(\llbracket \textsf{sk} \rrbracket , \textsf{msg})\), all probes in \({\bar{\mathscr {I}} }'\,{:}{=}\,({\bar{\mathscr {I}} }_\textbf{r}', {\bar{\mathscr {I}} }_{\textbf{e}'}', {\bar{\mathscr {I}} }_\textsf{sk} ')\,{:}{=}\,\textsf {SimIn}_{\textsf{Sign}}({\bar{\mathscr {I}} }_{\textsf{Sign}})\) are of the form \(\bar{\rho }_{\textbf{r}, i, i_\textsf{rep}, j}\in {\bar{\mathscr {I}} }_\textbf{r}'\) for some \((i, i_\textsf{rep}, j)\in [\ell , \textsf{rep}, d]\), \(\bar{\rho }_{\textbf{e}', i, i_\textsf{rep}, j}\in {\bar{\mathscr {I}} }_{\textbf{e}'}'\) for some \((i, i_\textsf{rep}, j)\in [k, \textsf{rep}, d]\), and \(\bar{\textbf{s}}_i\in {\bar{\mathscr {I}} }_\textsf{sk} '\) for some \(i\in [d]\), and \(\max {(|{\bar{\mathscr {I}} }_\textbf{r}'|, |{\bar{\mathscr {I}} }_{\textbf{e}'}'|, |{\bar{\mathscr {I}} }_\textsf{sk} ')|}\le t\). It also holds that \((\textsf{sig},\textsf {SimOut}(\textsf {ExecObs}({\bar{\mathscr {I}} }', \textsf{Sign}, 1^\lambda )))\) follows the same distribution as \(\textsf {ExecObs}({\bar{\mathscr {I}} }_{\textsf{Sign}}, \textsf{Sign}, 1^\lambda )\). From Lemma 5.2, \(\textsf {SimOut}(\textsf{Sign}_\textsf{ER},\mathscr {I}')\) follows the same distribution as \((\textsf{sig},{\mathscr {L}})\), where \((\textsf{sig},{\mathscr {L}}) \leftarrow \textsf{ExecObs}({\bar{\mathscr {I}} }_{\textsf{Sign}}, \textsf{Sign}_\textsf{ER}, \textsf{msg})\). Thus the two hybrids are identical.

• \(\textsf{Hybrid}_{3}\): This hybrid corresponds to Fig. 9, in which the algorithms \(\textsf {ExecObs}({\bar{\mathscr {I}} }, \textsf{KeyGen}, 1^\kappa )\) and \(\textsf {ExecObs}({\bar{\mathscr {I}} }, \textsf{Sign}, \textsf{sk}, \textsf{msg})\) are replaced by \(\textsf{KeyGen}_{{\mathscr {L}}}(1^\kappa , {\bar{\mathscr {I}} })\) and \(\textsf{Sign}_{{\mathscr {L}}}(\textsf{sk}, \textsf{msg}, {\bar{\mathscr {I}} })\), respectively. The former is presented in Algorithm 15. The latter is defined analogously and deferred to the full version due to page limitations. Observe that since \(\textsf {ExecObs}({\bar{\mathscr {I}} }, \textsf{KeyGen}, 1^\kappa )\) outputs the same output as \(\textsf{KeyGen}(1^\kappa )\) as well as the value of the variables at indices \({\bar{\mathscr {I}} }\), any algorithm that outputs the same distribution is semantically identical. Since the variables in \({\bar{\mathscr {I}} }\) are now restricted to the randomness used in \(\textsf{AddRepNoise}\) it is clear that the algorithm \(\textsf{KeyGen}_{{\mathscr {L}}}\) outputs the same distribution . The same argument goes for \(\textsf{ExecObs}({\bar{\mathscr {I}} }, \textsf{Sign}, \textsf{sk}, \textsf{msg})\). Hence, the two hybrids are identical.

• \(\textsf{Hybrid}_{4}\): This hybrid corresponds to Fig. 10, in which the challenger artificially extends the set of probes queried to the key generation and signing algorithm. More specifically, we define \(\textsf{Extend}\) so that for any \(\rho _{\textbf{s}, i, i_\textsf{rep}, j}\in {\bar{\mathscr {I}} }_\textbf{s}\), all variables \(\rho _{\textbf{s}, i', i_\textsf{rep}, j}\) for \(i'\in [\ell ]\) are in \(\textsf{Extend}({\bar{\mathscr {I}} }_\textbf{s})\) (same for \(\textsf{Extend}({\bar{\mathscr {I}} }_\textbf{e})\), \(\textsf{Extend}({\bar{\mathscr {I}} }_\textbf{r})\), \(\textsf{Extend}({\bar{\mathscr {I}} }_{\textbf{e}'})\)). Conversely \(\textsf{Collapse}({\mathscr {L}}_\textbf{s}')\) discards the values of any variables that are in \({\bar{\mathscr {I}} }_\textbf{r}\) but not \({\bar{\mathscr {I}} }_\textbf{r}'\). Clearly, this does not modify the view of the adversary. This conceptual change will be necessary to reduce to a simpler signing algorithm in the following section.

Lastly, we prove that for any PPT adversary \(\mathcal {A}\) against the game described in \(\textsf{Hybrid}_4\) (cf. Fig. 10), we can construct an adversary \(\textbf{B}\) against the standard \(\textsf{EUF}\text {-}\textsf{CMA} \) security of small \(\mathsf {\text {Raccoon}}\) in Fig. 7. At a high level a challenger can simulate queries from \(\textsf{KeyGen}_{{\mathscr {L}}}\) by querying the public key \(\bar{\textbf{t}}\) from the oracle for \(\textsf{KeyGen}_{Small}\) and artificially sampling additional noises \((\tilde{\textbf{s}}, \tilde{\textbf{e}})\) as the sum of \(d-1\) small uniforms and outputting the public key \(\textbf{t}\,{:}{=}\,\left\lfloor \bar{\textbf{t}} +\textbf{A}\tilde{\textbf{s}}+\tilde{\textbf{e}} \right\rceil _{{\nu _\textbf{t}}} \) which will be distributed exactly as a public key for \(\textsf{KeyGen}_{{\mathscr {L}}}\). Similarly, a signature from \(\textsf{Sign}_\textsc {Small}\) can be mapped to a signature for \(\textsf{Sign}_{{\mathscr {L}}}\) by sampling the appropriate sums of uniform \((\tilde{\textbf{r}},\tilde{\textbf{e}}')\) and setting \(\textbf{w} =\left\lfloor \bar{\textbf{w}} +\textbf{A}\tilde{\textbf{r}}+\tilde{\textbf{e}}' \right\rceil _{{\nu _\textbf{w}}} \). Finally we show a forgery for \(\textsf{Sign}_{{\mathscr {L}}}\) can be mapped to a forgery for \(\textsf{Sign}_{Small}\) . The formal proof is given in the full version. This completes the proof.

7.3 \(\textsf{MLWE} + \textsf{SelfTargetMSIS} \Rightarrow \) \(\textsf{EUF}\text {-}\textsf{CMA}\) Security of Small Raccoon

Notations for Smooth Rényi Divergence. We further define some useful notations to aid the readability. For any \(c \in \mathcal {C}, \textbf{s} \in \mathcal {R}_q^\ell \), and \(\textbf{e} \in \mathcal {R}_q^k\), we note \(\textsf{center}\,{:}{=}\,c \cdot \begin{bmatrix} \textbf{s} \\ \textbf{e} \end{bmatrix} \in \mathcal {R}_q^{\ell + k}\) and recall \(T = d \cdot (\textsf{rep}- 1) + 1\). We define two distributions: \(\mathcal {P}\,{:}{=}\,{{\,\textrm{SU}\,}}({u_\textbf{w}}, T) ^{n(\ell + k)}\) and \(\mathcal {Q}(\textsf{center})\,{:}{=}\,\textsf{center} + \mathcal {P}\).

We bound the smooth Rényi divergence of \(\mathcal {P}\) and \(\mathcal {Q}\). For any \(\alpha = \omega _\textsf{asymp}(1)\) and \(\epsilon _\textsc {Tail} (\textsf{center}) = \frac{1}{\sqrt{2 \, \pi \, T}} \left( \frac{\alpha \, e \, \Vert \textsf{center}\Vert _2 }{2^{{u_\textbf{w}}} \cdot T}\right) ^T\) (see Conjecture 4.1 or Lemma 4.2), we define \(\epsilon _{\textsc {Tail}}\) and \(R_{\alpha }^{\epsilon _{\textsc {Tail}}}(\mathcal {P}; \mathcal {Q})\) to be any two values satisfying

where both probabilities are taken under the randomness of \((\textbf{s}, \textbf{e}) \leftarrow \text {RSU}(u_\textbf{t},T)^\ell \times \text {RSU}(u_\textbf{t},T)^k\). For efficiency and better parameters, we set \(\epsilon _{\textsc {Tail}}\) and \(R_{\alpha }^{\epsilon _{\textsc {Tail}}}(\mathcal {P}; \mathcal {Q})\) to be the smallest values satisfying the above inequality. The above parameters we provide is one set of candidate asymptotic parameters.

It remains to prove that small Raccoon in Fig. 7 is (standard) \(\textsf{EUF}\text {-}\textsf{CMA}\) secure. This is established in the following theorem.

Theorem 7.2

The small Raccoon in Fig. 7 is \(\textsf{EUF}\text {-}\textsf{CMA} \) secure under the \(\textsf{MLWE} _{q, \ell , k, {{\,\textrm{SU}\,}}({u_\textbf{t}}, T)}\) and \(\textsf{SelfTargetMSIS} _{q, \ell +1, k, \mathcal {C}, \beta }\) assumptions.

Formally, for any adversary \(\mathcal {A} \) against the \(\textsf{EUF}\text {-}\textsf{CMA} \) security game making at most \(Q_h\) random oracle queries and \({Q_s} \) signing queries, and \(\epsilon _{\textsc {Tail}}\) and \(R_\alpha ^{{\epsilon }_{\textsc {Tail}}} \left( \mathcal P; \mathcal Q \right) \) satisfying Eqs. (10) and (11), there exists adversaries \(\mathcal {B}\) and \(\mathcal {B}'\) against the \(\textsf{MLWE} _{q, \ell , k, {{\,\textrm{SU}\,}}({u_\textbf{t}}, T)}\) and \(\textsf{SelfTargetMSIS} _{q, \ell +1, k, \mathcal {C}, \beta }\) problems such that

where \(\textsf{Time} (\mathcal {A}) \approx \textsf{Time} (\mathcal {B}) \approx \textsf{Time} (\mathcal {B}')\).

We now present an overview of the proof which, due to page constraints, is left to the full version. As a first step we replace the hash function by a random oracle which we will program by first sampling \(c _{\textsf{poly}} \leftarrow \mathcal {C} \) and setting the hash function accordingly. Once this is done \(\textbf{w}\) can be defined as a function of \(c _{\textsf{poly}} \) rather than \((\textbf{r},\textbf{e}')\), using the equation \(\textbf{w} \,{:}{=}\,\textbf{A} \cdot \textbf{z}- c _{\textsf{poly}} \cdot \textbf{t} + \textbf{z} '\) where \(\textbf{z} ' \,{:}{=}\, c _{\textsf{poly}} \cdot \textbf{e} + \textbf{e}' \). We now observe that all variables can be computed as deterministic functions of \((\textbf{z},\textbf{z}')\), we thus want to prove that \((\textbf{z},\textbf{z}')\) are independent of \((\textbf{s},\textbf{e})\). Using the Smooth-Renyie divergence property of Lemma 4.2 we can bound the divergence between \((\textbf{z},\textbf{z}')=( c _{\textsf{poly}} \cdot \textbf{s} + \textbf{r}, c _{\textsf{poly}} \cdot \textbf{e} + \textbf{e}')\) and \((\textbf{r},\textbf{e}')\) which are sums of uniforms independent of the secret. Finally we can replace the public key with a uniform vector using \(\textsf{MLWE} \), and use the forgery output by the adversary to break \(\textsf{MSIS} \).

Looking at Theorem 7.2, it is clear that the security bottlenecks in Theorem 7.2 are the hardness of \(\textsf{MLWE}\), of \(\textsf{SelfTargetMSIS}\), and the smooth Rényi divergence (\(\epsilon _{\textsc {Tail}} \) and \(R_\alpha ^{\epsilon _{\textsc {Tail}}}\)). Instantiating Raccoon boils down to an optimization problem where we need to balance the hardness assumptions (\(\textsf{MLWE}\), \(\textsf{SelfTargetMSIS}\)), the smooth Rényi divergence and the performance metrics (size of \(\textsf{vk}\) and \(\textsf{sig}\)).

• Our analysis of \(\textsf{MLWE}\) and \(\textsf{SelfTargetMSIS}\) is fairly standard. We rely on the lattice estimator [2] for the concrete analysis of \(\textsf{MLWE}\). Following the Dilithium methodology [31, §C.3], we assume that breaking \(\textsf{SelfTargetMSIS}\) requires to either (a) break the second-preimage resistance of the hash function, or (b) break an inhomogeneous \(\textsf{MSIS}\) instance, for which the best known attack is in [10, §4.2].

• For the smooth Rényi divergence, one could use Lemma 4.2 for a provable bound. However, it is not tight so we opt instead to use Conjecture 4.1.

We refer the reader to the full version of this paper where we provide the relationship between parameters the security/efficiency metrics is in. In addition, we provide example parameters for the NIST security level I (Table 3).

We have presented \(\mathsf {\text {Raccoon}}\), a masking-friendly signature scheme with a formal security proof in the t-probing model based on standard lattice assumptions. We present a few natural extensions of our work:

• Tighter proof. The recent Hint-MLWE assumption by Kim et al. [30] seems perfectly suited to study \(\mathsf {\text {Raccoon}}\), as illustrated by a thresholded variant of \(\mathsf {\text {Raccoon}}\) [36]. For \(\mathsf {\text {Raccoon}}\) itself, an obstacle to a direct application is that [30] provided security reductions for Gaussian distributions, whereas \(\mathsf {\text {Raccoon}}\) uses sums of uniform distributions.

• More realistic models. While the t-probing model is a simple and convenient abstraction of real-world leakage, there exist more realistic models such as the random probing and noisy leakage models. We expect a security analysis in these models to be informative and to raise its own challenges.

• Real-world assessment. Since side-channel analysis are grounded in real-world deployment, this work needs to be completed with a study of the concrete leakage of \(\mathsf {\text {Raccoon}}\) when implemented on real-world devices.