Lecture 1: Introduction and Preliminaries

Cryptography (CS 427/529)

Tue, Thu 2:00-3:50pm

COVL (Covell Hall) 221

Instructor: Jiayu Xu

• Fourth-year assistant professor, research area: cryptography
• Email: xujiay@oregonstate.edu
• Office hours: Tue noon-1:50pm (before class), KEC 2021;�or by appointment/email

Teaching Assistant: Tingfei “Carlos” Feng

• Second-year PhD student, research area: cryptography
• Email: fengti@oregonstate.edu
• Office hours: TBD

Logistics

• 5 homeworks, 2-5 problems per homework
• Lowest score dropped
• Deadline in ~2 weeks
• No exams!

• Resubmission allowed
• I will explain solution in class after deadline
• After that, you can submit a correction of your previous submission (mistake you made + correct answer)
• MUST BE DONE BEFORE THE SECOND-TO-LAST CLASS (03/10)
• You can get up to 50% of your lost scores back
• First submission graded by TA, resubmission graded by me
• Resubmission will be graded more harshly (more rigor required)
• Example:
• You got 6/10 in 1st submission, then 8/10 in resubmission
• Final score (for this homework) = 6+(8-6)×50% = 7/10

• Can discuss with classmates, search solutions online, etc.
• MUST CITE YOUR SOURCE (e.g., title of book/link to webpage)
• Must write down your solution independently
• Submissions of 2 students should never look similar
• Use of generative AI (e.g., ChatGPT) allowed (but discouraged)
• MUST INCLUDE PROMPTS
• You must understand whatever you write
• I may ask you to explain your (re)submission in my office

Textbook

• No textbook
• 3 main reference books
• Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography (3rd edition). CRC Press, 2021. https://www.cs.umd.edu/~jkatz/imc.html
• Mike Rosulek. The Joy of Cryptography. MIT Press, 2026. https://joyofcryptography.com
• David Wong. Real-World Cryptography. Manning, 2021. https://www.oreilly.com/library/view/real-world-cryptography/9781617296710
• (My notations might be different)

​

What is Κρυπτογραφία?

Classical cryptography

• Ancient Greek
• κρυπτός (kryptós) = hidden / concealed / secret
• γράφειν (graphein) = to write
• “To write in a secret manner”
• Maintain secrecy of message over an insecure channel (encryption)
• Ad hoc construction of schemes (art)
• Design an encryption scheme → scheme broken (“cryptanalyzed”) → design a new scheme → new scheme broken → …

Modern cryptography (since 1970s): from art to science

• 1. Scope much broader
• Encryption schemes
• Message authentication codes
• Hash functions
• ……
• Protect communication against an adversary
• 2. Formal definitions of security
• “A scheme is secure if no adversary can break it with significant probability”
• “Break” is usually defined via a game (played between adversary and an imaginary challenger)
• “A scheme is secure if no adversary can win the security game with significant probability”

• 3. Formal proofs of security
• Usually based on assumptions (number theoretical/security of underlying schemes)
• “If assumption A holds, then scheme S is secure (per the security definition)”

From theory to practice

• 1. Identify a need
• “I need a secure encryption scheme”
• 2. Propose a scheme
• 3. Prove security of scheme
• “Thm: If assumption A holds, then encryption scheme S is secure”
• 4. Standardize scheme (by ISO, IETF, …)
• 5. Implement scheme
• This class: steps 1, 2, 3 (theoretical cryptography)
• Steps 4, 5 → cryptographic engineering
• It is possible that a “provably secure” scheme is broken in practice due to bugs in implementation

Warning: math

• This class is about defining and proving security of cryptographic schemes, in an abstract, mathematically rigorous manner
• … NOT about implementing and applying such schemes (that’s for a course in “applied security”)
• What we will do is defining and proving stuff (pen and paper)
• … NOT programming

Preliminaries

Bitstrings

Discrete probability theory

Basic facts

Independence of events

Conditional probability

Test your knowledge…