ENGG 5383

Applied Cryptography
Sherman Chow
Chinese University of Hong Kong
Spring 2023
Lecture 2: Encryption

18th January 2023 ENGG5383 Applied Cryptography 1

“Basic” Requirement of IT-Security
▪ Alice sends a message to Bob, Eve wants to eavesdrop
▪ Bob must have a secret from Eve (otherwise Eve = Bob)
▪ Alice and Bob must share a “secret” not known to Eve
▪ Consider Alice used “information” X other than m to create c
▪ Eve has unbounded power, she can try all possible X’s
▪ Yet ciphertext is uniquely decipherable, so Bob must know part of X
▪ Key generation algorithm G(1λ) → k
▪ Security parameter λ is for determining the security level
▪ Ek (m) → c, Dk (c) → m // Symmetric-key encryption

18th January 2023 ENGG5383 Applied Cryptography 2/40

 n-1

(Shannon) Entropy H(x) = -å Pr(xi )logPr(xi )

i=0

▪ H(x) --- A measure of the amount of information (about x)

▪ that is missing before reception

▪ Consider a fair coin, Pr(x0) = Pr(x1) = ½

▪ - lg(1/2) = -(lg1 – lg 2) = -(0 – 1) = 1
▪ Here, lg means log2 (so lg 2 = 1), not following “ISO notation”…
▪ So, we use 1 bit to denote this event (of coin tossing)
▪ with probability ½ we gain this 1 bit of info is 0 (or 1)

▪ Looking ahead: for a set Y of size 2c (without any “compression”)

▪ each element in Y can be represented by lg(2c) = c-bit string

18th January 2023 ENGG5383 Applied Cryptography 3/40

“Insecurity” of Substitution Ciphers
▪ Let’s use the definition of entropy to evaluate English characters
▪ True prob. distribution of alphabets in English is “unknown”
▪ Character entropy: 4.219 according to character occurrence
frequency (when all characters are independent)
▪ Yet, English has common bi-/tri-gram → 2.77
▪ E.g., qu is a character-level bigram
▪ Shannon's estimation: 0.6 - 1.3 bits per character

▪ Frequency analysis
▪ e.g., www.cryptool-online.org/?Itemid=117
▪ Check Chapter 1 of Stinson’s book
▪ www.math.uwaterloo.ca/~dstinson/books.html

18th January 2023 ENGG5383 Applied Cryptography 4/40

XOR, One-Time Pad, and IT-Security
▪ XOR: For b1 ⊕ b2 where b1 is a bit, see the table below
▪ For bit-string operation S1 ⊕ S2, just ⊕ in a bit-wise manner

▪ OTP: G(1λ) outputs a random λ-bit string as k XOR 0 1

▪ Ek (m) → c = m ⊕ k; 0 0 1
▪ m is λ-bit long 1 1 0
▪ Dk (c) → m = c ⊕ k

▪ Def. of Information-Theoretic Security: H(m) = H(m | c)

▪ R.H.S.: conditional entropy of the plaintext given the ciphertext
▪ i.e., Pr(M = m | C = c) = Pr (M = m)

18th January 2023 ENGG5383 Applied Cryptography 5/40

OTP is Secure
▪ Pr(M = m | C = c)
= Pr(M = m ∧ C = c) / Pr(C = c) [Bayes’ law]
= Pr(M = m) Pr(C = c|M = m) / Pr(C = c) [prob. def.]
= Pr(M = m) Pr(C = c | M = m)
/ Σm’  M Pr(M = m’) Pr(C = c | M = m’)
= Pr(M = m)  (1/2λ) / Σm’  M { Pr(M = m’)  (1/2λ)}
= Pr(M = m) / 1
since Pr(C = c|M = m’) = 1/2λ for all c and m’ for OTP

18th January 2023 ENGG5383 Applied Cryptography 6/40

This Lecture
▪ Security against computationally-bounded adversary
▪ also known as (a.k.a.) probabilistic polynomial-time adversary

▪ “Symmetric-Key Primitives”
▪ and constructing Symmetric-Key Encryption from them

▪ “Public-Key Primitives”
▪ and their number-theoretic candidate constructions
▪ and constructing public-key encryption from them

▪ Modeling security of Public-Key Encryption

18th January 2023 ENGG5383 Applied Cryptography 7/40
Probabilistic Polynomial Time (PPT) Algo
▪ y = A(x)
▪ Input x is of size/length n
▪ We write |x|= n
▪ Run-time is O(nc): c being a constant
▪ We say a PPT algorithm is an “efficient” algorithm
▪ Probabilistic: allows to “flip a coin” to make it randomized
▪ y  A(x)
▪ y denotes the random variable corresponds to A’s output
▪ Or y = A(x; r), where r denotes A’s internal coin tossing
▪ r’s length is also polynomial in n

