Paper 2008/482

The Generic Hardness of Subset Membership Problems under the Factoring Assumption

Tibor Jager and Jörg Schwenk

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.

Note: Revised and significantly extended version.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cryptographic assumptionssubset membershipquadratic residuositysubgroup decision problemgeneric ring algorithms
Contact author(s)
tibor jager @ rub de
History
2009-02-19: revised
2008-11-19: received
See all versions
Short URL
https://ia.cr/2008/482
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/482,
      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},
      url = {https://eprint.iacr.org/2008/482}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.