Revised Estimations for Cost and Success Probability of GNR-Enumeration

Payandeh, A. R.; Moghissi, G. R.

doi:10.22061/jecei.2023.9228.588

Document Type : Original Research Paper

Authors

Department of ICT, Malek-Ashtar University of Technology, Tehran, Iran.

https://doi.org/10.22061/jecei.2023.9228.588

Abstract

Background and Objectives: Since exact manner of BKZ algorithm for higher block sizes cannot be studied by practical running, therefore simulation of BKZ is used to predict the total cost of BKZ and quality of output basis. This paper revises some main components of BKZ-simulation for better predictions.
Methods: At first, by definition of full-enumeration success probability, the optimal enumeration radius is formally defined. Next, this paper defines three more pruning types, besides the well-known pruning by bounding function in GNR-enumerations, and consequently uses these four pruning types collectively in revision of success probability estimation. Also, by using these four pruning types and the process of updating-radius, this paper revises the estimation of enumeration cost. Finally, this paper introduces a simple technique to generate partially better bounding functions.
Results: For block sizes of 50≤β≤240, better domains of radius parameters in GNR enumeration are formally introduced. Also, our revised estimation of success probability (for GNR bounding function) in our test results shows non-negligible gap from former estimations in some main former studies. Moreover, our results show that the cost results by our proposed estimator of GNR-enumeration cost are closer to the cost results determined in experimental running of enumeration, than the cost results by Chen-Nguyen estimator.
Conclusion: This paper revises the estimators of cost and success probability for GNR-Enumeration, and justifies the value of these revised estimators by sufficient test results (in actual running and simulation of BKZ). Also our novel definition of optimal enumeration radius can be used effectively in actual running and simulation of BKZ.

Keywords

20.1001.1.23223952.2023.11.2.20.2

Main Subjects

Lattice-based Cryptography

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit: http://creativecommons.org/licenses/by/4.0/

Publisher’s Note

JECEI Publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Publisher

Shahid Rajaee Teacher Training University

References

[1] Y. Chen, P. Q. Nguyen, “BKZ 2.0: Better lattice security estimates,” in Proc. International Conference on the Theory and Application of Cryptology and Information Security: 1-20, Berlin Heidelberg, 2011.

[2] S. Bai, D. Stehlé, W. Wen, “Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ,” in Proc. Advances in Cryptology – ASIACRYPT 2018: 369-404, 2018.

[3] Y. Aono, Y. Wang, T. Hayashi, T. Takagi, “Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator,” in Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques: 789-819, Berlin, Heidelberg, 2016.

[4] J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte, Zhenfei Zhang, “Choosing parameters for NTRUEncrypt,” Cryptology ePrint Archive, Report 2015/708, 2015.

[5] M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. W. Postlethwaite, F. Virdia, T. Wunderer, “Estimate all the {LWE, NTRU} schemes!,” in Proc. International Conference on Security and Cryptography for Networks, 2018.

[6] M. R. Albrecht, et al., “Estimate all the {LWE, NTRU} schemes!,” [Online]. Available at: https://estimate-all-the-lwe-ntru-schemes.github.io/docs/.

[7] “Post-Quantum Cryptography Standardization Project”, [Online]. Available at: https://csrc.nist.gov/Projects/post-quantum-cryptography.

[8] J. Sharafi, H. Daghigh, “A Ring-LWE-based digital signature inspired by Lindner–Peikert scheme,” J. Math. Cryptology, 16(1): 205-214, 2022.

[9] N. Samardzic, A. Feldmann, A. Krastev et al., “CraterLake: a hardware accelerator for efficient unbounded computation on encrypted data,” in Proc. ISCA: 173-187, 2022.

[10] K. Cong, D. Cozzo, V. Maram, N. P. Smart, “Gladius: LWR based efficient hybrid public key encryption with distributed decryption,” in Proc. International Conference on the Theory and Application of Cryptology and Information Security: 125-155, Cham, 2021.

[11] T. Espitau, A. Joux, N. Kharchenko, “On a dual/hybrid approach to small secret LWE,” in Proc. International Conference on Cryptology in India: 440-462, Cham, 2020.

[12] G. Moghissi, A. Payandeh, “Better sampling method of enumeration solution for BKZ-Simulation,” ISC Int. J. Inf. Secur., 13(2): 177-208, 2021.

