Arvutiteaduse instituut
  1. Kursused
  2. 2013/14 sügis
  3. Krüptoloogia II (MTAT.07.003)
EN
Logi sisse

Krüptoloogia II 2013/14 sügis

Previous Years: 2008 » 2009 » 2010 » 2012

  • About
  • Lectures
  • Homeworks
  • Admininistation

Syllabus

  • How to Model Cryptographic Primitives and Protocols
  • Analysis of Randomised Algorithms
  • Computational Indistinguishability
  • Semantic Security and Cryptosystems
  • Security Notions for Public Key Cryptosystems
  • Message Authentication Codes
  • Commitment schemes
  • Entity Authentication
  • Sigma protocols
  • Digital signatures
  • Zero-knowledge proofs

Authorship of example solutions

The example solutions to most of the exercises are generated in close collaboration with students. For many exercises, I have taken the solution type set by a student and modified it. By doing it I have tried to keep the original solution scheme but iron out some technical wrinkles or add emphasis on the details I believe are worth stressing. The PDF files do not contain explicit references of authorship, I will thank all of my contributors separately

  • Alisa Pankova
  • Filip Ivanov
  • Ilya Kuzovkin
  • Ivo Kubjas
  • Margus Niitsoo
  • Pille Pullonen
  • Prastudi Fauzy
  • Sanja Scepanovic

The table showing who are the authors of which exercises can be downloaded form here Δ

How to Model Cryptographic Primitives and Protocols

Lecture (PDF)

  • Cryptographic absraction techniques
  • Functional requirements. Attacks and security requirements
  • Discrete logarithm and abstract DL, CDH and DDH groups
  • Factorisation problem and abstract distribution of RSA moduli
  • Basic reductions between DL, CDH and DDH problems
  • Random self-reducibility and its consequences

Exercise session (PDF)

  • Formalisation of cryptographic primitives
  • Formalisation of attack senarios and security definitions
  • Self-reducibility and Diffie-Hellman problem

Example solutions

  • Electronic lottery
  • Hash functions
  • Password hashing
  • Random self-reducibility of discrete logarithm
  • Random self-reducibility of Computational Diffie-Hellman Problem
  • Weak random self-reducibility of Decisional Diffie-Hellman Problem
  • Random self-reducibility of Decisional Diffie-Hellman Problem
  • Alternative explanation to random self-reducibility of Decisional Diffie-Hellman Problem

Analysis of Randomised Algorithms

Lecture (PDF)

  • Turing Machines. Random Access Machines. Circuits
  • Chebyshev, Markov and Jensen inequalities
  • Standard amplification techniques and their connection to inequalities
  • Relation between expected and strict running-time
  • Total probability formula and analysis by exhaustive decomposition
  • Entropy and its basic properties

Exercise session (PDF)

  • Subtleties and paradoxes of computational models
  • Applications of total probability formula
  • Applications of Chebyshev, Markov and Jensen inequalities

Example solutions

  • From expected running time to strict running time
  • Amplification by majority voting
  • Standard analysis of combiner constructions
  • On the necessity of universality in the timing model

Literature:

  • Stintson, Cryptography: Theory and Practice, Chapter 2 (entropy).
  • Cook, S. A., Reckhow, R. A. Time-bounded random access machines.
  • C. E. Shannon, Communication Theory of Secrecy Systems

Computational Indistinguishability

Lecture (PDF)

  • Statistical and computational distance
  • Pseudorandom generators, functions and permutations
  • Guessing games and semantic security
  • IND-SEM theorem and some conclusions

Exercise session (PDF)

  • Statistical tests
  • Trade-offs between false positives and false negatives
  • Naive estimates on computational distance
  • Properties of computational distance
  • Application of guessing games

Example solutions

  • Tradeoffs between false positives and false negatives
  • Explicit estimation of computational distances
  • Lottery game with indistinguishable distributions
  • Classical hybrid argument

Semantic Security and Cryptosystems

Lecture (PDF)

  • The proof of IND-SEM theorem
  • Symmetric key cryptosystems
  • IND-FPA security and semantic security
  • Insufficiency of IND-FPA security in practical settings
  • IND-CPA security and constructive IND-SEM theorem
  • PRF/PRP switching lemma

Supporting materials

  • IND-SEM proof in details (PDF)

