Consider the following experiment:
Let there be a machine which runs (ie. continually clocks) an LFSR of size (ie. number of bits) $b$, having a button that, when pressed, extracts the next $t$ bits from the LFSR, prints them onto a paper ticket, deposits the ticket into a sealed, opaque urn, and complements every bit in the LFSR (ignore, for the sake of argument, the case where the LFSR gets reset to all zeroes); the machine continues to run normally afterwards.
Now place this machine in a room, completely isolated from the outside, and have a number (say $n$) of players form a line and, one by one, step into the room and press the button. After all $n$ of them are finished, retrieve the sealed urn.
The LFSR's feedback polynomial, initial state and clocking frequency are public parameters, as are the numbers $b$ and $t$.
Now there's an attacker whose purpose is to match at least one ticket in the urn to one of the players. The attacker has access to all the public parameters, knows the order in which the players are lined up, can measure the time each one enters the room (but cannot, obviously, know exactly when a player pushes a button, since that happens inside the isolated room), and may collude with a fraction q of the players in order to achieve its goal.
The questions, then, are:
- Which parameters (ie. $b$, $t$, $q$, clocking frequency is a little trickier) can ensure the attacker has no more chance of succeeding than he would by guessing?
- Would replacing the LFSR by an ASG be any better? any worse?
A note on clocking frequency: for technical reasons, the clocking frequency is forced to be relatively low, say no more than 2kHz (ie. one clock pulse every one two-thousandth of a second).
A note on collusion and what the players can and can't do: the players can be assumed to have at their disposal a timing device of their choosing, with the accuracy they see fit (if this proves to be too powerful an advantage, an analysis with restrictions is greatly appreciated!); a player does not see the number they get (they actually don't get it per se, since the number goes into the urn).
The rationale behind all this is that we're trying to generate true-ish random numbers from an LFSR: the random variable to harness is the times at which the button is pressed, the LFSR is there just to provide for confusion of the generated values; if one where to use the number of seconds since the experiment's beginning, the attacker could easily match the tickets to the players; if one where to use the LFSR without complementing, the attacker could compare them according to the order in which the LFSR (all of whose parameters are public) generates them; I believe (with absolutely no basis!) that complementing after each extraction could do the trick.
English is not my mother language, I'm sorry if I haven't made myself clear enough, please do ask for clarifications if needed.
This is not homework, tough it may look like it :)
EDIT: It has been brought up more than once in the answers that knowing so much and being able to do so much, gives the attacker too much power, so i decided to make the LFSR's initial state secret. Now the last paragraph in the explanation above should read:
The LFSR's feedback polynomial and clocking frequency are public parameters, as are the numbers $b$ and $t$. The LFSR's initial state is secret, and unknown to the attacker.