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