Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Massively parallel sharing lattice basis reduction

Please always quote using this URN: urn:nbn:de:0297-zib-85209
under review
  • For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Nariaki Tateiwa, Yuji ShinanoORCiD, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, Katsuki FujisawaORCiD
Document Type:ZIB-Report
Tag:Discrete optimization; Lattice problem; Lattice-based cryptography; Parallel algorithms; Shortest vector problem; Ubiquity Generator Framework
MSC-Classification:00-XX GENERAL
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
CCS-Classification:D. Software
G. Mathematics of Computing
J. Computer Applications
PACS-Classification:00.00.00 GENERAL
Date of first Publication:2021/12/08
Series (Serial Number):ZIB-Report (21-38)
under review
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.