gg-lll / greedy-global-lll

Implementations of Greedy-Global variants of LLL-style algorithms

Greedy-Global-LLL

This repository contains implementations accompanying the paper [5] titled "A Greedy Global Framework for LLL". The algorithms implemented are: Pot-DeepLLL [2], SS-DeepLLL [3], and their Greedy-Global variants proposed in [5]. The Pot-DeepLLL, SS-DeepLLL, Pot-GGLLL and SS-GGLLL algorithms use the GSO update techniques from [4], that make them more efficient than BKZ-8! SS-GGLLL gives shorter vectors than BKZ-12 for dimensions 100 and after.

The descriptions of the files that can be found in this repository are listed below.

• common.cpp   common.h   standalone_reduction.cpp   preprocessed_reduction.cpp For a given input basis, the functions contained in common.cpp may be used to run various lattice basis reduction algorithms. The menu-driven execution of individual algorithms is in standalone_reduction.cpp and preprocessed_reduction.cpp for multi-precision and standard datatype implementations respectively.

  • LLL (multi-precision implementation with overestimated precision)
  • Pot-DeepLLL (standard datatype implementation and multi-precision implementation with overestimated precision)
  • SS-DeepLLL (standard datatype implementation and multi-precision implementation with overestimated precision)
  • Pot-GGLLL (standard datatype implementation and multi-precision implementation with overestimated precision)
  • SS-GGLLL (standard datatype implementation and multi-precision implementation with overestimated precision)

• generate_SVP_bases.cpp
  Can be used to generate SVP Challenge style bases.

• collate.cpp
  Can be used to collate the results from multiple output files in one place.

• SVP_Bases   SVP_Bases_FPLLL   SVP_Bases_LLLReduced
  The input bases are contained in the zip file SVP_Bases. The same bases are in the zip file SVP_Bases_FPLLL, formatted for the use of FPLLL functions. The zip file SVP_Bases_LLLReduced contains the SVP_Bases in the other files, but 0.99-LLL reduced.

• SVP_Outputs_Standalone   SVP_Outputs_Preprocessed
  The outputs from our programs are contained in the zip files SVP_Outputs_Standalone and SVP_Outputs_Preprocessed for multi-precision and standard implementations respectively.

• Standalone_Averages   Preprocessed_Averages
  This folder contains the summaries reported in our paper.

References:

[1] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Mathematical programming, 66(1):181–199, 1994.

[2] Felix Fontein, Michael Schneider, and Urs Wagner. PotLLL: a polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73(2):355–368, 2014.

[3] Masaya Yasuda and Junpei Yamaguchi. A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths. Designs, Codes and Cryptography, 87(11):2489–2505, 2019.

[4] Junpei Yamaguchi and Masaya Yasuda. Explicit formula for gram-schmidt vectors in LLL with deep insertions and its applications. In Jerzy Kaczorowski, Josef Pieprzyk, and Jacek Pomykala, editors, Number-Theoretic Methods in Cryptology, pages 142–160, Cham, 2018. Springer International Publishing.

[5] Sanjay Bhattacherjee, Julio Hernandez-Castro and Jack Moyler. A Greedy Global Framework for LLL, Cryptology ePrint Archive, Paper 2023/261, https://eprint.iacr.org/2023/261.

Contributors: Sanjay Bhattacherjee ([email protected]) and Jack Moyler ([email protected])