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
-
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}
}
