Cryptology ePrint Archive: Report 2008/286

One-Up Problem for (EC)DSA

Daniel R. L. Brown

Abstract: The one-up problem is defined for any group and a function from the group to integers. An instance of problem consists of two points in the group. A solution consists of another point satisfying an equation involving the group and the function. The one-up problem must be hard for the security of (EC)DSA. Heuristic arguments are given for the independence of the discrete log and one-up problems. DSA and ECDSA are conjectured to be secure if the discrete log and one-up problems are hard and the hash is collision resistant.

Category / Keywords: public-key cryptography / DSA, ECDSA

Date: received 25 Jun 2008

Contact author: dbrown at certicom com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20080703:185816 (All versions of this report)

Short URL: ia.cr/2008/286

Discussion forum: Show discussion | Start new discussion