On 19/08/2013 10:27, Adam P. Goucher wrote:
Warren wrote:
The time consumption here seems to be with fast multiplication about N^2 * logN ops per plaintext bit which for N bit message and key would be N^3 * logN.
What?!
Multiplication takes O(N log N log log N), not O(N^2 log N). There's a very big difference. (It only takes one multiplication per loop.)
Also, by the way, I think to get theoretical nirvana with BlumBlumShub you must only use one bit of r at a time, not 32 bits (right?) costing a factor 32 work.
No, that's unnecessary. The last 32 bits will certainly be uniformly distributed (up to a ridiculously microscopic difference) amongst the 2^32 possibilities, and the significant bits of r will sufficiently mess up any possible patterns between consecutive words outputted by Blum-Blum-Shub.
According to the WP article on BBS, the bits are only guaranteed random enough if you use "O(log log M) lower-order bits of each x_n" where M is the modulus. You were proposing M~=2^2048 so log log M is about 11. ... But there's a paper by Koblitz and Menezes ("Another look at provable security, II") that (so it claims; I haven't checked the details) actually works through the analysis with numbers rather than O(...) everywhere, and it turns out that for numbers of this sort of size you end up with no useful security guarantee at all! (That is, the implicit constants in the various O()s screw you over.) Before you get anything useful you need moduli about 5000 bits in length (extracting a single bit from each squaring), at which case the attacker needs to do something like 2^84 operations to break the cipher. If Koblitz and Menezes are right, BBS doesn't seem like an attractive option, despite its elegance. For a bit more, see the top answer to this crypto.stackexchange.com question: http://crypto.stackexchange.com/questions/3454/blum-blum-shub-vs-aes-ctr-or-... -- g