International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Generic Hardness of Subset Membership Problems under the Factoring Assumption

Authors:
Tibor Jager
Jörg Schwenk
Download:
URL: http://eprint.iacr.org/2008/482
Search ePrint
Search Google
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
}