{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:50:50Z","timestamp":1778215850458,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,12,11]],"date-time":"2009-12-11T00:00:00Z","timestamp":1260489600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s00145-009-9047-0","type":"journal-article","created":{"date-parts":[[2009,12,10]],"date-time":"2009-12-10T14:58:02Z","timestamp":1260457082000},"page":"457-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":40,"title":["Discrete Logarithm Problems with Auxiliary Inputs"],"prefix":"10.1007","volume":"23","author":[{"given":"Jung Hee","family":"Cheon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,11]]},"reference":[{"key":"9047_CR1","unstructured":"M. Abdalla, M. Bellare, P. Rogaway, DHAES: An encryption scheme based on Diffie\u2013Hellman problem. IEEE P1363a Submission (1998). Available at \n                    http:\/\/grouper.ieee.org\/groups\/1363\/addendum.html"},{"key":"9047_CR2","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","volume":"55","author":"E. Bach","year":"1990","unstructured":"E. Bach, Explicit bounds for primality testing and related problems. Math. Comput.\n                           55, 355\u2013380 (1990)","journal-title":"Math. Comput."},{"key":"9047_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-540-24676-3_14","volume-title":"Proceedings of Eurocrypt 2004","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in Proceedings of Eurocrypt 2004, LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 223\u2013238"},{"key":"9047_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/978-3-540-24676-3_4","volume-title":"Proceedings of Eurocrypt 2004","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, X. Boyen, Short signatures without random oracles, in Proceedings of Eurocrypt 2004, LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 56\u201373"},{"issue":"3","key":"9047_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00145-007-9005-7","volume":"21","author":"D. Boneh","year":"2008","unstructured":"D. Boneh, X. Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol.\n                           21(3), 149\u2013177 (2008)","journal-title":"J. Cryptol."},{"key":"9047_CR6","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-44448-3_3","volume-title":"Proceedings of Asiacrypt 2000","author":"D. Boneh","year":"2000","unstructured":"D. Boneh, A. Joux, P. Nguyen, Why textbook ElGamal and RSA encryption are insecure, in Proceedings of Asiacrypt 2000, LNCS, vol. 1976 (Springer, Berlin, 2000), pp. 30\u201343"},{"key":"9047_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-540-28628-8_3","volume-title":"Proceedings of Crypto 2004","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Proceedings of Crypto 2004, LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 41\u201355"},{"issue":"4","key":"9047_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00145-004-0314-9","volume":"17","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing. J. Cryptol.\n                           17(4), 297\u2013319 (2004). Extended abstract in proceedings of Asiacrypt 2001, LNCS, vol. 2248 (Springer, Berlin, 2001), pp. 514\u2013532","journal-title":"J. Cryptol."},{"key":"9047_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/11426639_26","volume-title":"Proceedings of Eurocrypt 2005","author":"D. Boneh","year":"2005","unstructured":"D. Boneh, X. Boyen, E. Goh, Hierarchical identity based encryption with constant size ciphertext, in Proceedings of Eurocrypt 2005, LNCS, vol. 3494 (Springer, Berlin, 2005), pp. 440\u2013456. A full paper is available in \n                    http:\/\/crypto.stanford.edu\/~dabo\/papers\/shibe.pdf"},{"key":"9047_CR10","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/11535218_16","volume-title":"Proceedings of Crypto 2005","author":"D. Boneh","year":"2005","unstructured":"D. Boneh, C. Gentry, B. Waters, Collution resistant broadcast encryption with short ciphertexts and private keys, in Proceedings of Crypto 2005, LNCS, vol. 3621 (Springer, Berlin, 2005), pp. 258\u2013275"},{"key":"9047_CR11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-36288-6_3","volume-title":"Proceedings of Public Key Cryptography 2003","author":"A. Boldyreva","year":"2003","unstructured":"A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the Gap\u2013Diffie\u2013Hellman-group signature scheme, in Proceedings of Public Key Cryptography 2003, LNCS, vol. 2567 (Springer, Berlin, 2003), pp. 31\u201346"},{"key":"9047_CR12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-85538-5_3","volume-title":"Proceedings of Pairing 2008","author":"X. Boyen","year":"2008","unstructured":"X. Boyen, The uber-assumption family\u2014a unified complexity framework for bilinear groups, in Proceedings of Pairing 2008, LNCS, vol. 5209 (Springer, Berlin, 2008), pp. 39\u201356"},{"key":"9047_CR13","unstructured":"D. Brown, R. Gallant, The static Diffie\u2013Hellman problem. Available in \n                    http:\/\/eprint.iacr.org\/2004\/306"},{"key":"9047_CR14","series-title":"LNCS","first-page":"275","volume-title":"Proceedings of Eurocrypt 1994","author":"M. Burmester","year":"1994","unstructured":"M. Burmester, Y. Desmedt, A secure and efficient conference key distribution system (Extended Abstract), in Proceedings of Eurocrypt 1994, LNCS, vol. 950 (Springer, Berlin, 1994), pp. 275\u2013286"},{"key":"9047_CR15","series-title":"LNCS","first-page":"1","volume-title":"Proceedings of Eurocrypt 2006","author":"J. Cheon","year":"2006","unstructured":"J. Cheon, Security analysis of the strong Diffie\u2013Hellman problem, in Proceedings of Eurocrypt 2006, LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 1\u201311"},{"key":"9047_CR16","series-title":"LNCS","first-page":"530","volume-title":"Proceedings of Crypto\u00a0\u201988","author":"B. Boer den","year":"1989","unstructured":"B. den Boer, Diffie\u2013Hellman is as strong as discrete log for certain primes, in Proceedings of Crypto\u00a0\u201988, LNCS, vol. 403 (Springer, Berlin, 1989), pp. 530\u2013539"},{"key":"9047_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/978-3-540-30580-4_28","volume-title":"Proceedings of Public Key Cryptography 2005","author":"Y. Dodis","year":"2005","unstructured":"Y. Dodis, A. Yampolskiy, A verifiable random function with short proofs and keys, in Proceedings of Public Key Cryptography 2005, LNCS, vol. 3386 (Springer, Berlin, 2005), pp. 416\u2013431"},{"issue":"4","key":"9047_CR18","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. Elgamal","year":"1985","unstructured":"T. Elgamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory\n                           31(4), 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9047_CR19","doi-asserted-by":"crossref","unstructured":"K. Ford, The distribution of integers with a divisor in a given interval. Ann. Math. (2008, to appear)","DOI":"10.4007\/annals.2008.168.367"},{"issue":"16","key":"9047_CR20","doi-asserted-by":"publisher","first-page":"3113","DOI":"10.1016\/j.dam.2007.12.010","volume":"156","author":"S. Galbraith","year":"2008","unstructured":"S. Galbraith, K. Paterson, N. Smart, Pairings for cryptographers. Discrete Appl. Math.\n                           156(16), 3113\u20133121 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9047_CR21","first-page":"216","volume-title":"Proceedings of Eurocrypt \u201984","author":"J. Gordon","year":"1984","unstructured":"J. Gordon, Strong primes are easy to find, in Proceedings of Eurocrypt \u201984 (Springer, Berlin, 1984), pp. 216\u2013223"},{"key":"9047_CR22","doi-asserted-by":"crossref","unstructured":"D. Jao, K. Yoshida, Boneh\u2013Boyen signatures and the strong Diffie-Hellman problem, in Proceedings of Pairing (2009, to appear)","DOI":"10.1007\/978-3-642-03298-1_1"},{"key":"9047_CR23","doi-asserted-by":"crossref","unstructured":"N. Koblitz, A. Menezes, Pairing-based cryptography at high security levels, in Proceedings of IMA Conference of Cryptography and Coding 2005, pp. 13\u201336","DOI":"10.1007\/11586821_2"},{"key":"9047_CR24","series-title":"LNCS","first-page":"302","volume-title":"Proceedings of Pairing 2007","author":"S. Kozaki","year":"2007","unstructured":"S. Kozaki, T. Kutsuma, K. Matsuo, Remarks on Cheon\u2019s algorithms for pairing-related problems, in Proceedings of Pairing 2007, LNCS, vol. 4575 (Springer, Berlin, 2007), pp. 302\u2013316"},{"issue":"5","key":"9047_CR25","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1137\/S0097539796302749","volume":"28","author":"U. Maurer","year":"1999","unstructured":"U. Maurer, S. Wolf, The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms. SIAM J. Comput.\n                           28(5), 1689\u20131721 (1999)","journal-title":"SIAM J. Comput."},{"key":"9047_CR26","volume-title":"Handbook of Applied Cryptography","author":"A. Menezes","year":"1996","unstructured":"A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1996)"},{"issue":"2","key":"9047_CR27","first-page":"481","volume":"E85-A","author":"S. Mitsunari","year":"2002","unstructured":"S. Mitsunari, R. Sakai, M. Kasahara, A new traitor tracing. IEICE Trans. Fundam.\n                           E85-A(2), 481\u2013484 (2002)","journal-title":"IEICE Trans. Fundam."},{"key":"9047_CR28","first-page":"91","volume":"55","author":"V. Nechaev","year":"1994","unstructured":"V. Nechaev, Complexity of a deterministic algorithm for the discrete logarithm. Math. Zamet.\n                           55, 91\u2013101 (1994). English translation in Math. Notes\n                           55(2), 165\u2013172 (1994)","journal-title":"Math. Zamet."},{"key":"9047_CR29","series-title":"LNCS","first-page":"80","volume-title":"Proceedings in TCC 2006","author":"T. Okamoto","year":"2006","unstructured":"T. Okamoto, Efficient blind and partially blind signatures without random oracles, in Proceedings in TCC 2006, LNCS, vol. 3876 (Springer, Berlin, 2006), pp. 80\u201399"},{"key":"9047_CR30","doi-asserted-by":"publisher","first-page":"918","DOI":"10.2307\/2006496","volume":"32","author":"J. Pollard","year":"1978","unstructured":"J. Pollard, Monte Carlo methods for index computation (mod\u2009p). Math. Comput.\n                           32, 918\u2013924 (1978)","journal-title":"Math. Comput."},{"issue":"4","key":"9047_CR31","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s001450010010","volume":"13","author":"J. Pollard","year":"2000","unstructured":"J. Pollard, Kangaroos, monopoly and discrete logarithms. J. Cryptol.\n                           13(4), 437\u2013447 (2000)","journal-title":"J. Cryptol."},{"key":"9047_CR32","unstructured":"Recommended Elliptic Curves for Federal Government Use, Available at \n                    http:\/\/csrc.nist.gov\/CryptoToolkit\/dss\/ecdsa\/NISTReCur.pdf\n                    \n                  , 1999"},{"key":"9047_CR33","unstructured":"T. Satoh, On generalization of Cheon\u2019s algorithms. Preprint, 2008"},{"key":"9047_CR34","unstructured":"M. Scott, Multiprecision Integer and Rational Arithmetic C\/C++ Library. Available at \n                    http:\/\/indigo.ie\/~mscott\/"},{"key":"9047_CR35","doi-asserted-by":"publisher","first-page":"369","DOI":"10.2307\/2153041","volume":"58","author":"V. Shoup","year":"1992","unstructured":"V. Shoup, Searching for primitive roots in finite fields. Math. Comput.\n                           58, 369\u2013380 (1992)","journal-title":"Math. Comput."},{"key":"9047_CR36","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"Proceedings of Eurocrypt \u201997","author":"V. Shoup","year":"1997","unstructured":"V. Shoup, Lower bounds for discrete logarithms and related problems, in Proceedings of Eurocrypt \u201997, LNCS, vol. 1233 (Springer, Berlin, 1997), pp. 256\u201366"},{"key":"9047_CR37","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139165464","volume-title":"A Computational Introduction to Number Theory and Algebra","author":"V. Shoup","year":"2005","unstructured":"V. Shoup, A Computational Introduction to Number Theory and Algebra (Cambridge University Press, Cambridge, 2005)"},{"key":"9047_CR38","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(95)00164-6","volume":"157","author":"I. Shparlinski","year":"1996","unstructured":"I. Shparlinski, On finding primitive roots in finite fields. Theor. Comput. Sci.\n                           157, 273\u2013275 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9047_CR39","unstructured":"D. Sun, Elliptic curves with the minimized security loss of the strong Diffie\u2013Hellman problem, Ph.D. Dissertation, Seoul National University, 2007. Available at \n                    http:\/\/library.snu.ac.kr\/DetailView.jsp?uid=4&cid=2857710"},{"key":"9047_CR40","volume-title":"Introduction to Analytic and Probabilistic Number Theory","author":"G. Tenenbaum","year":"1995","unstructured":"G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory (Cambridge University Press, Cambridge, 1995)"},{"key":"9047_CR41","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/BFb0054891","volume-title":"Proceedings of Algorithmic Number Theory Symposium III","author":"E. Teske","year":"1998","unstructured":"E. Teske, Speeding up Pollard\u2019s rho method for computing discrete logarithms, in Proceedings of Algorithmic Number Theory Symposium III, LNCS, vol. 1423 (Springer, Berlin, 1998), pp. 541\u2013554"},{"issue":"1","key":"9047_CR42","first-page":"1","volume":"10","author":"Y. Wang","year":"1961","unstructured":"Y. Wang, On the least primitive root of a prime. Sci. Sin.\n                           10(1), 1\u201314 (1961)","journal-title":"Sci. Sin."},{"key":"9047_CR43","unstructured":"K. Yoshida, Boneh\u2013Boyen signatures and the strong Diffie\u2013Hellman problem, Master Thesis, University of Waterloo, 2009. Available at \n                    http:\/\/uwspace.uwaterloo.ca\/handle\/10012\/4219"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9047-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-009-9047-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9047-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9047-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:44:01Z","timestamp":1586335441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-009-9047-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,11]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["9047"],"URL":"https:\/\/doi.org\/10.1007\/s00145-009-9047-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,11]]},"assertion":[{"value":"10 April 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2009","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}