Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 2
Zurück zur Trefferliste

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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.