Weekly outline

• Χειμερινό Εξάμηνο 2023-2024
  

  Χειμερινό Εξάμηνο 2023-2024

  Διδάσκοντες:

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
  • Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
  • Παναγιώτης Γροντάς, Μεταδιδάκτορας (pgrontas@mail.ntua.gr)
  • Νίκος Λεονάρδος, Επ. Καθηγητής (υπό διορισμό) (nleon@cs.ntua.gr)

  
  

  Βοηθοί Διδασκαλίας:
  

  • Θωμάς Σουλιώτης, Υ.Δ.
  • Pourandokht Behrouz, Υ.Δ.
  • Μαριάννα Σπυράκου, Υ.Δ.
  • Ελένη Μακρή, Υ.Δ.
  • Δανάη Μπάλλα, Υ.Δ.
  • Ορέστης Κωνσταντινίδης, Υ.Δ.

  
  

  Επικοινωνία: crypto@corelab.ntua.gr
  

  
  

  Διαλέξεις (έναρξη: 3/10)

  • Τρίτη 15:30-18:00, Αιθ. 007, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ 
  • Παρασκευή 18:15-20:00, Αμφ. 3, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ

  
  

  Βασική βιβλιογραφία:
  

  [ΖΠΓ]: Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς: Υπολογιστική Κρυπτογραφία, Κάλλιπος, 2015. 
  [LK2]: Jonathan Katz and Yehuda Lindell: Introduction to Modern Cryptography (2nd edition).
  [BoSh]: D. Boneh and V. Shoup: A Graduate Course in Applied Cryptography (free draft, κατεβάστε την τελευταία έκδοση)

  • Ανακοινώσεις Forum
  • Βιβλιογραφία - Υλικό - Σύνδεσμοι Page
  • Ασκήσεις Folder
  • Βιβλία - σημειώσεις Folder
  • Υποβολή 1ης σειράς ασκήσεων Assignment
  • Υποβολή 2ης σειράς ασκήσεων Assignment
  • Υποβολή 3ης σειράς ασκήσεων Assignment
  • Υποβολή Project Assignment
• Εβδομάδα 2/10-6/10
  

  Εβδομάδα 2/10-6/10

  
  

  ΤΡΙΤΗ 3/10

  • Διαδικαστικά Μαθήματος
  • Επισκόπηση αρχών και εφαρμογών της σύγχρονης κρυπτογραφίας.

  Διαφάνειες διάλεξης

  
  

  ΠΑΡΑΣΚΕΥΗ 6/10

  • Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.
  • Δείκτης σύμπτωσης (Coincidence Index).
  • Τέλεια μυστικότητα κατά Shannon.

  Διαφάνειες διάλεξης (σελ. 1-20)

  Προτεινόμενη μελέτη: 

  • [ΖΠΓ]: κεφ. 1.4.3 
  • [LK2]: κεφ. 2
• Εβδομάδα 9/10-13/10
  

  Εβδομάδα 9/10-13/10

  ΤΡΙΤΗ 10/10

  • Τέλεια Μυστικότητα
  • Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
    
  • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.

   Διαφάνειες Διάλεξης (σελ. 20-45)

   Προτεινόμενη μελέτη: 

  •   [ΖΠΓ] κεφ 1.4.3, 6.3 
  •   [LK2] κεφ. 2

  Προαιρετική Μελέτη: 

  • Russell Impagliazzo, A Personal View of Average-Case Complexity, (pdf).
    

  
  

  ΠΑΡΑΣΚΕΥΗ 13/10

  Εισαγωγή στη Θεωρία Αριθμών

  • Διαιρετότητα, ΜΚΔ: ιδιότητες - αλγόριθμος Ευκλείδη
  • Πρώτοι αριθμοί, συνάρτηση φ του Euler
  • Ισοτιμίες, αριθμητική modulo, ο δακτύλιος Z_m 
  • Μικρό Θεώρημα Fermat 
  • Θεωρία ομάδων: τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες, δακτύλιοι, σώματα

  
  Διαφάνειες διάλεξης (1-20)
  

  Προτεινόμενη μελέτη: [ΖΠΓ] 2.1, 4.1, 4.2, 4.3