18th January 2023 ENGG5383 Applied Cryptography 8/40

Negligible Function
▪ A function v(n) is called negligible, denoted negl(n), if:
▪ (∀c > 0) (∃n’) (∀n ≥ n’) [v(n) ≤ 1/nc]
▪ Less than the inverse of any polynomial for large enough n

▪ Prob. of breaking a secure system should be negligible in n

▪ Let poly(n) denote some polynomial function in n

▪ We have poly(n)  negl(n) = negl(n)

18th January 2023 ENGG5383 Applied Cryptography 9/40

Security Parameter (& some notations)
▪ We want a “set” of cryptosystems parameterized by n
▪ Algo.’s run by all parties take commonly agreed input n
▪ They run in time polynomial in their input length n
▪ Notations:
▪ poly(n): runtime of all parties are sufficiently fast, e.g., n3
▪ negl(n): e.g., 1/2n is in negl(n)
▪ 1n denotes n “copies” of 1’s, i.e., 1n is in {0, 1}n
▪ Security parameter of the system is 1n (with length n bits)
▪ but not n (length of n is log(n) bits)
18th January 2023 ENGG5383 Applied Cryptography 10/40
Symmetric-Key Primitives
▪ Pseudorandom Generator (PRG)
▪ Pseudorandom Function (PRF)
▪ Pseudorandom Permutation (PRP)

▪ Pseudorandomness: its output is “computationally

indistinguishable” from true randomness
▪ “Computational” indistinguishability
▪ only holds against a computationally bounded adversary
▪ distinguish: the difference in the probabilities of concluding it is
a truly random function / a randomly chosen function is negligible

18th January 2023 ENGG5383 Applied Cryptography 11/40

Pseudorandom Generator (PRG)
▪ Definition:
▪ Inputs a short, truly random “seed” (or calling it a secret key)
▪ Outputs a long string of “pseudorandom” bits
▪ Construction:
▪ E.g., Blockcipher (e.g., AES) run in “counter mode”
▪ Mode of operation: to use a fixed input-output block-cipher E() to
encrypt an arbitrarily long message (with many message blocks)
▪ Application: can be used to build “Stream cipher”
▪ Stream cipher”: Encrypt 1 bit at a time
▪ It can be treated as a “Stateful symmetric-key encryption”
18th January 2023 ENGG5383 Applied Cryptography 12/40
Counter Mode and PRG
▪ Counter mode for c[0] c[1] c[2] c[3]

encrypting Counter = i i+1 i+2 i+3

4 blocks of message: E(k,) E(k,) E(k,) E(k,)

▪ Here i, i+1, … are    
the input of E(k, )
m[0] m[1] m[2] m[3]

▪ Counter-mode construction of PRG from blockcipher E():

no exclusive OR and just treat c[0] … c[n] as the output
▪ Recall that PRG only has the key k as input and there is no m

18th January 2023 ENGG5383 Applied Cryptography 13/40

PRG ➔ Stateful SKE
▪ (c, s’)  E(m; s), (m, s’)  D(c; s)
▪ where s is the old (secret) state and s’ is the new state
▪ Ingredient: A (non-trivial PRG) G: {0, 1}λ → {0, 1}n+λ
▪ from λ-bit string to (n+λ)-bit string (stretching)
▪ a trivial PRG: if {0, 1}λ → {0, 1}λ, just directly output the input
▪ denote it as G() = G1() o G2 () where |G1 ()| = n, and |G2()| = λ

▪ To encrypt m with state s, output c = m ⊕ G1(s), s’ = G2(s)

▪ To decrypt c with state s, output m = c ⊕ G1(s), s’ = G2(s)
▪ Problem: encryptor and decryptor need to synchronize

18th January 2023 ENGG5383 Applied Cryptography 14/40

Pseudorandom Func. & Permutation
▪ Pseudorandom Function (PRF) defined over (K,X,Y): F: K  X → Y
▪ K is the key space, usually just a set of bit-strings
▪ “efficient” (a.k.a. PT) algorithm to evaluate F(k, x) exists

▪ Pseudorandom Permutation (PRP) defined over (K,X): E: K  X → X

▪ “efficient” deterministic algorithm to evaluate E(k, x) exist
▪ E(k,  ) is one-to-one
▪ “efficient” inversion algorithm D(k, y) exists
▪ Note: it is an abstraction of “stateless” “block-cipher”

