Math 2.0

Information and communication theory, circuits Definition

One-way function

Builds on FunctionProbabilistic Turing machineP

Definition

A function f ⁣:{0,1}∗→{0,1}∗f \colon \set{0,1}^* \to \set{0,1}^* is one-way if it has these two properties.

  1. Easy to compute: some deterministic algorithm computes f(x)f(x) in time polynomial in ∣x∣\abs{x}.
  2. Hard to invert: let AA be a probabilistic polynomial-time algorithm and let pp be a polynomial. Then for all sufficiently large nn, Pr⁡[f(A(1n,f(x)))=f(x)]<1p(n).\Pr\big[f(A(1^n, f(x))) = f(x)\big] < \frac{1}{p(n)}.

The probability is over xx uniform in {0,1}n\set{0,1}^n and over the random bits of AA. The input 1n1^n gives AA the length nn in unary.

Remarks

The inverter succeeds if it finds any preimage of f(x)f(x), not necessarily xx itself.

Example of a candidate: let f(p,q)=pqf(p, q) = pq on pairs of nn-bit numbers. Restricted to pairs of primes, this is believed to be one-way. On arbitrary pairs of numbers the situation differs, since a random product often has small factors that are easy to find.

Non-example: the identity function satisfies clause 1 but fails clause 2, since A(1n,y)=yA(1^n, y) = y always inverts it.

If one-way functions exist, then P≠NP\mathrm{P} \ne \mathrm{NP}. Indeed, if P=NP\mathrm{P} = \mathrm{NP}, a preimage of yy can be found bit by bit in polynomial time with an NP oracle.

Reading path

To understand this page from the ground up, read these 16 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionP, concept, no evidence levelPconceptProbabilistic Turing machine, concept, no evidence levelProbabilistic Turing …conceptProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionFunction, definition, no evidence levelFunctiondefinitionOne-way function, definition, no evidence levelOne-way functiondefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. P concept
  3. Probabilistic Turing machine concept
  4. Proposition concept
  5. Set definition
  6. Implication definition
  7. Predicate definition
  8. Ordered pair definition
  9. Existential quantifier definition
  10. Universal quantifier definition
  11. Cartesian product definition
  12. Subset definition
  13. Uniqueness quantifier definition
  14. Binary relation definition
  15. Function definition
  16. One-way function definition

Further reading

  1. Web https://en.wikipedia.org/wiki/One-way_function, Definition
About this page
TagQ7N6JJANT4
URIm2://Q7N6JJANT4
Kinddefinition
WritingW1 stated
MSC94A60, 68Q17, 68P25
DefinesOne-way function
UsesFunction, Probabilistic Turing machine, P
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.