The Sufficiency of One-Way Functions in Advanced Cryptography

102 concepts65 papers1 proposal

In theoretical cryptography, complexity assumptions are organized in a strict hierarchy. At the top sit highly structured algebraic assumptions, such as the hardness of factoring or the Learning with Errors (LWE) problem, alongside heavy obfuscation machinery like Indistinguishability Obfuscation (iO). At the absolute bedrock lies the One-Way Function (OWF)—a function that is easy to compute but computationally infeasible to invert.

For decades, a central goal in cryptographic foundations has been assumption minimization: proving that advanced, highly interactive, or seemingly complex primitives do not require specialized algebraic structures, but can instead be built entirely from any generic OWF.

Minimizing assumptions is not merely an exercise in theoretical elegance; it is a strategy for long-term security. If a protocol relies on a specific algebraic structure (like a elliptic curve group), a single mathematical breakthrough or a sufficiently powerful quantum computer can shatter its security entirely. By contrast, if a primitive can be constructed from any OWF, its security is universal: it stands as long as complexity-based cryptography itself is possible.


From Structured Algebra to Pure Pseudorandomness

To understand why one-way functions are sufficient for complex tasks, we must look at how structured algebraic requirements can be dismantled into pure pseudorandomness. A classic example of this paradigm shift is bit commitment—a fundamental building block for zero-knowledge proofs and secure protocols where a sender locks a secret value in a box and opens it later.

Early commitment schemes relied on one-way permutations, a restrictive subset of one-way functions that preserve the size of the input space. However, Moni Naor demonstrated in Bit Commitment Using Pseudorandomness that any generic pseudorandom generator (PRG) is sufficient to achieve secure bit commitment.