• Εβδομάδα 16/10-20/10
  

  Εβδομάδα 16/10-20/10

  ΤΡΙΤΗ 17/10

  • Σύμπλοκα, ομάδα πηλίκο, θεώρημα Lagrange
  • Έλεγχος πρώτων με θεώρημα του Fermat
  • Κινέζικο Θεώρημα Υπολοίπων
  • Η δομή των ομάδων Z*p και U(Zpq)
    
    

    Διαφάνειες διάλεξης (21-32)
  
    Προτεινόμενη μελέτη: [ΖΠΓ] 2.2, 2.3, 4.5 [LK2] 8.1-8.3 (συμπληρωματικά)

  
  

  ΠΑΡΑΣΚΕΥΗ 20/10

  • Τετραγωνικά Υπόλοιπα
  • Τετραγωνικές ρίζες modulo n και παραγοντοποίηση
  • Σύμβολα Legendre και Jacobi
  • Έλεγχοι πρώτων αριθμών Fermat και Miller-Rabin
  • Ευεπίλυτα και Δυσεπίλυτα αριθμητικά προβλήματα

  
  

    Διαφάνειες διάλεξης (33-46)
  

  
  

    Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, 4.5, 4.6, 4.7 [LK2] 8.2.2 (συμπληρωματικά)
• Εβδομάδα 23/10-27/10
  

  Εβδομάδα 23/10-27/10

  ΤΡΙΤΗ 24/10

  • Κρυπτοσυστήματα τμήματος (block ciphers). 
    
  • Δίκτυα Feistel. 
    
  • Κρυπτοσύστημα DES, S-boxes, MITM attack. 
    
  • Βελτιώσεις: 3-DES, DES-X. 

  
  

    Διαφάνειες διάλεξης (1-13) 
  

    Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3

  
  

  
  

  ΠΑΡΑΣΚΕΥΗ 27/10

  Επέτειος 28ης ΟΚΤΩΒΡΙΟΥ - Δεν έγινε μάθημα
• Εβδομάδα 30/10 - 03/11
  

  Εβδομάδα 30/10 - 03/11

  ΤΡΙΤΗ 31/10

  
  

  • Τρόποι λειτουργίας των blockciphers
  • Το κρυπτοσύστημα AES
  • Αλγεβρική περιγραφή του AES

  
  

  Διαφάνειες διάλεξης (14-25)
  

  Συμπληρωματικά: Raj Jain, Washington University in Saint Louis, και περιγραφή του AES στο επίσημο site του NIST.
  

  Προτεινόμενη μελέτη: [ΖΠΓ] 5.3 - 5.6

  
  

  ΠΑΡΑΣΚΕΥΗ 3/11

  
  

  • Γεννήτριες Ψευδοτυχαιότητας
  • Ψευδοτυχαίες συναρτήσεις και μεταθέσεις
  • Γεννήτρια Blum-Blum-Shub
    
  • Κρυπτοσυστήματα ροής
    
  • Γεννήτρια RC4

  
  

  Διαφάνειες διάλεξης (1-36)

  
  

  Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3)

  
  
• Εβδομάδα 6/11 - 10/11
  

  Εβδομάδα 6/11 - 10/11

  
  

  ΤΡΙΤΗ 7/11

  
  

  • Γεννήτρια Blum-Blum-Shub (επανάληψη)
    
  • Καταχωρητές Ολίσθησης Γραμμικής Ανάδρασης
    
  • eStream
    
  • Συναρτήσεις μονής κατεύθυνσης
  • Συναρτήσεις σύνοψης
  • Ασφάλεια συνάρτησης Chaum-van Heijst-Pfitzman

  
  

  Διαφάνειες διάλεξης: Stream Ciphers (37-42), Hash Functions (1-13)

  
  

  Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3), [ΖΠΓ] 6.1, 8.1- 8.2, [LK2] 7.1, 5.1
  

  
  

  
  

  ΠΑΡΑΣΚΕΥΗ 10/11

  
  

  • Παράδοξο Γενεθλίων - Βελτιωμένες Επιθέσεις
  • Κατασκευή Merkle-Damgård
  • Δένδρα Merkle
    
  • Χρήσεις συναρτήσεων σύνοψης

  
  

  Διαφάνειες διάλεξης: Hash Functions (14-32)

  Προτεινόμενη Μελέτη: [ΖΠΓ] 8.2-8.3, [LK2]: 5.2, [BoSh]: 8.3, 8.4

  
  

  
  

  
  

  
  

  
  
• Εβδομάδα 13/11 - 17/11
  

  Εβδομάδα 13/11 - 17/11

  
  

  ΤΡΙΤΗ 14/11 - Εφαρμογές Συναρτήσεων Σύνοψης
  

  • Σχήματα δέσμευσης
  • Ασφαλής αποθήκευση κωδικών
  • Timestamping
  • Proof-of-Work, δένδρα Merkle

  
  

  Διαφάνειες: Hash Applications

  Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.4-8.6
  

  
  

  • Message Authentication Codes
  • MAC με hash functions (HMAC)

  
  

  Διαφάνειες: MAC
  

  Προτεινόμενη μελέτη: [BoSh] 8.7, 9.1-9.4 (συνοπτικά)
  

  
  

  ΠΑΡΑΣΚΕΥΗ 17/11 

  Επέτειος Πολυτεχνείου.
  
