現在更新を停止中です。詳細は こちら
2011年度前期「数理科学特論13」「MMA数学特論I」
"Advanced Topics in Cryptography"
-
担当教員： Kirill Morozov 教員 教員ウェブページ
開講時限： 水曜4限（14:50～16:20）
対象学年： 学部4年・MMA修士およびその他の数理学修士
特記事項： 講義やその他の伝達はすべて英語で行われます。
連絡事項
There will be no office hours (Prof. Morozov and TA) on July 27.
July 27 is a STRICT DEADLINE for submission of the final report.
テキスト
Chapter 8 in Victor Shoup "A Computational Introduction to Number Theory and Algebra", 2nd ed., Cambridge University Press, 2008.
Available from HERE.
成績評価
- Approximately 2 sets of exercises for homework.
(to be distributed later) - Report IN ENGLISH at the end of the course.
オフィスアワー
Professor Morozov's room: 209 (floor 1)
17:00 -- 18:00, Wednesday. EXCEPT:
- May 4th (G.W. / NO CLASS)
- May 18th and 25th
- June 15th
- July 20th
TAのオフィスアワー
TA's room: Graduate Students Room #2
Office Hours: Same as above, but please feel free to visit anytime.
I recommend you to email me before your visiting.
(but not mandatory)
TA will be away from Fukuoka or be absent:
- 6th and 20th, July (Research Meeting)
予定（Plan of this course）
Part I: Background
- 1. Elements of probability theory and information theory:
Probability distributions, conditional probability and independence, random variables, expectation and variance, some useful bounds, statistical distance; entropy as a measure of randomness, its variants and their basic properties. - 2. Hashing:
Pairwise independence and universal hashing, examples. - 3. Leftover Hash Lemma:
Basic statement and its proof, other variants of this lemma.
Part II: Applications (subject to availability of time)
- 4. Information-theoretically secure cryptographic protocols:
Definition of cryptographic protocol, information-theoretic security, definition of secure key agreement (SKA), a construction of information-theoretical SKA from correlated randomness using leftover hashing, and its security proof; more cryptographic protocols. - 5. Construction of pseudorandom generators from any one-way permutation:
Computational security, definitions of one-way permutations and pseudorandom generators, construction, proof sketch with emphasis on application of the leftover hash lemma. - 6. Exposure-resilient functions (ERF):
Definition of ERF, some constructions of ERF using leftover hashing, application to all-or-nothing transforms.
参考文献
- Items 1-3 are in the most part covered in Chapter 8 in Victor Shoup "A Computational Introduction to Number Theory and Algebra", 2nd edition, Cambridge University Press, 2008 (available online).
- Item 4 is covered in Chapters 2 and 8 in Pim Tuyls, Boris Skoric and Tom Kevenaar (editors) "Security with Noisy Data", Springer, 2007.
- Item 5 is covered in Chapters 2 and 3 in Oded Goldreich "Foundations of Cryptography - Volume I (Basic Tools)", Cambridge University Press, 2001 (draft fragments available online).
- Item 6 is covered in Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai " Exposure-Resilient Functions and All-or-Nothing Transforms ", Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science, Volume 1807, pages 453-469, Springer, 2000.
- Introduction to cryptography: Nigel Smart "Cryptography, An Introduction", McGraw-Hill, 2002 (the third edition is available online).
- Introduction to cryptography (also): Douglas R. Stinson "Cryptography: Theory and Practice", 3rd edition, CRC Press, 2005.
[日本語訳] 櫻井幸一（監訳）「暗号理論の基礎」（共立出版）. - Introduction to information theory: Thomas M. Cover and Joy A. Thomas "Elements of Information Theory", 2nd edition, Wiley, 2006.
- Charles H. Bennett, Gilles Brassard, Claude Crépeau, Ueli M. Maurer: Generalized privacy amplification. IEEE Transactions on Information Theory 41(6), pp. 1915-1923, 1995.
授業ログ
Apr. 13, 2011 / #1 Introduction + Basics I
- Introduction and Motivation
- Basic Probability Theory I
- COURSE NOTES (4/13)
Disclaimer: These notes are only an approximate description of the actual presentation at the lecture.
Apr. 20, 2011 / #2 Basics II
- Basic Probability Theory II :
Basic definitions (continued), De Morgan's law, Boolean distributive law and the union bound.
Reading: textbook, pages 208-210, up to and including the statement of Theorem 8.1.
Apr. 27, 2011 / #3 Basics III, Conditional Probability and Independence
- Basic Probability Theory III :
Inclusion/exclusion principle, product distribution. - Conditional probability and independence :
Conditional distribution, independent events, law of total probability, Bayes' theorem, k-wise independence.
Reading: textbook, pages 210-218, up to Example 8.15.
- Exercise Set 1
To be handed in on May 11.
May. 4, 2011 / NO CLASS (holiday)
May. 11, 2011 / #4 k-wise independent families of events, Independence of random variables I
- k-wise independent families of events: definitions, examples.
- Random variables and independence :
Definitions, conditional distribution, k-wise independent families of random variables, examples.
Reading: textbook, pages 218-225, up to Equation (8.13).
May. 18, 2011 / #5 Independence of random variables II, Secret sharing I
- Pairwise and mutually independent families of random variables (r.v.), some characterizations of independent families of r.v.
- One-time pad encryption :
Proof of independent and uniform ciphertexts, counterexample for the case of re-used keys. - Additive secret sharing :
A scheme, its correctness and security justification.
Reading: textbook, pages 225-230.
May. 25, 2011 / #6 Secret sharing II
- (n,n) additive scheme, DNF-based (k,n) threshold scheme, Shamir's scheme and its security proof.
Reading: textbook, pages 231-232; chapter 23 in Smart's book; chapter 13 in Stinson's book.
Jun. 1, 2011 / #7 Secret sharing III
- Shamir's scheme - example and discussion, some terminology.
- Some useful bounds: Markov's inequality, Chebyshev's inequality (and some special cases), the law of large numbers, Chernoff bound (only the statement).
Reading: chapter 13 in Stinson's book; textbook, pages 233-242.
Jun. 8, 2011 / #8 Verifiable Secret Sharing and Multiparty Computation
- GUEST LECTURE
by Prof. Yvo Desmedt (University College London, UK)
Introduction to verifiable secret sharing (VSS) and multi-party computation (MPC).
Ito-Saito-Nishizeki replicated secret sharing scheme (SSS).
Maurer's construction of secure MPC via VSS based on replicated SSS.
Reading: chapter 26 in Smart's book.
Jun. 15, 2011 / #9 Some useful bounds II / Balls and bins I
- Some useful bounds II: Proof of the Chernoff bound.
- Balls and bins I: Upper bounds on the probability of collision and on the expectation of the maximum number of balls in a bin.
Reading: textbook, pages 242-247 up to (but not including) Theorem 8.28.
- Exercise Set 2
Jun. 22, 2011 / #10 Balls and bins II / Hash functions
- Balls and bins II: Birthday paradox.
- Hash functions: Pairwise independent and universal hash functions: definitions; pairwise independence property implies universal one; application to information-theoretic authentication.
Reading: textbook, pages 247-248, 252-254.
Jun. 29, 2011 / #11 Constructions of hash functions I
- Constructions of hash functions I: Some pairwise independent and universal families of hash functions.
Reading: textbook, pages 252-257 up to (but not including) Example 8.39.
- The final report task
SUBMISSION DEADLINE: July 27th
Jul. 6, 2011 / #12 Constructions of hash functions II / Statistical distance and its properties I
- Constructions of hash functions II: a universal hash family with the size of key set smaller than the size of pre-image.
- Statistical distance and its properties I.
Reading: textbook, pages 257, 260-263 up to (but not including) Theorem 8.33.
Jul. 13, 2011 / #13 Statistical distance II: Some more properties
- Collision probability, Renyi entropy (of order 2) and its properties. / Almost uniform distributions.
Reading: Cover and Thomas' book, pages 16-25 and 28-30, Bennett et al's paper, Section IV.
Jul. 20, 2011 / #14 Conditional entropy (II): some properties
- Jensen's inequality / Shannon entropy: definition, basic properties, some examples, conditional entropy.
Reading: textbook, pages 263-264, Cover and Thomas' book, pages 13-18, 25-27.
Jul. 27, 2011 / #15 Final Remarks
- Leftover hash lemma, with proof.
- Privacy amplification theorem, with proof.
- Application to protection from eavesdropping.
Reading: Bennett et al's paper, Sections III, IV.
- SUBMISSION DEADLINE of The final report task
