The Security Implications of Cryptographic Decryption Failures

36 concepts24 papers1 proposal

Traditional public-key cryptography, such as RSA, is designed to be perfectly deterministic: if a message is encrypted correctly, it will always decrypt perfectly. However, next-generation post-quantum cryptography (PQC)—specifically lattice-based schemes like Ring-Learning With Errors (RLWE) and code-based schemes like Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC)—operates under a fundamentally different paradigm. These primitives treat encryption as a noisy communication channel.

To obscure the secret key from eavesdroppers, these algorithms intentionally inject a small amount of mathematical noise into the ciphertext. During decryption, the legitimate receiver uses their secret key to filter out this noise. However, because the noise is generated probabilistically, there remains a tiny, non-zero probability that the noise vectors align in a worst-case configuration, exceeding the error-correction capacity of the underlying code. When this happens, a validly encrypted ciphertext fails to decrypt. As Georg Maringer et al. demonstrate in Information- and Coding-Theoretic Analysis of the RLWE/MLWE Channel, this Decryption Failure Rate (DFR) acts as a critical bottleneck, forcing a direct trade-off between a scheme's data transmission efficiency and its concrete security level.

Why Failures Leak Secrets: The Reaction Attack

A rare decryption failure might seem like a minor reliability inconvenience, but in the presence of an active adversary, it represents a catastrophic security vulnerability. The danger stems from a binary feedback loop: when a decryption failure occurs, the system typically outputs a detectable error state or behaves differently than it would during a successful decryption.

Imagine the secret key as a geometric boundary in a high-dimensional space; any ciphertext containing noise that falls inside this boundary decrypts successfully, while noise falling outside causes a failure. An attacker can exploit this by mounting a reaction attack. By crafting specific, adversarial ciphertexts with precisely calibrated error vectors and submitting them to a decryption oracle, the attacker observes whether the system succeeds or fails.

Successful Decryption: Noise falls INSIDE the decoding boundary.
[ Ciphertext + Attacker Noise ] ----> ( Secret Key Boundary ) ----> Success (No Leak)

Decryption Failure: Noise falls OUTSIDE the decoding boundary.
[ Ciphertext + Attacker Noise ] ----> ( Secret Key Boundary ) --+--> Failure (Leaks Boundary Location!)
                                                                |
                                                                v
                                                     [ Attacker learns key geometry ]

