九州大学学術情報リポジトリ
Kyushu University Institutional Repository
Efficient Implementation and Performance
Evaluation of Lattice/based Cryptography over Memory/Constrained Environments
袁, ヤ
https://doi.org/10.15017/4060003
出版情報：九州大学, 2019, 博士（機能数理学）, 課程博士 バージョン：
権利関係：
（様式３）
氏 名 ：袁 ヤ
論 文 名 ：
Efficient Implementation and Performance Evaluation of Lattice-based Cryptography over Memory-Constrained Environments
(格子暗号方式のメモリ制限下での効率的な実装法および性能評価)
区 分 ：甲論 文 内 容 の 要 旨
Traditional public-key cryptography algorithms such as the popular RSA and elliptic curve cryptography is the critical technology to advanced cybersecurity. However, since 1994 Peter Shor proposed an algorithm that can crack all RSA and elliptic curve cryptography, quantum computers using Shor's algorithm that brings with it a significant threat to the modern cryptosystems, applications, communication protocols, and so on. Thus, the practical research of new cryptography secure against attacks by quantum computers is required.
In August 2015, the National Security Agency (NSA) announced its plans to transition to quantum-resistant algorithms. In 2016, the National Institute of Standards and Technology (NIST) launched a project to solicit, evaluate, and standardize post-quantum cryptography (PQC) in a bid to develop the next-generation quantum-safe cryptographic standard.
Lattice-based cryptography, as one of the strongest candidates of PQC, has attracted a lot of interest from the cryptographic community because of its high-security, efficiency, and applicability. In this thesis, we focus on the efficient implementation and performance evaluation of lattice-based cryptography.
Firstly, we propose an efficient implementation of a lattice-based encryption scheme on a memory-constrained Java Card. We implement the original ring-LWE based encryption scheme on a standard Java Card platform by combining the number theoretic transform and improved Montgomery modular multiplication without any cryptographic co-processor support. We then optimize discrete Ziggurat sampling and Knuth-Yao methods to sample from prescribed probability distributions on our Java Card. Our result demonstrates that implementing more lattice-based cryptosystems on memory-constrained devices is feasible.
Secondly, we present the first implementation of several candidate algorithms for the NIST PQC project on JavaScript-enabled platforms with good performance, portability, and scalability. We use the number theoretic transform to speed up polynomial multiplication and the modified Knuth-Yao algorithm for efficient discrete Gaussian sampling. We report the performance of our JavaScript implementation on multiple platforms, including Web browsers, embedded devices, Android phones, and so on. Our proof-of-concept implementation demonstrates that some of the lattice-based cryptosystems can be implemented efficiently in JavaScript.
Lastly, based on the above results, we present an approach using lattice-based cryptography as a proof-of-concept for securing power substation communications. We implement a digital signature Dilithium and an encryption scheme Kyber on an intelligent electronic device (IED), transmitted encrypted data on a simulated substation Ethernet LAN using multicast message packets based on the international standard IEC 61850, and measure their performance. Our implementation performs better than traditional RSA cryptosystems that the execution of Dilithium and Kyber on the low-specification device could be completed in 2 or 3 ms. We show that some of the lattice-based cryptosystems could run fast on IEDs and probably could be used to ensure the confidentiality and integrity of substation communications in the quantum computing era.
Hence, our work could be a good reference for lattice-based cryptography in the standardization process of NIST. In our future work, we expect to improve the implementation for particular platforms and investigate more lattice-based cryptosystems on multiple platforms for the NIST PQC standardization project.
