4 ms·
> What the paper shows is that often it is assumed that words drawn from an IID distribution of letters can be treated as if the distribution of words is unifor
by tveita 13y ago
> What the paper shows is that often it is assumed that words drawn from an IID distribution of letters can be treated as if the distribution of words is uniform
Is this assumption really that common? It seems like a strange assumption to make, since even biased coin flips with P(Head) = 0.99 would be independent and identically distributed.
- CatMtKing 13y agoThat doesn't sound identically distributed to me... am I missing something?
- thesteamboat 13y agoIt's not that the P(heads)=P(tails), but rather the coins are identical to each other. Each throw of the coin has the same probability and is independent of other throws of the coin.
- timtadh 13y agoNot being any sort of expert I don't know how important their result is. They cite a couple of papers in which use AEP (Asymptotic Equipartition Property) to treat words drawn from IID distributions of letters as uniform. The paper I looked at was in turn about brute force attacks. So essentially this paper is arguing that analysis of brute force attacks must necessarily account for the non-uniform structure of the source distribution. On the surface it seems like this only really effects things which rely on treating these types of distributions. It is difficult for me to say how this effects the analysis of primitives when using keys derived from user input. In practice I don't think it makes much difference as we are already getting quite good at exploiting the distributions from which people seem to draw passwords. However, it may have some important implications for the theoretical side of cryptography.