2024 - T3 - WS2 - Emerging topics in design and cryptanalysis of post-quantum schemes

Collection 2024 - T3 - WS2 - Emerging topics in design and cryptanalysis of post-quantum schemes

Organisateur(s) Chakraborty, Olive ; Kahrobaei, Delaram ; Perret, Ludovic ; Robinson, Angela
Date(s) 04/11/2024 - 08/11/2024
URL associée https://indico.math.cnrs.fr/event/5777/
13 20

One Bit (per Ring) to Rule Them All - Imperfect Randomness Harms Lattice Signatures (work in progress)

De Alexander May

The Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol's zero-knowledge property ensures that a signature does not leak information on its secret key $\vec s$, which is achieved by blinding $\vec s$ via proper randomness~$\vec y$. Most prominent Fiat-Shamir examples are DSA signatures and the new post-quantum standard Dilithium. In practice, DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness~$\vec y$ per signature. Similar attacks now emerge for lattice-based signatures, such as Dilithium. %, requiring leakage in only a \emph{single} bit of $\vec y$. We build on, improve and generalize the pioneering leakage attack on Dilithium by Liu, Zhou, Sun, Wang, Zhang, and Ming. \emph{In theory}, their original attack can recover a 256-dimensional subkey of Dilithium-II (aka ML-DSA-44) from leakage in a single bit of $\vec{y}$ per signature, in any bit position $j \geq 6$. However, the memory requirement of their attack grows exponentially in the bit position $j$ of the leak. As a consequence, if the bit leak is in a high-order position, then their attack is infeasible. In our improved attack, we introduce a novel transformation, that allows us to get rid of the exponential memory requirement. Thereby, we make the attack feasible for \emph{all} bit positions $j \geq 6$. Furthermore, our novel transformation significantly reduces the number of required signatures in the attack. The attack applies more generally to all Fiat-Shamir-type lattice-based signatures. While, in principle, one can base the security of these signatures on Regev's \emph{plain} LWE, most practical schemes use for efficiency either \emph{ring} or \emph{module} LWE. For a signature scheme based on module LWE over an $\ell$-dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a $\frac{1}{\ell}$-fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $\ell = 1$, the attack thus recovers the whole key. For Dilithium-II, which uses $\ell = 4$, knowledge of a $\frac{1}{4}$-fraction of the 1024-dimensional secret key lets its security estimate drop significantly from $128$ to $84$ bits. In contrast, in the plain LWE setting, the attack recovers only a single integer coordinate of the secret key, and thereby reduces the security level at most by a few bits. Our results thus indicate a drawback of module LWE, and especially ring LWE schemes, in the presence of bad randomness.

Informations sur la vidéo

Données de citation

  • DOI 10.57987/IHP.2024.T3.WS2.013
  • Citer cette vidéo May, Alexander (07/11/2024). One Bit (per Ring) to Rule Them All - Imperfect Randomness Harms Lattice Signatures (work in progress). IHP. Audiovisual resource. DOI: 10.57987/IHP.2024.T3.WS2.013
  • URL https://dx.doi.org/10.57987/IHP.2024.T3.WS2.013

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis