Results 1 to 3 of 3

Math Help - One-way Function

  1. #1
    Junior Member
    Joined
    Mar 2013
    From
    u.s.
    Posts
    50

    One-way Function

    I'm trying to wrap my head around what a one-way function is. The definition I found is complicated to understand (for me anyways) and it states the following:

    Informally, a function is a one-way function if

    1. The description of is publicly known and does not require any secret information for its operation.

    2. Given , it is easy to compute .

    3. Given , in the range of , it is hard to find an such that . More precisely, any efficient algorithm solving a P-problem succeeds in inverting with negligible probability.

    The existence of one-way functions is not proven. If true, it would imply . Therefore, it would answer the complexity theory NP-problem question of whether all apparently NP-problems are actually P-problems. Yet a number of conjectured one-way functions are routinely used in commerce and industry. For example, it is conjectured, but not proved, that the following are one-way functions:

    1. Factoring problem: , for randomly chosen primes .

    2. Discrete logarithm problem:


    for a generator of for some prime .

    3. Discrete root extraction problem: , for in , in and relatively prime to , and primes. This is the function commonly known as RSA encryption.

    4. Subset sum problem: , for , and -bit integers .

    5. Quadratic residue problem.


    I was wondering if someone could explain it a little better? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,661
    Thanks
    606

    Re: One-way Function

    Hey rhymin.

    If we are talking about functions that are reversible (as opposed to those that are not like hash functions), then the main idea of a one way function is that its easy to compute, but hard to invert.

    In a function that is invertible, you have an inverse map which is f^(-1)(x) where you can use f^(-1)(f(x)) = x to get back your original input. This is what happens in cryptography where you encode something by using h = f(x) and then you apply f^(-1)(h) = x to get back your original data.

    If it is hard to undo (or invert) it means that the computational complexity for undoing is going to be high (like exponentially high or greater than polynomial).

    The class of problems that are hard to compute or find but easy to check are called NP problems. You can check the solution very quickly, but finding the solution probabilistically will take a long time.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2013
    From
    u.s.
    Posts
    50

    Re: One-way Function

    Thank you Chiro!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 16th 2013, 12:38 AM
  2. Replies: 20
    Last Post: November 27th 2012, 05:28 AM
  3. Replies: 0
    Last Post: October 19th 2011, 04:49 AM
  4. Replies: 4
    Last Post: October 27th 2010, 05:41 AM
  5. Replies: 3
    Last Post: September 14th 2010, 02:46 PM

Search Tags


/mathhelpforum @mathhelpforum