The Security Gap in Non-Uniform Data Distributions

This direction is merged into another direction: uniform source distribution assumption. Its last version stays readable and citable here.

Version 1 of 112 papers19 conceptsfrozen 2026-10-04

In theoretical cryptography, we often assume a "perfect" world where every secret—be it a password, an encryption key, or a database record—is chosen uniformly at random from a set of possibilities. This assumption is mathematically convenient: it allows researchers to prove security bounds using entropy and probability theory.

However, a growing body of research suggests that this "uniformity assumption" creates a dangerous gap between theory and practice. In reality, human-generated data and natural datasets are highly skewed, often following power laws like Zipf’s Law. When cryptographic protocols meet this non-uniform reality, the security guarantees often evaporate.

The Predictability of Human Choice

The most visible failure of the uniformity assumption is in password security. While a computer might choose a random string of characters, humans do not. Ding Wang and colleagues demonstrated in Zipf's Law in Passwords that user-generated passwords follow a power-law distribution. By analyzing 97 million leaked passwords, they showed that attackers have a massive advantage because users gravitate toward a predictable subset of the keyspace.

This predictability means that standard metrics like entropy significantly overestimate how hard a password is to crack. Even modern advice, such as using three random words, falls short because of human cognitive biases. Sirvan Almasi argues in Five Word Password Composition Policy that because humans don't pick words with uniform probability, we actually need five words to achieve the security level that experts originally intended for three.

Why Skewed Data Breaks Encryption

The problem extends beyond passwords into how we store and query encrypted data. Many efficient encrypted database schemes, such as Order-Revealing Encryption (ORE), are designed to allow sorting and range queries without decrypting the data. These schemes often come with proofs of security—but those proofs frequently assume the underlying data is uniformly distributed.

Paul Grubbs, Thomas Ristenpart, and their co-authors showed in Leakage-Abuse Attacks against Order-Revealing Encryption that when these schemes are applied to real-world, non-uniform data (like ZIP codes or surnames), they become vulnerable. An attacker with access to the encrypted database and a small amount of public auxiliary information can exploit the frequency and distribution of the data to recover nearly all the original plaintext.

As Murat Kantarcioglu and Chris Clifton pointed out in Security Issues in Querying Encrypted Data, a server cannot be both perfectly secure and highly efficient. If the data is skewed, an adversary can identify specific records simply by observing access patterns or frequency distributions, forcing a trade-off between performance and cryptographic "perfection."

Overestimating Concrete Security

The discrepancy between uniform theory and non-uniform reality isn't just a problem for passwords and databases; it affects the very foundations of modern cryptography. The Learning With Errors (LWE) problem is the backbone of lattice-based, post-quantum cryptography. However, Hao Chen and colleagues found in On the Concrete Security of LWE with Small Secret that standard security estimators are often too optimistic. When secrets are small or non-uniformly distributed, actual lattice reduction attacks can break these systems much faster than theoretical models predict.

To address this, researchers are moving toward more rigorous statistical frameworks. Jeremiah Blocki suggests in Towards a Rigorous Statistical Analysis of Empirical Password Datasets that we must bound the "guessing curve"—the probability an attacker succeeds within a certain number of attempts—without relying on simplified mathematical patterns like Zipf's Law, which can themselves be inaccurate.

Building Intuition: The "Ideal Attacker"

The core insight of this research direction is that security is relative to the attacker's knowledge of the distribution.

If an attacker knows that a dataset is skewed (e.g., they know that "Smith" is a common surname or that "123456" is a common password), they don't need to brute-force the entire keyspace. They only need to target the high-probability peaks of the distribution. Theoretical models that assume a flat, uniform distribution essentially "blind" themselves to these peaks, leading to an overestimation of how much work an attacker actually has to do.

True security in the real world requires designing protocols that remain robust even when the data is messy, patterned, and predictably human.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_security_gap_in_non_uniform_data_dis_0ae61b72,
  title = {The Security Gap in Non-Uniform Data Distributions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-security-gap-in-non-uniform-data-distributions/rdr_0ae61b7293624051bbc73ac1db2535ee},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_security_gap_in_non_uniform_data_dis_0ae61b72_v1,
  title = {The Security Gap in Non-Uniform Data Distributions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-security-gap-in-non-uniform-data-distributions/rdr_0ae61b7293624051bbc73ac1db2535ee/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}