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). 

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.

The hardness assumption of approximate shortest vector problem (SVP) within the polynomial factor in polynomial time reduced to the security of many lattice-based cryptographic primitives, so solving this problem, breaks these primitives. In this paper, we investigate the suitability of combining the best techniques in general search/optimization, lattice theory and parallelization technologies for solving the SVP into a single algorithm. Our proposed algorithm repeats three steps in a loop: an evolutionary search (a parallelized Genetic Algorithm), brute-force of tiny full enumeration (in role of too much local searches with random start points over the lattice vectors) and a single main enumeration.  The test results showed that our proposed algorithm is better than LLL reduction and may be worse than the BKZ variants (except some so small block sizes). The main drawback for these test results is the not-sufficient tuning of various parameters for showing the potential strength of our contribution. Therefore, we count the entire main problems and weaknesses in our work for clearer and better results in further studies. Also it is proposed a pure model of Genetic Algorithm with more solid/stable design for SVP problem which can be inspired by future works.

We introduce a new technique for BKZ reduction, which incorporated four improvements of BKZ 2.0 (including: sound pruning, preprocessing of local blocks, shorter enumeration radius and early-abortion). This algorithm is designed based on five claims which be verified strongly in experimental results. The main idea is that, similar to progressive BKZ which using decrement of enumeration cost after each sequence incremental reduction to augment the block size, we use the decrement of enumeration cost after each round of our algorithm to augment the success probability of bounding function. Also we discussed parallelization considerations in our technique.

In this paper we explore a mechanized verification of the NTRUEncrypt scheme, with the formal proof system Isabelle/HOL. More precisely, the functional correctness of this algorithm, in its reduced form, is formally verified with computer support. We show that this scheme is correct what is a necessary condition for the usefulness of any cryptographic encryption scheme. Besides, we present a convenient and application specific formalization of the NTRUEncrypt scheme in the Isabelle/HOL system that can be used in further study around the functional and security analysis of NTRUEncrypt family.