Timeline for Are LFSRs enough for this?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 16, 2014 at 13:11 | history | edited | mpr | CC BY-SA 3.0 |
Restrict knowledge of initial state
|
| Oct 15, 2014 at 15:37 | answer | added | bmm6o | timeline score: 1 | |
| Oct 15, 2014 at 12:36 | comment | added | mpr | This LFSR complements itself after you extract a number from it, so you should explore a binary tree where in each step you either clock the LFSR once more, or complement it. Granted, without an initialization phase to scramble things up a bit, it would be trivial to just step it and see. | |
| Oct 15, 2014 at 7:23 | history | tweeted | twitter.com/#!/StackCrypto/status/522286551015776256 | ||
| Oct 15, 2014 at 1:17 | comment | added | bmm6o | If I know the initial state, can't I just step my copy of the LFSR until its state matches one of the tickets? If the time makes sense, assume it was the first player's otherwise keep stepping. Or are we assuming that there are too many steps to make this feasible? | |
| Oct 14, 2014 at 21:26 | vote | accept | mpr | ||
| Oct 15, 2014 at 12:36 | |||||
| Oct 14, 2014 at 17:48 | answer | added | fgrieu♦ | timeline score: 2 | |
| Oct 14, 2014 at 16:56 | comment | added | mpr | Yes, indeed, that's correct! Do you believe it should be clarified in the question proper? | |
| Oct 14, 2014 at 16:46 | comment | added | fgrieu♦ | I do not think that my first comment needs to be incorporated in the question. $\;$ Is it correct that the adversary knows the value on every ticket, and wants to assign which ticket was generated by which player, with odds better than random? | |
| Oct 14, 2014 at 15:07 | history | edited | mpr | CC BY-SA 3.0 |
Added suggestions from first comments
|
| Oct 14, 2014 at 15:03 | comment | added | mpr | Yup, I was just trying to keep it simple, do you believe including this on the question would make it better? If you do, I'll gladly include it :) Regarding your other questions, I'll edit the question proper with clarifications. | |
| Oct 14, 2014 at 15:03 | comment | added | fgrieu♦ | On the problem: Are the experimenters that collude with the adversary capable of $\;$ a) telling which number they drew? $\;$ b) telling exactly when they pressed the button? $\;$ c) pressing the button at a chosen instant? | |
| Oct 14, 2014 at 14:56 | comment | added | fgrieu♦ | Incidentally: we know how to tweak an LFSR with a primitive polynomial of degree $b$ into a generator with almost identical output save for an extra 0, making the period $2^b$ rather than $2^b-1$, and insuring that the generator can't become stationary when complemented; see this. | |
| Oct 14, 2014 at 13:29 | history | asked | mpr | CC BY-SA 3.0 |