Applied Cryptography American University of Beirut

Applied Cryptography
CMPS 297AD/396AI, Fall 2025

Lecturer: Nadim Kobeissi Website: [Link]

Problem Set 1: Provable Security Foundations

Instructions: This problem set covers the foundations of provable security from topics 1.1a , 1.2b and
1.3c of the course. Submit your solutions as a neatly formatted PDF. You are encouraged to collaborate
with classmates in studying the material, but your submitted solutions must be your own work. For
proofs, clearly state your assumptions, steps, and conclusions.
a [Link]
b [Link]
c [Link]

1 Cryptographic Foundations (20 points)

1.1 Basic Concepts (10 points)
1. (3 points) Define the three primary security goals of cryptography in your own words and provide a
real-world example for each that wasn’t explicitly mentioned in the lectures.
2. (3 points) Explain Kerckhoff’s principle and why it remains fundamental to modern cryptography. Pro-
vide an example of a security system that violates this principle and describe the potential conse-
quences.
3. (4 points) Compare and contrast symmetric and asymmetric cryptography:
(a) Explain the fundamental difference in their key management approach.
(b) For each type, identify which mathematical or computational assumptions their security typi-
cally relies on.
(c) Describe a scenario where one would be clearly preferable to the other.

1.2 Perfect Secrecy (10 points)

1. (3 points) Consider a modified one-time pad where we use the bitwise AND (∧) operation instead of
XOR (⊕):
Enc(𝐾, 𝑀) = 𝐾 ∧ 𝑀 and Dec(𝐾, 𝐶) = ?
(a) Is this scheme correct? If yes, specify the decryption function. If not, explain why.
(b) Does this scheme provide perfect secrecy? Justify your answer.
2. (4 points) Consider the following variant of a one-time pad operating on decimal digits (0-9):
Enc(𝐾, 𝑀) = (𝐾 + 𝑀) (mod 10) and Dec(𝐾, 𝐶) = (𝐶 − 𝐾) (mod 10)
where 𝐾, 𝑀, 𝐶 ∈ {0, 1, 2, … , 9}.
(a) Prove that this scheme is correct.
(b) Prove that this scheme provides perfect secrecy, assuming 𝐾 is chosen uniformly at random.
3. (3 points) Consider a one-time pad where the key length is half the message length:
Enc(𝐾, 𝑀) = (𝐾 ⊕ 𝑀1 , 𝐾 ⊕ 𝑀2 ) where 𝑀 = (𝑀1 , 𝑀2 ) and |𝑀1 | = |𝑀2 | = |𝐾|.
Provide a specific attack that breaks the confidentiality of this scheme, showing clearly the informa-
tion an attacker can extract from the ciphertext.

CMPS 297AD/396AI, Fall 2025 Page 1 of 4

Applied Cryptography American University of Beirut

2 Provable Security (20 points)

2.1 Libraries and Indistinguishability (10 points)
1. (5 points) Consider the following libraries:

ℒ2
ℒ1
init():
init(): 𝑅 1 ↞ { 0, 1} 𝑛
𝐾 ↞ { 0, 1} 𝑛 ≊ 𝑅 2 ↞ { 0, 1} 𝑛

query(𝑀): query(𝑀):
return 𝐾 ⊕ 𝑀 if 𝑀 = 𝑅1 return 𝑅2
else return 𝑀 ⊕ 𝑅1 ⊕ 𝑅2

Are these libraries indistinguishable? Either prove they are indistinguishable or provide a distinguisher
program that can tell them apart with non-negligible probability.
2. (5 points) For each of the following pairs of libraries, state whether they are indistinguishable and
briefly justify your answer:

ℒB
ℒA

f(𝑥):
(a) f(𝑥): ≊
𝑦 ↞ { 0, 1} 𝑛
𝑦 ↞ { 0, 1} 𝑛
𝑧 ↞ { 0, 1} 𝑛
return 𝑦
return 𝑦

ℒC
ℒD
𝐾 ↞ { 0, 1} 𝑛

enc(𝑀):
enc(𝑀): 𝐶 ↞ { 0, 1} 𝑛
(b) 𝐶 ≔𝐾⊕𝑀 ≊ return 𝐶
return 𝐶
dec(𝐶):
dec(𝐶): 𝑀 ↞ { 0, 1} 𝑛
𝑀 ≔𝐾⊕𝐶 return 𝑀
return 𝑀

2.2 Security Proofs (10 points)

1. (5 points) Let Σ = (KeyGen, Enc, Dec) be a secure one-time pad encryption scheme for messages in
′ ′ ′
{0, 1}𝑛 . Consider the following modified scheme Σ′ = (KeyGen , Enc , Dec ):
′
KeyGen () = 𝐾 ↞ KeyGen()
′
Enc (𝐾, 𝑀) = (𝐶1 , 𝐶2 ) where 𝐶1 ↞ Enc(𝐾, 𝑀) and 𝐶2 ↞ Enc(𝐾, 𝑀 ⊕ 1𝑛 )
′
Dec (𝐾, (𝐶1 , 𝐶2 )) = Dec(𝐾, 𝐶1 )

Determine whether Σ′ is a secure encryption scheme. If it is secure, provide a formal proof. If it is not
secure, describe a concrete attack that breaks its confidentiality and explain why the attack works.

CMPS 297AD/396AI, Fall 2025 Page 2 of 4

Applied Cryptography American University of Beirut

