CryptoDB
Algebraic Linear Analysis for Number Theoretic Transform in Lattice-Based Cryptography
| Authors: | |
|---|---|
| Download: | |
| Abstract: | The topic of verifying postquantum cryptographic software has never been more pressing than today between the new NIST postquantum cryptosystem standards being finalized and various countries issuing directives to switch to postquantum or at least hybrid cryptography in a decade. One critical issue in verifying lattice-based cryptographic software is range-checking in the finite-field arithmetic assembly code which occurs frequently in highly optimized cryptographic software. For the most part these have been handled by Satisfiability Modulo Theory (SMT) but so far they mostly are restricted to Montgomery arithmetic and 16-bit precision. We add semi-automatic range-check reasoning capability to the CryptoLine toolkit via the Integer Set Library (wrapped via the python package islpy) which makes it easier and faster to verify more arithmetic crypto code, including Barrett and Plantard finite-field arithmetic, and show experimentally that this is viable on production code. |
BibTeX
@article{tches-2025-35792,
title={Algebraic Linear Analysis for Number Theoretic Transform in Lattice-Based Cryptography},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={668-692},
url={https://tches.iacr.org/index.php/TCHES/article/view/12230},
doi={10.46586/tches.v2025.i3.668-692},
author={Chun-Ming Chiu and Jiaxiang Liu and Ming-Hsien Tsai and Xiaomu Shi and Bow-Yaw Wang and Bo-Yin Yang},
year=2025
}