## Abstract

Most algorithms for hard lattice problems are based on the principle of rank reduction: to solve a problem in a d-dimensional lattice, one first solves one or more problem instances in a sublattice of rank d–1, and then uses this information to find a solution to the original problem. Existing lattice sieving methods, however, tackle lattice problems such as the shortest vector problem (SVP) directly, and work with the full-rank lattice from the start. Lattice sieving further seems to benefit less from starting with reduced bases than other methods, and finding an approximate solution almost takes as long as finding an exact solution. These properties currently set sieving apart from other methods. In this work we consider a progressive approach to lattice sieving, where we gradually introduce new basis vectors only when the sieve has stabilized on the previous basis vectors. This leads to improved (heuristic) guarantees on finding approximate shortest vectors, a bigger practical impact of the quality of the basis on the run-time, better memory management, a smoother and more predictable behavior of the algorithm, and significantly faster convergence – compared to traditional approaches, we save between a factor 20 to 40 in the time complexity for SVP.

Original language | English |
---|---|

Title of host publication | Post-Quantum Cryptography |

Subtitle of host publication | 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings |

Editors | T. Lange, R. Steinwandt |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 292-311 |

Number of pages | 20 |

ISBN (Electronic) | 978-3-319-79063-3 |

ISBN (Print) | 978-3-319-79062-6 |

DOIs | |

Publication status | Published - 2018 |

Event | 9th International Conference on Post-Quantum Cryptography (PQCrypto 2018) - Fort Lauderdale, United States Duration: 9 Apr 2018 → 11 Apr 2018 Conference number: 9 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10786 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 9th International Conference on Post-Quantum Cryptography (PQCrypto 2018) |
---|---|

Abbreviated title | PQCrypto 2018 |

Country/Territory | United States |

City | Fort Lauderdale |

Period | 9/04/18 → 11/04/18 |

## Keywords

- Lattice sieving
- Lattice-based cryptography
- Nearest neighbor searching
- Shortest vector problem (SVP)