<p>Does there exist a function <span class="math-container">$f(x,y)$</span> with these properties:</p>
<ol>
<li><p>Computing <span class="math-container">$f(x,y)$</span> is in P.</p>
</li>
<li><p><span class="math-container">$f$</span> is associative:  <span class="math-container">$f(x, f(y, z)) = f(f(x, y), z)$</span>.</p>
</li>
<li><p><span class="math-container">$f$</span> is one-way (assuming P <span class="math-container">$\neq$</span> NP):  Given the value <span class="math-container">$v$</span> of some <span class="math-container">$f(x, y)$</span>, zero or one of the values <span class="math-container">$x$</span> and <span class="math-container">$y$</span>, and given that there exists a solution, it is difficult to compute a <span class="math-container">$z$</span> and <span class="math-container">$w$</span> for which <span class="math-container">$f(z,w) = v$</span>.</p>
</li>
</ol>

CC BY-SA 4.0
2024-03-24T20:28:09.953Z
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)).$$
orlp
CC BY-SA 4.0
2024-03-25T23:16:35.487Z
https://crypto.stackexchange.com/q/17935/351
D.W.
<hash-function><one-way-function>
Does there exist a cryptographic associative hash function?
Dale
# Does there exist a cryptographic associative hash function?

(Asked by: username_0 on 2024-03-24)

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$.

**Tags:** hash-function, one-way-function

> **Comments:**
> **username_1**: 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)).$$  
> **username_2**: https://crypto.stackexchange.com/q/17935/351  

---

## 0 answers

