[145240] in cryptography@c2.net mail archive
Re: What's the state of the art in factorization?
daemon@ATHENA.MIT.EDU (Samuel Neves)
Wed Apr 21 22:06:45 2010
Date: Thu, 22 Apr 2010 00:29:33 +0100
From: Samuel Neves <sneves@dei.uc.pt>
To: cryptography@metzdowd.com
In-Reply-To: <20100421014035.GD24404@np305c2n2.ms.com>
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
On 21-04-2010 02:40, Victor Duchovni wrote:
> EC definitely has practical merit. Unfortunately the patent issues around
> protocols using EC public keys are murky.
>
> Neither RSA nor EC come with complexity proofs.
>
While EC (by that I assume you mean ECDSA) does not have a formal
security proof, i.e., it is as hard as the EC discrete log, it it much
closer to one than RSA is to factoring. In particular, Pointcheval and
Stern, and later Brown come close to a formal proof for ECDSA [1].
If one goes further into other schemes, there is Rabin-Williams for the
factoring problem. There are also the schemes by Goh et al. [2] that are
reducible to the CDH and DDH problems in generic abelian groups (like
EC.) Would patents also apply to one of these schemes over an elliptic
curve?
Best regards,
Samuel Neves
[1] http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-54.ps
[2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
