Contemporary Cryptography Concepts

Introduction to Cryptography

• The course is titled LMAT2450 - Cryptography.
• The course is taught by François Koeune, Olivier Pereira, and T. Peters
• The course focuses on the algorithmic and mathematical aspects of securing information.

Course Goal

• Students will understand fundamental concepts, methods, and algorithms used to secure information.

Related Courses at UCL

• Information theory and coding, taught by J. Louveaux and B. Macq. and O. Pereira
• Secure electronic circuits and systems, taught by F.-X. Standaert
• Privacy Enhancing Technologies, taught by O. Pereira and F.-X. Standaert
• Secured systems engineering, taught by A. Legay
• Computer System Security, taught by R. Sadre
• Number Theory, taught by P.-E. Caprace and O. Pereira

Other Related Courses

• Machine Learning, taught by J. Lee and M. Verleysen
• Computer Networks, taught by O. Bonaventure
• Discrete Mathematics II: Algorithms and complexity, taught by J.-C. Delvenne
• Ethics and ICT, taught by A. Gosseries and O. Pereira

Class Organisation

• Lectures are held on Wednesday from 14:00 to 16:00.
• Exercises are held on Wednesday from 16:15 to 18:15.
• TAs are Antoine Legat and Alexis Vuille.
• Students are allowed to use slides and personal notes during exams
• Past exam questions are often used as exercises.

Syllabus

• The course will cover Introduction (1 lecture)
• Symmetric cryptography (4 lectures)
• Asymmetric cryptography and algorithmic number theory (5 lectures)
• Post-quantum cryptography (1 lecture)

Support Material

• Introduction to Modern Cryptography (3rd edition) by J. Katz and Y. Lindell, Chapman & Hall/CRC - 2021, http://www.cs.umd.edu/~jkatz/imc.html
• Other references (see also Moodle):
• D. Stinson, Cryptography, Theory and Practice, 3rd edition, Chapman & Hall/CRC, 2005.
• N.P. Smart, Cryptography Made Simple, Springer, 2016. (Free access within UCLouvain network)
• A.J. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, 1999. (Free on http://www.cacr.math.uwaterloo.ca/hac/)
• D. Boneh, V. Shoup, A Graduate Course in Applied Cryptography, Free draft on http://toc.cryptobook.us/.
• S. Gabraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012, Extended version from author's homepage.

Cryptography...

• COD defines cryptography as "the art of writing or solving codes".
• This definition was mostly true until the mid-20th century
• Cryptography was primarily used by armies and diplomats.

Cryptography... Today

• Cryptography is used widely in daily life.
• Examples include car security systems, identification cards, and security in financial transactions.
• Cryptography is much more than just encryption, instead it's also used in key exchange, identification and is used in elections.

The Cryptography Problem

• The diagram shows a basic message encryption problem between 2 users (A and B).
• A sends a message m to B.
• The system receives m and encrypts it into c and sends it to B.
• B decrypts the message and reads m.

Message Encryption

• An encryption scheme consists of three components: Gen, Enc, and Dec.

• Gen probabilistically produces a key, k

• Enc encrypts the message, m, using the key k, producing a ciphertext, c

• Dec decrypts the ciphertext, c, using the key, k, recovering the original message, m

• The Scytale (Greece, 7th century BC) involves using a cylinder to encrypt messages based on its diameter.

• The Caesar's cipher (Rome, 1st c. BC) involves shifting each letter of the alphabet a fixed number of positions.

Cryptanalysis

• Cryptanalysis is the art of code-breaking or cracking codes.
• In cryptanalysis, the attacker should consider which information should be secret, like Gen, Enc, Dec, or k.
• The attacker should identify which attack scenario would be used. Possible attacks include eavesdropping or chosen-plaintext attacks.
• Kerckhoffs' principle (1883) states that only the secret key should be kept secret. This principle is to ensure that the encryption scheme and algorithm can be public knowledge.

Cryptanalysis: Attacker Model

• The attacker needs to determine which attack scenario is relevant.
  • Passive attacks (e.g., ciphertext-only, known-plaintext) involve observing the ciphertext only, or observing plaintext/ciphertext pairs
  • Active attacks (e.g., chosen-plaintext, chosen-ciphertext) involve the ability to choose messages to be encrypted or decrypted.

Mono-alphabetic Substitution

• An improvement on Caesar's cipher, allows any permutation of the alphabet.
• The possible keys are 26! ≈ 2⁸⁸
• To break this, frequency analysis can be useful if the plaintext language is known.
• This shows that frequency analysis can be useful in breaking substitution ciphers.

Mono-alphabetic Substitution (Frequencies)

• Frequency analysis can help in breaking codes because letter frequencies in English and other languages vary.

Vigenère Cipher

• A further improvement over substitution ciphers using a repeating key to determine the shift factor for each letter
• To break this, enough ciphertext is needed to determine the keylength by trial and error.
• Frequency analysis is then used to break the code.

Historic Ciphers

• Cryptography has a long history.
• For example. D. Kahn, or J. Stern.

Modern Cryptography

• Definitions, assumptions, proofs.

Modern Cryptography: Definitions

• Defining what needs to be done, and defining why one scheme is better than another.

Example of Encryption

• Cryptography needs to define security for encryption schemes.
  • Given a ciphertext, an attacker shouldn't be able to recover the key or the plaintext.
  • Given a ciphertext, an attacker shouldn't be able to recover any character or function of the plaintext.

Modern Cryptography: Precise Assumptions

• Most schemes rely on computational assumptions, useful for abstraction and scheme comparison.

Modern Cryptography: Proof of Security

• Relate schemes, definitions, and assumptions using a reductionist approach. If a scheme can be broken, an assumption can also be falsified.

Modern Cryptography: Definitions (Limitations)

• Science vs. real-world limitations.
• Checking intuitive properties.
• Comparing with other definitions and attack examples.
• Using definitions for a period of time.

Perfect Encryption

• Shannon (1949) showed that theoretically, perfect encryption is possible.

Perfect Encryption (Definition)

• A triple (Gen, Enc, Dec) is perfectly secret if the probability of a ciphertext given a message is equal to the probability of the message
• Enc, Dec may be probabilistic or deterministic.
• M and C are sets of possible messages and ciphertexts.

Perfect Encryption (Equivalent Definition)

• If for any two messages (m and m'), in a given ciphertext, the probability of m is equal to m'
• This means that the ciphertext corresponding to the two messages cannot be distinguished.

Perfect Encryption (Example)

• The One-Time Pad (OTP) is a perfectly secret encryption scheme.
• OTP uses a key that is as long as the message.
• Each bit of the message is XORed with the corresponding key bit to produce the ciphertext.
• XOR is a binary operation that returns 1 if the inputs are different and 0 if they are the same.

One-Time Pad

• The one-time pad is perfectly secret but is not convenient to use.
• The key needs to be as long a message to be secure.
• If a key is used twice with multiple messages, then the adversary can solve the code.

Limits of Perfect Secrecy

• Schemes with shorter key lengths than messages can't be perfectly secret
• Because of this the ciphertext is not equally probable under different messages.

Conclusion

• Perfectly secret encryption schemes exist, but are difficult to use.
• Shannon's work indicates that a theoretical limit exists under various assumptions.
• The next topic in the course will discuss bounded computational power.