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.
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) |
ISSN: | 1438-0064 |
Notes: | Revised version is accepted to HiPC 2021 |