Paper 2009/621
On the Analysis of Cryptographic Assumptions in the Generic Ring Model
Tibor Jager and Jörg Schwenk
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 $\Z_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 nongeneric 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 $\Z_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. Thus, from this point of view results in the generic ring model are still interesting. Motivated by this fact, we show also that solving the quadratic residuosity problem generically is equivalent to factoring.
Note: Revision includes some simplifications and corrections.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Full version of Asiacrypt 2009 paper
 Keywords
 Generic ring modelanalysis of cryptographic assumptions
 Contact author(s)
 tibor jager @ rub de
 History
 20120125: last of 6 revisions
 20091217: received
 See all versions
 Short URL
 https://ia.cr/2009/621
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/621, author = {Tibor Jager and Jörg Schwenk}, title = {On the Analysis of Cryptographic Assumptions in the Generic Ring Model}, howpublished = {Cryptology ePrint Archive, Paper 2009/621}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/621}}, url = {https://eprint.iacr.org/2009/621} }