18th January 2023 ENGG5383 Applied Cryptography 15/40

Security of PRF
▪ For a random key k
▪ Note: |k| bit of randomness f1 f2 f3 f4 f: {0,1} → {0,1}
XY XY XY XY i.e., X = Y = {0, 1},|X|= 2
▪ f(k,) is “indistinguishable” from 0 0 0 0 0 1 0 1 Funs[X, Y] = {f1, f2, f3, f4}
▪ a random function in Funs[X,Y] = {“00”, “01”, “10”, “11”}
1 0 1 1 1 0 1 1
▪ the set of all functions from X to Y Each fi “has” 2 bits
▪ |X|lg(|Y|) bit of randomness for index i ∈ {1, 2, 3, 4}
▪ Notation: the size of set X (the input space here) is |X|
▪ When |X|lg(|Y|) > |k|, how can it be possible?
▪ Intuition: an adversary can only make polynomially-many queries
▪ and thus it does not have enough time to infer which “world” it is in

▪ Secure PRF → Secure (non-stateful) SKE

▪ But we did not study the security definition of the latter yet (stay tuned)

18th January 2023 ENGG5383 Applied Cryptography 16/40

PRG vs. PRF
▪ PRG: a single output appears random if the input was chosen at random.
▪ PRF: all its outputs appear random, regardless of how the corresponding
inputs were chosen, as long as the key is randomly drawn

▪ Can we use PRG to build PRF?

▪ Suppose PRG G() outputs a bit string of nc long
▪ We build a PRF with key being the seed k of PRG
▪ and use a clg(n)-bit long input to specify the 1 bit in G(k)’s output
▪ i.e., Output G(k)[x], where S[i] denote the i-th bit of string S
▪ So for a non-trivial PRF, we have |X| = ω(lg(n))

▪ There exists a way to use PRG to build (non-trivial) PRF [details omitted]
18th January 2023 ENGG5383 Applied Cryptography 17/40
Key Management for Symmetric-Keys
▪ How many keys for the whole network if each of them
establish a confidential channel for each other?

▪ Recall: Alice and Bob must share a secret not known

to Eve because Eve is unbounded
▪ What if the eavesdropper we are worrying of is bounded?

18th January 2023 ENGG5383 Applied Cryptography 18/40

Public-Key Encryption
▪ KeyGen(1λ) → (sk, pk)
▪ Epk (m) → c, Dsk (c) → m
▪ How many key(pair)s are needed for n nodes?

▪ Computable: Anyone can efficiently execute E()

▪ Invertible: Alice can “invert” the function E()
▪ Easily invertible given auxiliary information sk
▪ Difficult to invert without sk

18th January 2023 ENGG5383 Applied Cryptography 19/40

Public-Key Primitives: OWF, OWP, TDP
▪ One-Way Functions (OWF)
▪ Easy to compute
▪ Computation: Given x, derive f(x) can be done in polynomial time
▪ Difficult to invert
▪ Inversion: Given f(x) (and the description of f() itself), deriving x will take
an exponential time
▪ One-Way Permutations (OWP)
▪ + Must be possible to invert
▪ cf. Can’t invert f at -1 for f(x) := x2: R → R≥0
▪ where R = set of real numbers and R≥0 = set of non-negative real numbers
▪ Trap-door Permutations (TDP)
▪ + Easy to invert when given some “auxiliary info” is given

18th January 2023 ENGG5383 Applied Cryptography 20/40

Formal Definition of OWF/P
▪ Pr(f(z) = f(x) | x ∈ {0, 1}λ, y ← f(x), z ← A(y, 1λ)) = negl(λ)

▪ For a random x
▪ Give y = f(x) to the adversary A()
▪ A is supposed to return z
▪ Such that y = f(z)
▪ Question: why not just require x = z?

▪ If f is also one-to-one, f is called a one-way permutation

18th January 2023 ENGG5383 Applied Cryptography 21/40
Trapdoor Permutation
▪ For every λ
▪ There exists a string T (the “trapdoor”)
▪ of polynomial length, |T| ≤ poly(λ)
▪ and a polynomial-time “inversion” algorithm Inv() s.t.
▪ Inv(f(x), T) = x, for any x ∈ {0, 1}λ

▪ Wait, you told me that it is one-way, but now you told

