On the ana­ly­sis of cryp­to­gra­phic as­sump­ti­ons in the ge­ne­ric ring model

Tibor Jager, Jörg Schwenk

Jour­nal of Cryp­to­lo­gy

Ab­stract

The ge­ne­ric ring model con­s­i­ders al­go­rith­ms that ope­ra­te on ele­ments of an al­ge­braic ring by per­for­ming only the ring ope­ra­ti­ons and wi­thout ex­ploit­ing pro­per­ties of a given re­pre­sen­ta­ti­on of ring ele­ments. It is used to ana­ly­ze the hard­ness of com­pu­ta­tio­nal pro­blems de­fined over rings. For in­stan­ce, it is known that brea­king RSA is equi­va­lent to fac­to­ring in the ge­ne­ric ring model (Ag­gar­wal and Mau­rer, Eu­ro­crypt 2009). Do hard­ness re­sults in the ge­ne­ric ring model sup­port the con­jec­tu­re that sol­ving the con­s­i­de­red pro­blem is also hard in the stan­dard model, where ele­ments of $Z_n$ are re­pre­sen­ted by in­te­gers mo­du­lo $n$?

We prove in the ge­ne­ric ring model that com­pu­ting the Ja­co­bi sym­bol of an in­te­ger mo­du­lo $n$ is equi­va­lent to fac­to­ring. Since there are sim­ple and ef­fi­ci­ent non-ge­ne­ric al­go­rith­ms which com­pu­te the Ja­co­bi sym­bol, this pro­vi­des an ex­amp­le of a na­tu­ral com­pu­ta­tio­nal pro­blem which is hard in the ge­ne­ric ring model, but easy to solve if ele­ments of $Z_n$ are given in their stan­dard re­pre­sen­ta­ti­on as in­te­gers. Thus, a proof in the ge­ne­ric ring model is un­for­t­u­n­a­te­ly not a very strong in­di­ca­tor for the hard­ness of a com­pu­ta­tio­nal pro­blem in the stan­dard model.

De­s­pi­te this ne­ga­ti­ve re­sult, ge­ne­ric hard­ness re­sults still pro­vi­de a lower com­ple­xi­ty bound for a large class of al­go­rith­ms, na­me­ly all al­go­rith­ms sol­ving a com­pu­ta­tio­nal pro­blem in­de­pen­dent of a given re­pre­sen­ta­ti­on of ring ele­ments. Thus, from this point of view re­sults in the ge­ne­ric ring model are still in­te­res­ting. Mo­ti­va­ted by this fact, we show also that sol­ving the qua­dra­tic re­si­duo­si­ty pro­blem ge­ne­ri­cal­ly is equi­va­lent to fac­to­ring.

Tags: