Cryptographic Protocols Without Random Oracles

15 concepts14 papers1 proposal

In theoretical cryptography, proving that a protocol is secure requires showing that any adversary capable of breaking the protocol can also be used to solve a notoriously difficult mathematical problem. For decades, cryptographers have relied on a powerful shortcut to construct these proofs: the Random Oracle Model (ROM).

In the ROM, we imagine that a cryptographic hash function is a perfectly random, black-box oracle. If you feed it an input, it spits out a truly random output. If an adversary queries the oracle with the same input later, it receives the same random output.

This abstraction is incredibly convenient for security proofs. Because the proof's author controls the simulated environment, they can "program" the oracle's responses. If the simulator knows what the adversary is querying, it can strategically embed a hard mathematical problem into the oracle's output, trapping the adversary into solving it.

However, random oracles do not exist in the real world. Real-world hash functions like SHA-256 or SHA-3 are deterministic, public algorithms with fixed mathematical structures. They possess algebraic properties that a sophisticated attacker might exploit. Consequently, a protocol proven secure in the idealized ROM might become vulnerable when deployed with a real hash function.

To bridge this gap, a major research direction focuses on designing protocols secure in the standard model—meaning their security proofs rely strictly on standard mathematical hardness assumptions without assuming the existence of an ideal hash function.

The Mechanics of Standard Model Proofs

Without a programmable random oracle to inject mathematical traps, how can a simulator prove security? The core intuition lies in shifting the algebraic complexity away from the hash function and directly into the protocol's public parameters, keys, or ciphertexts.

Consider Identity-Based Encryption (IBE), where a user's public key is simply an arbitrary string representing their identity (like an email address). In the ROM, a protocol can map this identity string to a usable mathematical group element by running it through the random oracle. In the standard model, this mapping must be handled algebraically without losing security.

Xavier Boyen achieved this breakthrough in Secure Identity Based Encryption Without Random Oracles. Instead of hashing an identity string to a random group element, the scheme structures the system's public parameters as a sequence of group elements. When an identity is evaluated, these elements are combined algebraically. This structure allows a security simulator to inject an instance of the Decisional Bilinear Diffie-Hellman (DBDH) problem directly into the public parameters. If an adversary manages to break the encryption for a specific identity, the algebraic interplay allows the simulator to extract the solution to the hard problem.

Eliminating Oracles in Signatures and Delegated Cryptography

The challenge of removing random oracles intensifies when protocols require advanced privacy or delegation features, such as group signatures or proxy re-signatures.

Group signatures allow a user to sign a message anonymously on behalf of a group, while a group manager retains the ability to reveal the signer's identity in case of disputes. Early efficient schemes relied heavily on random oracles to bind the identity components securely. To eliminate this reliance, Xiaohui Liang et al. designed a novel group signature scheme in Short Group Signature Without Random Oracles. By carefully structuring the algebraic credentials, the authors achieved full anonymity and traceability in the standard model while significantly reducing the size of public keys and signatures.

A similar evolution occurred in proxy re-signatures, where a semi-trusted proxy transforms a signature from one user into a signature from another without learning the underlying private keys. Early identity-based proxy re-signatures used random oracles to prevent adversaries from forging proxy keys. Jun Shao et al. bypassed this requirement in Proxy Re-signature Schemes Without Random Oracles, presenting the first identity-based proxy re-signature scheme secure in the standard model. This foundation was later expanded by Xiaodong Yang et al. in Revocable identity-based proxy re-signature against signing key exposure, which introduced user revocation mechanisms and server-aided verification under the standard Computational Diffie-Hellman (CDH) assumption.

This standard-model paradigm has also been vital for certificateless cryptography, which aims to eliminate the heavy management overhead of traditional digital certificates. For instance, Ji‐Jian Chin et al. introduced the first efficient certificateless identification scheme in the standard model in An Efficient and Provable Secure Certificateless Identification Scheme in the Standard Model. More recently, Fatemeh Rezaeibagha et al. developed a lightweight certificateless signature scheme for the Industrial Internet of Things (IIoT) in Fully Secure Lightweight Certificateless Signature Scheme for IIoT, proving its resistance to sophisticated "universal attacks" without relying on ideal hash assumptions.

Advanced Data Operations and Searchable Encryption

As cloud computing expanded, the need to perform computations on encrypted data without decrypting it brought new challenges to standard-model design. A prime example is Public Key Encryption with Equality Test (PKEET), which allows a cloud server to determine whether two different ciphertexts contain the same underlying plaintext.

In the random oracle model, equality testing is often achieved by hashing the plaintext and appending it to the ciphertext. In the standard model, this approach fails because an adversary could exploit the deterministic nature of real hash functions. To solve this, Jae Hong Seo et al. proposed the first generic framework for PKEET in the standard model in Public Key Encryption with Equality Test in the Standard Model. Rather than relying on hash outputs, their framework uses bilinear pairings to verify equality structurally. This concept was later extended to fine-grained access control by Yuzhao Cui et al. in Attribute-Based Equality Test Over Encrypted Data Without Random Oracles, allowing equality testing only if the tester's attributes satisfy a specific access policy.

Error-tolerant and broadcast systems have undergone a similar transition. Yanli Ren et al. introduced a "fuzzy" identity-based encryption scheme in New Fuzzy Identity-Based Encryption in the Standard Model that allows successful decryption even if the recipient's identity attributes do not perfectly match the encryption key, provided they are close enough. The authors later adapted these principles to multi-recipient systems in Fully Anonymous Identity-based Broadcast Encryption without Random Oracles, ensuring complete recipient anonymity under standard bilinear assumptions.

Hardness Assumptions as the Ultimate Anchor

To eliminate the random oracle, a protocol must anchor its security entirely to well-defined mathematical problems. Depending on the application's goals, these anchors vary across different mathematical domains:

By replacing the idealized abstraction of the random oracle with concrete, structured mathematical problems, this body of research ensures that when a protocol is deployed in the real world, its security guarantees remain fully intact.

Key Foundational Work

Short Group Signature without Random Oracles (2007) — contributed 1 concept elements to this direction.
Secure Identity Based Encryption Without Random Oracles (2004) — contributed 1 concept elements to this direction.
Proxy Re-Signature Schemes without Random Oracles (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_standard_model_security_d437658d,
  title = {standard model security},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/standard-model-security/rdr_d437658d1f1447b18b5722da3ea63783},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_standard_model_security_d437658d_v1,
  title = {standard model security},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/standard-model-security/rdr_d437658d1f1447b18b5722da3ea63783/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake