`> Correct me if I'm wrong here, but uniformity of the linear function isn't> sufficent even if we implemented like this (right now it's more a+X than> a <dot> X).>> The part which suggests choosing an irreducible poly and a value "a" in the> preprocessing stage ... last I checked the value for a and the poly need to> be secret.  How do you generate poly and a, Catch-22?  Perhaps I'm missing> something and someone can point it out.No, the value (the parameter pi) are specifically described as "the publicparameter".  See the "Preprocessing" paragraph at the end of section 1.2on page 3.  "This string is then hardwired into the implementation and need not be kept secret."All that's required is that the adversary can't tailor his limitedcontrol over the input based on knowing pi.There's a simple proof in all the papers that if an adversary knows*everything* about the randomness extraction function, and has totalcontrol over the input distribution, you're screwed.Basically, suppose you have a 1024-bit input block, the attackeris required to choose a distribution with at least 1023 bits of entropy,and you only want 1 bit out.  Should be easy, right?Well, with any *fixed* function, the possible inputs are divided intothose that hash to 0, and those that hash to 1.  One of those setsmust have at least 2^1023 members.  Suppose it's 0.  The attacker canchoose the input distribution to be "uniformly at random from the>= 2^1023 inputs that hash to 0" and keep the promise while totallybreaking your extraction function.But this paper says that if the attacker has to choose 2^t possibleinput distributions (based on t bits of control over the input)*before* the random parameter pi is chosen, then they're locked out.*After* learning pi, they can choose *which* of the 2^t inputdistributions to use.The thing is, you need a parameterized family of hash functions.They choose a random multiplier mod GF(2^n).  Their constructionis based on the well-known 2-universal family of hash functionshash(x) = (a*x+b) mod p.The /dev/random input mix is based on choosing a "random" polynomial(since there was a lot of efficiency pressure, it isn't actually veryrandom; the question is, is it non-random enough to help an attacker).Remiander modulo a uniformly chosen random irreducible polynomial is awell-known ("division hash") family of universal hash functions, butit's a little bit weaker than the above, and I have to figure out ofthe proof extends.-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`