Paving the Way for SQI<span style="font-variant: small-caps">sign</span>: Toward Efficient Deployment on 32-bit Embedded Devices

Abstract

The threat of quantum computing has spurred research into post-quantum cryptography. SQIsign, a candidate submitted to the standardization process of the National Institute of Standards and Technology, is emerging as a promising isogeny-based signature scheme. This work aimed to enhance SQIsign’s practical deployment by optimizing its low-level arithmetic operations. Through hierarchical decomposition and performance profiling, we identified the ideal-to-isogeny translation, primarily involving elliptic curve operations, as the main bottleneck. We developed efficient 32-bit finite field arithmetic for elliptic curves, such as basic operations, like addition with carry, subtraction with borrow, and conditional move. We then implemented arithmetic operations in the Montgomery domain, and extended these to quadratic field extensions. Our implementation offers improved compatibility with 32-bit architectures and enables more fine-grained SIMD acceleration. Performance evaluations demonstrated the practicality in low-level operations. Our work has potential in easing the development of SQIsign in practice, making SQIsign more efficient and practical for real-world post-quantum cryptographic applications.

Keywords

• post-quantum cryptography
• isogeny-based cryptography
• digital signature
• sign%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> SQI<span style="font-variant: small-caps">sign</span>
• elliptic curves