Revised Estimations for Cost and Success Probability of GNR-Enumeration

kground 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 ۵۰≤β≤۲۴۰, 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