me that there is a trapdoor, so is it one-way or not?
▪ Answer: A() did not see the trapdoor T.
18th January 2023 ENGG5383 Applied Cryptography 22/40
More Details in Formalisms
▪ How is the trapdoor born?
▪ Recall that we want to study (T)OWF/P for building PKE
▪ We want to generate a pair of public-private key together
▪ Everyone use the same function?
▪ We need a definition for a family of OWFs
▪ Analogy: PRFs is also a family, each function in the PRF family is
indexed by a key, so picking a key ➔ choosing a function
▪ So the definition of OWF/P should be fixed to also include the
random choice in picking f() from the function family

▪ P.S. existence of PRG  existence of OWF [details omitted]

18th January 2023 ENGG5383 Applied Cryptography 23/40
Some Complexity Theory
▪ P = NP means
▪ every problem whose solution can be quickly verified (NP)
▪ can also be quickly solved (P)
▪ The existence of OWFs trivially implies that P != NP
▪ (The existence of PRG also implies P != NP)
▪ (PRG exists if and only if OWF exists)
▪ Yet, even if we assume P != NP, we do not know how
to prove that OWFs exist
▪ We can only say we have some “candidate” for OWF
18th January 2023 ENGG5383 Applied Cryptography 24/40
OWF Candidate (+ Provable Security)
▪ Integer Multiplication vs. Factoring
▪ Try factoring 2021
▪ f(p, q) = p  q
▪ where p and q are λ-bit primes
▪ In other words, domain of f is a pair of two λ-bit primes

▪ If factoring is hard, then f is provably OWF

▪ Under assumption Y, then X is provably secure.
▪ The only way to “break” system X is to solve problem Y

18th January 2023 ENGG5383 Applied Cryptography 25/40

OWP (via Modular Exponentiation)
▪ f(x, p, g) = (gx mod p, p, g)
▪ OR fp, g(x) = gx mod p
▪ To invert, it is to solve Discrete Logarithm Problem (DLP)
▪ Now, some Number Theory (or Abstract Algebra)!

▪ http://cacr.uwaterloo.ca/hac
▪ http://www.shoup.net/ntb

18th January 2023 ENGG5383 Applied Cryptography 26/40

Groups
▪ A (finite) set G and a “group operation” (say *) that is
▪ closed (∀a, b in G, a * b is also in G)
▪ associative (∀a, b, c in G, (a * b) * c = a * (b * c) holds)
▪ equipped with identity e, (∀a in G, e * a = a * e = a holds)
▪ invertible (∀a in G, ∃b in G s.t. a * b = b * a = e holds)
▪ commutative for Abelian group (∀a, b in G, a * b = b * a)
▪ Examples:
▪ Z (integers, with addition operation; infinite group)
▪ Gn (G, a group; coordinate-wise operation)

18th January 2023 ENGG5383 Applied Cryptography 27/40

Finite Cyclic Group
▪ Order of a group g0
▪ denoted by |G|
▪ number of elements in G g6 g1
▪ Cyclic group
▪ (in multiplicative notation)
▪ there is one element g s. t.
g5 g2
▪ G = {g0, g1, g2, ..., g|G| - 1}

▪ E.g., ZN g4 g3
▪ consider g = 1, or any g s.t. gcd(g, N) = 1
18th January 2023 ENGG5383 Applied Cryptography 28/40
Multiplicative Group of ZN
▪ ZN*: set of elements from ZN that are relatively prime to N
▪ (just notation “clash”, not to be confused with the operation *)
▪ a and b are relatively prime if gcd(a, b) = 1
▪ For any N, 0 is not in ZN*
▪ For any prime p, Zp* = Zp \ {0}

18th January 2023 ENGG5383 Applied Cryptography 29/40

Fermat’s Little Theorem
▪ Order of a (in Zp*) is the smallest x s.t. ax = 1 mod p

▪ FLT: For any prime p, and x in Zp*, xp-1 = 1 mod p

▪ All elements’ orders are (p – 1)?

▪ E.g.: Consider p > 3 and (p – 1)2

▪ Exercise: show gx mod p is a OWP candidate

▪ (Do not bother w/ one-wayness first, prove that it is a permutation)

18th January 2023 ENGG5383 Applied Cryptography 30/40

RSA (Rivest-Shamir-Adleman 1978)
▪ Most widely accepted&implemented approach to PKE
▪ “Block cipher” where 0 ≤ m, c ≤ N - 1 for some N

18th January 2023 ENGG5383 Applied Cryptography 31/40

RSA (Some Mathematics Behind)
▪ fe, N(x) = xe mod N, where N = p * q, x in ZN* and e in ZΦ(N)*

▪ Euler phi-function: For any positive integer m, Φ(m) is the

