IACR paper details
Title  Irreducibility to the OneMore Evaluation Problems: More May Be Less 

Booktitle  IACR Eprint archive 

Pages  

Year  2007 

URL  http://eprint.iacr.org/2007/435 

Author  Daniel R. L. Brown 

Abstract 
For a randomselfreducible function, the evaluation problem is
irreducible to the onemore evaluation problem, in the following
sense. An irreduction algorithm exists that, given a reduction
algorithm from the evaluation to the onemore evaluation problem,
solves a separator problem: the evaluation problem itself. Another
irreduction shows that if the computational DiffieHellman problem
is reduced to the gap DiffieHellman problem, then the decision
DiffieHellman 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 onemore variants of the RSA and discrete logarithm
problems may be easier than the standard variants, and that the gap
DiffieHellman problem may be easier than the standard
DiffieHellman problem.


Search for the paper
@misc{eprint200713715,
title={Irreducibility to the OneMore Evaluation Problems: More May Be Less},
booktitle={IACR Eprint archive},
keywords={foundations / irreduction, onemore 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
}
Download a complete BibTeX file.