シラバス GRADUATE SCHOOL
暗号プロトコル（後期2単位）
教授 有田 正剛
１．授業のねらい
暗号プロトコルとは、複数のパーティがお互いの入力を隠したまま、必要な情報のみをやりとりし、目標とする機能を協調して実現する方法である。「協調して」とは言ってもプロトコルを実行するパーティには悪意を持って他のパーティの情報を盗み取ろうとするものがいるので、暗号技術を用いて安全性を確立することが肝要となる。この講義では、暗号プロトコルのフォーマルな安全性定義を踏まえた上で、その実現方法の理論的な基盤を学ぶ。さらに、より実践的な方式としてzk-SNARKや準同型暗号についても学ぶ。
２．到達目標
- 暗号プロトコルのフォーマルな安全性定義を理解する
- コミットメントやゼロ知識証明などのプリミティブな暗号プロトコルを理解する
- 回路の秘密分散やガーブル化など、暗号プロトコルの実現方法の理論的な基盤を理解する
- zk-SNARKや準同型暗号の基本方式を理解する
３．授業計画と開講形態
開講形態は原則として全回教室での対面授業として開催する。
第1-2回 一方向関数と疑似乱数
<一方向関数,擬似乱数生成器,ハードコアビット,擬似ランダム関数,計算量的識別不可能性,統計的識別不可能性>
第3回 コミットメントプロトコル
<秘匿性,束縛性,Blumコミットメント,Naorコミットメント,対話的ハッシュ>
第4回 ゼロ知識証明プロトコル
<NP完全,3色問題,知識のゼロ知識証明,ハミルトン閉路>
第5回 暗号プロトコルの安全性定義
<プロトコル実行モデル,理想機能,安全な実現,ハイブリッドモデル,結合定理>
第6-7回 回路の秘密分散
<秘密分散,紛失通信プロトコル,GMW方式,SPDZ>
第8-9回 回路のガーブル化
<ガーブリングスキーム,回路秘匿性, Yaoの2パーティプロトコル>
第10-11回 マリシャスアドバーサリとBGWコンパイラ
<マリシャスアドバーサリ,Commit and Prove, BGWコンパイラ, 汎用的結合可能性>
第12-13回 zk-SNARK (簡潔なゼロ知識証明)
<ペアリング,ブラインド評価,Quadratic Arithmetic Programs,指数知識仮定>
第14-15回 イデアル格子暗号と準同型暗号
<円分整数,イデアル格子,Ring-LWE問題,準同型暗号>
４．教科書
特に指定しない。
５．参考書
- J. Katz, Y. Lindell, "Introduction to Modern Cryptography: Principles And Protocols", Chapman & Hall/Crc, 2007.
６．関連科目
数論基礎、暗号・認証と社会制度、ブロックチェーン理論、量子計算と暗号理論と関連がある。
７．成績評価の方法と基準
到達目標を充足しているかどうかを評価の基準として、期末レポートにより評価する（90％）。なお、質問など授業への積極的な参加も評価対象とする（10％）。