CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems

Please always quote using this URN: urn:nbn:de:0297-zib-82802
  • Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

Download full text files

Export metadata

Author:Nariaki Tateiwa, Yuji ShinanoORCiD, Keiichiro Yamamura, Akihiro Yoshida, Shizuo KajiORCiD, Masaya YasudaORCiD, Katsuki FujisawaORCiD
Document Type:ZIB-Report
Tag:Discrete optimization; Lattice problem; Lattice-based cryptography; Parallel algorithms; Shortest vector problem; Ubiquity Generator Framework
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
PACS-Classification:00.00.00 GENERAL
Date of first Publication:2021/07/08
Series (Serial Number):ZIB-Report (21-16)