CryptoDB
The Generic Hardness of Subset Membership Problems under the Factoring Assumption
Authors: | |
---|---|
Download: | |
Abstract: | We analyze a large class of subset membership problems related to integer factorization. We show that there is no algorithm solving these problems efficiently without exploiting properties of the given representation of ring elements, unless factoring integers is easy. Our results imply that problems with high relevance for a large number of cryptographic applications, such as the quadratic residuosity and the subgroup decision problems, are generically equivalent to factoring. |
BibTeX
@misc{eprint-2008-18096, title={The Generic Hardness of Subset Membership Problems under the Factoring Assumption}, booktitle={IACR Eprint archive}, keywords={Cryptographic assumptions, subset membership, quadratic residuosity, subgroup decision problem, generic ring algorithms}, url={http://eprint.iacr.org/2008/482}, note={ tibor.jager@rub.de 14294 received 14 Nov 2008, last revised 19 Feb 2009}, author={Tibor Jager and Jörg Schwenk}, year=2008 }