Weekly outline

• Γενικά (Ακ. Έτος 2023 - 2024)
  

  Γενικά (Ακ. Έτος 2023 - 2024)

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

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

  
  

  Ημέρα και ώρα: Πέμπτη, 16:15-20:00 (Aίθουσα 1.1.31 - παλαιά κτίρια ηλεκτρολόγων)

  Έναρξη μαθημάτων: 14/3/2024

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

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

  
  

  
  

  • Ανακοινώσεις Forum
  • Ασκήσεις Folder
  • Υποβολή 1ης σειράς ασκήσεων Assignment
• Μέρος 1: Blockchain & Consensus
  

  Μέρος 1: Blockchain & Consensus

  • Εισαγωγή σε Blockchain & Bitcoin.
  • Περιγραφή του αλγορίθμου του Bitcoin backbone.
  • Ορισμός των ιδιοτήτων common prefix, chain quality, chain growth. Selfish mining.
    
  • Αποδείξεις ασφάλειας του Bitcoin backbone. (Δηλαδή, ότι οι παραπάνω ιδιότητες ικανοποιούνται με "μεγάλη πιθανότητα".)
  • Το πρόβλημα Consensus. Αποδείξεις για την αναγκαιότητα του t<n/2 ή t<n/3 (αναλόγως το μοντέλο).
  • Επίλυση consensus με Bitcoin backbone; 2-for-1 proof of work.
  • Εισαγωγή φραγμένων καθυστερήσεων στο μοντέλο (bounded delay model).
  • Δυναμική εκτέλεση με μη σταθερό αριθμό παικτών (target recalculation, Bahack's attack).
  • Ανάλυση χωρίς συγχρονισμένα ρολόγια. Ballot theorems.
  • Το πρωτόκολλο Dolev-Strong.
    

  
  

  Διαφάνειες
  

  
  Οι διαλέξεις βασίστηκαν στις δημοσιευσεις:
  

  • The Bitcoin Backbone Protocol: Analysis and Applications, Juan Garay, Aggelos Kiayias, Nikos Leonardos. https://eprint.iacr.org/2014/765
  • The Bitcoin Backbone Protocol with Chains of Variable Difficulty, Juan Garay, Aggelos Kiayias, Nikos Leonardos. https://eprint.iacr.org/2016/1048
  • How Does Nakamoto Set His Clock? Full Analysis of Nakamoto Consensus in Bounded-Delay Networks, Juan Garay, Aggelos Kiayias, Nikos Leonardos. https://eprint.iacr.org/2020/277
    
• Μέρος 2: Byzantine Agreement
  

  Μέρος 2: Byzantine Agreement

  • Το πρόβλημα Byzantine Agreement
    
  • Η μέθοδος Exponential Information Gathering - EIG
  • Η μέθοδος Weak-Graded-King Consensus
  • Παραμετρικά κάτω φράγματα, ελάχιστη συνδεσιμότητα δικτύου

  
  

  Διαφάνειες: 

  • Byzantine Agreement
  • Exponential Information Gathering

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

  • Αmotz Bar-Noy, Danny Dolev, Cynthia Dwork, and H. Raymond Strong. Shifting gears: Changing algorithms on the fly to expedite byzantine agreement. Inf. Comput., 97(2):205{233, 1992
    
  • P. Berman, J.A. Garay and K.J. Perry, “Towards Optimal Distributed Consensus,” Proc. 30th FOCS, pp. 410–415, 1989.
  • Matthias Fitzi, Ueli M. Maurer: "From partial consistency to global broadcast", STOC 2000: 494-503

  
  
• Μέρος 3. Ηλεκτρονικές Ψηφοφορίες
  

  Μέρος 3. Ηλεκτρονικές Ψηφοφορίες

  • Το σύστημα ηλεκτρονικών ψηφοφοριών Helios
  • Προβλήματα κατά την κατασκευή μη αλληλεπιδραστικών αποδείξεων μηδενικής γνώσης λόγω χρήσης του weak Fiat Shamir Transform και συνέπειες στην επαληθευσιμότητα.
  • Decentralized Voting

  Διαφάνειες

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

  Dispute-free Scalable Open Vote Network using zk-SNARKs (iacr.org)