Massively parallel sharing lattice basis reduction
Zitieren Sie bitte immer diese 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.
Verfasserangaben: | Nariaki Tateiwa, Yuji ShinanoORCiD, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, 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: | 00-XX GENERAL |
06-XX ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35] | |
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) | |
CCS-Klassifikation: | D. Software |
G. Mathematics of Computing | |
J. Computer Applications | |
PACS-Klassifikation: | 00.00.00 GENERAL |
Datum der Erstveröffentlichung: | 08.12.2021 |
Schriftenreihe (Bandnummer): | ZIB-Report (21-38) |
ISSN: | 1438-0064 |
Bemerkungen: | under review |