Discovery Sagaサイレントキーワード俯瞰

耐量子暗号 / 格子 / learning with errors問題 / 最短ベクトル問題 / 安全性解析 / 格子暗号 / LWE問題 / BKZアルゴリズム / 講師簡約アルゴリズム / 安全性評価 / 格子理論 / 公開鍵暗号 / 暗号 / アルゴリズム

来たる量子計算機の完成に備え、耐量子公開鍵暗号の安全性解析を行った。特に、その中でも最も注目されている格子暗号を対象とし、安全性の根拠となる最短ベクトル問題やlearning with errors（LWE）問題の困難性解析を行った。まず、代表的な近似最短ベクトル探索アルゴリズムとして知られるLLLアルゴリズムにおいて、低次元の場合に厳密な最短ベクトルを出力する条件を厳密に整理した。さらに、様々な変形方式のあるLWE問題を包括的に解く枠組みを整理し、その枠組みでの困難性を評価した。

これまで、格子暗号の安全性を見積もるために、Kannanの埋め込み法とBai-Galbraithの埋め込み法の二つが広く用いられてきた。本研究は、格子暗号の安全性を見積もるためのLWE問題の一般的な定式化を捉え、従来よりもLWE問題の計算量解析をより統一的に行えるようになったという意味で学術的意義を持つ。さらに、本研究は、将来量子計算機が実用化された場合の情報社会の安全性を守るための耐量子公開鍵暗号の実用化へ向けて重要な社会的意義を持つ研究となった。

暗号認証等 / アルゴリズム / 情報基礎 / 数理工学 / 情報システム / 楕円曲線暗号 / 実装攻撃 / 公開鍵暗号 / 離散対数 / XTR / 電力解析 / 暗号 / 情報セキュリティ / RSA暗号 / サイドチャネル攻撃 / 実装解析 / 高速実装

(1)楕円曲線暗号において、個別に議論されてきたサイドチャネル攻撃およびその防御法を、攻撃者の能力に関する仮定を明らかにした上で、事前計算テーブルの有無に着目し体系的に類別した。この分類を基にして、サイドチャネル攻撃に対する防御法の構成に対して、メモリと速度の観点から統一的見通しを与えた。
次にサイドチャネル攻撃に対する、事前計算テーブルを用いる新たな防御法として、wNAF(Width-w Non-Adjacent Form、幅w非隣接形式)法を用いた防御法を提案し、その安全性・効率性の解析を行なった。この防御法は、メモリと速度のトレードオフの関係において、最適であることも理論的に示した。
また、べき指数展開処理時に漏洩するサイドチャネル情報を用いて秘密べき指数を導出する方法について考察し、wNAF展開、fractional window展開については、SPAなどによりべき指数展開処理の実行シーケンスの特徴が検出できた場合に、観測した実行シーケンスから秘密べき指数を導出するアルゴリズムを構成した。
(2)楕円曲線暗号に対する実装攻撃の防御法として、Randomized Binary Signed Digitsとよばれる手法が提案されていたが、この防御法の不完全性を明らかした。
また、XTRとよばれる特殊な離散対数問題を利用した公開鍵暗号に対する実装攻撃の理論解析を行い、その防御法も検討した。その上で、XTRと楕円曲線暗号との性能比較を行った。
(3)代表的なKoblitz曲線を用いた公開鍵暗号に対する実装攻撃の理論分類・評価と同時に、実験的検証も試みた。特に、実装攻撃に対する2つの新しい防御法を提案した。2つの手法とも、単純電力解析に耐性を持つように固定パターン再符号化を利用するものである。プロジェクト最後の年であり、これまでの研究成果を整理し、残された検討課題を議論した。特にRFIDなどの現実のユビキタスシステムにおける実装環境での攻撃とその対策も考察した。

【研究分担者】
田端利宏	岡山大学	大学院・自然科学研究科	助教授	(Kakenデータベース)
桶屋勝幸	日立製作所	システム研究所	研究員
高木剛	公立はこだて未来大学	システム情報科学部	助教授	(Kakenデータベース)