Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets

Preimage sampling is a fundamental tool in lattice-based cryptography, and its performance directly impacts that of the cryptographic mechanisms relying on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In an effort to improve preimage sampling for Micciancio-Peikert (MP) trapdoors, Lyubashevsky and Wichs (LW) introduced a new sampler which leverages rejection sampling but suffers from strong parameter requirements that hampered performance. As a consequence it seemed to be restricted to theoretical applications and has not been, to our knowledge, considered for real-world applications.

Our first contribution is to revisit the LW sampler by proposing an improved analysis which yields much more compact parameters. This leads to gains on the preimage size of about 60% over the LW sampler, and up to 25% compared to the original MP sampling technique. It thus sheds a new light on the LW sampler, opening promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. To provide further improvements, we show that it perfectly combines with the approximate trapdoors approach by Chen, Genise and Mukherjee, but with a smaller preimage error.

Building upon those results, we introduce a hash-and-sign signature scheme called Phoenix. The scheme is based on the \(\mathrm {M\text {-}LWE}\) and \(\textrm{M}\text {-}\textrm{SIS}\) assumptions and features attractive public key and signature sizes which are even smaller than those of the most recent gadget-based construction Eagle of Yu, Jia and Wang (Crypto’23). Moreover, Phoenix is designed to support a broad variety of distributions (uniform, spherical Gaussian, etc.) which can facilitate implementation, in particular in constrained environments.

1. 1.

   By “original”, we mean the LW sampler with the parameters resulting from the original analysis in [34].

2. 2.

   See Remark 3.2 for details on the definition of k.

3. 3.

   It is also the case for the original MP sampler as it may happen (albeit with negligible probability) that the sampler fails if \(\textbf{R}\) has norm larger than the bound used to set the Gaussian width s.

4. 4.

   For ease of exposition, we simplify the formulas in this paragraph but we stress that the final estimates in Tables 2, 3 and 4 are computed with the exact parameter settings.

5. 5.

   The other public key matrix \(\textbf{A}'\) is generated using a public seed of 256 bits.

6. 6.

   This slack comes from the multiplication \(M_\tau (\textbf{B}_L)\tau (\textbf{v}_2)\) in the coefficient embedding. Later we choose 3-smooth conductors yielding \(\mu = \sqrt{2}\), and \(\mu = 1\) for power-of-two conductors.

7. 7.

   Choosing \(\ell = k-2\) or \(\ell = k-1\) is possible as opposed to the approach in [11] because \(\textbf{e}\) is smaller by a factor of \(\sqrt{3} \omega (\sqrt{\log _2 nd})\).

This work has received a French government support managed by the National Research Agency in the ASTRID program, under the national project AMIRAL with reference ANR-21-ASTR-0016, and in the MobiS5 project with reference ANR-18-CE-39-0019-02 MobiS5. We warmly thank Vadim Lyubashevsky for helpful discussions on the Lyubashevsky-Wichs sampler, as well Nicholas Genise for interesting discussions on approximate trapdoors.

Authors and Affiliations

1. Orange Labs, Applied Crypto Group, Cesson-Sévigné, France

   Corentin Jeudy & Olivier Sanders

2. University of Rennes, CNRS, IRISA, Rennes, France

   Corentin Jeudy

3. Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, 14000, Caen, France

   Adeline Roux-Langlois

Corresponding author

Correspondence to Corentin Jeudy .

Editors and Affiliations

1. Tampere University, Tampere, Finland

   Markku-Juhani Saarinen

2. University of Louisville, Gaithersburg, MD, USA

   Daniel Smith-Tone

A Concrete Security Analysis

In this section we recall the methodology we use to estimate the bit security of the forgery and key recovery attacks in Sect. 4 and for Phoenix in Sect. 6.4. All our estimates use the Core-SVP model where the cost of the attack is given by the cost of running once the self-dual BKZ lattice reduction [37] with block size B. The cost is then modeled by the best known cost for lattice sieving, i.e., \(2^{0.292B}\) for the classical security and \(2^{0.257B}\) for the quantum security.

Under the Gaussian Heuristic and the Geometric Series Assumption, the BKZ algorithm with blocksize B would find a vector \(\textbf{v}\) in a N-dimensional lattice \(\mathcal {L}\) with \(\Vert \textbf{v}\Vert _2 \le \delta _{B}^N \text {Vol}(\mathcal {L})^{1/N}\), where \(\delta _{B} \approx ((\pi B)^{1/B} B/(2\pi e)))^{1/(2(B - 1))},\) by [10].

