The Generic Hardness of Subset Membership Problems under the Factoring Assumption

Tibor Jager; Jörg Schwenk

Paper 2008/482 Original: eprint.iacr.org/2008/482 ↗

The Generic Hardness of Subset Membership Problems under the Factoring Assumption

Tibor Jager

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2009-02-19: last updated; 2008-11-19: published
Short URL: https://ia.cr/2008/482
License: https://creativecommons.org/licenses/by/4.0/

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