Weekly outline

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

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

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


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

    Έναρξη μαθημάτων: 2/3/2023 


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



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

    Έναρξη του μαθήματος

    • Διαδικαστικά μαθήματος
    • Επανάληψη Βασικών Εννοιών
    • Πρωτόκολλα ταυτοποίησης
    • Ψηφιακές υπογραφές από πρωτόκολλα ταυτοποίησης
    • Ανάλυση ασφάλειας υπογραφών Schnorr
    • Εναλλακτικά μοντέλα και υποθέσεις (OMDL, AGM)

    Διαφάνειες

    Μελέτη: 

    [LK2] Ενότητες 12.1, 12.2, 12.4, 12.5

    [BoSh] Ενότητες 18.1, 18.2, 19.1, 19.2 

    Papers για εργασία παρουσίασης (μία εργασία):

    • Georg Fuchsbauer, Eike Kiltz, and Julian Loss, The algebraic group model and its applications, Advances in Cryptology – CRYPTO 2018 (Cham) (Hovav Shacham and Alexandra Boldyreva, eds.), Springer International Publishing, 2018, pp. 33–62
    • Zhang, C., Zhou, HS., Katz, J. (2022). An Analysis of the Algebraic Group Model. In: Agrawal, S., Lin, D. (eds) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022. Lecture Notes in Computer Science, vol 13794. Springer, Cham. https://doi.org/10.1007/978-3-031-22972-5_11 



    • 2. zk- SNARKS - Μέρος 1ο

      • Interactive Proofs
      • Βασικά εργαλεία (Σχήματα Δέσμευσης, Schartz - Zippel Λήμμα, Πολυωνυμική Παρεμβολή)
      • Συστατικά και ορισμός zk-SNARKS
      • Polynomial Commitments
      • KZG Commitments
      • Non - falsifiable assumptions

      Διαφάνειες: Μέρος 1ο & Μέρος 2ο

      Μελέτη

      [JT] Κεφ. 3, 11, 12, 15

      Papers για εργασία παρουσίασης (τρεις εργασίες):

      R. S. Wahby, I. Tzialla, A. Shelat, J. Thaler and M. Walfish, "Doubly-Efficient zkSNARKs Without Trusted Setup," 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2018, pp. 926-943, doi: 10.1109/SP.2018.00060. 

      Lee, J. (2021). Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments. In: Nissim, K., Waters, B. (eds) Theory of Cryptography. TCC 2021. Lecture Notes in Computer Science, vol 13043. Springer, Cham. https://doi.org/10.1007/978-3-030-90453-1_1

      Bootle, J., Chiesa, A., Sotiraki, K. (2021). Sumcheck Arguments and Their Applications. CRYPTO 2021. https://eprint.iacr.org/2021/333

      • 3. zk - SNARKs - Μέρος 2ο

        • Επανάληψη KZG Commitments, προσθήκη ZK, multi-commitments
        • Bulletproofs
        • Interactive Oracle Proofs
        • Sum-Check & GKR
        • Σύνθετα Polynomial Commitment Schemes
        • PLONK IOP

        Μελέτη

        [JT] Κεφ. 4.1, 4.6, 14

        Διαφάνειες: Μέρος 1ο & Μέρος 2ο

        • 4. Ηλεκτρονικές Ψηφοφορίες - Μέρος 1ο (Verifiability)

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

          Διαφάνειες

          • 5. Blockchain & Consensus

            • Περιγραφή του αλγορίθμου του Bitcoin backbone.
            • Ορισμός των ιδιοτήτων common prefix, chain quality, chain growth.
            • Απόδειξη (στο μοντέλο του τυχαίου μαντείου) ότι σε μία πολυωνυμικά φραγμένη εκτέλεση του Bitcoin ικανοποιούνται οι παραπάνω ιδιότητες με "μεγάλη πιθανότητα" (δεν ισχύουν με πιθανότητα εκθετικά μικρή στην παράμετρο ασφάλειας).
            • Λύση του consensus με τον αλγόριθμο του Bitcoin και 1/3-φραγμένο αντίπαλο

            Διαφάνειες

            Η διάλεξη βασίστηκε στις δημοσιεύσεις:


            • 6. Byzantine Agreement

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


              Διαφάνειες: 

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


              • 7. Ηλεκτρονικές Ψηφοφορίες - Μέρος 2ο (Privacy and Decentralized Voting)

                • Μυστικότητα ψήφου - το μοντέλο BPRIV - απόδειξη μυστικότητας Helios.
                • Παραλλαγές Helios για everlasting privacy
                • Παραλλαγές Helios για receipt - freeness και participation privacy και σχετικές επεκτάσεις του BPRIV.
                • Coercion Resistance στο μοντέλο JCJ.
                • Αποκεντρωμένες ψηφοφορίες και blockchain.
                • Σχέσεις ιδιοτήτων.


                Διαφάνειες


                • 8. Distributed Cryptography - Μέρος 1ο

                  • 9. Distributed Cryptography - Μέρος 2ο

                    • 10. Blockchain Summer School

                      https://mega-ace.corelab.ntua.gr/index.php/program

                      • 11. Blind Signatures

                        • Ανώνυμο Ηλεκτρονικό Χρήμα με Κεντρικές Αρχές
                        • Ανώνυμες Ψηφοφορίες
                        • Μοντελοποίηση Ασφάλειας
                        • Τυφλές Υπογραφές RSA
                        • Τυφλές Υπογραφές από Σ-Πρωτόκολλα (Schnorr, Okamoto-Schnorr)
                        • Απόδειξης Ασφάλειας - Το πρόβλημα ROS

                        Slides

                        • 12. Παρουσιάσεις Εργασιών

                          1. Georg Fuchsbauer, Eike Kiltz, Julian Loss: The Algebraic Group Model and its Applications. CRYPTO (2) 2018: 33-62, Zhang, C., Zhou, HS., Katz, J. (2022). An Analysis of the Algebraic Group Model. ASIACRYPT 2022. Slides
                          2. Lee, J. (2021). Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments. Theory of Cryptography. TCC 21. Slides
                          3. Bootle, J., Chiesa, A., Sotiraki, K. (2021). Sumcheck Arguments and Their Applications. CRYPTO 2021. Slides.
                          4. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). Slides.
                          5. Kelkar, M., Zhang, F., Goldfeder, S., Juels, A. (2020). Order-Fairness for Byzantine Consensus. In CRYPTO 2020. Slides.
                          6. Abraham, I., Asharov, G. & Yanai, A. Efficient Perfectly Secure Computation with Optimal Resilience. J Cryptol, (2022). Slides
                          7. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. EuroSys '18: Proceedings of the Thirteenth EuroSys Conference. Slides