Does there exist a function $f(x,y)$ with these properties:

  1. Computing $f(x,y)$ is in P.

  2. $f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$.

  3. $f$ is one-way (assuming P $\neq$ NP): Given the value $v$ of some $f(x, y)$, zero or one of the values $x$ and $y$, and given that there exists a solution, it is difficult to compute a $z$ and $w$ for which $f(z,w) = v$.

  • 2
    $\begingroup$ I find it hard to call $f$ a cryptographic hash function, because while I don't have an example that violates your one-way property, collision resistance is trivially broken: $$f(f(v, x), y) = f(x, f(y, v)).$$ $\endgroup$
    – orlp
    Mar 24 at 20:28
  • 1
    $\begingroup$ crypto.stackexchange.com/q/17935/351 $\endgroup$
    – D.W.
    Mar 25 at 23:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.