CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems
Zitieren Sie bitte immer diese 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.
Verfasserangaben: | Nariaki Tateiwa, Yuji ShinanoORCiD, Keiichiro Yamamura, Akihiro Yoshida, Shizuo KajiORCiD, Masaya YasudaORCiD, Katsuki FujisawaORCiD |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Discrete optimization; Lattice problem; Lattice-based cryptography; Parallel algorithms; Shortest vector problem; Ubiquity Generator Framework |
MSC-Klassifikation: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) |
PACS-Klassifikation: | 00.00.00 GENERAL |
Datum der Erstveröffentlichung: | 08.07.2021 |
Schriftenreihe (Bandnummer): | ZIB-Report (21-16) |
ISSN: | 1438-0064 |
Bemerkungen: | Revised version is accepted to HiPC 2021 |