<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8520</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-12-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Massively parallel sharing lattice basis reduction</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-85209</identifier>
    <note>under review</note>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <author>Nariaki Tateiwa</author>
    <submitter>Yuji Shinano</submitter>
    <author>Yuji Shinano</author>
    <author>Masaya Yasuda</author>
    <author>Shizuo Kaji</author>
    <author>Keiichiro Yamamura</author>
    <author>Katsuki Fujisawa</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Discrete optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice-based cryptography</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest vector problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="00-XX">GENERAL</collection>
    <collection role="msc" number="06-XX">ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35]</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="HPO-NAVI">HPO-NAVI</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8520/ZIB-Report-21-38.pdf</file>
  </doc>
  <doc>
    <id>8280</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-07-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-82802</identifier>
    <note>Revised version is accepted to HiPC 2021</note>
    <enrichment key="opus.source">publish</enrichment>
    <author>Nariaki Tateiwa</author>
    <submitter>Yuji Shinano</submitter>
    <author>Yuji Shinano</author>
    <author>Keiichiro Yamamura</author>
    <author>Akihiro Yoshida</author>
    <author>Shizuo Kaji</author>
    <author>Masaya Yasuda</author>
    <author>Katsuki Fujisawa</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Discrete optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice-based cryptography</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest vector problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8280/ZIB-Report-21-16.pdf</file>
  </doc>
</export-example>
