Re: [math-fun] Goucher's suggested cryptosystem
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.
Also, with Goucher's system the preprocessing time (to determine p,q from key) is rather large, maybe of order N^4,
I can get O(N^3 log N log log N) by naive Miller-Rabin on every value in a range of length O(N), which will on average contain a prime by the prime number theorem. The constant factor can be heavily optimised by using trial division.
(And slower if use slow multiplication.) The security level is around N^(1/3) considering NFS integer factoring algorithm.
Are you saying that if I gave you a black box oracle capable of constant-time integer factorisation, you could break my cryptosystem? I highly doubt it, since there's no obvious way of determining M from the output of the BBS (which you can in turn only compute if you know both a sequence of ciphertext and corresponding plaintext).
So... asymptotic-wise, this sucks, it is even worse than everything I said before!
Well, you included an extra factor of N in the time it takes to multiply two numbers...
Elegance-wise, it is very neatly defined.
Thank you. Sincerely, Adam P. Goucher http://cp4space.wordpress.com
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
I wrote:
... 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.
It's maybe worth stressing that that's how conservative you need to be when using BBS if you want to avail yourself of the *proofs* of security it comes with. If you're content to say "No one knows a way to break BBS that's better than factoring the modulus, and no one knows a feasible way to factor 2048-bit numbers in reasonable time" then you can stick with your 2048-bit modulus and pulling out 32 bits from each squaring, and I guess you'll probably be OK in practice. But I'm not an expert on this stuff, and the paragraph above may be too optimistic. -- g
participants (2)
-
Adam P. Goucher -
Gareth McCaughan