Re: [cryptography] What's the state of the art in factorization?
On 23/04/2010 11:57, Paul Crowley wrote: [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? There is RSA or Rabin using a signature scheme with message recovery. With a public modulus of n bits, and a hash of h bits, signing a message adds only h bits, as long as - the message to sign is at least (n-h) bits and - you do not care about spending a few modular multiplication to recover some (n-h) bits of the message [where few is 17, 2 or 1 for popular public exponents e of 65537, 3, 2] This is standardized by ISO/IEC 9796-2 (which add a few bits of overhead to h, like 16 when n is a multiple of 8). It is used (with a deprecated and not-quite-perfect option set of ISO/IEC 9796-2) in many applications where size matters, in particular EMV Smart Cards, and the European Digital Tachograph. With e=2 and the newer (randomized) schemes of ISO/IEC 9796-2, you get security provably related to factoring or breaking the hash. François Grieu [I suddenly got a batch of old messages, and wonder what is the appropriate list address] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [cryptography] What's the state of the art in factorization?
Jonathan Katz wrote: [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf On the other hand, there is one published scheme that gives a slight improvement to our paper (it has fewer on-line computations): it is a paper by Chevallier-Mames in Crypto 2005 titled An Efficient CDH-Based Signature Scheme with a Tight Security Reduction. My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? Incidentally, the paper doesn't note this but that second scheme has a non-tight reduction to the discrete log problem in exactly the way that Schnorr does. -- __ \/ o\ Paul Crowley, p...@ciphergoth.org /\__/ http://www.ciphergoth.org/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [cryptography] What's the state of the art in factorization?
On Fri, Apr 23, 2010 at 3:57 AM, Paul Crowley p...@ciphergoth.org wrote: My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? http://eprint.iacr.org/2007/019 Has one. Caveat lector. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