• Εβδομάδα 21/11 - 24/11
  

  Εβδομάδα 21/11 - 24/11

  ΤΡΙΤΗ 21/11

  • Μοντέλα και ορισμοί ασφάλειας
  • Τύποι επιθέσεων
  • Παίγνια Μη Διακρισιμότητας
  • Γενική μορφή κρυπτογραφικών αναγωγών
  • Ανάλυση ασφάλειας ανταλλαγής κλειδιού Diffie-Hellman
  • Εισαγωγή στο RSA

  Διαφάνειες Διάλεξης

  Προτεινόμενη μελέτη: [ΖΠΓ] 1.4, 6.2, 6.3 [LK2] 1.4 
  

  Προαιρετική Μελέτη: 

  • W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Inf. Theor., 22(6):644-654, September 1976.
  • Neil Koblitz, Alfred Menezes, Another Look at “Provable Security”, (pdf).
    
  • Ivan Damgard, A proof reading of some issues in cryptography, (pdf).

  
  ΠΑΡΑΣΚΕΥΗ 24/11
  

  • Κρυπτογραφία Δημοσίου Κλειδιού
  • Ορισμός RSA
  • Παρατηρήσεις Λειτουργίας
  • Αριθμοθεωρητικές Επιθέσεις

  Διαφάνειες Διάλεξης (1-37) - Κώδικας Sage

  [ΖΠΓ] 6.4, [LK2] 11.5.1, 11.5.2, 11.5.4, 11.5.6, [BoSh] 10.3
  

  Προαιρετική μελέτη:
  

  • Factorization of a 768-bit RSA modulus (iacr.org)
    
  • Dan Boneh, Twenty Years of Attacks on the RSA Cryptosystem (nmsu.edu)
    
  • Alexander May, Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, (pdf)
  • Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter, Ron was wrong, Whit is right, (pdf)

  
  
• Εβδομάδα 28/11 - 01/12
  

  Εβδομάδα 28/11 - 01/12

  ΤΡΙΤΗ 28/11/23

  Το κρυπτοσύστημα RSA (ολοκλήρωση)
  

  • Μοντελοποίηση - Ιδιότητες IND-CPA, IND - CCA
  • Malleability
  • Διαρροή parity - location bits και 'σπάσιμο' RSA
  • Επιθέσεις Padding Oracle (Bleichenbacher)
  • RSA - OAEP

  Διαφάνειες Διάλεξης (38-56) 
  

  Συνολική Μελέτη RSA: [ΖΠΓ] 6.4, [LK2] 11.5.1, 11.5.2, 11.5.4, 11.5.6, [BoSh] 10.3

  Προαιρετική μελέτη:
  

  • Daniel Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 (pdf)

  Κρυπτοσυστήματα Διακριτού Λογαρίθμου
  

  • Προβλήματα DLP, CDHP, DDHP (επανάληψη)
  • Random Self-Reducibility
  • Αλγόριθμοι Διακριτού Λογαρίθμου (Shanks, Pohlig-Hellman, Index Calculus)
  • Ευκολία DDHP στο Z_p^*
  • Επιλογή Ομάδας, Μέγεθος παραμέτρων

  Slides DLP (1-20)

  Μελέτη: [ΖΠΓ] 4.8, [LK2] 8.3.2, 8.3.3, 9.2.1, 9.2.2, 9.3, 9.4 [BoSh] 10.5

  Προαιρετική μελέτη:
  

  • Dan Boneh, The Decision Diffie-Hellman Problem (pdf)

   

  ΠΑΡΑΣΚΕΥΗ 01/12/23

  Κρυπτοσυστήματα Διακριτού Λογαρίθμου

  • Ευκολία DDHP στο Z_p^* (διευκρινίσεις)
  • Ελλειπτικές Καμπύλες
  • Pairings
  • Τριμερής Ανταλλαγή Κλειδιού

  Slides DLP (21-56)
  

  Μελέτη: [ΖΠΓ] 12.2, 12.3 [LK2] 8.3.4

  Προαιρετική μελέτη:
  

  • Pairings For Beginners (Craig Costello)
  • Elliptic Curve Cryptography in Practice
    

  • Περί των ελλειπτικών Καμπυλών NIST. 

  • https://saweis.net/posts/nist-curve-seed-origins.html

  • https://words.filippo.io/dispatches/seeds-bounty/

    
    

  
  

  
  
