دانشگاه تربیت دبیر شهید رجائی
انتشارات دانشگاه تربیت دبیر شهید رجائی

  اخبار و اعلانات

 آمار

تعداد نشریات11
تعداد شماره‌ها218
تعداد مقالات2,188
تعداد مشاهده مقاله3,160,538
تعداد دریافت فایل اصل مقاله2,292,344
Payandeh, A., Moghissi, G. R.. (1402). Revised Estimations for Cost and Success Probability of GNR-Enumeration. فناوری آموزش, 11(2), 459-480. doi: 10.22061/jecei.2023.9228.588
A. R. Payandeh; G. R. Moghissi. "Revised Estimations for Cost and Success Probability of GNR-Enumeration". فناوری آموزش, 11, 2, 1402, 459-480. doi: 10.22061/jecei.2023.9228.588
Payandeh, A., Moghissi, G. R.. (1402). 'Revised Estimations for Cost and Success Probability of GNR-Enumeration', فناوری آموزش, 11(2), pp. 459-480. doi: 10.22061/jecei.2023.9228.588
Payandeh, A., Moghissi, G. R.. Revised Estimations for Cost and Success Probability of GNR-Enumeration. فناوری آموزش, 1402; 11(2): 459-480. doi: 10.22061/jecei.2023.9228.588

Revised Estimations for Cost and Success Probability of GNR-Enumeration

Journal of Electrical and Computer Engineering Innovations (JECEI)
دوره 11، شماره 2، مهر 2023، صفحه 459-480    اصل مقاله (1.07 M)
نوع مقاله: Original Research Paper
شناسه دیجیتال (DOI): 10.22061/jecei.2023.9228.588
نویسندگان
A. R. Payandeh* ؛ G. R. Moghissi
Department of ICT, Malek-Ashtar University of Technology, Tehran, Iran.
تاریخ دریافت: 22 دی 1401،  تاریخ بازنگری: 05 اردیبهشت 1402،  تاریخ پذیرش: 17 اردیبهشت 1402 
چکیده
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.
کلیدواژه‌ها
BKZ Simulation؛ Enumeration Cost؛ Success Probability؛ Optimal Enumeration Radius؛ Bounding Function Generator
مراجع
[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.

 

آمار
تعداد مشاهده مقاله: 295
تعداد دریافت فایل اصل مقاله: 246


سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب