Revised Method for Sampling Coefficient Vector of GNR-enumeration Solution

Full Text (PDF, 1269KB), PP.1-20

Views: 0 Downloads: 0

Author(s)

Gholam Reza Moghissi 1,* Ali Payandeh 1

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

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2022.03.01

Received: 2 Oct. 2021 / Revised: 18 Nov. 2021 / Accepted: 25 Dec. 2021 / Published: 8 Aug. 2022

Index Terms

BKZ Simulation, GNR Enumeration, Coefficient Vector, Sampling Method, Expected Value, Variance.

Abstract

For selecting security parameters in lattice-based cryptographic primitives, the exact manner of BKZ algorithm (as total cost and specification of output basis) should be estimated in high block sizes. The simulations of BKZ are used to predict (estimate) the exact manner of BKZ algorithm which cannot be studied by practical running of BKZ algorithm for higher block sizes. Sampling method of GNR (Gamma-Nguyen-Regev) enumeration solution vector v is one of the main components of designing BKZ-simulation and it includes two phases: sampling the norm of solution vector v and sampling corresponding coefficient vectors. Our work, by Moghissi and Payandeh in 2021, entitled as “Better Sampling Method of Enumeration Solution for BKZ-Simulation”, introduces a simple and efficient idea for sampling the norm and coefficient vectors of GNR enumeration solution v. This paper proposes much better analysis for approximating the expected value and variance of the entries of these coefficient vectors. By this analysis, our previous idea for sampling the coefficient vectors is revised, which means that the expected value and variance of every entry in these coefficient vectors sampled by our new sampling method, are more close to the expected value and variance of corresponding entries in original sampling method, while these new sampled coefficient vectors include no violation from main condition of GNR bounding function (i.e., our new sampling method is not a rejection sampling). 

Cite This Paper

Gholam Reza Moghissi, Ali Payandeh, "Revised Method for Sampling Coefficient Vector of GNR-enumeration Solution", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.8, No.3, pp. 1-20, 2022. DOI:10.5815/ijmsc.2022.03.01

Reference

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

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

[3]M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. W. Postlethwaite, F. Virdia, and T. Wunderer. “Estimate all the {LWE, NTRU} schemes!”, In SCN, pages 351–357, 2018. 

[4]Shi Bai, Damien Stehlé, Weiqiang Wen, “Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ”, ASIACRYPT 2018.

[5]Moghissi, G., Payandeh, A. (2021). “Better Sampling Method of Enumeration Solution for BKZ-Simulation”, The ISC International Journal of Information Security, 13(2), pp. 177-208. doi: 10.22042/isecure.2021.225886.531.  

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

[7]Zhongxiang Zheng, Xiaoyun Wang, Yang Yu, “Orthogonalized lattice enumeration for solving SVP”, Science China Information Sciences 2018.

[8]Moghissi, Gholam Reza, and Ali Payandeh. "A Parallel Evolutionary Search for Shortest Vector Problem." International Journal of Information Technology and Computer Science, (2019).

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

[10]Moghissi, Gholam Reza, and Ali Payandeh. "Using Progressive Success Probabilities for Sound-pruned Enumerations in BKZ Algorithm." International Journal of Computer Network and Information Security 9.9 (2018): 10.

[11]D. Micciancio and O. Regev, “Lattice-based cryptography”, In Post-quantum cryptography, pp. 147-191, Springer Berlin Heidelberg, 2009.

[12]Moghissi, Gholam Reza, and Ali Payandeh. “Rejecting claimed speedup of 2^(β/2) in extreme pruning and revising BKZ 2.0 for better speedup”, Journal of Computing and Security, 2021; 8(1): 65-91. doi: 10.22108/jcs.2021.121191.1044. 

[13]Jensen, Johan Ludwig William Valdemar, "Sur les fonctions convexes et les inégalités entre les valeurs moyennes", Acta mathematica 30 (1906): 175-193.

[14]Gholam Reza Moghissi, Ali Payandeh, "Optimal bounding function for GNR-enumeration", International Journal of Mathematical Sciences and Computing (IJMSC), Vol.8, No.1, pp. 1-17, 2022. DOI: 10.5815/ijmsc.2022.01.01.

[15]Moghissi, Gholam Reza, and Ali Payandeh. "Formal Verification of NTRUEncrypt Scheme." International Journal of Computer Network and Information Security 8.4 (2016): 44.