Timeline for Proof that MAC and hash composition is insecure
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2019 at 2:27 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
fix
|
| Mar 8, 2019 at 1:45 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Fix the ordering of terms in polynomial evaluation MACs.
|
| May 25, 2018 at 14:23 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Redoubly clarify what $C$ is.
|
| May 24, 2018 at 4:43 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Lemma 3.3, not Lemma 3. Give some intuition about what function $A$ serves.
|
| May 16, 2018 at 0:13 | comment | added | Squeamish Ossifrage | @fgrieu They are related: $\varepsilon$-almost strongly universal means $\Pr[H(x) = h, H(y) = h'] \leq \varepsilon^2$ for all $x \ne y$, $h$, and $h'$; that implies $\varepsilon$-almost universal, meaning $\Pr[H(x) = H(y)] \leq \varepsilon$ for all $x$ and $y$; unqualified, these mean $\varepsilon = 1/|\mathcal T|$, which when $|\mathcal T| = 2^\lambda$ is negligible in the security parameter $\lambda$. (Here $H$ is a random variable taking values in a function space; write $H_k$ for some key $k$ if you want to make the key explicit.) | |
| May 15, 2018 at 21:09 | comment | added | fgrieu♦ | Ahh; so I would be off when I reason with this definition of (plain vanilla) universal hash function, also regurgitated at the end on my current tentative answer. Sad, I was so proud that it nicely goes with Katz and Lindell's strongly universal (hash) function $$\forall(m,m')\in\mathcal M^2,\forall(t,t')\in\mathcal T^2,\ m\ne m'\implies\mathsf{Pr}_{k\in\mathcal K}\Big[H(k,m)=t\wedge H(k,m')=t'\Big]=\frac1{|\mathcal T|^2}$$ | |
| May 15, 2018 at 20:31 | comment | added | Squeamish Ossifrage | @fgrieu As far as I can tell it's the standard definition of $\varepsilon$-almost universal for $\varepsilon$ negligible in the security parameter: a random function $H$ such that for any $x \ne y$, $\Pr[H(x) = H(y)] \leq \varepsilon$. | |
| May 15, 2018 at 20:18 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Clarify how universal relates to epsilon-almost universal.
|
| May 15, 2018 at 20:12 | comment | added | fgrieu♦ | At least, I think that now I get that we both lean towards impossibility to exhibit the question's counterexample, contrary to that comment. That's a progress. But I'm still lost among the definitions of smurf-universal-hash-function, and reconciling with what the OP stated. | |
| May 15, 2018 at 19:35 | comment | added | Squeamish Ossifrage | @fgrieu Clearer? | |
| May 15, 2018 at 19:35 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Reformat.
|
| May 15, 2018 at 3:34 | history | edited | Squeamish Ossifrage | CC BY-SA 4.0 |
Cull stray prime.
|
| May 14, 2018 at 23:14 | vote | accept | Daniel | ||
| May 14, 2018 at 16:43 | comment | added | fgrieu♦ | I recognize that an answer flies high over my head when I can't immediately tell if its conclusion is that the proposition in the question is right or wrong. I'm precisely at that point. | |
| May 14, 2018 at 2:02 | history | answered | Squeamish Ossifrage | CC BY-SA 4.0 |