Re: [cryptography] What's the state of the art in factorization?

2010-07-11 Thread Francois Grieu
 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?

2010-07-09 Thread Paul Crowley

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?

2010-07-09 Thread Zooko O'Whielacronx
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