International Association
for Cryptologic Research

Abstract  The generic ring model considers algorithms that operate on elements of an algebraic ring by performing only the ring operations

and without exploiting properties of a given representation of ring elements. It is used to analyze the hardness of computational

problems defined over rings. For instance, it is known that breaking RSA is equivalent to factoring in the generic ring model

(Aggarwal and Maurer, Eurocrypt 2009). Do hardness results in the generic ring model support the conjecture that solving the considered problem is also hard in

the standard model, where elements of ℤ

n

are represented by integers modulo n?

We prove in the generic ring model that computing the Jacobi symbol of an integer modulo n is equivalent to factoring. Since there are simple and efficient non-generic algorithms which compute the Jacobi symbol,

this provides an example of a natural computational problem which is hard in the generic ring model, but easy to solve if

elements of ℤ

n

are given in their standard representation as integers. Thus, a proof in the generic ring model is unfortunately not a very

strong indicator for the hardness of a computational problem in the standard model.

Despite this negative result, generic hardness results still provide a lower complexity bound for a large class of algorithms,

namely all algorithms solving a computational problem independent of a given representation of ring elements. From this point

of view, results in the generic ring model are still interesting. Motivated by this fact, we also show that solving the quadratic

residuosity problem generically is equivalent to factoring.

• Content Type Journal Article
• Pages 1-21
• DOI 10.1007/s00145-012-9120-y
• Authors

  • Tibor Jager, Institut für Kryptographie und Sicherheit, Karlsruhe Institute of Technology, Karlsruhe, Germany
  • Jörg Schwenk, Horst Görtz Institute for IT Security, Ruhr-University Bochum, Bochum, Germany

• Journal Journal of Cryptology
• Online ISSN 1432-1378
• Print ISSN 0933-2790

From: Thu, 08 Mar 2012 06:51:31 GMT