Study Notes on Secure Encryption in Idealized and Practical Settings

Secure Encryption in the Idealized and Practical Settings

Overview

• Presenter:

  • Ming-Deh Huang

  • Computer Science Department, University of Southern California

• Course:

  • CSCI 556: Introduction to Cryptography

• Date:

  • February 3, 2026

Supplemental Reading

• Chapters referenced:

  • Chapter 3 and 6 A and B from "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, published by Chapman & Hall/CRC.

Key Theorems and Concepts

Theorem on Ciphertext and Message Distribution

• Statement: If the ciphertext distribution is the same regardless of the message distribution, then the ciphertext (c) and the plaintext (message m) are independent random variables.

• Example: In a one-time pad encryption, the ciphertext and the message are independent random variables.

Theorem on Semantic Security

• Context: A is a probabilistic polynomial-time algorithm trying to learn a property about plaintext m from ciphertext c.

• Definitions:

  • Output z is a random variable that takes values in {0, 1} depending on c and a random bit string α used by A.

  • If c and m are independent and the plaintext distribution is such that the probability that the plaintext possesses a property is 1/2, then the success probability of A in learning the property is also 1/2.

• Example: The one-time pad encryption is semantically secure based on this theorem.

Security Model: EAV Security

• General Concept: Security modeled via a distinguishing game.

• Components:

  • A key k chosen from a keyspace K d 𝑅 K (randomly chosen and fixed throughout the game, hidden from the adversary).

  • Only two messages of interest m0 and m1 selected by adversary A.

  • A random bit b chosen from {0, 1} (hidden from A) to determine which message to encrypt.

  • The ciphertext c generated from the encryption of the selected message.

  • A outputs b' ∈ {0, 1} after a polynomial period of time and wins if b = b'.

Question: Message Distribution in EAV Experiment

• Inquiry: What is the distribution of messages in this experimental setup?

Theorem on Perfect Secrecy

• Statement: If the ciphertext c is completely independent of the plaintext, then in the EAV game, the success probability of any adversary A is 1/2.

• Proof Approach:

  1. Apply the semantic security theorem to A.

  2. Let χ(m) = i if m = mi; with Pr[mi] = 1/2 for i ∈ {0, 1}.

• Corollary: The one-time pad is demonstrated to be EAV secure under this condition.

Insecurity of One-Time Pad for Multiple Encryptions

• Observation: When using the same key for multiple encryptions:

  • Given:

  • $c<em>1 = m</em>1 \bigoplus r$

  • $c<em>2 = m</em>2 \bigoplus r$

  • Therefore:

  • $c<em>1 \bigoplus c</em>2 = m<em>1 \bigoplus m</em>2$

Proposal for Improvement in Idealized Settings

• Need: A fresh random r for every independent encryption to maintain security.

• Functionality:

  • Utilize a random n-bit-to-n-bit function f: {0, 1}n → {0, 1}n.

• Encryption Process:

  • To encrypt x ∈ {0, 1}n:

  • Generate r ∈R {0, 1}n.

  • Produce ciphertext: c d (r, f(r) igoplus x).

• Type of Encryption: Probabilistic encryption.

Key Query Considerations

• Key Specification: Defined as f ∈ Fun.

• Key Length: For a random function producing n-bits, the key has a length of magnitude $n2^n$.

Algorithm with Oracle Function

• Description:

  • An algorithm A can query an oracle function f with $N imes O(1)$ many x ∈ {0, 1}n (with a max run time of $N imes O(1)$) to get values of f(x).

  • A outputs either 0 or 1 upon termination.

Multiple Encryption and Security Analysis

• Context: EAV security in case of multiple encryptions where database consists of sets of chosen messages denoted as m' b.

• Procedures:

  • Choose a bit b ∈R {0, 1} and encrypt m' b (hidden from adversary).

  • Output b' based on polynomial-time play and determine win conditions.

• Questions Raised: Identifying message distributions in EAV multiple encryption experiments.

CPA Security Considerations

• Description: A allows polynomial (n^O(1)) number of encryption queries.

• Observation: The one-time pad can produce deterministic outputs c1 = m1 ⊕ k under a single query, leading to concerns over CPA insecurity.

• Claim: All deterministic encryptions are CPA-insecure.

Security Claims Based on Encryption with Random Functions

• Observations: If using functions derived from pseudorandom generators, successful adversaries against functions G or pseudorandom function F indicate vulnerabilities in the system.

Comparison of Distinguisher Outcomes

• Concept: A distinguisher's role is to distinctly identify if functions are pseudorandom or regular based on their structured measurements.

• Contrast: Between general outcomes based on pseudorandom distributions versus those derived from nonrandom structures, allowing insights into probabilities of guessing success.

Block Ciphers

• Definition: An efficient keyed permutation:

  • Formatted as: $F: {0, 1}^n imes {0, 1}^l o {0, 1}^l$ where:

  • $F_k(x) = F(k, x)$ signifies a bijection that is computable effciently.

• Ideal: The pseudorandom permutation standard for real-world applications leads to ciphers such as DES and AES being utilized.

Question on EAV-Security of Encryption Schemes

1. Encrypt long messages M into blocks and apply functions such as F(k, mi) ensuring independence of blocks.

2. Consider randomization through established versions, choosing r and proceeding with encryption effectively.

Evaluation of Security Claims

• Determining if the encryption schemes hold up to EAV standards:

  • Highlight distinctions between randomized and deterministic efforts providing security or otherwise.

Conclusion

• Lemma on Uniform Distribution: Under ideal conditions, functions that yield distinct entries maintain uniform distributions conducive to EAV standards. Therefore ensuring independence across inputs enhances security robustness.