NoteVerse

Random Oracle Model and Authenticated Encryption. Generic Constructions of Authenticated Encryption Schemes

Comprehensive study notes, diagrams, and exam preparation for Random Oracle Model and Authenticated Encryption. Generic Constructions of Authenticated Encryption Schemes.

Random Oracle Model and Authenticated Encryption. Generic Constructions of Authenticated Encryption Schemes

Definition

Random Oracle Model (ROM):
A security model in which a hash function is assumed to behave like a truly random function accessible to all parties through an oracle. Every input gives a uniformly random output, and the same input always returns the same output. This idealization is used to prove security properties of cryptographic constructions.

Authenticated Encryption (AE):
A symmetric encryption scheme that simultaneously provides:

Confidentiality

  • : the plaintext is hidden from attackers.

Integrity / Authenticity

  • : any modification of the ciphertext is detected and rejected.

Generic Construction of AE:
A standard method of building authenticated encryption from simpler primitives, usually by combining:

  • an encryption algorithm,
  • a message authentication code (MAC) or hash-based authentication,
  • and sometimes a random oracle or hash-based derivation.

A secure AE scheme typically ensures that adversaries cannot distinguish encryptions of chosen messages and cannot forge valid ciphertexts, even after seeing many encrypted messages.

Main Content

1. Random Oracle Model

Idealized hash-function assumption

In the ROM, a hash function is replaced by a theoretical oracle that produces random-looking outputs. This allows cryptographers to analyze schemes under a powerful abstraction. For example, if a construction uses a hash function to derive encryption keys or authentication tags, the ROM assumes those values behave as if generated randomly.

Why it matters in security proofs

The ROM often enables proofs of security that are much simpler than standard-model proofs. Many generic AE schemes rely on hash functions to bind ciphertexts, associated data, and keys together. By treating the hash as random, the proof can argue that attackers gain no useful structure from the outputs.

Example:
If a scheme computes a tag as H(key || nonce || ciphertext), the ROM models H as a random oracle. An attacker who changes the ciphertext cannot predict the new valid tag without querying the oracle on the exact modified input.

ASCII illustration for oracle access

Adversary ----query----> Random Oracle H
    ^                      |
    |----same input---------|
    |<---same random output--|

The important property is consistency: the same input always yields the same output, but the output is otherwise random.

2. Authenticated Encryption

Confidentiality plus integrity together

AE is designed to solve a weakness in plain encryption. Traditional encryption can hide messages, but it does not automatically prevent tampering. AE adds authentication so that decryption succeeds only if the ciphertext is authentic and unmodified.

Common AE security goals

A secure AE scheme should resist:

  • ciphertext-only attacks,
  • chosen-plaintext attacks,
  • chosen-ciphertext attacks,
  • forgery of valid ciphertexts,
  • misuse of unauthenticated associated data.

Example:
A secure messaging app uses AE so that if an attacker flips a bit in the encrypted message, the receiver’s decryption routine rejects it rather than outputting corrupted plaintext.

How AE is typically structured

  • A plaintext is encrypted with a secret key.
  • A tag or authentication code is computed over the ciphertext and possibly additional data.
  • The receiver verifies the tag before accepting the plaintext.

ASCII illustration for AE flow

Sender:   plaintext + key --> Encrypt --> ciphertext + tag
Receiver: ciphertext + tag --> Verify --> plaintext or reject

AE is crucial because it ensures that secrecy and authenticity are not treated as separate add-ons, but as a unified security goal.

3. Generic Constructions of Authenticated Encryption Schemes

Encrypt-then-MAC as a generic approach

One of the most important generic constructions is Encrypt-then-MAC (EtM). First, the message is encrypted, then a MAC is applied to the ciphertext. This approach is widely recommended because it gives strong security under standard assumptions when implemented correctly.

Other composition patterns and their security

Common approaches include:

  • MAC-then-Encrypt (MtE): authentication tag is computed on plaintext before encryption.
  • Encrypt-and-MAC (E&M): encryption and MAC are computed independently.
  • Encrypt-then-MAC (EtM): ciphertext is authenticated after encryption.

Among these, EtM is generally the best-known generic construction for AE because the tag protects the ciphertext directly, making tampering detectable before decryption.

Example of Encrypt-then-MAC

  1. Compute ciphertext: C = Enc_K1(M)
  2. Compute tag: T = MAC_K2(C)
  3. Send (C, T)

At the receiver:

  1. Verify T on C
  2. If valid, decrypt M = Dec_K1(C)
  3. Otherwise reject

Why this is strong:
An attacker cannot alter the ciphertext without also producing a valid tag, which should be infeasible if the MAC is secure.

ASCII illustration for Encrypt-then-MAC

Plaintext M
   |
   v
Encrypt with K1
   |
   v
Ciphertext C -----> MAC with K2 -----> Tag T
   |                                   |
   +------------- send (C, T) ---------+

Working / Process

1. Choose secure underlying primitives

Select an encryption scheme that provides confidentiality and a MAC or hash-based authenticator that provides unforgeability. In ROM-based settings, a hash function may also be used as a random oracle to derive keys, nonces, or tags.

2. Construct the authenticated encryption scheme

Use a secure composition method such as Encrypt-then-MAC. Encrypt the message first, then authenticate the ciphertext and any associated data. If associated data is needed, include it in the MAC input so that metadata is protected too.

3. Encrypt, transmit, verify, and decrypt

  • Sender encrypts the plaintext.
  • Sender computes the authentication tag.
  • Receiver verifies the tag before decryption.
  • If verification fails, the ciphertext is rejected.
  • If verification succeeds, the receiver safely decrypts the message.

Process example

Sender
M -> Enc -> C -> MAC -> T -> transmit (C, T)

Receiver
receive (C, T) -> verify T -> if valid, Dec(C) -> M
                           -> else reject

This process ensures that attackers cannot learn the plaintext or modify it undetected.

Advantages / Applications

Strong protection against active attacks

AE protects not just against eavesdropping but also against tampering, replay, and message forgery. This is essential in hostile network environments.

Widely used in real-world systems

AE is used in secure messaging, HTTPS/TLS, VPNs, disk encryption modes, wireless communication, and authenticated APIs. Generic constructions provide a foundation for building these systems securely.

Useful for modular cryptographic design

The ROM and generic AE constructions allow designers to combine separate primitives in a structured way. This helps in proving security properties and in understanding why a scheme is safe.

Summary

  • The Random Oracle Model treats a hash function like a perfectly random oracle for security analysis.
  • Authenticated Encryption combines confidentiality and integrity in one scheme.
  • Generic constructions, especially Encrypt-then-MAC, are a standard way to build secure AE schemes.

Important terms to remember: Random Oracle Model, Authenticated Encryption, confidentiality, integrity, MAC, Encrypt-then-MAC, ciphertext, tag, associated data

← Prev: Applications of Hash Functions
Next: Key-exchange Problem →