Lecture 13: Pseudo Random Functions and Variants

Overview

• Introduction to pseudo random functions (PRF) as building blocks in symmetric key cryptography.
• Discussion on variants of PRFs: pseudo random permutations (PRP) and strong pseudo random permutations (SPRP).
• Construction of pseudo random generators (PRG) from PRFs.

Pseudo Random Functions (PRF)

• Definition: A PRF is a deterministic algorithm with two inputs: a random key and an input block.
  • Key (K): Uniformly random, size n (security parameter).
  • Input (x): Block size l bits.
  • Output (y): Size Big L bits.

Usage of PRF

• PRFs are used in cryptographic primitives where:
  • A random key is generated and shared (not known to the attacker).
  • Key remains fixed during the session.
  • The PRF acts as a keyed function f_k producing Big L bit outputs from l bit inputs.

Security Properties

• Requirement: The output of a keyed function should resemble a truly random function if the key is unknown.
• Indistinguishability: No polynomial-time algorithm should distinguish between the output of a PRF and a truly random function.
• Key Concept: Each entry in a truly random function's table is independent; thus, different inputs yield independent outputs.

Indistinguishability Experiment

• Setup: The distinguisher queries the function at multiple inputs.
• Mechanism: The challenger randomly generates outputs either from a truly random function or a PRF:
  1. If coin toss is 0, outputs from a truly random function.
  2. If coin toss is 1, outputs from the keyed function.
• Goal: Distinguisher should not significantly identify which mechanism produced the outputs.

Distinguisher Advantage

• Defined as the probability the distinguisher can identify the origin of the samples.
• Should be bounded by half plus a negligible function.
• Equivalence: If distinguishing advantage is negligible, the function is a PRF.

Example of Non-PRF Construction

• XOR function: If f(x) = K XOR x, it fails as a PRF since outputs for different inputs are related, allowing a distinguisher to identify the function.

Pseudo Random Permutation (PRP)

• A PRP is a special type of PRF where the keyed function is a bijection.
• Security Property: Similar to PRF, but requires no polynomial-time distinguisher can distinguish it from a truly random bijection.
• Relationship:
  • If a PRF has an output size polynomially related to n, it acts as a PRP.
  • A PRP is a strong variant of a PRF.

Strong Pseudo Random Permutation (SPRP)

• A stronger version of PRP where the distinguisher has access to both the function and its inverse.
• Indistinguishability Condition: Same as PRP, but even harder to distinguish due to access to the inverse.

Construction of Pseudo Random Generator (PRG) from PRF

• Given a secure PRF, a PRG can be constructed:
  • Takes a key of size n and produces an output of size t * Big L bits.
  • Outputs are generated by invoking the PRF on known inputs (1 to T).
• Proof of Security: If a distinguisher can distinguish outputs of PRG from a truly random generator, it implies a distinguishable PRF, leading to a contradiction of security assumptions.

Summary

• Discussed PRFs, PRPs, SPRPs, and the construction of PRGs from PRFs.
• Emphasized the security definitions and relationships among these cryptographic primitives.