Abstract
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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
By “original”, we mean the LW sampler with the parameters resulting from the original analysis in [34].
- 2.
See Remark 3.2 for details on the definition of k.
- 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.
- 5.
The other public key matrix \(\textbf{A}'\) is generated using a public seed of 256 bits.
- 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.
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})\).
References
Agrawal, S., Kirshanova, E., Stehlé, D., Yadav, A.: Practical. Round-Optimal Lattice-Based Blind Signatures. In: CCS (2022). https://doi.org/10.1145/3548606.3560650
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math, Cryptol. 9(3), 169–203 (2015)
Alkim, E., Barreto, P.S.L.M., Bindel, N., Krämer, J., Longa, P., Ricardini, J.E.: The lattice-based digital signature scheme qTESLA. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 441–460. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57808-4_22
Banaszczyk, W.: New Bounds in Some Transference Theorems in the Geometry of Numbers. Math, Ann (1993)
Bert, P., Eberhart, G., Prabel, L., Roux-Langlois, A., Sabt, M.: Implementation of lattice trapdoors on modules and applications. In: Cheon, J.H., Tillich, J.-P. (eds.) PQCrypto 2021 2021. LNCS, vol. 12841, pp. 195–214. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_11
Bert, P., Fouque, P.-A., Roux-Langlois, A., Sabt, M.: Practical implementation of ring-SIS/LWE based signature and IBE. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 271–291. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_13
Beullens, W., Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Lattice-based blind signatures: short, efficient, and round-optimal. IACR Cryptol. ePrint Arch. p. 77 (2023)
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3
Bos, J.W., et al.: CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM. In: EuroS &P (2018). https://doi.org/10.1109/EuroSP.2018.00032
Chen, Y.: Réduction de Réseau et Sécurité Concrète du Chiffrement Complètement Homomorphe. Ph.D. thesis, Paris 7 (2013)
Chen, Y., Genise, N., Mukherjee, P.: Approximate trapdoors for lattices and smaller hash-and-sign signatures. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11923, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_1
Cheon, J.H., et al.: HAETAE: Shorter lattice-based fiat-shamir signatures. IACR Cryptol. ePrint Arch. p. 624 (2023)
Le Dévéhat, A., Shizuya, H., Hasegawa, S.: On the higher-bit version of approximate inhomogeneous short integer solution problem. In: Conti, M., Stevens, M., Krenn, S. (eds.) CANS 2021. LNCS, vol. 13099, pp. 253–272. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92548-2_14
Devevey, J., Fawzi, O., Passelègue, A., Stehlé, D.: On rejection sampling in lyubashevsky’s signature scheme. In: ASIACRYPT (2022). https://doi.org/10.1007/978-3-031-22972-5_2
Devevey, J., Passelègue, A., Stehlé, D.: G+G: A fiat-shamir lattice signature based on convolved gaussians. In: ASIACRYPT (2023). https://doi.org/10.1007/978-981-99-8739-9_2
Ducas, L., Espitau, T., Postlethwaite, E.W.: Finding short integer solutions when the modulus is small. In: CRYPTO (2023). https://doi.org/10.1007/978-3-031-38548-3_6
Ducas, L., et al.: CRYSTALS-dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptographic Hardware Embed. Syst. 2018, 238–268 (2018). https://doi.org/10.13154/tches.v2018.i1.238-268
Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_2
Ducas, L., Micciancio, D.: Improved short lattice signatures in the standard model. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 335–352. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_19
Espitau, T., et al: A simpler, parallelizable. maskable variant of falcon. In: EUROCRYPT (2022). https://doi.org/10.1007/978-3-031-07082-2_9
Espitau, T., Kirchner, P.: The nearest-colattice algorithm: time-approxmation tradeoff for approx-CVP. In: ANTS XIV (2020)
Espitau, T., Tibouchi, M., Wallet, A., Yu, Y.: Shorter hash-and-sign lattice-based signatures. In: CRYPTO (2022). https://doi.org/10.1007/978-3-031-15979-4_9
Genise, N., Micciancio, D.: Faster gaussian sampling for trapdoor lattices with arbitrary modulus. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 174–203. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_7
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC (2008). https://doi.org/10.1145/1374376.1374407
Jackson, K., Miller, C., Wang, D.: Evaluating the security of CRYSTALS-dilithium in the quantum random oracle model. IACR Cryptol. ePrint Arch, pp. 1968 (2023)
Jeudy, C., Roux-Langlois, A., Sanders, O.: Lattice signature with efficient protocols. application to anonymous credentials. In: CRYPTO (2023). https://doi.org/10.1007/978-3-031-38545-2_12
Jeudy, C., Roux-Langlois, A., Sanders, O.: Phoenix: hash-and-sign with aborts from lattice gadgets. IACR Cryptol. ePrint Arch, pp. 446 (2023)
Kiltz, E., Lyubashevsky, V., Schaffner, C.: A concrete treatment of fiat-shamir signatures in the quantum random-oracle mode. In: EUROCRYPT (2018). https://doi.org/10.1007/978-3-319-78372-7_18
Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565–599 (2014). https://doi.org/10.1007/s10623-014-9938-4
Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 373–403. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_13
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_43
Lyubashevsky, V., Nguyen, N.K., Plançon, M.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. In: CRYPTO (2022). https://doi.org/10.1007/978-3-031-15979-4_3
Lyubashevsky, V., Nguyen, N.K., Plançon, M., Seiler, G.: Shorter Lattice-Based Group Signatures via “Almost Free” Encryption and Other Optimizations. In: ASIACRYPT (2021). https://doi.org/10.1007/978-3-030-92068-5_8
Lyubashevsky, V., Wichs, D.: Simple lattice trapdoor sampling from a broad class of distributions. In: PKC (2015). https://doi.org/10.1007/978-3-662-46447-2_32
Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster. smaller. In: EUROCRYPT (2012). https://doi.org/10.1007/978-3-642-29011-4_41
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. (2007). https://doi.org/10.1137/S0097539705447360
Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: EUROCRYPT (2016). https://doi.org/10.1007/978-3-662-49890-3_31
NIST: Post-Quantum Cryptography Standardization. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization
NIST: Post-quantum cryptography: standardization of additional digital signature schemes. https://csrc.nist.gov/Projects/pqc-dig-sig/standardization
Peikert, C.: Limits on the hardness of lattice problems in l\({}_{\text{ p }}\) norms. Comput. Complex. (2008). https://doi.org/10.1007/s00037-008-0251-3
Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: CRYPTO (2010). https://doi.org/10.1007/978-3-642-14623-7_5
del Pino, R., et al.: Raccoon: a side-channel secure signature scheme. https://github.com/masksign/raccoon/blob/main/doc/raccoon.pdf
del Pino, R., Katsumata, S.: A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling. In: CRYPTO (2022). https://doi.org/10.1007/978-3-031-15979-4_11
del Pino, R., Lyubashevsky, V., Seiler, G.: Lattice-based group signatures and zero-knowledge proofs of automorphism stability. In: CCS (2018). https://doi.org/10.1145/3243734.3243852
Prest, T.: Sharper bounds in lattice-based cryptography using the Rényi divergence. In: ASIACRYPT (2017). https://doi.org/10.1007/978-3-319-70694-8_13
Prest, T., et al.: FALCON. Tech. rep. (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022
Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing (2012). https://doi.org/10.1017/cbo9780511794308.006
Yu, Y., Jia, H., Wang, X.: Compact lattice gadget and its applications to hash-and-sign signatures. In: CRYPTO (2023). https://doi.org/10.1007/978-3-031-38554-4_13
Zhang, S., Yu, Y.: Towards a simpler lattice gadget toolkit. In: PKC (2022). https://doi.org/10.1007/978-3-030-97121-2_18
Acknowledgments
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.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Concrete Security Analysis
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.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Jeudy, C., Roux-Langlois, A., Sanders, O. (2024). Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets. In: Saarinen, MJ., Smith-Tone, D. (eds) Post-Quantum Cryptography. PQCrypto 2024. Lecture Notes in Computer Science, vol 14771. Springer, Cham. https://doi.org/10.1007/978-3-031-62743-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-62743-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-62742-2
Online ISBN: 978-3-031-62743-9
eBook Packages: Computer ScienceComputer Science (R0)