Oneway functions
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory.
For an overview see these slides on one-way functions and the wiki articles:
The existence of such one-way functions is still an open conjecture. Their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science. The converse is not known.
Surveys
Key articles
- A pseudorandom generator from any one-way function
- No better ways to generate hard NP instances than random
- On One-way Functions from NP-Complete Problems
- On the Existence of Weak One-Way Functions
- One-way Functions In Reversible Computations
- Coin Flipping of Any Constant Bias Implies One-Way Functions
Hash functions
One-Way Functions in Cryptography are used as hash maps.
Constructions of hash functions
- Fast and Powerful Hashing using Tabulation
- Explicit Orthogonal Arrays and Universal Hashing
- A universal whitening algorithm for commercial random number generators
- Analysis of the New Standard Hash Function
- Almost collision-flat universal hash functions and mosaics of designs
- Bandwidth-Hard Functions from Random Permutations
- A Hash Table Without Hash Functions: get the most out of random bits
Related topics
Kolmogorov complexity
- Finding Connections between One-Way Functions and Kolmogorov Complexity
- On one-way functions and Kolmogorov complexity
- One-Way Functions and the Hardness of Time-Bounded Kolmogorov Complexity
- Symmetry of information and one-way functions
- A duality between one-way functions and average-case symmetry of information
- On One-way Functions and Hardness of Kolmogorov Complexity
- Kolmogorov One-Way Functions Revisited
- On One-way Functions and Sparse Languages
- On Interactive Kolmogorov Complexity and Key-Agreement
- One-way functions using Algorithmic and Classical Information Theories
- Characterizing Derandomization Through Levin-Kolmogorov Complexity
Quantum computation