Computational Cryptography

Abstract

Το βιβλίο αποσκοπεί να εισαγάγει τον αναγνώστη στις θεμελιώδεις έννοιες και τεχνικές της κρυπτογραφίας, με έμφαση στην αλγοριθμική και υπολογιστική διάστασή τους. Τα περιεχόμενα συνοπτικά: - Εισαγωγή σε βασικές έννοιες αλγορίθμων και πολυπλοκότητας: ανάλυση αλγορίθμων, αποδοτικότητα, πολυωνυμικός χρόνος, πιθανοτικοί αλγόριθμοι, κλάσεις πολυπλοκότητας. - Στοιχεία θεωρίας αριθμών και θεωρίας ομάδων: αριθμητική modulo, ομάδες, δακτύλιοι, σώματα, Κινέζικο Θεώρημα Υπολοίπων, Θεωρήματα Fermat, Euler, Lagrange, πρωταρχικές ρίζες, συνάρτηση φ του Euler, τετραγωνικά υπόλοιπα, σύμβολα Legendre και Jacobi. - Υπολογιστική πολυπλοκότητα και αλγόριθμοι για βασικά αριθμοθεωρητικά προβλημάτων: επαναλαμβανόμενος τετραγωνισμός, Ευκλείδειος, επεκτεταμένος Ευκλείδειος, υπολογισμός συμβόλου Jacobi, ρίζες modulo n, έλεγχοι πρώτων αριθμών (Fermat, Solovay-Strassen, Miller-Rabin, αλγόριθμος AKS), παραγοντοποίηση (μέθοδος ρ, μέθοδος Dixon), διακριτός λογάριθμος (Shanks, Pohling-Hellman, index-calculus). - Συμμετρικά κρυπτοσυστήματα: πακέτου (DES, AES), ροής (stream ciphers). Τρόποι λειτουργίας. Κρυπτοσυστήματα δημοσίου κλειδιού: RSA, ElGamal. Ανταλλαγή κλειδιού Diffie-Hellman. - Σχήματα ψηφιακών υπογραφών (RSA, DSS), υπογραφές ειδικού σκοπού (μιας χρήσης, τυφλές, αδιαμφισβήτητες). - Κρυπτογραφικά πρωτόκολλα (διαμοιρασμού μυστικού, ρίψης νομίσματος, ανταλλαγής κλειδιού). - Αποδείξεις ασφάλειας βασισμένες σε γενικά παραδεκτές υποθέσεις υπολογιστικής δυσκολίας, μοντέλα ασφάλειας (KPA, CPA, CCA, IND-CPA, IND-CCA), κρυπτογραφικές αναγωγές. - Συναρτήσεις σύνοψης (hash functions) και συναρτήσεις μονής κατεύθυνσης. Ψευδοτυχαιότητα. - Αποδείξεις μηδενικής γνώσης. Πρωτόκολλα ταυτοποίησης. - Προηγμένα θέματα: κβαντική και μετα-κβαντική κρυπτογραφία, ελλειπτικές καμπύλες, σύνθεση πρωτοκόλλων, διγραμμικές απεικονίσεις, κρυπτογραφία με lattices.

This book aims to introduce the reader to the fundamental concepts and techniques of modern cryptography, with an emphasis on their algorithmic and computational aspects. Concretely, the book contains the following topics: - Introduction to basic algorithmic and computational complexity concepts such as: algorithm analysis, efficiency, polynomial time, probabilistic algorithms, complexity classes. - Elements of number theory and group theory: modular arithmetic, groups, rings, fields, Chinese Remainder Theorem, Fermat's, Euler's, and Lagrange's Theorems, primitive roots, Euler's totient function, quadratic residues, Legendre and Jacobi symbols. - Computational complexity and algorithms for fundamental number-theoretic problems: repeated squaring, Euclidean and extended Euclidean algorithms, Jacobi symbol computation, roots modulo n, primality tests (Fermat, Solovay-Strassen, Miller-Rabin, AKS algorithm), factorization methods (ρ method, Dixon's method), discrete logarithm (Shanks, Pohling-Hellman, index-calculus). - Symmetric cryptosystems: block ciphers (DES, AES), stream ciphers, modes of operation. - Public-key cryptosystems: RSA, ElGamal, Diffie-Hellman key exchange. - Digital signature schemes: RSA, DSS, special-purpose signatures (one-time, blind, undeniable). - Cryptographic protocols: secret sharing, coin flipping, key exchange. - Security proofs based on computational hardness assumptions, security models (KPA, CPA, CCA, IND-CPA, IND-CCA), cryptographic reductions. - Hash functions and one-way functions: pseudo-randomness. - Zero-knowledge proofs: identification protocols. - Advanced topics: quantum and post-quantum cryptography, elliptic curves, protocol composition, bilinear maps, lattice-based cryptography.