Solving noisy systems of equations to enhance side-channel attacks on Dilithium
*Konstanty Junosza-SzaniawskiCorresponding authorkonstanty.szaniawski@pw.edu.plFaculty of Mathematics and Information SciencePl. Politechniki 1Warsaw University of TechnologyWarsaw, 00-661, Poland0000-0003-0352-8583View full profile → , Piotr Lewandowskipiotr.lewandowski11.stud@pw.edu.plFaculty of Mathematics and Information SciencePl. Politechniki 1Warsaw University of TechnologyWarsaw, 00-661, PolandView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Apr 2025
- Published Online:
- 22 May 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2598
- Pages:
- 2333–2347
Abstract
Keywords
Subject Classifications
References
[1] N. I. of Standards and Technology, “Module-lattice-based digital signature standard. (department of commerce, washington, d.c.), federal information processing standards publication (fips) nist fips 204.” (2024). [Online]. Available: https://doi.org/10.6028/NIST.FIPS.20
[2] N. I. of Standards and Technology, Kevin Kimball, “Announcing request for nominations for publickey post-quantum cryptographic algorithms, docket no. 161116999-6999-02,” (2017). [Online]. Available: https://www.federalregister.gov/documents/2016/12/20/2016-30615/announcing-request-for-nominations-for-public-keypost-quantum-cryptographic-algorithms
[3] N. Tahat, A. K. Alomari, O. M. Al-Hazaimeh, and M. F. Al-Jamal, “An efficient self-certified multi-proxy signature scheme based on elliptic curve discrete logarithm problem,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 4, pp. 935–948 (2020). [Online]. Available: https://doi.org/10.1080/09720529.2020.1734293
[4] A. Pandey and I. Gupta, “A new undeniable signature scheme on general linear group over group ring,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 25, no. 5, pp. 1261–1273 (2022). [Online]. Available: https://doi.org/10.1080/09720529.2020.1744814
[5] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509 (1997). [Online]. Available: https://doi.org/10.1137/S0097539795293172
[6] L. Harn and T. Kiesler, “Improved rabin’s scheme with high efficiency,” Electronics Letters, vol. 25, pp. 726–728 (1989).
[7] M. Alaroud, N. Tahat, A. K. Alomari, and O. M. Al-hazaimeh, “A novel chaotic map partially blind signature scheme based on quadratic residue problems,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 3, pp. 1059–1071 (2024). [Online]. Available: https://doi.org/10.47974/JDMSC-1823.
[8] H.-F. Wang, S. Zhang, Y.-F. Zhao, and K.-H. Yeon, “Quantum mechanical algorithm for solving quadratic residue equation,” International Journal of Theoretical Physics, vol. 48, no. 11, pp. 3262–3267 (Nov. 2009). [Online]. Available: https://doi.org/10.1007/s10773-009-0115-x
[9] P. Klimov, A. Bengtsson, C. Quintana, A. Bourassa, S. Hong, A. Dunsworth, K. Satzinger, W. Livingston, V. Sivak, M. Niu, T. Andersen, Y. Zhang, D. Chik, J. Chen, C. Neill, C. Erickson, A. G. Dau, A. Megrant, P. Roushan, A. Korotkov, J. Kelly, V. Smelyanskiy, Y. Chen, and H. Neven, “Optimizing quantum gates towards the scale of logical qubits,” Nature Communications, vol. 15, p. 2442 (2024). [Online]. Available: https://www.nature.com/articles/s41467-024-46623-y
[10] M. A. Quantum, “Interferometric single-shot parity measurement in an inas-al hybrid device,” arXiv (April 2024). [Online]. Available: https://www.microsoft.com/enus/research/publication/interferometric-single-shot-paritymeasurement-in-an-inas-al-hybrid-device/
[11] E. G. Rieffel, A. A. Asanjan, M. S. Alam, N. Anand, D. E. Bernal Neira, S. Block, L. T. Brady, S. Cotton, Z. Gonzalez Izquierdo, S. Grabbe, E. Gustafson, S. Hadfield, P. A. Lott, F. B. Maciejewski, S. Mandr`a, J. Marshall, G. Mossi, H. M. Bauza, J. Saied, N. Suri, D. Venturelli, Z. Wang, and R. Biswas, “Assessing and advancing the potential of quantum computing: A nasa case study,” Future Generation Computer Systems, vol. 160, pp. 598–618 (2024). [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167739X24003121
[12] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, ser. STOC ’05. New York, NY, USA: Association for Computing Machinery, p. 84–93 (2005). [Online]. Available: https://doi.org/10.1145/1060590.1060603
[13] D. Jao and L. De Feo, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in Post-Quantum Cryptography, B.-Y. Yang, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 19–34 (2011).
[14] J. Ding and D. Schmidt, “Rainbow, a new multivariable polynomial signature scheme,” in Applied Cryptography and Network Security, J. Ioannidis, A. Keromytis, and M. Yung, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 164–175 (2005).
[15] R. J. McEliece, “A public key cryptosystem based on algebraic coding theory,” in DSN Progress Report (1978). [Online]. Available: https://api.semanticscholar.org/CorpusID:56502909
[16] D. J. Bernstein, D. Hopwood, A. H¨ulsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe, and Z. Wilcox-O’Hearn, “Sphincs: Practical stateless hash-based signatures,” in Advances in Cryptology – EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 368–397 (2015).
[17] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehl´e, “Crystals-Dilithium – algorithm specifications and supporting documentation (version 3.1),” (2021). [Online]. Available: https://pq-crystals.org/dilithium/
[18] S. Marzougui, V. Ulitzsch, M. Tibouchi, and J. Seifert, “Profiling side-channel attacks on dilithium: A small bitfiddling leak breaks it all,” IACR Cryptol. ePrint Arch., pp. 106 (2022). [Online]. Available: https://eprint.iacr.org/2022/106
[19] L. Lerman, G. Bontempi, and O. Markowitch, “Power analysis attack: an approach based on machine learning,” International Journal of Applied Cryptography, vol. 3, no. 2, pp. 97–115 (2014), pMID: 62722. [Online]. Available: https://www.inderscienceonline.com/doi/abs/10.1504/IJACT.2014.062722
[20] B. B. Brumley and N. Tuveri, “Remote timing attacks are still practical,” in Computer Security – ESORICS 2011, V. Atluri and C. Diaz, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 355–371 (2011).
[21] M. Guri, “Pixhell attack: Leaking sensitive information from air-gap computers via ‘singing pixels’,” in 2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC), pp. 976–987 (2024).
[22] L. Simon and R. Anderson, “Pin skimmer: inferring pins through the camera and microphone,” in Proceedings of the Third ACM Workshop on Security and Privacy in Smartphones & Mobile Devices, ser. SPSM ’13. New York, NY, USA: Association for Computing Machinery, pp. 67–78 (2013). [Online]. Available: https://doi.org/10.1145/2516760.2516770.
[23] P. Ravi, M. P. Jhanwar, J. Howe, A. Chattopadhyay, and S. Bhasin, “Side-channel assisted existential forgery attack on dilithium - a NIST PQC candidate,” Cryptology ePrint Archive, Paper 2018/821, (2018). [Online]. Available: https://eprint.iacr.org/2018/821
