2018/02/21 現在

授業科目名 暗号理論特論
英文授業科目名 Advanced Topics on Cryptography
開講年度 2017年度 開講年次 全学年
開講学期 後学期 開講コース・課程 博士前期課程、博士後期課程
授業の方法 講義 単位数 2
科目区分 大学院専門教育科目 - 専門科目Ⅱ
開講学科・専攻 情報学専攻
担当教員名 太田 和夫
居室 東3-928(太田),東3-924(岩本)
公開E-Mail {kazuo.ohta} [at] uec.ac.jp,{mitsugu} [at] uec.ac.jp
授業関連Webページ なし
更新日 2017/12/15 23:14:20 更新状況 公開中

We can classify the modern cryptography into two categories: based on a computational complexity theory and information theory. We will select several topics from each category and give their explanation from basic knowledge to state-of-the-art applications. The goal of this class is to master the ways of thinking such as proof methodology of an idea of the formulation of the security  for evaluated protocols (that is, objects or systems).
Discrete mathematics, Algorithm, Data Structure, Cryptology, Information Theory
Advanced Computer Science, Advanced Theoretical Computer Science, Advanced Information Theory
教科書等 [1] On the exact security of Full Domain Hash (Crypto 2000)
[2] Optimal security proofs for PSS and other signature schemes
(Eurocrypt '02) 共に http://www.jscoron.fr/publications/ から入手可能
[3] D. Pointcheval, J.Stern: Security Arguments for Digital Signatures and Blind Signatures. J. of Cryptology, 2000, Vol 13, Issue 3, pp 361–396
[4] M. Bellare and G. Neven: Multi-signatures in the plain public-Key model and a general forking lemma.
ACM-CCS, 390-399, 2006.
[5]  J. Katz, N. Wang: Efficiency improvements for signature schemes with tight security reductions.
ACM-CCS, 2003, pp. 155-164
[6] M. Abdalla, P-A. Fouque, V. Lyubashevsky, M. Tibouchi: Tightly Secure Signatures From Lossy Identification Schemes. J. of Cryptology, Vol. 29, Issue 3, pp 597–633, 2016.
[7] M. Mitzenmacher and E. Upfal, Probability and Computing, 2nd ed. Cambridge, 2017.
[8] J. A. Garay, A. Kiayias, and N. Leonardos: The Bitcoin Backbone Protocol with Chains of Variable Difficulty, CRYPTO 2017.
前半(太田)では,RSA暗号を用いたHash関数署名法(RSA Full Domain Hash Signature Shemes)の安全性について厳密な証明を与える.さらにサントソバグス先生(I専攻,助教)に,その証明法を使った署名法について最新の研究動向についてに紹介していただく.後半(岩本)では,近年ビットコインの理論解析などにも用いられ,理論計算機科学・暗号理論・情報理論・理論経済学で極めて重要な概念であるマルチンゲールと関連する諸性質についての解説を行う
In the first half, we will give a proof on the security of the Hash function signature scheme using the RSA public-key cryptosystem (RSA Full Domain Hash Signature Shemes) and explain the research trends on digital signature schemes. Then, recent topics on the security proofs of signature schemes based on RSA will be explained.
In the latter half, we will perform the commentary about martingale which is recently used in the analysis of bitcoin. Martingale is an extremely important concept in computer science, cryptology, information theory, and economics.

第1回(10/04): ガイダンスと講義の概要 [Guidance of the Class]
第2回(10/11): 署名法の安全性     [The security of Signature Schemes]
第3回(10/18): Rabin暗号 (Provable Security への導入として)
(10/25): 休講
第4回(11/01): 確率論の復習(1) [Review of Probability (1)]
第5回(11/08): 確率論の復習(2) [Review of Probability (2)]
第6回(11/15): FDH 署名の構成法とその安全性 [Constructions of Full Domain Hash
第7回(11/22): f-FDH 署名の安全性証明(制約条件つき) 文献[1]   [Security Proof of f-FDH Signature Scheme]
第8回(11/29): f-FDH 署名の安全性証明とRSA-FDH署名について 文献[1,2]  [Security Proof of f-FDH Signature Scheme and RSA-FDH Signature schemes]
第9回(12/06): RSA-FDH 署名の安全性証明 (つづき: 厳密版) 文献[2] [Security Proof of RSA-FDH Signature Scheme]
第10回 (12/13): Introduction to Public Key Identification Schemes.  ([4])
第11回 (12/20): Security proofs for Identification Schemes: Rewinding vs Non-Rewinding ([5],[6])
第12回(1/10): Martingaleとは     文献[7]
第13回(1/17): Martigale Stopping Times        文献[7]
(1/24): 休講
第14回(1/31): Wald's Inequality   文献[7]
第15回(2/07): Azuma-Hoeffding inequality とその応用 文献 [8], まとめ  [Concluding Remarks]
Review well. Specifically, about the contents which handled only sketching (outline) of the proof in our class, give a proof at your  review.
We will evaluate you in both your reports and your contribution degree (your answers to question situations) in class.
We do not establish our office hour in particular. Visit our laboratory after taking the appointment by an email beforehand when you have questions etc.
学生へのメッセージ 論理的な思考ができていること.キッチリと論文を読む習慣が身につくように指導したい.RSA法などの公開鍵暗号の知識を前提とします.
The logical thing that should be mastered. We want to guide you so that you form the habit of reading article exactly. We assume that you have learned knowledge of the public key crypto system such as the RSA scheme.
その他 なし
キーワード 情報セキュリティ,計算量理論,公開鍵暗号,本人確認,デジタル署名,証明可能安全性,識別不可能性,帰着技法,帰着技法の最適性,確率的手法,計算機科学,情報理論,確率論
Information security, computational complexity theory, public key cryptosystem, authentication, digital signature, provable security, indistinguishability, reduction technique, the optimality of reduction technique, probabilistic method, computer science, information theory, probability theory