量子計算と暗号理論（後期2単位）

教授 有田 正剛

１．授業のねらい

本講義では、量子計算の数学的枠組みを学んだ上で、量子計算が暗号の解読にどのように役立つか、とくにRSA暗号や楕円曲線暗号などの数論的な暗号を解読する原理について学ぶ。さらに、量子計算に対しても安全であると考えられている耐量子計算機暗号として、格子暗号、符号ベース暗号および同種写像暗号について学ぶ。

２．到達目標

・量子計算の数学的枠組みを理解する
・量子計算による暗号解読について理解する
・耐量子計算機暗号について理解する

３．授業計画と開講形態

開講形態は原則として全回教室での対面授業として開催する。

[量子計算の数学的枠組み]
第1-2回 複素数体上の線形代数
　　　　<ベクトル空間,線形演算子,固有ベクトル,エルミート演算子,ユニタリ演算子>
第3-4回 量子力学の公準
　　　　<量子ビット,観測,もつれ状態,密度演算子,Private Quantum Channel>
第5-6回 量子計算のユニバーサルゲート
　　　　<ブロッホ球,回転演算子,ハダマードゲート,π/8ゲート,CNOTゲート>

[量子計算による暗号解読]
第7-8回 量子フーリエ変換と位相推定
　　　　<量子フーリエ変換,位相推定,Shorのアルゴリズム,Groverのアルゴリズム>
第9回 隠れ部分群問題
　　　　<巡回群,CRSシステム,隠れシフト問題,CSIDH,2面体群>

[耐量子計算機暗号]
第10-11回 格子暗号
　　　　<格子,逐次最小,SVP,CVP,LWE問題,ガウス分布,LWE暗号>
第12-13回 符号ベース暗号
　　　　<線形符号,シンドローム復号問題,符号語探索問題,McEliece暗号,MDPC McEliece暗号>
第14-15回 同種写像暗号
　　　　<楕円曲線,超特異曲線,同種写像,同種写像問題,SIDH,CSIDH>

４．教科書

特に指定しない。

５．参考書

Michael A.Nielsen and Isaac L.Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010

６．関連科目

アルゴリズム基礎、数論基礎、暗号・認証と社会制度、暗号プロトコルと関連がある。

７．成績評価の方法と基準

到達目標を充足しているかどうかを評価の基準として、期末レポートにより評価する（90％）。なお、質問など授業への積極的な参加も評価対象とする（10％）。