Undergraduate Course: Introduction to Modern Cryptography (INFR11131)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 11 (Year 4 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | Cryptography is the formal study of the notion of security in information systems. The course will offer an introduction to modern cryptography focusing on models and proofs of security for various basic cryptographic primitives and protocols. Cryptographic proofs are conditional on assumptions that fall in two categories: "system assumptions" such as the faithful execution of code, or the availability of private randomness and "computational assumptions". The latter are related to the computational complexity of various problems (including factoring large numbers and others). Students will learn to model security problems and prove them secure under precisely formulated system and computational assumptions. |
| Course description |
The course is divided in two parts: Private Key and Public Key.
Topics covered in the Private Key part are: classical ciphers (Caesar, Vigenere), one-time pad and perfect secrecy, computational secrecy, pseudorandom functions and permutations, CPA security, CCA security and proofs by reduction. The following topics are also briefly discussed: block ciphers, modes of operation, message integrity, hash functions and MACs.
In the Public Key part we cover: hard computational problems such as factoring and discrete log, the Diffie-Hellman key exchange protocol, ElGamal and digital signatures. Other topics that may also be discussed (depending on time) are: zero-knowledge proofs, Schnorr Identification, commitment schemes and oblivious transfer protocols. A tentative outline of the material is given below.
Part 1: Private Key
- Classical ciphers: Shift cipher, Vigenere
- Perfect secrecy
- One-time pad (OTP)
- Computational secrecy
- Pseudorandom generators (PRG)
- Pseudo-OTP
- Security against chosen-plaintext attacks (CPA)
- Pseudorandom functions / permutations (PRF / PRP)
- CPA-secure encryption using PRF/PRP: block ciphers
- Modes of operation: block ciphers, stream ciphers
- Malleability
- Security against chosen-ciphertext attacks (CCA)
- Padding-oracle attacks: non-CCA secure schemes
- Secrecy vs. integrity: message authentication codes (MAC)
- Hash functions
Part 2: Public Key
- Digital Signatures
- Trapdoor One-Way functions
- Random oracles
- Cyclic groups
- The discrete logarithm/Diffie-Hellman assumptions
- Key exchange and the Diffie-Hellman protocol
- Public Key Encryption
- Security against chosen-plaintext attacks
- ElGamal Encryption
- Zero-Knowledge proofs
- The Schnorr identification scheme
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
It is RECOMMENDED that students have passed
Computer Security (INFR10067) AND
Algorithms and Data Structures (INFR10052)
|
Co-requisites | |
| Prohibited Combinations | Students MUST NOT also be taking
Introduction to Modern Cryptography (UG) (INFR11221)
|
Other requirements | MSc students must register for this course, while Undergraduate students must register for INFR11221 instead.
This course has the following prerequisites:
1 Computer security: familiarity with basic concepts such as public and private-key encryption, one-time pad, PRG, AES, RSA
2 Probability: random variables, independence, Bayes' theorem, statistical distance, union bound
3 Algorithms: asymptotics and big-O notation
4 Mathematical maturity and being comfortable with reading and constructing mathematical proofs |
Information for Visiting Students
| Pre-requisites | As above. |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2024/25, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 2 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 18,
Feedback/Feedforward Hours 2,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
76 )
|
| Assessment (Further Info) |
Written Exam
70 %,
Coursework
30 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
70% Exam
30% Coursework |
| Feedback |
Not entered |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | Introduction to Modern Cryptography (INFR11131) | 2:120 | |
Learning Outcomes
On completion of this course, the student will be able to:
- apply basic number theory, group theory and discrete probability to analyse cryptographic algorithms
- understand the notions of pseudorandom functions/generators and their connection with encryption schemes
- develop the ability to model security problems and to write security proofs
- understand fundamental cryptographic primitives including Key Exchange, Digital Signatures, Oblivious Transfer, Public-Key Encryption, Commitment, and critique or prove the security of candidate cryptographic schemes that are supposed to realize the above primitives
- understand basic computational problems that are important for cryptography such as the factoring problem, the RSA problem, the discrete-logarithm problem, and develop the ability to reduce the security of cryptographic schemes to computational problems
|
Contacts
| Course organiser | Mr Michele Ciampi
Tel: (0131 6)51 5661
Email: michele.ciampi@ed.ac.uk |
Course secretary | Miss Yesica Marco Azorin
Tel: (0131 6)50 5194
Email: ymarcoa@ed.ac.uk |
|
|
University Homepage