Giant Footprint Sharing: Classic McElieceの復号処理における省メモリ実装手法

• Item type: SIG Technical Reports(1)
• 公開日: 2024-11-26
• タイトル: Giant Footprint Sharing: Classic McElieceの復号処理における省メモリ実装手法
• タイトル / 言語: en
• タイトル: A Memory-Efficient Decryption Implementation for Classic McEliece
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 認証
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: パナソニック株式会社
• 著者所属: パナソニックホールディングス株式会社
• 著者所属: パナソニックホールディングス株式会社
• 著者所属: パナソニック株式会社
• 著者所属(英): en
• 著者所属(英): Panasonic Corporation
• 著者所属(英): en
• 著者所属(英): Panasonic Holdings Corporation
• 著者所属(英): en
• 著者所属(英): Panasonic Holdings Corporation
• 著者所属(英): en
• 著者所属(英): Panasonic Corporation
• 著者名: 劉, 聰; 矢内, 直人; 西田, 直央; 丸子, 彰
• 著者名(英): Cong, Liu; Naoto, Yanai; Naohisa, Nishida; Akira, Maruko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Classic McEliece は NIST による耐量子計算機暗号の標準化候補の暗号化方式として注目されている．しかしながら，復号処理の負荷が大きく，計算資源に制約のある環境には適さない．本稿では Classic McEliece の復号処理においてメモリサイズを削減する手法 Giant Footprint Sharing を提案する．大まかには，Classic McEliece では秘密情報から計算される多数の中間出力がメモリ上に格納されるが，Giant Footprint Sharing はこれらのうちボトルネックとなる部分を格納できる配列構造をメモリ上で共有することで，メモリサイズを削減する．Giant Footprint Sharing は高速フーリエ変換と併用することで高速化も可能である．Giant Footprint Sharing を Arm Cortex-M33 上で実装評価したところ，復号を扱う既存の高速実装 (Chenら，TCHES 2021) と比べて計算時間の実質的な劣化なく，メモリサイズを 46% まで削減できることを確認した．Giant Footprint Sharingについて詳細な検討を行ったところ，本稿の実装はいずれのコンパイラ最適化オプションを用いたとしてもメモリサイズが一定であること，また，メモリサイズと計算時間のトレードオフにおいて最適解となる実装であることも示す．本稿の手法は，大きな行列計算を含み，かつ，各変数のライフサイクルが短いアルゴリズムなら適用が期待できる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Classic McEliece has garnered attention as a candidate in NIST post-quantum cryptography standardization. However, it suffers from high computational demands during the decryption process, making it unsuitable for resource-constrained devices. This paper proposes a method that reduces memory size during decryption in Classic McEliece. The decryption algorithm processes a large number of in-memory intermediate states computed from the secrets. We identify the largest state among them and implement a memory-sharing structure using it, thereby reducing the overall memory footprint. The proposed method can also be combined with existing acceleration techniques. We evaluate the proposed method on the Arm Cortex-M33 and show that our implementation reduces memory size by up to 46% without significant degradation in computation time compared to previous research (Chen et al., TCHES 2021). A detailed examination of the proposed method further reveals that our implementation maintains a constant memory size regardless of the compiler optimization, and it achieves an optimal balance in the trade-off.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11238429
• 書誌情報: 研究報告電子化知的財産・社会基盤（EIP）; 巻 2024-EIP-106, 号 24, p. 1-8, 発行日 2024-11-26
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8647
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会