The International Arab Journal of Information Technology (IAJIT)


LWE Based Quantum-Resistant Pseudo-Random Number Generator

In the realm of cryptography, computational statistics, gaming, simulation processes, gambling, and other related fields, the design of Cryptographically Secure Pseudo-Random Number Generators (CSPRNGs) poses a significant challenge. With the rapid advancement of quantum computing, the imminent “quantum-threat” looms closer, posing a risk to our current cryptographically secure PRNGs. Consequently, it becomes crucial to address these threats seriously and develop diverse tools and techniques to ensure that cryptographically secure Pseudo-Random Number Generators (PRNGs) remain unbreakable by both classical and quantum computers. this paper presents a novel approach to constructing an effective Quantum-Resistant Pseudo-Random Number Generator (QRPRNG) using the principles of lattice-based Learning with Errors (LWE). LWE is considered quantum-resistant due to its reliance on the hardness of problems like the Shortest Vector Problem and Closest Vector Problem. Our work focuses on developing a QRPRNG that utilizes a Linear Feedback Shift Register (LFSR) to generate a stream of pseudo-random bits. To construct a secure seed for the QRPRNG, LWE is employed. The proposed QRPRNG incorporates a secure seed input to the LFSR, and employs a Homomorphic function to protect the security of the finite states within the LFSR. NIST statistical tests are conducted to evaluate the randomness of the generated output by the constructed QRPRNG. The proposed QRPRNG achieves a throughput of 35.172 Mbit/s.

[1] Abdulsalam S., Olaniyi M., and Ahmed A., “Enhanced Tiny Encryption Algorithm for Secure Electronic Health Authentication System,” International Journal of Information Privacy, Security and Integrity, vol. 3, no. 3, 2018. DOI:10.1504/IJIPSI.2018.10013222

[2] Albrecht M., Player R., and Scott S., “on the Concrete Hardness of Learning with Errors,” Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169-203, 2015. DOI:10.1515/jmc-2015-0016

[3] Banerjee A., Peikert C., and Rosen A., “Pseudorandom Functions and Lattices,” in Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, UK, pp. 719-737, 2012. 4_42

[4] Becker A., Gama N., and Joux A., “Solving Shortest and Closest Vector Problems: The Decomposition Approach,” Cryptology ePrint Archive, 2013.

[5] Bennett C. and Brassard G., “Quantum Cryptography: Public Key Distribution and Con Tos5,” Theoretical Computer Science, vol. 560, pp. 7-11, 2014.

[6] Blum M. and Micali S., Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, Association for Computing Machinery, 2019. DOI:10.1145/3335741.3335751

[7] Chowdhury S. and Maitra S., “Efficient Software Implementation of Linear Feedback Shift Registers.,” in Proceedings of the 2nd International Conference on Cryptology, Chennai, pp. 297-307, 2001.

[8] Delgado-Mohatar O. and Fúster-Sabater A., “Software Implementation of Linear Feedback Shift Registers over Extended Fields,” in Proceedings of the International Joint Conference CISIS’12-ICEUTE´ 12-SOCO´ 12 Special Sessions, Ostrava, pp. 117-126, 2013.

[9] Espinosa García J., Cotrina G., Peinado A., and Ortiz A., “Security and Efficiency of Linear Feedback Shift Registers in GF(2n) Using n-Bit Grouped Operations,” Mathematics, vol. 10, no. 6, 2022. 7390/10/6/996#

[10] Ferguson N., Schneier B., and Kohno T., Cryptography Engineering: Design Principles and Practical Applications, Wily, 2015.

[11] Hassan S. and Bokhari M., “Design of Pseudo Random Number Generator using Linear Feedback Shift Register,” International Journal of Engineering and Advanced Technology, vol. 9, no. 2, 2019. DOI: 10.35940/ijeat.B2912.129219

[12] Krivenko S. and Krivenko S., “Many-to-Many Linear-Feedback Shift Register,” in Proceedings of the IEEE 34th International Scientific Conference on Electronics and Nanotechnology, Kyiv, pp. 176-178, 2014. doi: 10.1109/ELNANO.2014.6873939

[13] Kumar A. and Mishra A., “Evaluation of Cryptographically Secure Pseudo Random Number Generators for Post Quantum Era,” in Proceedings of the IEEE 7th International Conference for Convergence in Technology, Mumbai, pp. 1-5, 2022. doi: 10.1109/I2CT54291.2022.9824543.

[14] Laarhoven T., “Sieving for Closest Lattice Vectors (With Preprocessing),” in Proceedings of the International Conference on Selected Areas in Cryptography, Canada, pp. 523-542, 2017.

[15] L’Ecuyer P., Random Number Generation, Springer Berlin Heidelberg, 2012.

[16] Naor M. and Reingold O., “Constructing Pseudo- Random Permutations with A Prescribed Structure,” Journal of Cryptology, vol. 15, pp. 97- 918 The International Arab Journal of Information Technology, Vol. 20, No. 6, November 2023 102, 2002. 0008-5

[17] Nejatollahi H., Dutt N., Ray S., Regazzoni F., Banerjee I., and Cammarota R., “Post-quantum Lattice-Based Cryptography Implementations: A Survey,” ACM Computing Surveys, vol. 51 no. 6, pp. 1-41, 2019.

[18] Pandit A., Kumar A., and Mishra A., “Lwr-based Quantum-Safe Pseudo-Random Number Generator,” Journal of Information Security and Applications, vol. 73, 2023.

[19] PCG, A Family of Better Random Number Generators | PCG, A Better Random Number Generator. https://www.pcg-

[20] Peikert C., SVP, Gram-Schmidt, LLL. 1, pp. 1-5, 2013.

[21] Rai V., Tripathy S., and Mathew J., “Memristor Based Random Number Generator: Architectures and Evaluation,” Procedia Computer Science, vol. 125, pp. 576-583, 2018.

[22] Regev O., “CS 294.1 The Learning with Errors Problem: Introduction and Basic Cryptography Solving Systems of Linear Equations,” 2018.

[23] Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., and Leigh S., A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards and Technology, 2010.

[24] Shaheen S., Yousaf M., and Jalil M., “A Smart Card Oriented Secure Electronic Voting Machine Built on NTRU,” The International Arab Journal of Information Technology, vol. 17, no. 3, pp. 386- 393, 2020. doi: 10.34028/iajit/17/3/12

[25] Shrestha B., Multiprime Blum-Blum-Shub Pseudorandom Number Generator, Master Thesis, Naval Postgraduate School Monterey United States, 2016.

[26] Tang X., Xu J., and Duan B., “A Memory-efficient Simulation Method of Grover's Search Algorithm,” Computers, Materials and Continua, vol. 57, no. 2, 2018.

[27] Tsaban B. and Vishne U., “Efficient Linear Feedback Shift Registers with Maximal Period,” Finite Fields and Their Applications, vol. 8, no. 2, pp. 256-267, 2002.

[28] Ugwuishiwu C., Orji U., Ugwu C, and Asogwa, C., “An Overview of Quantum Cryptography and Shor’s Algorithm,” International Journal of Advanced Trends in Computer Science and Engineering, vol. 9, no. 5, 2020.

[29] Xoroshiro128+ — RandomGen 1.23.1 Documentation. gen/devel/bit_generators/xoroshiro128.html.

[30] Yi X., Paulet R., and Bertino E., Homomorphic Encryption and Applications, Springer, 2014.