{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:18:59Z","timestamp":1776784739830,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"252","license":[{"start":{"date-parts":[[2006,4,5]],"date-time":"2006-04-05T00:00:00Z","timestamp":1144195200000},"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":"

\n Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a\n hidden<\/italic>\n element\n \n \n \n \n \n \u03b1\n \n <\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n \n \n F<\/mml:mi>\n <\/mml:mrow>\n p<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n \\alpha \\in \\mathbb {F}_p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is prime, from rather short strings of the most significant bits of the residue of\n \n \n \n \n \n \u03b1\n \n <\/mml:mi>\n t<\/mml:mi>\n <\/mml:mrow>\n \\alpha t<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for several randomly chosen\n \n \n \n \n t<\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n \n \n F<\/mml:mi>\n <\/mml:mrow>\n p<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n t\\in \\mathbb {F}_p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Gonz\u00e1lez Vasco and the first author have recently extended this result to subgroups of\n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n p<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msubsup>\n \\mathbb {F}_p^*<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of order at least\n \n \n \n \n p<\/mml:mi>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 3<\/mml:mn>\n +<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n p^{1\/3+\\varepsilon }<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for all\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and to subgroups of order at least\n \n \n \n \n p<\/mml:mi>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:msup>\n p^\\varepsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for almost all\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the\n multipliers<\/italic>\n \n \n \n t<\/mml:mi>\n t<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and thus extend this result to subgroups of order at least\n \n \n \n \n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n p<\/mml:mi>\n \n )<\/mml:mo>\n \n 1<\/mml:mn>\n \n \u2212\n \n <\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n (\\log p)\/(\\log \\log p)^{1-\\varepsilon }<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for all primes\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . As in the above works, we give applications of our result to the bit security of the Diffie\u2013Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.\n <\/p>","DOI":"10.1090\/s0025-5718-05-01797-7","type":"journal-article","created":{"date-parts":[[2005,8,10]],"date-time":"2005-08-10T10:23:21Z","timestamp":1123669401000},"page":"2073-2080","source":"Crossref","is-referenced-by-count":7,"title":["A hidden number problem in small subgroups"],"prefix":"10.1090","volume":"74","author":[{"given":"Igor","family":"Shparlinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Winterhof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2005,4,5]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"D. Boneh and R. Venkatesan, \u201cHardness of computing the most significant bits of secret keys in Diffie\u2013Hellman and related schemes\u201d, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129\u2013142.","DOI":"10.1007\/3-540-68697-5_11"},{"key":"2","isbn-type":"print","first-page":"675","article-title":"Rounding in lattices and its cryptographic applications","author":"Boneh, Dan","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0898713900"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S1631-073X(03)00281-4","article-title":"Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order","volume":"337","author":"Bourgain, Jean","year":"2003","journal-title":"C. R. Math. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/1631-073X","issn-type":"print"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1112\/S0024610702004040","article-title":"Bounds on exponential sums and the polynomial Waring problem mod \ud835\udc5d","volume":"67","author":"Cochrane, Todd","year":"2003","journal-title":"J. London Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"issue":"3-4","key":"5","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s00037-002-0174-3","article-title":"On the hardness of approximating the permanent of structured matrices","volume":"11","author":"Codenotti, Bruno","year":"2002","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9316-0","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0387947779"},{"key":"7","doi-asserted-by":"crossref","unstructured":"S. D. Galbraith, H. J. Hopkins and I. E. Shparlinski, \u201cSecure bilinear Diffie\u2013Hellman bits\u201d, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 3108 (2004), 370\u2013378. Archive,","DOI":"10.1007\/978-3-540-27800-9_32"},{"key":"8","isbn-type":"print","first-page":"257","article-title":"On the security of Diffie-Hellman bits","author":"Gonz\u00e1lez Vasco, Maria Isabel","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3764365102"},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1093\/qjmath\/51.2.221","article-title":"New bounds for Gauss sums derived from \ud835\udc58\ud835\udc61\u210e powers, and for Heilbronn\u2019s exponential sum","volume":"51","author":"Heath-Brown, D. R.","year":"2000","journal-title":"Q. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"key":"10","first-page":"111","article-title":"Estimates for Gaussian sums and Waring\u2019s problem modulo a prime","volume":"198","author":"Konyagin, S. V.","year":"1992","journal-title":"Trudy Mat. Inst. Steklov.","ISSN":"https:\/\/id.crossref.org\/issn\/0371-9685","issn-type":"print"},{"key":"11","unstructured":"S. V. Konyagin, \u201cBounds of exponential sums over subgroups and Gauss sums\u201d, Proc 4th Intern. Conf. Modern Problems of Number Theory and Its Applications, Moscow Lomonosov State Univ., Moscow, 2002, 86\u2013114 (in Russian)."},{"key":"12","series-title":"Cambridge Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542930","volume-title":"Character sums with exponential functions and their applications","volume":"136","author":"Konyagin, Sergei V.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521642639"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-45708-9_28","article-title":"Hidden number problem with the trace and bit security of XTR and LUC","author":"Li, Wen-Ching W.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/354044050X"},{"key":"14","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0521392314","edition":"2"},{"key":"15","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Handbook of applied cryptography","author":"Menezes, Alfred J.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0849385237"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1023\/A:1025436905711","article-title":"The insecurity of the elliptic curve digital signature algorithm with partially known nonces","volume":"30","author":"Nguyen, Phong Q.","year":"2003","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"17","volume-title":"Primzahlverteilung","author":"Prachar, Karl","year":"1957"},{"issue":"1676","key":"18","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1098\/rsta.1993.0139","article-title":"Discrete logarithms and local units","volume":"345","author":"Schirokauer, Oliver","year":"1993","journal-title":"Philos. Trans. Roy. Soc. London Ser. A","ISSN":"https:\/\/id.crossref.org\/issn\/0962-8428","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/3-540-61581-4_66","article-title":"Discrete logarithms: the effectiveness of the index calculus method","author":"Schirokauer, Oliver","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540615814"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1006\/jnth.1996.0121","article-title":"On exponential sums with sparse polynomials and rational functions","volume":"60","author":"Shparlinski, Igor","year":"1996","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/3-540-45624-4_28","article-title":"On the generalised hidden number problem and bit security of XTR","author":"Shparlinski, Igor E.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3540429115"},{"key":"22","unstructured":"I. E. Shparlinski, \u201cPlaying \u2018Hide-and-Seek\u2019 in finite fields: Hidden number problem and its applications\u201d, Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1, Univ. of Oviedo, 2002, 49\u201372."},{"key":"23","isbn-type":"print","first-page":"286","article-title":"Exponential sums and lattice reduction: applications to cryptography","author":"Shparlinski, Igor E.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540439617"},{"key":"24","series-title":"Progress in Computer Science and Applied Logic","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8037-4","volume-title":"Cryptographic applications of analytic number theory","volume":"22","author":"Shparlinski, Igor","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3764366540"},{"key":"25","isbn-type":"print","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-540-24632-9_30","article-title":"A nonuniform algorithm for the hidden number problem in subgroups","author":"Shparlinski, Igor E.","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/3540210180"},{"key":"26","unstructured":"I. E. Shparlinski and A. Winterhof, \u201cNoisy interpolation of sparse polynomials in finite fields\u201d, Appl. Algebra in Engin., Commun. and Computing, (to appear)."},{"key":"27","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Cryptography","author":"Stinson, Douglas R.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/1584882069","edition":"2"},{"issue":"4","key":"28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.4064\/aa96-4-6","article-title":"A note on Waring\u2019s problem in finite fields","volume":"96","author":"Winterhof, Arne","year":"2001","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2005-74-252\/S0025-5718-05-01797-7\/S0025-5718-05-01797-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2005-74-252\/S0025-5718-05-01797-7\/S0025-5718-05-01797-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:31:29Z","timestamp":1776781889000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2005-74-252\/S0025-5718-05-01797-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4,5]]},"references-count":28,"journal-issue":{"issue":"252","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["S0025-5718-05-01797-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-05-01797-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2005,4,5]]}}}