Cryptology ePrint Archive: Report 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.
Category / Keywords: Cryptographic assumptions, subset membership, quadratic residuosity, subgroup decision problem, generic ring algorithms
Date: received 14 Nov 2008, last revised 19 Feb 2009
Contact author: tibor jager at rub de
Available formats: PDF | BibTeX Citation
Note: Revised and significantly extended version.
Version: 20090219:122851 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]