International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 8, No. 1, 8 Feb. 2022
Cover page and Table of Contents: PDF (size: 837KB)
Author(s)
Index Terms
Search algorithm, Approximate algorithm, Success probability, Enumeration cost, Time complexity.
Abstract
The proposed pruning technique by Gama-Nguyen-Regev for enumeration function makes this pruned enumeration (GNR-enumeration) as a claimant practical solver for SVP. The total cost of GNR-enumeration over a specific input lattice block with pre-defined enumeration radius and success probability would be minimized, just if this enumeration uses an optimal bounding function for pruning. Unfortunately, the running time of the original proposed algorithm of searching optimal bounding function by the work of Chen-Nguyen (in 2011) is not analyzed at all, so our work in this paper tries to introduce some efficient searching algorithms with exact analysis of their time/space complexity. In fact, this paper proposes a global search algorithm to generate the optimal bounding function by a greedy idea. Then, by using our greedy strategy and defining the searching steps based on success probability, a practical search algorithm is introduced, while it’s time-complexity can be determined accurately. Main superiorities of our algorithm include: complexity analysis, using high-performance version of each sub-function in designing search algorithm, jumping from local optimums, simple heuristics to guide the search, trade-off between quality of output and running time by tuning parameters. Also by using the building blocks in our practical search algorithm, a high-quality and fast algorithm is designed to approximate the optimal bounding function.
Cite This Paper
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
Reference
[1]D. Micciancio and O. Regev, “Lattice-based cryptography”, In Post-quantum cryptography, pp. 147-191, Springer Berlin Heidelberg, 2009.
[2]Moghissi, Gholam Reza, and Ali Payandeh. "A Parallel Evolutionary Search for Shortest Vector Problem." International Journal of Information Technology and Computer Science, (2019).
[3]Zhongxiang Zheng, Xiaoyun Wang, Yang Yu, “Orthogonalized lattice enumeration for solving SVP”, Science China Information Sciences 2018.
[4]Aono, Yoshinori, Phong Q. Nguyen, Yixin Shen, “Quantum lattice enumeration and tweaking discrete pruning”, International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2018.
[5]N. Gama, P. Q. Nguyen, and O. Regev, “Lattice enumeration using extreme pruning”, In Proc. EUROCRYPT ’10, volume 6110 of LNCS. Springer, 2010.
[6]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.
[7]ACD+18. 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.
[8]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.
[9]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.
[10]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.
[11]“SVP Challenge”, [Online]. Available: https://www.latticechallenge.org/svp-challenge/index.php.
[12]Moghissi, Gholam Reza, and Ali Payandeh. "Formal Verification of NTRUEncrypt Scheme." International Journal of Computer Network and Information Security 8.4 (2016): 44.