What's the state of the art in factorization?

[Samuel Neves]

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 at metzdowd.com