tag:blogger.com,1999:blog-2752058700154467226.post983296615830499220..comments2020-08-08T17:19:12.696+01:00Comments on Bristol Cryptography Blog: Study group: RSA-based standard model signaturesNigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-2752058700154467226.post-5486125353605234252011-10-24T20:07:09.377+01:002011-10-24T20:07:09.377+01:00The bottleneck of the signing algorithm in {CS, Fi...The bottleneck of the signing algorithm in {CS, Fischlin, HW, ...} is the (deterministic or randomized) generation of the primes. As Nigel points out, generating a 160-bit prime takes considerably more CPU time than one standard RSA exponentiation. <br /><br />In our papers from Crypto 08 and Asiacrypt 11 we show techniques to decrease the size of the primes from 160 to 80 bits or less. In that case the signing algorithm of our strong RSA schemes is almost as efficient as that of RSA-FDH, with the price of a large public key. Our RSA schemes are still less efficient.<br /><br />I'm also curious to find out how efficient these schemes really are.Eikehttps://www.blogger.com/profile/11526803785298158097noreply@blogger.comtag:blogger.com,1999:blog-2752058700154467226.post-20217026506511441112011-10-20T14:51:38.659+01:002011-10-20T14:51:38.659+01:00The killer is the fact that you need, when signing...The killer is the fact that you need, when signing an m bit message, to apply the "hash function" m times. Each invocation of the hash function requires invoking a PRF an expected t times where 1/t is the probability of getting a prime number of the requisite size.<br /><br />So if signing a 160 bit hash (which is what would happen in practice), then CPU time is going to be roughly 160*t times slower than standard RSA (at least)Nigel Smarthttps://www.blogger.com/profile/17681184541012804026noreply@blogger.comtag:blogger.com,1999:blog-2752058700154467226.post-15591396408559635872011-10-20T14:39:54.782+01:002011-10-20T14:39:54.782+01:00Excellent post! I'm really curious how efficie...Excellent post! I'm really curious how efficient these would be in practice. Not because it's a big deal (the authors cheerfully admit that all the prime-finding is a killer), but because I think it's interesting to know what the options are if you want to stick with RSA.Matthew Greenhttps://www.blogger.com/profile/05041984203678598124noreply@blogger.com