[13] N. Gama, P. Q. Nguyen, O. Regev, “Lattice enumeration using extreme pruning,” in Proc. EUROCRYPT ’10, volume 6110 of LNCS. Springer, 2010.

[14] G. R. Moghissi, A. Payandeh, “Rejecting claimed speedup of in extreme pruning and revising BKZ 2.0 for better speedup,” J. Comput. Secur., 8(1): 65-91, 2021.

[15] L. Devroye, “Sample-based non-uniform random variate generation,” in Proc. the 18th conference on Winter simulation: 260-265, 1986.

[16] Y. Chen, “Reduction de reseau et securite concrete du chiffrement completement homomorphe,” PhD thesis, Paris 7, 2013.

[17] “SVP Challenge,” [Online]. Available at: https://www.latticechallenge.org/svp-challenge/index.php.

[18] D. Goldstein, A. Mayer, “On the equidistribution of Hecke points,” Forum Math., 15(2): 165-190, Berlin, 2003.

[19] GitHub hosting service, “fplll library project,” [Online]. Available at: https://github.com/fplll/.

[20] V. Shoup, “NTL: a library for doing number theory”. [Online]. Available at: http://www.shoup.net/ntl/.

[21] G. R. Moghissi, A. Payandeh, "Using progressive success probabilities for sound-pruned enumerations in BKZ algorithm," Int. J. Compu. Network Inf. Secur, 10(9): 10-24, 2018.

[22] L. Ducas, “Shortest vector from lattice sieving: A few dimensions for free,”in Proc. EUROCRYPT: 125-145, 2018.

[23] Z. Zheng, X. Wang, Y. Yu, “Orthogonalized lattice enumeration for solving SVP,” Sci. China Inf. Sci. 61: 032115, 2018.

[24] G. R. Moghissi, A. Payandeh, "Optimal bounding function for GNR-enumeration," Int. J. Math. Sci. Comput. (IJMSC), 8(1): 1-17, 2022.

[25] G. R. Moghissi, A. Payandeh, "Design of optimal progressive BKZ with increasing success-probabilities and increasing block-sizes," J. Comput. Secur., 9(2): 65-93, 2022.

[26] D. J. Bernstein et al., NTRU Prime. Technical report, National Institute of Standards and Technology, 2020.

[27] J. Bos et al., "CRYSTALS - kyber: A CCA-secure module-lattice-based KEM," in Proc. 2018 IEEE European Symposium on Security and Privacy (EuroS&P): 353-367, London, UK, 2018.

[28] J. P. D’Anvers et al., SABER. Technical report, National Institute of Standards and Technology (2020).

[29] G. R. Moghissi, A. Payandeh, "Revised method for sampling coefficient vector of GNR-enumeration solution," Int. J. Math. Sci. Comput. (IJMSC), 8(3): 1-20, 2022.

LETTERS TO EDITOR

Journal of Electrical and Computer Engineering Innovations (JECEI) welcomes letters to the editor for the post-publication discussions and corrections which allows debate post publication on its site, through the Letters to Editor. Letters pertaining to manuscript published in JECEI should be sent to the editorial office of JECEI within three months of either online publication or before printed publication, except for critiques of original research. Following points are to be considering before sending the letters (comments) to the editor.

[1] Letters that include statements of statistics, facts, research, or theories should include appropriate references, although more than three are discouraged.

[2] Letters that are personal attacks on an author rather than thoughtful criticism of the author’s ideas will not be considered for publication.

[3] Letters can be no more than 300 words in length.

[4] Letter writers should include a statement at the beginning of the letter stating that it is being submitted either for publication or not.

[5] Anonymous letters will not be considered.

[6] Letter writers must include their city and state of residence or work.

[7] Letters will be edited for clarity and length.

Name *

Email Address *

Affiliation *

Comments *

Security Code *

Journal of Electrical and Computer Engineering Innovations (JECEI)

Revised Estimations for Cost and Success Probability of GNR-Enumeration

References

References

Send comment about this article

Volume 11, Issue 2
July 2023
Pages 459-480

Revised Estimations for Cost and Success Probability of GNR-Enumeration

References

References

Send comment about this article

Volume 11, Issue 2July 2023Pages 459-480

Volume 11, Issue 2
July 2023
Pages 459-480