2. (5 points) Consider the following game between a challenger and an adversary 𝒜:

(a) The adversary selects two messages 𝑀0 and 𝑀1 of the same length.
(b) The challenger selects a uniform random bit 𝑏 ↞ {0, 1} and a uniform random key 𝐾 ↞ {0, 1}𝑛 .
(c) The challenger computes 𝐶 = 𝐾 ⊕ 𝑀𝑏 and gives 𝐶 to the adversary.
(d) The adversary outputs a bit 𝑏′ as its guess for 𝑏.
Prove that for any adversary 𝒜, the probability that 𝑏′ = 𝑏 is exactly 1/2. Explain what this result tells
us about the security of the one-time pad.

3 Computational Cryptography (30 points)

3.1 Computational Security Concepts (15 points)
1. (5 points) Explain why computational security is important in practice despite the existence of information-
theoretic security. Discuss the limitations of both approaches.
2. (5 points) Consider a brute-force attack on AES-128:
(a) Using the monetary cost table provided in the lecture, estimate how much it would cost to try
all possible keys.
(b) Discuss whether the computational approach to security makes sense in light of this cost.
3. (5 points) The “birthday paradox” is crucial for understanding many cryptographic attacks. If a hash
function produces outputs of length 𝑛 bits:
(a) Approximately how many random inputs would you need to hash before finding a collision with
50% probability?
(b) How many bits of output would a hash function need to be reasonably secure against birthday
attacks for the next decade?

3.2 Distinguishability (15 points)

1. (7 points) Consider the following two libraries:

ℒ1 ℒ2

sample(): sample():
≊
𝑋 ↞ { 0, 1} 𝑛 𝑌 ↞ { 0, 1} 𝑛
𝑌 ≔ 𝑋 ⊕ 1𝑛 𝑋 ≔ 𝑌 ⊕ 1𝑛
return (𝑋, 𝑌 ) return (𝑋, 𝑌 )

Use the hybrid proof technique to show these libraries are indistinguishable. Clearly describe each
intermediate hybrid library.
2. (8 points) Consider a protocol where Alice wants to send encrypted messages to Bob. They use the
following scheme:

ℒreal
ℒideal
𝐾 ↞ { 0, 1} 𝑛

encrypt(𝑀): encrypt(𝑀):
≊
𝑅 ↞ { 0, 1} 𝑛 𝐶1 ↞ {0, 1}𝑛
𝐶1 ≔ 𝑅 𝐶2 ↞ {0, 1}𝑛
𝐶2 ≔ 𝐾 ⊕ 𝑅 ⊕ 𝑀 return (𝐶1 , 𝐶2 )
return (𝐶1 , 𝐶2 )

CMPS 297AD/396AI, Fall 2025 Page 3 of 4

Applied Cryptography American University of Beirut

(a) The above libraries are not actually indistinguishable! Construct a distinguisher.
(b) Propose a minimal modification to make the above “real” library secure and explain why your
modification works.

4 Application of Cryptographic Principles (30 points)

1. (15 points) One-Time Pad in the Real World
A startup claims to have developed a “quantum-resistant ultra-secure messaging system” based on
the one-time pad. They provide the following details:

• The system uses a hardware random number generator to produce one-time pads.
• Each user receives a 1TB USB drive containing pre-generated pad data during account registra-
tion.
• When sending a message, the app encrypts it with a portion of the pad, marks that portion as
used, and sends the ciphertext.
• When the user has used 80% of their pad, the app automatically requests a new USB drive.

Provide a detailed critique of this system:

(a) Identify at least three practical problems with this implementation.
(b) Explain how each problem compromises security or usability.
(c) Suggest improvements to address each issue while maintaining the theoretical security of OTP.
2. (15 points) Symmetric Encryption Protocol Analysis
A software company is implementing a secure communication protocol for their instant messaging
application. They propose the following scheme:

• Each user generates a random 128-bit key 𝐾 during account creation.

• To send a message 𝑀, the sender computes 𝐶 = 𝐾 ⊕ 𝑀 and transmits 𝐶.
• When two users want to communicate, they first exchange their keys through a “top secret chan-
nel” established by the company’s server.
• The company claims their protocol is “as secure as one-time pad” because they use the XOR op-
eration.

Address the following aspects of this system:

(a) Using the provable security framework discussed in class, analyze whether this scheme provides
the confidentiality properties claimed by the company.
(b) Identify at least three major security vulnerabilities in the described approach.
(c) The company is considering having users generate new keys daily instead of just once. Explain
whether this modification would address the vulnerabilities you identified.
(d) Propose a modified protocol that would significantly improve security while still using only sym-
metric cryptography concepts covered in class so far. Justify your choices using the security prin-
ciples we’ve discussed.

Bonus Challenge (20 extra points): The discrete logarithm problem is fundamental to many crypto-
graphic systems. Consider a cyclic group 𝐺 of prime order 𝑝 with generator 𝑔. The discrete logarithm
problem is: given ℎ ∈ 𝐺, find 𝑥 such that 𝑔𝑥 = ℎ.
Imagine a scenario where the discrete logarithm problem could be solved efficiently. Select one mod-
ern cryptographic protocol that relies on the hardness of this problem, and analyze:

1. The specific impact on the protocol’s security.

2. How the protocol would need to be modified to remain secure.
3. Whether any alternative mathematical problems could serve as suitable replacements.

CMPS 297AD/396AI, Fall 2025 Page 4 of 4