Key Recovery via Decryption Failure Oracles

This direction is split into other directions: decryption failure probability. Its last version stays readable and citable here.

Version 1 of 135 papers61 conceptsfrozen 2026-10-04

In classical cryptography, we often assume that decryption is a perfect, deterministic process: if you have the right key, you get the right message. However, in the emerging world of Post-Quantum Cryptography (PQC)—specifically lattice-based and code-based schemes—this assumption is frequently violated. To achieve high performance, these schemes allow for a tiny, non-zero probability of decryption failure.

While a failure rate of $2^{-128}$ might seem like a mere reliability nuisance, researchers have shown it is actually a profound security vulnerability. A decryption failure is not just a "glitch"; it is a leakage of information about the secret key.

The Geometry of a Failure

To understand why failures leak information, we must look at how modern schemes like BIKE or FrodoPKE work. These systems rely on adding "noise" to data. Decryption is essentially a process of removing that noise. If the noise is too "large" or "unlucky" in its orientation relative to the secret key, the decoder fails to recover the original message.

As Hyeongmin Choe, Damien Stehlé, and their colleagues demonstrate in Attacks Against the INDCPA-D Security of Exact FHE Schemes, a failure occurs precisely when the noise crosses a specific geometric boundary defined by the secret key. By repeatedly sending ciphertexts and observing whether they succeed or fail—treating the decryption process as a "failure oracle"—an attacker can map out this boundary and eventually reconstruct the secret key itself.

From Reliability to Reaction Attacks

This class of exploit is known as a reaction attack. The attacker doesn't need to see the decrypted plaintext; they only need to know if decryption happened correctly.

In code-based systems like BIKE, Nir Drucker, Shay Gueron, and Dusan Kostic have highlighted that these failures can leak the structure of the underlying parity-check equations. In On constant-time QC-MDPC decoding with negligible failure rate, they argue that for a scheme to be secure against active adversaries (IND-CCA security), the failure rate must be driven down to "negligible" levels—often as low as $2^{-128}$—to ensure an attacker cannot collect enough failure data within a human lifetime.

The Message Independence Requirement

A subtle but critical requirement for security is that these failures must be message-agnostic. If a failure is more likely to happen for certain messages than others, the attacker gains an even more powerful lever.

Nir Drucker and Edoardo Persichetti explored this in their work on the Fujisaki-Okamoto (FO) transformation. The FO transformation is the mathematical "glue" used to turn a basic encryption scheme into a secure key encapsulation mechanism. For this glue to hold, the probability of failure must depend only on the keys and the random noise, not the secret message itself. If this independence is violated, the security proofs crumble, as the failure becomes a side-channel for the message content.

Eliminating the Oracle

There are two primary schools of thought on how to solve the decryption failure problem:

  1. Statistical Suppression: This approach, favored by the NIST PQC finalists, involves using sophisticated decoders and larger parameters to push the failure rate so low that it is statistically impossible to trigger. Yu Yu and Kang Yang have worked on tighter security proofs to quantify exactly how low this rate needs to be to maintain security in the face of average-case decryption errors.
  2. Deterministic Correctness: Some researchers argue that the only way to be truly safe is to eliminate failures entirely. Dongxi Liu and Surya Nepal proposed Compact-LWE, which uses secret scaling factors and specific modular arithmetic to ensure 100% decryption success. By making the scheme deterministic, they remove the failure oracle entirely, which is particularly vital for IoT devices where retransmissions are costly.

The shift from "textbook" perfect decryption to "probabilistic" PQC decryption has turned what was once a simple functional requirement into a primary security frontier. As Shanxiang Lyu and Cong Ling note in their work on lattice codes, the challenge for the next generation of cryptography is balancing the efficiency of these noisy channels with the absolute necessity of closing the failure-based side channel.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_key_recovery_via_decryption_failure_orac_8914e209,
  title = {Key Recovery via Decryption Failure Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/key-recovery-via-decryption-failure-oracles/rdr_8914e2093bbb49e999677451c12ab918},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_key_recovery_via_decryption_failure_orac_8914e209_v1,
  title = {Key Recovery via Decryption Failure Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/key-recovery-via-decryption-failure-oracles/rdr_8914e2093bbb49e999677451c12ab918/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}