## Samenvatting

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.

Originele taal-2 | Engels |
---|---|

Titel | Post-Quantum Cryptography |

Subtitel | 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings |

Redacteuren | T. Lange, R. Steinwandt |

Plaats van productie | Dordrecht |

Uitgeverij | Springer |

Pagina's | 292-311 |

Aantal pagina's | 20 |

ISBN van elektronische versie | 978-3-319-79063-3 |

ISBN van geprinte versie | 978-3-319-79062-6 |

DOI's | |

Status | Gepubliceerd - 2018 |

Evenement | Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018 - Fort Lauderdale, Verenigde Staten van Amerika Duur: 9 apr. 2018 → 11 apr. 2018 Congresnummer: 9 |

### Publicatie series

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

Volume | 10786 LNCS |

ISSN van geprinte versie | 0302-9743 |

ISSN van elektronische versie | 1611-3349 |

### Congres

Congres | Post-Quantum Cryptography |
---|---|

Verkorte titel | PQCrypto 2018 |

Land/Regio | Verenigde Staten van Amerika |

Stad | Fort Lauderdale |

Periode | 9/04/18 → 11/04/18 |