Evidence For Cryptomania: Do One-Way Functions And Public-Key Cryptography Exist?

Evidence for One-Way Functions

A one-way function is a mathematical function that is easy to compute on every input, but hard to invert given the image of a random input. More precisely, a function f: X → Y is one-way if:

There exists a polynomial-time algorithm to compute f(x) for any x in X
For a randomly selected y from the image of f, there does not exist a polynomial-time algorithm to find any x such that f(x) = y, with non-negligible probability

Informally, one-way functions act like a “mathematical black hole” – information goes into the function easily but does not come out. The study of these paradoxical objects is important because their existence implies things that were previously unimaginable in cryptography.

Defining One-Way Functions

The concept of a one-way function was formally introduced in the 1978 paper “On the Impossibility of Constructing One-Way Permutation Functions” by William Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr. This paper gave the first rigorous framework for modeling and reasoning about one-way functions.

Table of Contents

A function f operating on finite binary strings can be defined as one-way if it possesses three key properties:

Easy to compute: There exists a polynomial-time algorithm A such that for every x, A(x) = f(x)
Hard to invert: For every probabilistic polynomial-time algorithm A’, for a randomly selected y in the image of f, the probability that A'(y) computes some x such that f(x) = y is negligible
Well-behaved: f is computable in polynomial time, f is length-regular in that |x| ≈ |f(x)|, and f is one-to-one.

The most important criterion is the second one, regarding the difficulty of inverting f given an output y. This is key because if f could be efficiently inverted, it could not serve as the trapdoor needed for many celebrated applications in cryptography.

Candidate One-Way Functions

Since the recognition of their importance, researchers have proposed many candidate one-way functions. Three well-known examples are:

Modular Squaring

For an integer n that is the product of two large secret primes p and q, consider the function:

f(x) = x² mod n

It is conjectured that modular squaring is a one-way function, relying on the apparent difficulty of factoring n into its constituent primes p and q. While computing f(x) for a given x is easy, recovering x from f(x) seems to require factoring n, allowing this function to serve as a one-way function candidate.

Discrete Logarithm

In a finite cyclic group G with generator g, the discrete logarithm problem asks: given elements g and h in G, find an integer x such that:

h = g^x

The function f(x) = g^x is also a candidate one-way function, because computing exponentials mod G is efficient, but discrete logarithms appear intractable.

Integer Factorization

Factoring an integer n into its prime factors appears difficult. Therefore, the following is considered a one-way function candidate:

f(p,q) = p * q

Where p and q are large, random primes. Multiplying p and q is easy. But recovering the prime factors p and q given their product n = p * q seems prohibitively difficult for classical computers.

Evidence Supporting Existence

There is currently no mathematical proof that one-way functions exist. However, there is strong evidence from empirical tests, applications that rely on candidate one-way functions, and reductions between hard problems. Three supporting arguments are:

Withstanding cryptanalysis: Proposed one-way function candidates have withstood decades of analysis, with no efficient general attacks discovered.
Enabling applications: Systems relying on the one-way nature of functions like RSA and discrete logs have been successfully deployed.
Reductions: Factoring, discrete logs, and other problems are reducible to each other, providing indirect hardness evidence.

For these reasons, most researchers believe that one-way functions do likely exist, both in theory and specifically instantiated as the multiplication and exponentiation functions commonly relied upon today.

Implications for Cryptography

The existence of one-way functions enables a remarkable possibility first identified by Diffie and Hellman – constructing cryptographic systems where keys can be made public. Two important examples are public-key cryptosystems and digital signatures.

Public-Key Cryptosystems

If one-way trapdoor functions exist, there can be cryptography where an encryption key is made public without compromising security. Early examples include the Diffie-Hellman key exchange and RSA encryption.

For RSA, the one-way function f(x) = x^e mod n is used, where n is publicly known but it is intractable to take e-th roots modulo a composite n without extra “trapdoor” information about n’s factors. This allows n and e to serve as a public key, enabling encryption by anyone.

Digital Signatures

One-way trapdoor functions also enable digital signatures. Signing involves a private transformation like decryption, which can be verified using public information. For example, in RSA signatures, a message m is signed by decrypting using the private key to compute s = m^d mod n. This s can then be verified as authentic by checking that s^e = m mod n.

Open Problems

Fundamental questions around one-way functions remain unanswered. Two central open problems are explicitly proving that they exist, either unconditionally or based on common cryptographic assumptions, and finding candidate one-way functions that offer robust security guarantees.

Proving One-Way Functions Exist

No one-way function candidates have been proven to definitively satisfy the strict definition. Using assumptions like P ≠ NP or the existence of trapdoor predicates, results have shown that one-way functions follow. An important open problem is exhibiting an unconditional proof that one-way functions exist – or on the contrary, proving no such functions exist.

Finding Strong One-Way Functions

The known one-way function candidates have some potential vulnerabilities. Factoring and taking discrete logs, while difficult, are vulnerable to quantum attacks. New cryptographic schemes like lattices and isogenies may offer more robust security, but their one-wayness is less established. Developing alternative one-way function proposals with concrete security guarantees remains an open research challenge.