シラバス参照

講義概要/Course Information
2024/03/29 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
暗号理論特論
英文授業科目名
/Course title (English)
Advanced Topics on Cryptography
科目番号
/Code
開講年度
/Academic year
2017年度 開講年次
/Year offered
全学年
開講学期
/Semester(s) offered
後学期 開講コース・課程
/Faculty offering the course
博士前期課程、博士後期課程
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
大学院専門教育科目 - 専門科目Ⅱ
開講類・専攻
/Cluster/Department
情報学専攻
担当教員名
/Lecturer(s)
太田 和夫
居室
/Office
東3-928(太田),東3-924(岩本)
公開E-mail
/e-mail
{kazuo.ohta} [at] uec.ac.jp,{mitsugu} [at] uec.ac.jp
授業関連Webページ
/Course website
なし
更新日
/Last update
2019/03/21 16:04:09 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標(2,000文字以内)
/Themes and goals(up to 2,000 letters)
現代暗号理論は,計算量理論と情報理論に基づいた2通りの体系に分類できる.
それぞれの体系についてテーマを選択して,基礎知識から説明を解き起こして,応用にまで言及する.定式化の理念および安全の証明方法などの考え方が理解できることを目標とする.

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).
前もって履修
しておくべき科目(1,000文字以内)
/Prerequisites(up to 1,000 letters)
離散数学,アルゴリズム・データ構造,暗号理論,情報理論
Discrete mathematics, Algorithm, Data Structure, Cryptology, Information Theory
前もって履修しておくこ
とが望ましい科目(1,000文字以内)
/Recommended prerequisites and preparation(up to 1,000 letters)
計算科学特論,理論計算機科学特論,情報理論特論などを合わせて聴講すると,さらに理解が深まります.
Advanced Computer Science, Advanced Theoretical Computer Science, Advanced Information Theory
教科書等(1,000文字以内)
/Course textbooks and materials(up to 1,000 letters)
[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.
授業内容と
その進め方(2,000文字以内)
/Course outline and weekly schedule(up to 2,000 letters)
前半(太田)では,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]
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)(1,000文字以内)
/Preparation and review outside class(up to 1,000 letters)
復習をしっかり行ってください.具体的には,授業で証明のスケッチ(概略)のみを扱った内容について,復習時に証明をつけること.
Review well. Specifically, about the contents which handled only sketching (outline) of the proof in our class, give a proof at your  review.
成績評価方法
および評価基準
(最低達成基準を含む)
(1,000文字以内)
/Evaluation and grading
(up to 1,000 letters)
レポートと,授業中の講義へ貢献度(質問に対する回答状況など)を考慮して総合的に評価する.
We will evaluate you in both your reports and your contribution degree (your answers to question situations) in class.
オフィスアワー:
授業相談(1,000文字以内)
/Office hours(up to 1,000 letters)
特に設けない.質問等があるときは事前にメールでアポイントメントを取ってから研究室を訪問すること.
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.
学生へのメッセージ(1,000文字以内)
/Message for students(up to 1,000 letters)
論理的な思考ができていること.キッチリと論文を読む習慣が身につくように指導したい.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.
その他
/Others
なし
キーワード
/Keywords
情報セキュリティ,計算量理論,公開鍵暗号,本人確認,デジタル署名,証明可能安全性,識別不可能性,帰着技法,帰着技法の最適性,確率的手法,計算機科学,情報理論,確率論
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