Skip to main content

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very eficientefficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unqiueunique preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not univertibleuninvertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash-function function is univertibleuninvertible (this is why we store hashes of passwords). Also, that RSA is one-way (an: an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is univertibleuninvertible is clear from the definitions (write down your definition of one-way function ,it: it should be immediate ,ifimmediate; if not, edit your question adding that definition).

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very eficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unqiue preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not univertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash-function is univertible (this is why we store hashes of passwords). Also, that RSA is one-way (an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is univertible is clear from the definitions (write down your definition of one-way function ,it should be immediate ,if not edit your question adding that definition).

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very efficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unique preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not uninvertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash function is uninvertible (this is why we store hashes of passwords). Also, that RSA is one-way: an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is uninvertible is clear from the definitions (write down your definition of one-way function: it should be immediate; if not, edit your question adding that definition).

Source Link
Henno Brandsma
  • 3.9k
  • 16
  • 20

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very eficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unqiue preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not univertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash-function is univertible (this is why we store hashes of passwords). Also, that RSA is one-way (an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is univertible is clear from the definitions (write down your definition of one-way function ,it should be immediate ,if not edit your question adding that definition).