Cryptology ePrint Archive: Report 2007/442

Another Look at Non-Standard Discrete Log and Diffie-Hellman Problems

Neal Koblitz and Alfred Menezes

Abstract: We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these non-standard problems.

Category / Keywords: public-key cryptography /

Publication Info: Also available at http://anotherlook.ca

Date: received 26 Nov 2007, last revised 15 Aug 2011

Contact author: ajmeneze at uwaterloo ca

Available formats: PDF | BibTeX Citation

Version: 20110815:115328 (All versions of this report)

Discussion forum: Show discussion | Start new discussion