Our second algorithm is for gadget subgaussian sampling. One distinguishing feature of our Gaussian sampler is that it does not need floating-point arithmetic, which makes it better compatible with constrained environments. Our first algorithm is for gadget Gaussian sampling. In this work, we propose two new gadget sampling algorithms for arbitrary moduli. Considering the necessity of arbitrary moduli, developing simpler and more practical gadget algorithms for arbitrary moduli is crucial to improving the practical performance of lattice based applications. The gadget algorithms for power-of-base moduli are very efficient and simple, however the current algorithms for arbitrary moduli are still complicated and practically more costly despite several efforts. These results fill the long-term gap in practical gadget-based signatures.Īs a building block, gadgets and associated algorithms are widely used in advanced lattice cryptosystems. It not only greatly outperforms the state-of-the-art LWE-based hash-and-sign signatures, but also has an even smaller size than the LWE-based Fiat-Shamir signature scheme Dilithium. The LWE-based scheme also achieves a desirable overall performance. The NTRU-based scheme offers comparable efficiency to Falcon and Mitaka and a simple implementation without the need of generating the NTRU trapdoor. Compared to the Gaussian-distributed errors in previous algorithms, the deterministic errors have a smaller size, which lead to a substantial gain in security and enables a practically working instantiation.Īs the applications, we present two practically efficient gadget-based signature schemes based on NTRU and Ring-LWE respectively. This ensures the security of the signature applications. We show that for uniformly random targets, the preimage and error distributions are simulatable without knowing the trapdoor. To this end, we develop a compact gadget framework in which the used gadget is a \emph computes the error and then randomly samples the preimage. This work aims to improve the practicality of gadget-based cryptosystems, with a focus on hash-and-sign signatures. For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based signatures. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions. In the past decade, they have been applied to build versatile and powerful cryptosystems. Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. Nevertheless, the key recovery in Mitaka requires much more traces than it does in Falcon, due to their different lattice Gaussian samplers. The same leakages exist within the integer Gaussian samplers of Mitaka, and they can also be used to mount key recovery attacks. Furthermore, combining the sign leakage and the aforementioned leakage, one can recover the key with only 45 000 signature measurements in a short time.Īs a by-product, we also extend our power analysis to Mitaka that is a recent variant of Falcon. We also show that this single bit of leakage is in effect enough for practical key recovery: with 170 000 traces one can fully recover the key of Falcon-512 within half an hour. We identify the leakage within the reference implementation of Falcon on an ARM Cortex-M4 STM32F407IGT6 microprocessor. This leakage was exposed in 2018 by Kim and Hong, but it is not considered in the Falcon’s implementation and unexploited for side-channel analysis until now. The analysis relies on the leakage of random sign flip within the integer Gaussian sampling. Our second result is a practical power analysis targeting the integer Gaussian sampler of Falcon. In addition, our approach is robust to inaccurate leakage classification, which is another advantage over parallelepiped-learning attacks. As a comparison, even with 106 traces, the former attack still needs about 1000 hours CPU time of lattice reduction for a full key recovery. Our approach substantially reduces the the requirement of measurements and computation resources: 220 000 traces is sufficient to recover the secret key of Falcon-512 within half an hour with a probability of ≈ 25%. Instead of resorting to the fourth moment as in former parallelepiped-learning attacks, we work with the second order statistics covariance and use its spectral decomposition to recover the secret information. The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. In this work, we study Falcon’s side-channel resistance by analysing its Gaussian samplers. Due to its low bandwidth and high efficiency, Falcon is seen as an attractive option for quantum-safe embedded systems. Falcon is one of the three post-quantum signature schemes selected for standardization by NIST.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |