0
$\begingroup$

Is there any (current) cryptosystem or digital signature or cryptographic primitive that uses the BBS PRG in order to generate its secret keys?

$\endgroup$
  • 2
    $\begingroup$ Why do you ask? $\endgroup$ – CodesInChaos Jan 3 '15 at 21:10
4
$\begingroup$

I don't know of any implementations that use BBS. I hope no important system is using BBS. BBS is a poor choice for practical use. The only benefit it has is that it comes with some security proofs -- but it turns out that those proofs are useless for all practical instantiations of BBS (for realistic parameter settings), so they're pretty much irrelevant in practice. See Blum Blum Shub vs. AES-CTR or other CSPRNGs for details.

$\endgroup$
  • $\begingroup$ I saw the link you suggested, and I understand that BBS with a "logical "modulus (say at most 4096 bits) does not come with a security proof, which does not imply that it is not secure. $\endgroup$ – 111 Jan 5 '15 at 11:25
  • 2
    $\begingroup$ @111, right, but: if it doesn't have a security proof, then BBS has no advantages over competing schemes, so there would be no good reason to choose BBS. $\endgroup$ – D.W. Jan 5 '15 at 23:13
1
$\begingroup$

I am not aware of any implementation of this proposal, but it should be secure: Usually, when theoretically designing a cryptosystem, one assumes access to a good (pseudo)randomness source without precisely specifying its nature. It is certainly possible to use a Blum-Blum-Shub generator, but care must be taken that its modulus and initial state are chosen in a secure way: the generated random sequence is just as weak as the seed, so a system that does this must have access to a good entropy source, which you could just use instead. In case this is undesirable (for instance, when the entropy source yields bits very slowly or becomes unavailable after initialization), stretching an initial high-entropy seed using any cryptographically secure pseudo-random number generator should be good. However, Blum-Blum-Shub is very slow compared to other generators (such as, for instance, Keccak/SHA3), which is likely the reason this design is not used in practice with Blum-Blum-Shub.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.