Timeline for How to build a periodic PRF from a PRF?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 8, 2021 at 7:30 | vote | accept | Tristan Nemoz | ||
| Jun 8, 2021 at 3:00 | history | tweeted | twitter.com/StackCrypto/status/1402098277596733444 | ||
| Jun 7, 2021 at 21:49 | history | became hot network question | |||
| Jun 7, 2021 at 16:52 | comment | added | Samuel Neves | Well, there are two bad events in the ideal world: $k = 0$, with probability $2^{-n}$, and $x_i = x_j \oplus k, 0 \le i < j < q$. Summing over all queries, $P[x_i = x_j \oplus k] = q(q-1)/2^n$. So the PRF advantage of $g_k$ is going to be something like $\mathbf{Adv}_f^{\mathrm{PRF}}(2q) + 2^{-n} + \frac{q(q-1)}{2^n}$. You can mount a distinguisher on $g_k$ by querying $\approx 2^{n/2}$ distinct random inputs $x_i$, obtaining a collision. From this collision you can obtain with high probability $k = x_i \oplus x_j$, and confirm with another query that you're working with $g_k$. | |
| Jun 7, 2021 at 16:47 | answer | added | Mikero | timeline score: 4 | |
| Jun 7, 2021 at 13:44 | history | asked | Tristan Nemoz | CC BY-SA 4.0 |