Exercise session (PDF Δ)

  • Random functions and permutations
  • Analysis of PRF/PRP switching lemma
  • Game-based proof for the PRF/PRP lemma
  • Anaysis of ECB, CBC, CTR encryption modes
  • Left-or-right and real-or-random games

Example solutions

  • Insecurity of ECB mode of operation
  • Static non-malleability implies IND-CPA security
  • BAD reduction schema and its applications
  • Horizon splitting technique and its applications
  • Insecurity of three round Feistel constuction against chosen ciphertext attacks

Additional exercises (PDF)

  • Celebrated Feistel construction
  • Constructions for pseudorandom generators
  • Circular constructions: PRP => RPF => PRP, PRF => PRG => PRF

Security Notions for Public Key Cryptosystems

Lecture (PDF)

  • IND-CPA security and semantic security
  • Security of the ElGamal cryptosystem
  • Hybrid encryption and its security
  • IND-CCA1 security and improper usage of decryption key
  • IND-CCA2 security and non-malleability

Exercise session (PDF)

  • Analysis of hybrid encryption scheme
  • Non-malleability and IND-CCA2 security
  • Security of the Goldwasser-Micali cryptosystem
  • Practical variants of the ElGamal cryptosystem
  • Homomorphic cryptosystems and non-malleability

Example solutions

  • Security of hash ElGamal cryptosystem

Message Authentication Codes

Lecture (PDF)

  • Simmons's lower bounds
  • Almost universal hash functions
  • Security of polynomial hashing
  • Cryptographic hash functions and their properties

Exercise session (PDF)

  • CBC-MAC
  • NMAC, HMAC
  • UMAC construction
  • Authenticated symmetric key encryption

Example solutions

  • Security analysis of a message authentication protocol
  • Security of authenticated encryption
  • Security of authenticated encryption
  • Security of Poly-AES construction with randomised nonce
  • Hashing as a way to extend the domain of message authentication codes

Commitment schemes

Lecture (PDF)

  • Hiding and binding property
  • Cryptosystems as commitment schemes
  • Homomorphic commitments
  • Non-malleable commitments

Exercise session (PDF)

  • List commitments
  • Cryptographic poker game
  • Manually authenticated hybrid encryption

Example solutions

  • Second preimage resistance implies one-wayness
  • User-aided-key-agreement based on IND-CCA2 secure encryption
  • User-aided-key-agreement based on non-malleable encryption
  • Partial double-opening of list commitment schemes
  • Basic properties of dual mode commitments

Entity authentication

Lecture (PDF)

  • Challenge-Response protocols
  • Zero-knowledge proofs of knowledge
  • Schnorr identification scheme
  • Knowledge extraction

Exercise session (PDF)

  • Security of Kerberos and MAP-1
  • Proofs of possession

Example solutions

  • Liveness proof based on a one-way permutation.pdf
  • Simplified security analysis of MAP-I protocol

Sigma Protocols

Lecture (PDF)

  • Knowledge extraction
  • Disjunctive and conjunctive compositions
  • Honest verifier zero-knowledge proofs of knowledge
  • Certified computations for semihonest verifier

Exercise session (PDF)

  • Examples of sigma protocols
  • Proofs of knowledge for various relations
  • Matrix games and details of knowledge extraction
  • Various applications of Forking Lemma

Example solutions

  • Sigma protocol for the Pedersen commitment scheme

Digital Signatures

Lecture (PDF Δ)

  • One-time signatures
  • Full domain hash
  • Fiat-Shamir heuristics
  • Random Oracle Model
  • Forking Lemma and Random Oracle Model
  • Generic Signature Schemes

Exercise session (PDF Δ)

  • RSA signature
  • Schnorr signature
  • Signatures with additional properties

Example solutions

  • Full domain hash in random oracle-model

Zero-knowledge Proofs

Lecture (PDF Δ)

  • Honest Verifier Zero Knowledge
  • CDS proofs for complex relations
  • Non-Interactive Zero Knowledge
  • Secure coin-flipping and fully secure Zero Knowledge

Exercise session (PDF Δ)

  • Applications of CDS proof technique
  • Zero knowledge proofs for NP-complete problems

Example solutions

  • Simulator for the Fiat-Shamir identification protocol
  • Soundness of QNR-ZK protocol with disjunctive proof of knowledge
  • Simulator for the QNR-ZK protocol with disjunctive proof of knowledge
  • Knowledge-extraction and simulation distance in QNR-ZK-delay protocol
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo