International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Daniel R. L. Brown
Download:
URL: http://eprint.iacr.org/2007/435
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13715,
  title={Irreducibility to the One-More Evaluation Problems: More May Be Less},
  booktitle={IACR Eprint archive},
  keywords={foundations / irreduction, one-more evaluation, gap DHP},
  url={http://eprint.iacr.org/2007/435},
  note={ dbrown@certicom.com 13850 received 23 Nov 2007, last revised 3 Dec 2007},
  author={Daniel R. L. Brown},
  year=2007
}