[Standard OWF] ---> [Pseudorandom Generator (PRG)] ---> [Naor's Commitment Protocol]
                                                              |
                                            +-----------------+-----------------+
                                            |                                   |
                                    [Hiding Property]                   [Binding Property]
                                 Receiver cannot guess               Sender cannot change
                                 seed from PRG output                mind due to expansion

The intuition behind why this works lies in how a PRG stretches a short random seed into a longer, indistinguishable-from-random string. In the protocol designed by the author, the receiver first sends a long random string. To commit to a bit, the sender uses a PRG to generate a pseudorandom string and either transmits it directly (to commit to 0) or transmits its bitwise XOR with the receiver's string (to commit to 1).

  • Why it hides: Because the output of a PRG is computationally indistinguishable from a truly random string, a polynomial-time receiver cannot tell whether they are looking at a raw PRG output or an XORed string.
  • Why it binds: Because the PRG expands the seed into a much larger space, the total number of valid PRG outputs is a miniscule fraction of the entire string space. It is statistically impossible for the sender to find a single seed that can successfully open the commitment as both a 0 and a 1.

Since PRGs can be constructed from any standard OWF, this result established that the absolute minimal complexity assumption is sufficient to support secure commitment infrastructure.


Eliminating Collision Resistance in Verifiable Computation

The quest for one-way function sufficiency also extends to interactive proofs and argument systems. When a weak client outsources a massive computation to a powerful server, they need a way to verify the result quickly. Traditionally, succinct argument systems achieved this by utilizing collision-resistant hash functions (CRHFs) to construct Merkle trees, allowing the prover to succinctly commit to the steps of a computation.

However, CRHFs require significantly more mathematical structure than simple OWFs. To determine whether this extra structure is truly necessary, Amit et al. constructed Constant-Round Arguments from One-Way Functions.

The authors demonstrated that OWFs are sufficient to build constant-round argument systems with nearly-linear verification time for depth-bounded computations. Instead of relying on global collision resistance to compress the entire computation tree into a single hash root, the protocol restructures the verification process. By leveraging localized verification paths and interactive challenges that can be validated via simple pseudorandomness, the authors bypassed the need for CRHFs entirely, albeit at the cost of a higher round complexity than protocols backed by stronger assumptions.


Bypassing Public-Key Machinery in Secure Computation

In Secure Multi-Party Computation (MPC), achieving round-optimal protocols (such as two-round two-party computation) historically demanded heavy public-key machinery, such as trapdoor permutations or oblivious transfer.

To lower this barrier, researchers have explored how modifying the environmental setup can alter the underlying mathematical requirements. For instance, Damgård et al. showed in On the Necessary and Sufficient Assumptions for UC Computation that by introducing a Key-Registration Authority, universally composable commitments can be realized using only OWFs, whereas traditional setup models like the Common Reference String require complex public-key encryption.

Taking this a step further, Polychroniadou et al. achieved round-optimal secure computation in Round-Optimal Token-Based Secure Computation by combining a minimal hardware assumption with the minimal cryptographic assumption of OWFs.

[Stateless Hardware Token] + [One-Way Functions] ---> Round-Optimal MPC (No Trapdoor Permutations)

By utilizing simple, stateless hardware tokens that can execute basic symmetric primitives, the authors eliminated the necessity for trapdoor permutations or collision-resistant hash functions. The token acts as a local, trusted isolated execution environment that can evaluate pseudorandom functions, allowing parties to establish secure channels and compute functions in a minimal number of rounds while relying strictly on symmetric-key assumptions.


Establishing Fundamental Hardness Bounds

The sufficiency of OWFs is a double-edged sword: if an advanced primitive can be built from an OWF, then the computational hardness of that primitive is also fundamentally tied to the existence of OWFs. This perspective has allowed researchers to prove that certain efficiency bottlenecks or security limitations are inescapable features of complexity theory.

A major breakthrough occurred in the foundations of data privacy. In Hardness of Non-Interactive Differential Privacy from One-Way Functions, Kowalczyk et al. proved that general-purpose, efficient algorithms for non-interactive differential privacy are computationally impossible if OWFs exist.

Prior proofs establishing this hardness relied on highly complex, non-standard cryptographic tools like Indistinguishability Obfuscation. By reducing the hardness framework solely to the existence of standard OWFs, the authors demonstrated that the gap between information-theoretic privacy and computationally practical data release is a pervasive, fundamental consequence of basic cryptography, rather than an artifact of specialized assumptions.

A similar lower-bound paradigm applies to data integrity. In The Complexity of Online Memory Checking, Naor et al. explored the limits of verifying remote data storage without reading the entire file. The authors proved that achieving verification efficiency that surpasses the standard information-theoretic storage-query product bound is computationally equivalent to the existence of one-way functions. If a system exhibits sub-linear overhead, it inherently possesses the power to compute cryptographic primitives.


Modern Frontiers: Symmetric Primitives in AI Safety

The philosophy of one-way function sufficiency has recently broken out of classical protocol design and entered modern AI safety, specifically in the domain of watermarking Large Language Models (LLMs). A robust watermark must alter the token distribution of an LLM such that the text is cryptographically undetectable to a reader, yet easily identifiable by the model owner—even if an adversary introduces insertions, deletions, or substitutions.

Intuitively, protecting text against adversarial edits might seem to require complex public-key signatures or heavy cryptographic machinery. However, Golowich et al. in Edit Distance Robust Watermarks via Indexing Pseudorandom Codes and Moitra et al. in Edit Distance Robust Watermarks for Language Models proved that this can be achieved using local, weak pseudorandom functions (PRFs).

[LLM Token Generation] ---> [Local Weak PRF Context Indexing] ---> [Watermarked Text]
                                                                          |
                                                        (Adversarial Edits / Mutations)
                                                                          v
                                                       [Robust Edit-Distance Detection]

Instead of signing the text globally, the authors' scheme uses a weak PRF to generate pseudorandom choices for token selection based on local context indices. Because the PRF outputs are computationally indistinguishable from true randomness to anyone without the secret key, the watermark remains entirely undetectable.

Crucially, by linking these pseudorandom choices to an indexing code robust to edit distances, the watermark can survive a constant fraction of arbitrary text mutations. By aligning the watermarking mechanism with simpler symmetric primitives rather than heavy public-key assumptions, the authors significantly lowered the theoretical and computational barriers to implementing provably secure AI safety measures.

Key Foundational Work

Bit Commitment Using Pseudorandomness (1991) — contributed 2 concept elements to this direction.
Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation (1998) — contributed 2 concept elements to this direction.
A Formal Treatment of Remotely Keyed Encryption (1998) — 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_one_way_function_sufficiency_a94e1e89,
  title = {one-way function sufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/one-way-function-sufficiency/rdr_a94e1e89eabb47b78eb97d7ae42dbdb1},
  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_one_way_function_sufficiency_a94e1e89_v1,
  title = {one-way function sufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/one-way-function-sufficiency/rdr_a94e1e89eabb47b78eb97d7ae42dbdb1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake