Timeline for PRFs / hash functions with a parameter amount of 'hot' bits?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 4, 2020 at 0:34 | vote | accept | lynn | ||
| Nov 30, 2020 at 16:02 | answer | added | Maeher | timeline score: 2 | |
| Nov 28, 2020 at 19:21 | comment | added | Maeher | I don't think it's something anyone has ever needed. The security proof should be straightforward. It's a pretty generic construction for a PRF with any efficiently samplable codomain. Just run the sampler using a random tape generated from a regular prf (stretched with a prg if necessary). | |
| Nov 28, 2020 at 19:07 | comment | added | lynn | This sounds sensible, but since there are chances of colliding with an already-hot bit, would require a slightly different construction, looping until all the bits are set to 1. Intuitively this sounds secure. Has this construction already been proposed in literature, and if so, is there a name assigned to it? | |
| Nov 28, 2020 at 18:34 | comment | added | Maeher | Use any prf to generate a random tape. Use the random tape to sample $i$ distinct indices. Set those bits to $1$. | |
| Nov 28, 2020 at 17:41 | history | asked | lynn | CC BY-SA 4.0 |