Paper 2007/435

Irreducibility to the One-More Evaluation Problems: More May Be Less

Daniel R. L. Brown

Abstract

For a random-self-reducible function, the evaluation problem is irreducible to the one-more evaluation problem, in the following sense. An irreduction algorithm exists that, given a reduction algorithm from the evaluation to the one-more evaluation problem, solves a separator problem: the evaluation problem itself. Another irreduction shows that if the computational Diffie-Hellman problem is reduced to the gap Diffie-Hellman problem, then the decision Diffie-Hellman problem is easy. Irreductions are primarily of theoretical interest, because they do not actually prove inequivalence between problems. What these irreductions suggest, though, is that one-more variants of the RSA and discrete logarithm problems may be easier than the standard variants, and that the gap Diffie-Hellman problem may be easier than the standard Diffie-Hellman problem.

Note: Minor changes.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
irreductionone-more evaluationgap DHP
Contact author(s)
dbrown @ certicom com
History
2010-06-09: last of 4 revisions
2007-11-24: received
See all versions
Short URL
https://ia.cr/2007/435
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/435,
      author = {Daniel R.  L.  Brown},
      title = {Irreducibility to the One-More Evaluation Problems: More May Be Less},
      howpublished = {Cryptology ePrint Archive, Paper 2007/435},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/435}},
      url = {https://eprint.iacr.org/2007/435}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.