{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T22:45:13Z","timestamp":1648766713223},"reference-count":25,"publisher":"American Mathematical Society (AMS)","issue":"288","license":[{"start":{"date-parts":[[2015,2,11]],"date-time":"2015-02-11T00:00:00Z","timestamp":1423612800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We investigate a recently proposed algorithm solving the strong discrete logarithm problem with auxiliary inputs, and show that this algorithm in general is not more efficient than ordinary discrete-logarithm-solving algorithms such as Pollard\u2019s rho method, by analyzing a lower bound on the sum of digits of integers.<\/p>","DOI":"10.1090\/s0025-5718-2014-02813-5","type":"journal-article","created":{"date-parts":[[2014,2,11]],"date-time":"2014-02-11T13:17:31Z","timestamp":1392124651000},"page":"1993-2004","source":"Crossref","is-referenced-by-count":5,"title":["Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs"],"prefix":"10.1090","volume":"83","author":[{"given":"Minkyu","family":"Kim","sequence":"first","affiliation":[]},{"given":"Jung Hee","family":"Cheon","sequence":"additional","affiliation":[]},{"given":"In-Sok","family":"Lee","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2014,2,11]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-540-24676-3_14","article-title":"Efficient selective-ID secure identity-based encryption without random oracles","author":"Boneh, Dan","year":"2004"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00145-007-9005-7","article-title":"Short signatures without random oracles and the SDH assumption in bilinear groups","volume":"21","author":"Boneh, Dan","year":"2008","journal-title":"J. Cryptology","ISSN":"http:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","unstructured":"D. Boneh, X. Boyen, and E. Goh, Hierarchical identity based encryption without constant size ciphertext, in Proceedings of Eurocrypt 2005, LNCS 3494, pp. 440-456, 2005.","DOI":"10.1007\/11426639_26"},{"key":"4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-28628-8_3","article-title":"Short group signatures","author":"Boneh, Dan","year":"2004"},{"key":"5","unstructured":"D. R. L. Brown and R. P. Gallant, The static Diffie-Hellman problem, Cryptology ePrint Archive, Report no. 2004\/306, 2004. Available from http:\/\/eprint.iacr.org\/2004\/306."},{"key":"6","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11535218_16","article-title":"Collusion resistant broadcast encryption with short ciphertexts and private keys","author":"Boneh, Dan","year":"2005"},{"key":"7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-85538-5_3","article-title":"The uber-assumption family: a unified complexity framework for bilinear groups","author":"Boyen, Xavier","year":"2008"},{"key":"8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11761679_1","article-title":"Security analysis of the strong Diffie-Hellman problem","author":"Cheon, Jung Hee","year":"2006"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s00145-009-9047-0","article-title":"Discrete logarithm problems with auxiliary inputs","volume":"23","author":"Cheon, Jung Hee","year":"2010","journal-title":"J. Cryptology","ISSN":"http:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/0-387-34799-2_38","article-title":"Diffie-Hellman is as strong as discrete log for certain primes","author":"den Boer, Bert","year":"1990"},{"issue":"6","key":"11","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/tit.1976.1055638","article-title":"New directions in cryptography","volume":"IT-22","author":"Diffie, Whitfield","year":"1976","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"12","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-540-85538-5_2","article-title":"Pairing lattices","author":"Hess, Florian","year":"2008"},{"key":"13","unstructured":"A. A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady, Vol. 7, pp. 595\u2013596, 1963."},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"http:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"15","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/3-540-48658-5_26","article-title":"Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms","author":"Maurer, Ueli M.","year":"1994"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1137\/S0097539796302749","article-title":"The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms","volume":"28","author":"Maurer, Ueli M.","year":"1999","journal-title":"SIAM J. Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"17","unstructured":"H. Minkowski, Geometrie der Zahlen, Leipzig und Berlin, Druck und Verlag von B. G. Teubner, 1910."},{"key":"18","unstructured":"S. Mitsunari, R. Sakai, and M. Kasahara, A new traitor tracing, IEICE Trans. Fundamentals, Vol. E58-A, No. 2, pp. 481-484, 2002."},{"key":"19","volume-title":"Introduction to number theory","author":"Nagell, Trygve","year":"1964","edition":"2"},{"key":"20","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/11681878_5","article-title":"Efficient blind and partially blind signatures without random oracles","author":"Okamoto, Tatsuaki","year":"2006"},{"issue":"143","key":"21","doi-asserted-by":"publisher","first-page":"918","DOI":"10.2307\/2006496","article-title":"Monte Carlo methods for index computation (\ud835\udc5a\ud835\udc5c\ud835\udc51\ud835\udc5d)","volume":"32","author":"Pollard, J. M.","year":"1978","journal-title":"Math. Comp.","ISSN":"http:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"22","unstructured":"T. Satoh, On generalization of Cheon\u2019s algorithms, Cryptology ePrint Archive, Report no. 2009\/058, 2009. Available from http:\/\/eprint.iacr.org\/2009\/058."},{"key":"23","first-page":"415","article-title":"Class number, a theory of factorization, and genera","author":"Shanks, Daniel","year":"1971"},{"key":"24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"http:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"25","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2003","ISBN":"http:\/\/id.crossref.org\/isbn\/0521826462","edition":"2"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-288\/S0025-5718-2014-02813-5\/S0025-5718-2014-02813-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-288\/S0025-5718-2014-02813-5\/S0025-5718-2014-02813-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T05:38:17Z","timestamp":1627623497000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-288\/S0025-5718-2014-02813-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,11]]},"references-count":25,"journal-issue":{"issue":"288","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["S0025-5718-2014-02813-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02813-5","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,11]]}}}