1.1 A.1 Key Recovery: \(\mathrm {M\text {-}LWE}\)

In all the schemes derived from the samplers in Sect. 4, the public key is given by \(\textbf{A}' \in R_q^{d \times m_1-d}\) and \(\textbf{B}= [\textbf{I}_d | \textbf{A}']\textbf{R}\bmod qR\) and the secret key by \(\textbf{R}\sim U(S_1^{m_1 \times m_2})\). Except for the LW signature, all our schemes use \(m_1 = 2d\). Key recovery thus corresponds to an instance of search \(\mathrm {M\text {-}LWE}_{n,d,m_1-d,q,U(S_1)}\) with \(m_2\) uniform ternary secrets. We use the lattice estimator [2] on the instance \(\textrm{LWE}_{nd,n(m_1-d),q,U(\{-1,0,1\})}\) to determine the minimal BKZ block size B among all the evaluated attacks. We discard the structure of the underlying ring and simply extend the dimensions by the ring degree n by considering the matrix \(M_\tau (\textbf{A}')\). To account for the \(m_2\) secrets, we consider the final cost to be that of running \(m_2\) times BKZ which gives a cost of \(m_2 2^{\nu B}\) for \(\nu \in \{0.292, 0.257\}\).

In the case of Phoenix, we apply public key compression which means that the adversary only has access to the high-order bits of \(\textbf{B}\). At a high-level, the key recovery consists in solving \(d(k-\ell )\) instances of \(\mathrm {M\text {-}LWE}\) to recover \(\textbf{R}\) from \(\textbf{B}_H \bmod q\). Since \(\textbf{B}_H\) contains less information on \(\textbf{R}\) than the full matrix \(\textbf{B}= [\textbf{I}_d | \textbf{A}']\textbf{R}\bmod qR\), we lower bound the complexity of key recovery by assessing the cost of recovering \(\textbf{R}\) given \(\textbf{B}\) as described above.

1.2 A.2 Forgery: \(\textrm{M}\text {-}\textrm{SIS}\) or \(\textrm{M}\text {-}\textrm{ISIS}\)

The complexity of the forgery can be estimated either by the security proof which relies on the \(\textrm{M}\text {-}\textrm{SIS}\) assumption, or by the \(\textrm{M}\text {-}\textrm{ISIS}\) assumption. In Sect. 4, we use the former approach on the \(\textrm{M}\text {-}\textrm{SIS}_{n,d,m,q,\beta ,\beta _\infty }\) assumption where the infinity norm \(\beta _\infty < q\) is discarded except for ensuring that q-vectors are not solutions. For Phoenix, we aim for a tighter security assessment using the \(\textrm{M}\text {-}\textrm{ISIS}_{n,d,m,q,\beta ',\beta _\infty '}\) assumption. Both approaches are detailed below.

1.2.1 A.2.1 Solving \(\textrm{M}\text {-}\textrm{SIS}\)

To estimate the security of \(\textrm{M}\text {-}\textrm{SIS}_{n,d,m,q,\beta ,\beta _\infty }\), we find the cost of finding \(\textbf{v}\in \mathcal {L}_q^\perp ([\textbf{I}_d | \textbf{A}' | \textbf{B}'])\) such that \(\Vert \textbf{v}\Vert _2 \le \beta \) and \(\Vert \textbf{v}\Vert _\infty \le \beta _\infty \), given \(\textbf{A}' \sim U(R_q^{d \times m_1-d})\) and \(\textbf{B}' \sim U(R_q^{d \times m_2})\) (with \(m = m_1 + m_2\)). We again look at the unstructured problem \(\textrm{SIS}_{nd, nm, q, \beta , \beta _\infty }\). For that, we first check that \(\min (\beta , \beta _\infty ) < q\) to avoid trivial solutions. Then, a standard optimization consists in finding a solution in a lattice of smaller dimension \(nd \le m^* \le nm\) and completing the solution with zeros. We then use BKZ in block size B such that \(\beta \ge \min _{nd \le m^* \le nm} \delta _{B}^{m^*} q^{nd/m^*}\). More precisely, for a fixed \(\beta \), we find \(m^*\) that maximizes \(\delta _{B} = \beta ^{1/m^*}q^{-nd/m^*{}^2}\) and then determine the block size B.

1.2.2 A.2.2 Direct Forgery: \(\textrm{M}\text {-}\textrm{ISIS}\)

In Phoenix, we estimate the forgery security via the \(\textrm{M}\text {-}\textrm{ISIS}\) assumption. A forgery consists of a vector \(\textbf{v}= [\textbf{v}_{1,1}^T | \textbf{v}_{1,2}^T | \textbf{v}_2^T]^T\) such that \([\textbf{I}_d | \textbf{A}' | \textbf{G}_H - \textbf{B}_H]\textbf{v}= \textbf{u}\bmod qR\) for a seemingly random and non-adversarial syndrome \(\textbf{u}= \mathcal {H}(\textsf{salt},\textbf{m})\). Since the adversary must provide the salt as part of the signature, the best strategy is to select an arbitrary message and salt, compute \(\textbf{u}= \mathcal {H}(\textsf{salt},\textbf{m})\) and find \(\textbf{v}\). Additionally, as \(\textbf{v}_2\) has very strict bounds (ternary), it is unlikely to have such small coefficients for \(\textbf{v}_2\) by solving \(\textrm{M}\text {-}\textrm{ISIS}\) on \(([\textbf{I}_d|\textbf{A}'|\textbf{G}_H-\textbf{B}_H], \textbf{u})\), unless they are set to zero. To hope for a valid forgery, one would thus fix a value for \(\textbf{v}_2 \in S_1^{d(k-\ell )}\) and solve the \(\textrm{M}\text {-}\textrm{ISIS}\) instance \(([\textbf{I}_d|\textbf{A}'], \textbf{u}' = \textbf{u}- (\textbf{G}_H-\textbf{B}_H)\textbf{v}_2)\) with norm bounds set from the signature verification from Algorithm 6.4. Setting \(\textbf{v}_2 = \textbf{0}\) would discard these columns which is done in the concrete attack below anyway. Due to the asymmetry of our preimages, the solution returned by the adversary should also have a specific form. In particular \(\textbf{v}_{1,1}, \textbf{v}_{1,2}\) are bounded both in Euclidean and infinity norms. This makes the fine-grained cryptanalysis difficult as current lattice reduction algorithms focus mostly on the Euclidean norm. Our approach is therefore once again to underestimate the actual cost of the attack by discarding the infinity norm and also the asymmetry of the solution. We believe that a thorough cryptanalysis would show that the forgery is more complex than the approach we describe here. More precisely, we simply evaluate the complexity of finding \(\textbf{v}_1\) such that \([\textbf{I}_d|\textbf{A}']\textbf{v}_1 = \textbf{u}' \bmod q\) and \(\Vert \textbf{v}_1\Vert _2 \le \beta = \sqrt{B_{1,1}^2 + B_{1,2}^2}\). We note that if \(\beta \) is close to or larger than \(q\sqrt{nd/12}\), this \(\textrm{M}\text {-}\textrm{ISIS}\) instance becomes trivial but not the forgery because of our infinity norm checks.

If \(\beta < q\sqrt{nd/12}\), a solution can be found using the Approximate CVP attack using the nearest-colattice algorithm of Espitau and Kirchner [21]. Given \((M_\tau ([\textbf{I}_d | \textbf{A}' ]), \tau (\textbf{u}')) \in \mathbb {Z}_q^{N \times D} \times \mathbb {Z}_q^{N}\), where \(N = nd\) and \(D = 2nd\), the algorithm can compute a solution within Euclidean norm \(\beta \) with BKZ of block size B such that \(\beta \ge \min \limits _{k^* \le D-N} \delta _{B}^{D-k^*} q^{N/(D-k^*)}\). Again, for a fixed \(\beta \), we find \(k^*\) which maximizes \(\delta _{B} = \beta ^{1/(D-k^*)}q^{-N/(D-k^*)^2}\) and then find the block size B.

Although our modulus is not particularly small with respect to the dimension and the \(\textrm{M}\text {-}\textrm{ISIS}\) bound, we also ran the estimator recently proposed by Ducas, Espitau and Postlethwaite [16] as a sanity check to make sure it does not lead to a more efficient attack than the previously described approach. Their tool unfortunately suffers from large memory requirements when computing the intersection of the hypercube and ball if the parameters are too large. We also leave this cryptanalysis to future work. The preimage and key compression can easily be reduced, and as a result the \(\textrm{M}\text {-}\textrm{ISIS}\) bound, to avoid these vulnerable parameter regimes at the expense of slightly larger signatures and/or keys. For example, if one were to take more conservative to achieve a smaller ratio \(\beta /q\), we could still get signatures of 2412 bytes and a public key of 2592 bytes. Nevertheless, we again insist on the fact that our scheme also places infinity norm bounds which may invalidate the attack or make it much more complex.

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics