{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T14:01:39Z","timestamp":1717682499532},"reference-count":24,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"<jats:p>The aim of the discrete logarithm problem with auxiliary inputs is to solve for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline1\" \/><jats:tex-math>${\\it\\alpha}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, given the elements <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline2\" \/><jats:tex-math>$g,g^{{\\it\\alpha}},\\ldots ,g^{{\\it\\alpha}^{d}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of a cyclic group <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline3\" \/><jats:tex-math>$G=\\langle g\\rangle$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, of prime order\u00a0<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline4\" \/><jats:tex-math>$p$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The best-known algorithm, proposed by Cheon in 2006, solves for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline5\" \/><jats:tex-math>${\\it\\alpha}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in the case where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline6\" \/><jats:tex-math>$d\\mid (p\\pm 1)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, with a running time of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline7\" \/><jats:tex-math>$O(\\sqrt{p\/d}+d^{i})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> group exponentiations\u00a0(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline8\" \/><jats:tex-math>$i=1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline9\" \/><jats:tex-math>$1\/2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> depending on the sign). There have been several attempts to generalize this algorithm to the case of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline10\" \/><jats:tex-math>${\\rm\\Phi}_{k}(p)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline11\" \/><jats:tex-math>$k\\geqslant 3$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. However, it has been shown by Kim, Cheon and Lee that a better complexity cannot be achieved than that of the usual square root algorithms.<\/jats:p><jats:p>We propose a new algorithm for solving the DLPwAI. We show that this algorithm has a running time of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline12\" \/><jats:tex-math>$\\widetilde{O}(\\sqrt{p\/{\\it\\tau}_{f}}+d)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> group exponentiations, where\u00a0<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline13\" \/><jats:tex-math>${\\it\\tau}_{f}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the number of absolutely irreducible factors of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline14\" \/><jats:tex-math>$f(x)-f(y)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We note that this number is always smaller than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157015000303_inline15\" \/><jats:tex-math>$\\widetilde{O}(p^{1\/2})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>In addition, we present an analysis of a non-uniform birthday problem.<\/jats:p>","DOI":"10.1112\/s1461157015000303","type":"journal-article","created":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T05:08:32Z","timestamp":1454044112000},"page":"1-15","source":"Crossref","is-referenced-by-count":5,"title":["A new approach to the discrete logarithm problem with auxiliary\u00a0inputs"],"prefix":"10.1112","volume":"19","author":[{"given":"Jung Hee","family":"Cheon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taechan","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,1,1]]},"reference":[{"key":"S1461157015000303_r11","doi-asserted-by":"publisher","DOI":"10.3792\/pjaa.68.338"},{"key":"S1461157015000303_r13","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-67-03433-3"},{"key":"S1461157015000303_r9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.02.019"},{"key":"S1461157015000303_r2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_4"},{"key":"S1461157015000303_r15","first-page":"3","article-title":"Polynomials with minimal set of values and the equation f (x) = f (y) in a finite prime field","volume":"38","author":"Mit\u2019kin","year":"1985","journal-title":"Mat. Zametki"},{"key":"S1461157015000303_r21","first-page":"73","article-title":"On waiting time in the scheme of random allocation of coloured particies","volume":"5","author":"Selivanov","year":"1955","journal-title":"Discrete Math. Appl."},{"key":"S1461157015000303_r5","first-page":"1","volume-title":"Advances in cryptology - EUROCRYPT 2006","author":"Cheon","year":"2006"},{"key":"S1461157015000303_r1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_14"},{"key":"S1461157015000303_r14","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2014-02813-5"},{"key":"S1461157015000303_r4","unstructured":"4. D. R.\u00a0L. Brown and R.\u00a0P. Gallant , \u2018The static Diffie\u2013Hellman problem\u2019, IACR Cryptology ePrint Archive (2004), http:\/\/eprint.iacr.org\/2004\/306."},{"key":"S1461157015000303_r22","doi-asserted-by":"publisher","DOI":"10.3792\/pja\/1195525741"},{"key":"S1461157015000303_r12","doi-asserted-by":"publisher","DOI":"10.3792\/pjaa.74.16"},{"key":"S1461157015000303_r24","volume-title":"Sur les Courbes alg\u00e9briques et les vari\u00e9t\u00e9s qui s\u2019en d\u00e9duisent","author":"Weil","year":"1948"},{"key":"S1461157015000303_r8","first-page":"121","volume-title":"Selected areas in cryptography 2013","author":"Cheon","year":"2013"},{"key":"S1461157015000303_r19","first-page":"918","article-title":"Monte Carlo methods for index computation (modp)","volume":"32","author":"Pollard","year":"1978","journal-title":"Math. Comp."},{"key":"S1461157015000303_r3","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_16"},{"key":"S1461157015000303_r6","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-009-9047-0"},{"key":"S1461157015000303_r16","first-page":"481","article-title":"A new traitor tracing","volume":"E85","author":"Mitsunari","year":"2002","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"S1461157015000303_r23","volume-title":"Modern computer algebra","author":"von\u00a0zur Gathen","year":"2003"},{"key":"S1461157015000303_r10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(88)90064-9"},{"key":"S1461157015000303_r17","first-page":"234","volume-title":"CANS","author":"Mohassel","year":"2011"},{"key":"S1461157015000303_r18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00053956"},{"key":"S1461157015000303_r20","unstructured":"20. T. Satoh , On generalization of Cheon\u2019s algorithm, IACR Cryptology ePrint Archive (2009),http:\/\/eprint.iacr.org\/2009\/058."},{"key":"S1461157015000303_r7","volume-title":"MSJ-KMS Joint Meeting 2012","author":"Cheon","year":"2012"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157015000303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T20:07:47Z","timestamp":1555704467000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157015000303\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157015000303"],"URL":"https:\/\/doi.org\/10.1112\/s1461157015000303","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}