Massively parallel sharing lattice basis reduction
Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, Katsuki Fujisawa
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.
最新の画像[もっと見る]
- 新サーバ室構築中 2年前
- 新サーバ室構築中 2年前
- 新サーバ室構築中 2年前
- フロー補完問題と線形計画問題 3年前
- 研究室紹介ビデオ 3年前
- 格子暗号の安全性を検証する最短ベクトル問題に対する解読 3年前
- 今年(2020年)の主な成果 4年前
- 今年(2020年)の主な成果 4年前
- 今年(2020年)の主な成果 4年前
- Graph500 情報更新:2020年11月 4年前
「Weblog」カテゴリの最新記事
- 自己紹介と重要リンク
- 東京メトロ、生成AIチャットボット導入 忘れ物検索など
- 米Appleの独自AI「Apple Intelligence」の技術詳細 基盤モデルや学習データなどを...
- API経由でいつでもネコを召喚できるサービス「Cat as a service」でいろんなネコを...
- VMware問題でIIJやNTTコムなどが大幅値上げ、クラウド料金が2~3倍になる場合も
- シャープの液晶パネル工場は、なぜAIデータセンターになるのか? 名乗りを上げたソ...
- 米Appleの独自AI「Apple Intelligence」の技術詳細 基盤モデルや学習データなどを...
- 人間に匹敵する知能を持った汎用人工知能を開発した研究者に総額100万ドルの賞金を...
- 「日本のAI支出は2028年に2兆5000億円を超える」とIDC――インテルプレスセミナーにて
- IBMがAI/データプラットフォーム「watsonx」をアップデート