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 $\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.Category / Keywords: foundations / Generic ring model, analysis of cryptographic assumptions Publication Info: Full version of Asiacrypt 2009 paper Date: received 17 Dec 2009, last revised 25 Jan 2012 Contact author: tibor jager at rub de Available format(s): PDF | BibTeX Citation Note: Revision includes some simplifications and corrections. Version: 20120125:215630 (All versions of this report) Discussion forum: Show discussion | Start new discussion