Editing One-way function (section)

==Candidates for one-way functions==
The following are several candidates for one-way functions (as of April 2009). Clearly, it is not known whether
these functions are indeed one-way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.{{Citation needed|reason=No sources are listed|date=March 2018}}

===Multiplication and factoring===
The function ''f'' takes as inputs two prime numbers ''p'' and ''q'' in binary notation and returns their product.  This function can be "easily" computed in [[big O notation|''O''(''b''<sup>2</sup>)]] time, where ''b'' is the total number of bits of the inputs.  Inverting this function requires finding the [[integer factorization|factors of a given integer]] ''N''.  The best factoring algorithms known run in <math>O\left(\exp\sqrt[3]{\frac{64}{9} b (\log b)^2}\right)</math>time, where b is the number of bits needed to represent ''N''.

This function can be generalized by allowing ''p'' and ''q'' to range over a  suitable set of [[semiprimes]].  Note that ''f'' is not one-way for randomly selected integers {{nowrap|''p'', ''q'' &gt; 1}}, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitrary ''p'' is odd is 1/2, and likewise for ''q'', so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability that ''p'' or ''q'' is even, is {{nowrap|1=1 − 1/4 = 3/4}}).

===The Rabin function (modular squaring)===
The '''Rabin function''',<ref name=Goldreich />{{rp|57}} or squaring [[modular arithmetic|modulo]] <math>N=pq</math>, where {{mvar|p}} and {{mvar|q}} are primes is believed to be a collection of one-way functions. We write
:<math>\operatorname{Rabin}_N(x)\triangleq x^2\bmod N</math>
to denote squaring modulo {{mvar|N}}: a specific member of the '''Rabin collection'''. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoring {{mvar|N}} (in the sense of [[polynomial-time reduction]]). Hence it can be proven that the Rabin collection is one-way if and only if factoring is hard. This also holds for the special case in which {{mvar|p}} and {{mvar|q}} are of the same bit length. The [[Rabin cryptosystem]] is based on the assumption that this Rabin function is one-way.

===Discrete exponential and logarithm===
[[Modular exponentiation]] can be done in polynomial time. Inverting this function requires computing the [[discrete logarithm]]. Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known. These groups are all [[finite abelian group]]s and the general discrete logarithm problem can be described as thus.

Let ''G'' be a finite abelian group of [[cardinality]] ''n''. Denote its [[group operation]] by multiplication. Consider a [[Primitive element (finite field)|primitive element]] {{nowrap|''&alpha;'' &isin; ''G''}} and another element {{nowrap|''&beta;'' &isin; ''G''}}. The discrete logarithm problem is to find the positive integer ''k'', where {{nowrap|1 ≤ ''k'' ≤ n}}, such that:

:<math>\alpha^k = \underbrace{\alpha \cdot \alpha \cdot \ldots \cdot \alpha}_{k \; \mathrm{times}} = \beta</math>

The integer ''k'' that solves the equation {{nowrap|1=''&alpha;<sup>k</sup>'' = ''&beta;''}} is termed the '''discrete logarithm''' of ''&beta;'' to the base ''&alpha;''. One writes {{nowrap|1=''k'' = log<sub>''&alpha;''</sub> ''&beta;''}}.

Popular choices for the group ''G'' in discrete logarithm [[cryptography]] are the cyclic groups [[multiplicative group of integers modulo n|('''Z'''<sub>''p''</sub>)<sup>''×''</sup>]] (e.g. [[ElGamal encryption]], [[Diffie–Hellman key exchange]], and the [[Digital Signature Algorithm]]) and cyclic subgroups of [[elliptic curve]]s over [[finite field]]s (''see'' [[elliptic curve cryptography]]).

An elliptic curve is a set of pairs of elements of a [[Field (mathematics)|field]] satisfying {{nowrap|1=''y''<sup>2</sup> = ''x''<sup>3</sup> + ''ax'' + ''b''}}. The elements of the curve form a group under an operation called "point addition" (which is not the same as the addition operation of the field). Multiplication ''kP'' of a point ''P'' by an integer ''k'' (''i.e.'', a [[Group action (mathematics)|group action]] of the additive group of the integers) is defined as repeated addition of the point to itself. If ''k'' and ''P'' are known, it is easy to compute {{nowrap|1=''R'' = ''kP''}}, but if only ''R'' and ''P'' are known, it is assumed to be hard to compute ''k''.

===Cryptographically secure hash functions===
There are a number of [[cryptographic hash function]]s that are fast to compute, such as [[SHA-256]]. Some of the simpler versions have fallen to sophisticated analysis, but the strongest versions continue to offer fast, practical solutions for one-way computation. Most of the theoretical support for the functions are more techniques for thwarting some of the previously successful attacks.

===Other candidates===
Other candidates for one-way functions include the hardness of the decoding of random [[linear code]]s, the hardness of certain [[lattice problems]], and the [[subset sum problem]] ([[Naccache–Stern knapsack cryptosystem]]).