If a chosen ciphertext fails to decrypt, it signals to the attacker that the combined noise (the attacker's injected noise plus the internal secret noise) has crossed the decoding threshold. By iteratively querying the oracle and tracking the failure boundary, the adversary can map out the exact geometry of the secret key.

This vulnerability is a shared characteristic across diverse post-quantum frameworks. As Nir Drucker et al. note in A toolbox for software optimization of QC-MDPC code-based cryptosystems, the decoding failure rate in code-based systems directly leaks structural information about the private key during chosen-ciphertext attacks. Similarly, Julian Renner et al. highlight in On a Rank-Metric Code-Based Cryptosystem with Small Key Size that minimizing or strictly bounding these failure rates is an absolute prerequisite for side-channel resistance. The core flaw is architectural: as Kimoon Kim et al. observe in Safety Analysis of Various Padding Techniques on Padding Oracle Attack, the mere existence of a detectable invalid state provides the fundamental feedback loop necessary for iterative recovery attacks.

The Threat of Message-Dependent Failures

The security risk intensifies if the decryption failure probability is message-dependent. In an ideal probabilistic cryptosystem, the chance of a decryption failure should be uniformly distributed across the entire message space. If the failure rate varies depending on the specific message being encrypted, the system leaks information not just about the key, but about the plaintext itself.

In On the Applicability of the Fujisaki-Okamoto Transformation to the BIKE KEM, Nir Drucker et al. dissect this exact vulnerability. Cryptographers routinely use the Fujisaki-Okamoto (FO) transformation to convert weakly secure Public Key Encryption (PKE) schemes into highly secure Key Encapsulation Mechanisms (KEMs) capable of resisting chosen-ciphertext attacks (IND-CCA security). However, standard FO security proofs rely on the assumption that decryption failures occur independently of the underlying message.

If an encryption scheme suffers from message-dependent failures, an adversary can intentionally select or identify plaintexts that exhibit higher failure rates. By observing which ciphertexts trigger failures, the attacker can deduce properties of the encrypted plaintext or accelerate key extraction. To counter this, the authors established a formal framework to reduce average-case decoding failure rates to worst-case correctness bounds, proving that establishing strict message-independence is vital for validating post-quantum security claims.

Pushing Failures to Negligibility

To secure these systems against active adversaries, engineers and theorists employ two primary strategies: suppressing the failure rate to a mathematically negligible threshold, or eliminating it entirely through deterministic design.

Advanced Coding and Constant-Time Decoders

The most common mitigation is to engineer the error-correction system so that the DFR drops below a negligible threshold (typically $2^{-128}$), meaning a failure is statistically impossible to observe within the lifetime of the universe.

To achieve this without bloated ciphertext sizes, researchers replace simple modulation with advanced coding theory. For example, Shanxiang Lyu et al. introduce sophisticated Lattice Codes for Lattice-Based PKE, optimizing linear labeling functions to drastically reduce failure rates while maintaining compact ciphertexts.

In code-based cryptography, the decoder implementation itself can introduce vulnerabilities. If a decoder takes a variable amount of time to resolve errors, it leaks side-channel information. To solve this, Nir Drucker et al. demonstrate in On constant-time QC-MDPC decoding with negligible failure rate that constant-time variants of iterative decoders (such as the Black-Gray decoder) can successfully eliminate timing channels while provably suppressing the decoding failure rate to the required $2^{-128}$ bound.

Deterministic Decryption

The alternative strategy is the total elimination of failure probabilities. In Repairing the Faure-Loidreau Public-Key Cryptosystem, Antonia Wachter-Zeh et al. construct a repaired rank-metric cryptosystem that provides completely deterministic decryption. By restructuring the key generation and error-construction parameters, the authors ensure that a legitimate receiver can always map the ciphertext back to the plaintext with absolute certainty. This completely removes the reaction attack surface, simplifying protocol integration by avoiding the complex security proofs required by probabilistic alternatives.

Induced Failures: Faults and Physical Degradation

Even when a cryptographic primitive is mathematically designed to have a negligible or zero decryption failure rate, physical realities can allow an attacker to force failures into the system.

Fault-Injection Attacks

An adversary with physical access to a device can use lasers, electromagnetic pulses, or voltage glitches to induce transient errors during computation. As Keita Xagawa et al. demonstrate in Fault-Injection Attacks Against NIST's Post-Quantum Cryptography Round 3 KEM Candidates, a single instruction-skipping fault can bypass the critical equality tests executed during KEM decapsulation. By forcing the system to skip these verification checks, the adversary tricks the device into processing corrupted ciphertexts, exposing intermediate values that lead to full key recovery.

Similarly, Fan Terry Zhang et al. show in Efficient Persistent Fault Analysis with Small Number of Chosen Plaintexts that injecting persistent faults into a device's lookup tables creates logical corruptions. This causes certain operations to yield "impossible" output values, allowing attackers to exploit ciphertext collisions and bypass standard algorithmic countermeasures like Boolean masking.

Exploiting Error Correction for Key Recovery

When physical degradation occurs naturally—such as data remanence decay in frozen RAM chips—the error-correction mechanisms designed to protect data can instead be leveraged by attackers to extract secrets. In Recovering AES Keys with a Deep Cold Boot Attack, Itamar Zimerman et al. demonstrate that combining deep learning architectures with logical SAT solvers allows attackers to reconstruct cryptographic keys from highly corrupted states.

By training a neural network to interpret the "bursty" decay patterns of physical memory, the system can correct noisy bit-flips even when more than 70% of the memory bits have degraded to a ground state. This highlights a recurring theme in modern hardware security: whether a decryption failure is caused by inherent mathematical noise, adversarial fault injection, or physical hardware decay, the resulting error patterns provide a powerful window into the underlying secret state.

Key Foundational Work

Safety Analysis of Various Padding Techniques on Padding Oracle Attack (2015) — contributed 1 concept elements to this direction.
Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes (2006) — 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_decryption_failure_probability_33580e84,
  title = {decryption failure probability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decryption-failure-probability/rdr_33580e8459e944a5a92577ee03ae8271},
  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_decryption_failure_probability_33580e84_v1,
  title = {decryption failure probability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decryption-failure-probability/rdr_33580e8459e944a5a92577ee03ae8271/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake