Pseudorandomness and Computationally Secure Encryption

Introduction

• Topic: Pseudorandomness and computationally secure encryption

• Presenter: Ming-Deh Huang

• Affiliation: Computer Science Department, University of Southern California

• Date: January 25, 2026

• Course: Lectures on CSCI 556 Introduction to Cryptography

Subunits

Unit 2.A: Secure encryption in the idealized setting

Unit 2.1: Pseudorandom generators and Pseudorandom functions

• Suggested supplemental reading:

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

Importance of Randomness in Cryptography

• Definition: Randomness is an essential resource in both cryptography and computation.

Application of Randomness

• In a one-time pad:

  • Requires n random bits to encrypt (and hide) a message of n bits.

  • The encryption process can be expressed as:

    • $c = m ⊕ k$

  • Where:

    • $m ∈ {0, 1}^n$ (message)

    • $k ∈_R {0, 1}^n$ (key, uniformly randomly chosen from all n-bit strings)

  • Explanation: The notation ${0, 1}^n$ represents the set of all n-bit strings. For instance, ${0, 1}^2 = {00, 01, 10, 11}$.

Efficiency of Randomness Usage

• The question arises: Can we use randomness more efficiently?

• Is it possible to "stretch" a random seed (of n bits) into a longer random-looking bit string (of $\gamma(n)$-length, with \gamma(n) > n )?

Pseudorandomness

Pseudorandom Generators

• Definition: A pseudorandom generator is an efficient function that "stretches" a random seed into a longer random-looking bit string:

  • The expression is:

  • r \overset{G}{\longrightarrow} G(r), |r| << |G(r)|

  • Request:

  • The output of G(r) is computationally/practically indistinguishable from a true random bit string of the same length.

• Application: Transform the one-time pad:

  • Instead of $E_k (m) = k ⊕ m$,

    • Use $E_k (m) = G(k) ⊕ m$

  • This results in a shorter key: $|k|$ can be much smaller than $|m|$.

Computational Indistinguishability

• Pseudorandom generator: defined as a function that produces outputs indistinguishable from true random bit strings for every polynomial-time algorithm.

• Key Aspect: No polynomial-time algorithm can distinguish the output of G from true random bit strings.

Construction of Pseudorandom Generators

• Family of Functions:

  • Consider a family of functions $G_n$ parameterized by $n$, where:

    • $G_n: {0, 1}^n \to {0, 1}^{\gamma(n)}$

  • This is efficient to compute (in $n^{O(1)}$ time).

Stretching Definition

• Definition of Stretching: \gamma(n) >> n , for instance, $\gamma(n) = 10n$ or $n^2$ (noting that $\gamma(n) = n^{O(1)}$).

• Probability Condition: For a polynomial-time decision algorithm $P$, the condition verifies:

  • |Pr{r \in {0, 1}^{\gamma(n)}}[P(r) = 1] - Pr{s \in {0, 1}^n}[P(G(s)) = 1]| < \frac{1}{n^c}

  • For sufficiently large $n$, for all c > 0 .

Remarks on Polynomial-Time Decision Algorithm

• Context: This algorithm models all possible randomness tests efficiently.

• Experimental Design: The distinguisher $P$ receives the output of the generator without knowledge of the input in one instance and a random bit string of equal length in another.

• Sufficiency of Tests: Traditional statistical randomness tests include:

  1. The last bit is 0 with probability $rac{1}{2}$.

  2. The XOR of all bits is 0 with probability $rac{1}{2}$.

• Under these conditions, for example, the bit string generated by $G(x) = x || y$, where $y = x \mod 2$ can appear statistically random, but it is not computationally pseudorandom.

Further Contextual Notes

• Computational Indistinguishability: The output is computationally indistinguishable from random bit strings under the condition that the generator function $G$ is known, and $x$ is secret and uniformly random.

Application to Encryption

Encryption Process

• Generative Process: Suppose $G_n: {0,1}^n \to {0,1}^{\gamma(n)}$ is a pseudorandom generator, with $\gamma(n) = 10n$ for the example.

• Encrypting a message $m$ of N-bits requires:

  • Choose a uniform random n-bit string $r$ where $\gamma(n) = N$.

  • For example, if $N = 1000$ then $n = 100$.

  • Perform encryption: $c \leftarrow G(r) ⊕ m$

  • Here, $r$ serves as the secret key.

Pseudorandomness Usage with Keyed Cryptography

• Example: If $G$ is public, then all aspects of the encryption function are known except for the key.

Construction and Security of Pseudorandom Functions

Theoretical Framework

• Function Definition: The family {$f_k$} indexed by keys $k$, such that:

  • $f_k: {0, 1}^{|k|} \to {0, 1}^{|k|}$ for every $k$.

  • Pseudorandom Family Condition: For every polynomial-time oracle Turing machine (an algorithm with an oracle) $A$,

  • There exists a negligible function $\epsilon : N \to [0, 1]$ so that:

  • |Pr{k \in R{0,1}^n}[A{fk(·)}(1^n) = 1] - Pr{f \in R {0,1}n}[A_{f(·)}(1^n) = 1]| < \epsilon(n) for every $n$.

Oracle Function Explanation

• Setup: The algorithm $A$ can query the oracle $f$ for $n^{O(1)}$ inputs and receive outputs.

• Maintains efficiency in $n^{O(1)}$ time, terminating with an output of either 0 or 1.

• Behavior: In this setting, $A$ can ask to see polynomially many $f(x)$ outputs before deciding a binary result.

Theorem on Pseudorandom Functions

Existence Condition

• Statement: If a pseudorandom generator exists with stretch $\gamma(n) = 2n$, then a pseudorandom function family exists.

  • For $x ∈ {0, 1}^n$, denote:

  • $G<em>0(x)$ as the first n bits and $G</em>1(x)$ as the last n bits of $G(x)$.

  • Define: $f<em>k(x) = G</em>{k<em>n}(G</em>{k<em>{n-1}}(\ldots(G</em>{k_1}(x))\ldots))$.

Vulnerability of Encryption Schemes

Vulnerability Under Chosen-Plaintext Attack (CPA)

• Discussion: The encryption scheme defined as $G(r) ⊕ m$ is vulnerable under CPA due to the reduced key length $r$.

  • If an adversary acquires the ciphertext $c$, the relation $G(r) = m ⊕ c$ reveals $G(r)$.

  • CPA Definition: Given ciphertext, the adversary queries the encryption of polynomially many plaintext messages $m$ using key $k$.

• Notably, a deterministic encryption scheme is especially vulnerable, particularly if only two candidate messages are available.

Historical Case Study

Midway Island Attack (World War II)

• Historical Context: May 1942, during the Pacific War.

  • The US Navy intercepted Japanese communication containing the ciphertext fragment "AF”.

  • They speculated that "AF" referred to "Midway Island", contrary to Washington’s initial disbelief.

  • To confirm their suspicion, they surreptitiously asked Midway troops to send a plaintext indicating fresh water supply levels, leading to strategic military advantage.

Conclusion

Final Remarks on Encryption Security

• To establish the security of newer encryption schemes:

  • Need to correlate security to the strength of pseudorandom generators.

  • Semantic security asserts that if a ciphertext does not reveal bits of a message with better than $rac{1}{2}$ probability, it aligns with confidentiality principles.

Summary of Findings

• The one-time pad and its characteristics, including vulnerabilities when reusing keys.

• The introduction of probabilistic encryption methods which refresh randomness through new keys for every encryption operation.

• The persistence of chosen-plaintext attacks and their implications for function templates in encryption practices.

• The dual principles of empirical verification from historical contexts and detailed algorithmic definitions to provide a grounded understanding of both practical cryptography and theoretical underpinnings in the digital age.