Timeline for Are there very strongly pseudorandom permutations?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 28, 2013 at 17:00 | answer | added | CCat | timeline score: 1 | |
| S Jun 27, 2013 at 20:27 | history | suggested | Kaveh | CC BY-SA 3.0 |
finxing LaTeX, adding tags
|
| Jun 27, 2013 at 20:23 | review | Suggested edits | |||
| S Jun 27, 2013 at 20:27 | |||||
| Jun 22, 2013 at 14:09 | comment | added | gowers | I think I've now found a construction that does what I want. | |
| Jun 20, 2013 at 9:36 | comment | added | gowers | Actually, scratch that -- I miscalculated the information-theoretic bound, which gives that exponentially many would be needed. | |
| Jun 19, 2013 at 8:45 | comment | added | gowers | I now think it may be possible to do something by composing polynomially many Feistel permutations. | |
| Jun 19, 2013 at 6:55 | comment | added | gowers | Yes. I was vague about it, but the precise requirement I would like is that $k$ should be at most a polynomial function of $n$ (or perhaps a very slightly superpolynomial function). | |
| Jun 19, 2013 at 1:08 | comment | added | Ryan O'Donnell | You must want some upper bound on $k$, right? Otherwise you could take $k = \log(2^n!)$ and then define $\phi(x,y) = \pi_x(y)$ where $\pi_x$ is the $x$th permutation on $\{0,1\}^n$ in lexicographic order. Then $\phi$ is completely indistinguishible from truly random. (I'm ignoring here the issue that $\log(2^n!)$ is not an integer, but one could hack around this.) | |
| Jun 18, 2013 at 17:13 | comment | added | Timothy Chow | If you don't get a good answer here on MO, you might try asking your question at cstheory.stackexchange.com | |
| Jun 18, 2013 at 17:00 | comment | added | gowers | I have now found a source that seems to suggest that the Luby-Rackoff construction won't give hardness greater than $2^n$. So it looks as though a different idea would be needed. But maybe there are some different ideas out there. | |
| Jun 18, 2013 at 14:14 | history | asked | gowers | CC BY-SA 3.0 |