• Εβδομάδα 5/12-8/12
  

  Εβδομάδα 5/12-8/12

  ΤΡΙΤΗ 05/12/2023

  • Το κρυπτοσύστημα El Gamal (Ιδιότητες Ασφάλειας - Malleability)
  • Το κρυπτοσύστημα Cramer - Shoup.
  • Σχήματα δέσμευσης με βάση το DLP
  • Secret Sharing - Threshold El Gamal

  Slides: DLP (57-96)

  Μελέτη: [ΖΠΓ] 6.5, 9.2, 9.3 [LK2] 11.4.1, 13.3 [BoSh] 10.6.1, 11.5, 22.1, 22.3

  ΠΑΡΑΣΚΕΥΗ 08/12/2023

  • Αποδείξεις μηδενικής γνώσης: Διαισθητικά Παραδείγματα - Ορισμός
  • Παραδείγματα από Θ. Πολυπλοκότητας
  • Πρωτόκολλο Schnorr

  Slides: ΖΚ (1-43)

  Μελέτη [ΖΠΓ] 10.1 - 10.3 [BoSh] 19.1, 19.4, 19.6

  Προαιρετική Μελέτη:

  • Zero Knowledge Proofs — A Primer

  • To Schnorr and beyond
    

  • Zero Knowledge Proofs: An illustrated primer

  • How To Simulate It - A Tutorial on the Simulation Proof Technique (iacr.org) (Ch.1, 2, 3, 5).

  • Unifying Zero-knowledge Proofs of Knowledge - Information Security and Cryptography Research Group - ETH Zürich

  
  
  

  
  
• Εβδομάδα 12/12-15/12
  

  Εβδομάδα 12/12-15/12

  ΤΡΙΤΗ 12/12/2023

  • Το Σ-πρωτόκολλο Chaum - Pedersen
  • Σύνθεση Σ-πρωτοκόλλων (AND, EQ, OR)

  Διαφάνειες: ZK (44-53)
  

  Προαιρετική Μελέτη:

  Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols | SpringerLink
  

  Ψηφιακές Υπογραφές

  • Μοντέλα Ασφάλειας
  • Υπογραφές RSA - FDH
  • To μοντέλο του τυχαίου μαντείου

  Διαφάνειες

  Μελέτη: [ΖΠΓ] 7.1 - 7.4, [LK2] 12.1 - 12.4. 

  Προαιρετική Μελέτη: Σημειώσεις Bellare - Rogaway για RSA-FDH και απόδειξη μη πλαστογραφησιμότητας (12.3.5 - pdf)

  
  

  ΠΑΡΑΣΚΕΥΗ 15/12

  Δεν έγινε μάθημα.

  
  
• Εβδομάδα 19/12-22/12/23
  

  Εβδομάδα 19/12-22/12/23

  
  

  ΤΡΙΤΗ 19.12.2023

  Ψηφιακές Υπογραφές (Μέρος 2ο)

  • Ψηφιακές Υπογραφές Διακριτού Λογαρίθμου (ElGamal, Schnorr, ECDSA, EdDSA)
  • Λύσεις στο πρόβλημα αυθεντικότητας κλειδιών
  • Ψηφιακές Υπογραφές με ιδιωτικότητα

  Διαφάνειες

  Μελέτη: [LK2] 10.4, 12.5, 

  Προαιρετική Μελέτη

  • [PS00] Security Arguments for Digital Signatures and Blind Signatures | Journal of Cryptology
  • Multi-signatures in the plain public-Key model and a general forking lemma
    
  • ECDSA Biased Nonces, Χρόνης Σαπουντζάκης

  ΠΑΡΑΣΚΕΥΗ 22.12.2023

  Κρυπτοψηφοφορίες

  • Απαιτήσεις ηλεκτρονικών ψηφοφοριών
  • Ομομορφικά συστήματα 
  • (Επαληθεύσιμα) Δίκτυα Μίξης 
  • Ψηφοφορίες με τυφλές υπογραφές
  • Ανοιχτά Θέματα

  Διαφάνειες
  

  Μελέτη: [ΖΠΓ] 11.1 [LK2] 13.3.3

  Προαιρετική Μελέτη:  [1707.08619] Public Evidence from Secret Ballots

  
  

  
  

  
  

  
  
• Εβδομάδα 8/1-12/1
  

  Εβδομάδα 8/1-12/1

  ΤΡΙΤΗ 9/1/2024

  • Ορισμός μοντέλου bitcoin.
  • Ορισμός ιδιοτήτων: common prefix, chain quality, chain growth.
  • Ορισμός τυχαίων μεταβλητών και απόδειξη λήμματος common prefix.

  Διαφάνειες

  Προτεινόμενη μελέτη: [ΖΠΓ] 11.3 - 11.4

  Προαιρετική μελέτη:  Bitcoin's Academic Pedigree, Arvind Narayanan and Jeremy Clark