一种适合资源受限设备的Falcon实现

A practical implementation of the signature scheme falcon suited for memory constrained device

Falcon是通过NIST第一轮筛选的唯一的基于NTRU格的签名方案.相较于其它的签名设计,Falcon的公钥长度和签名长度都较短,可有效降低通信的复杂度.它的劣势在于算法设计复杂,特别是其中的密钥生成算法和快速傅里叶采样算法难以理解且需要精细实现.本文分析了在内存资源受限的设备中实现Falcon签名方案的可行性,经过优化后,运行Falcon签名算法需要的动态内存降低到参考实现的37%.采用本文提出的实现方法,则签名需要334.7ms,签名验证需要6.16ms.

Falcon is the only NTRU-based signature scheme submitted for the NIST standardization process of postquantum cryptography.Compared to other signature schemes,Falcon has achieve very small public keys and signatures.The signature generation and verification procedures are very fast.The limitations are that both the key generation procedure and the fast Fourier sampling are non-trivial to understand and delicate to implement.This work aims to present an optimized implementation of Falcon suited for memory constrained devices.We managed to reduce the dynamic memory consumption of Falcon by 37%in comparison to the reference implementation..Besides,our implementation requires only 334.7ms for signing and 6.16ms for verification.