number of +ve int. < m that are relatively prime to m.
▪ Exercise 1: What is |Zm*|?
▪ Exercise 2: What is Φ(N) where N = p * q, p and q are prime?

▪ Euler’s Theorem: For any int. m, & x in Zm*, xΦ(m) = 1 mod m

▪ So, what is the trapdoor and the corresponding Inv. algo.?

▪ Extended Euclid Algorithm for finding G.C.D. [details later]

18th January 2023 ENGG5383 Applied Cryptography 32/40

Security Requirement of Encryption
▪ Without the “secret key”, the ciphertext is not “useful”
▪ What is the “secret key” is “useful” for?
▪ Decryption
▪ Refined: Without the “secret key”, the ciphertext is not
“useful” for decryption, i.e., “getting back” the plaintext
▪ Security requirement is related to an attack goal
▪ getting back the plaintext
▪ every part of it
▪ i.e., attack against one-wayness
▪ Let’s study the security of PKE first
▪ Why not SKE? Actually PKE security definition is “simpler”

18th January 2023 ENGG5383 Applied Cryptography 33/40

One-Wayness for Public-Key Encryption
▪ OWF: Pr(f(z) = f(x) | x ∈ {0, 1}λ; y ← f(x); z ← A(y, 1λ)) = negl(λ)

▪ The above def. is just 1 OWF

▪ It does not allow us to choose 1 OWF among a collection of OWFs

▪ More formally, a collection of OWFs is defined by:

▪ Pr(fpk(z) = y | pk  G(1λ); x  D(pk); y = fPK (x); z ← A(y, pk, 1λ))
▪ pk is the public system parameter, D(pk) is the domain determined by pk
▪ Exercise: Define a family of TDP

▪ OW for PKE: Pr(m’ = m |

(pk, sk)  G(1λ); m ← M, c  Epk(m); m’ ← A(c, pk, 1λ)) = negl(λ)

18th January 2023 ENGG5383 Applied Cryptography 34/40

One-Wayness, depicted
▪ A random plaintext is chosen by the challenger
▪ Challenge: a ciphertext encrypting it
▪ Adversary’s goal: recover the plaintext in full

Here is my public key, I would not tell you my private key

And I encrypt a random message, tell me what it is

Adversary Challenger
18th January 2023 ENGG5383 Applied Cryptography 35/40
Basic Principles in Cryptography
▪ What if we have a quantum computer which can factor
number larger than 15 with accuracy higher than 50%?

▪ Use another candidate of TDP (to instantiate, say, PKE)

▪ Abstraction/Distillation of properties we want
▪ “One-wayness” in TDP

▪ Is this kind of abstraction always the best?

▪ We may want more property, say, f(a) ∗ f(b) = f(a + b)
▪ Well, we can make a “more specific generalization”

18th January 2023 ENGG5383 Applied Cryptography 36/40

Is that OW-PKE good enough?
▪ Consider f’(x1, x2) = (f(x1), x2), is f’ a TDP if f is?
▪ Exercise: formally prove that f’ is a TDP

▪ OW-PKE inherently leaks some information of m.

▪ Have we proven anything if m is not random?

▪ Is the message we want to protect always random?

▪ How about defining f(x) s.t. it hides all information of x?

▪ Not really the right way… it becomes a chicken and egg situation

18th January 2023 ENGG5383 Applied Cryptography 37/40

Semantic Security of Encryption
▪ Two plaintexts are chosen by adversary
▪ Challenge: a ctxt. encrypting either 1 of them
▪ Adversary’s goal: outputs a single bit for distinguishing
between 2 possibilities
▪ This game is also called Chosen-Plaintext Attack (CPA)

I want to be challenged with these 2 messages: m0, m1

Now I encrypt a random 1 of them, make your guess

18th January 2023 ENGG5383 Applied Cryptography 38/40

What is semantic security modeling?
▪ Two plaintexts are chosen by adversary
▪ The attacker knows and can even influence what are
to be encrypted

▪ Adversary’s goal: outputs a single bit.

▪ i.e., to win this game (to break the security), the
attacker only needs to learn 1 bit.
▪ Security means not even 1 bit of information is leaked!

18th January 2023 ENGG5383 Applied Cryptography 39/40

Stay tuned
▪ Encryption
▪ Key-Exchange
▪ Decisional Diffie-Hellman Assumption
▪ ElGamal Encryption

▪ Authentication
▪ Hash Function
▪ Message Authentication Code
▪ Signatures

18th January 2023 ENGG5383 Applied Cryptography 40/40