Paper 2008/482

The Generic Hardness of Subset Membership Problems under the Factoring Assumption

Tibor Jager and Jörg Schwenk


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.

Note: Revised and significantly extended version.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Cryptographic assumptionssubset membershipquadratic residuositysubgroup decision problemgeneric ring algorithms
Contact author(s)
tibor jager @ rub de
2009-02-19: revised
2008-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tibor Jager and Jörg Schwenk},
      title = {The Generic Hardness of Subset Membership Problems under the Factoring Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2008/482},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.