並列化Quotient Pipeliningモンゴメリ乗算に基づくFp2 乗算器データパスの設計とその同種写像暗号への応用に関する検討

• Item type: SIG Technical Reports(1)
• 公開日: 2021-07-12
• タイトル: 並列化Quotient Pipeliningモンゴメリ乗算に基づくFp2 乗算器データパスの設計とその同種写像暗号への応用に関する検討
• タイトル / 言語: en
• タイトル: Design of Fp2 Multiplier Datapath Based on Parallelized QP Montgomery Multiplication and Its Application to Isogeny-based Cryptography
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: HWS
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学電気通信研究所／国立研究開発法人科学技術振興機構，さきがけ
• 著者所属: 東北大学電気通信研究所
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication Tohoku University / PRESTO, Japan Science and Technology Agency
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication Tohoku University
• 著者名: 上野, 嶺; 本間, 尚文
• 著者名(英): Rei, Ueno; Naofumi, Homma
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，同種写像暗号向け有限体乗算器の設計を示す．代表的な同種写像暗号である SIKE を低遅延化するためには Fp2 乗算の低遅延化が重要であり，Fp2 乗算一回は三回の Fp 乗算で実行されるため，三回の Fp 乗算を効率的に実行可能な剰余乗算器アーキテクチャが求められる．本稿では，Quotient-Pipelining (QP) モンゴメリ乗算と呼ばれるハードウェアアルゴリズムを三回の乗算を並列かつ効率的に実行できるように拡張した並列化 QP モンゴメリ乗算器の設計を示す．提案乗算器は従来の QP モンゴメリ乗算器のクリティカルパスとなっていた桁上げ伝搬加算器をパイプライン化することで動作周波数を向上しつつ並列化を可能とする．さらに，QP モンゴメリ乗算は冗長表現を用いるため，乗算器のオペランド長が大きくなり実装コストが増大するという問題があったが，SIKE で用いられる素数のモンゴメリ親和性 (Montgomery friendness) を活用することでこのオーバーヘッドを回避できることを示す．本稿では，提案乗算器を Xilinx Vertex-7 および Nangate 45 nm Open Cell Library を用いて実装し，その実装コストを評価する．その結果，提案乗算器は同デバイスに実装された既存の SIKEp434 向け乗算器よりも高速に SIKEp434 を実行できる可能性があることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a multiplier design for an isogeny-based KEM, SIKE. The proposed multiplier is based on a new Montgomery multiplication algorithm named parallelized quotient-pipelining (QP) Montgomery multiplication, which is an extension of QP Montgomery multiplication, because it is important for reducing SIKE latency to develop a multiplier that can perform three Fp multiplication efficiently in parallel to evaluate an Fp2 multiplication. In addition, we demonstrate that the overhead of (parallelized) QP Multiplication can be avoided by an optimal parameter choice utilizing the Montgomery friendness of SIKE prime. In this paper, we evaluate the proposed multiplier through experimental implementations on FPGA and ASIC and estimate the SIKE execution time. As a result, we confirm that the proposed multiplier may perform SIKEp434 faster than conventional multipliers for SIKEp434 on a Xilinx Vertex-7 FPGA.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2021-CSEC-94, 号 9, p. 1-6, 発行日 2021-07-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会