8520
eng
reportzib
1
--
2021-12-08
--
Massively parallel sharing lattice basis reduction
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.
1438-0064
urn:nbn:de:0297-zib-85209
under review
publish
under review
Nariaki Tateiwa
Yuji Shinano
Yuji Shinano
Masaya Yasuda
Shizuo Kaji
Keiichiro Yamamura
Katsuki Fujisawa
ZIB-Report
21-38
eng
uncontrolled
Discrete optimization
eng
uncontrolled
Lattice problem
eng
uncontrolled
Lattice-based cryptography
eng
uncontrolled
Shortest vector problem
eng
uncontrolled
Parallel algorithms
eng
uncontrolled
Ubiquity Generator Framework
Software
Mathematics of Computing
Computer Applications
GENERAL
GENERAL
ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35]
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Shinano, Yuji
MODAL-Gesamt
HPO-NAVI
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8520/ZIB-Report-21-38.pdf