{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:47:02Z","timestamp":1776728822727,"version":"3.51.2"},"reference-count":30,"publisher":"American Mathematical Society (AMS)","issue":"243","license":[{"start":{"date-parts":[[2004,2,3]],"date-time":"2004-02-03T00:00:00Z","timestamp":1075766400000},"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>\n                    We consider a generalisation of the\n                    <italic>hidden number problem<\/italic>\n                    recently introduced by Boneh and Venkatesan. The initial problem can be stated as follows: recover a number\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"a element-of double-struck upper F Subscript p\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>a<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:msub>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>p<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">a \\in \\mathbb {F}_p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    such that for many known random\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t element-of double-struck upper F Subscript p\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:msub>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>p<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">t \\in \\mathbb {F}_p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    approximations to the values of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"left floor a t right floor Subscript p\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow>\n                              <mml:mo>\u230a<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>a<\/mml:mi>\n                                <mml:mi>t<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mo>\u230b<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mi>p<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\left \\lfloor {a t}\\right \\rfloor _p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    are known. Here we study a version of the problem where the \u201cmultipliers\u201d\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t\">\n                        <mml:semantics>\n                          <mml:mi>t<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">t<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    are not known but rather certain approximations to them are given. We present a probabilistic polynomial time solution when the error is small enough, and we show that the problem cannot be solved if the error is sufficiently large. We apply the result to the bit security of \u201ctimed-release crypto\u201d introduced by Rivest, Shamir and Wagner, to noisy exponentiation black-boxes and to the bit security of the \u201cinverse\u201d exponentiation. We also show that it implies a certain bit security result for Weil pairing on elliptic curves.\n                  <\/p>","DOI":"10.1090\/s0025-5718-03-01495-9","type":"journal-article","created":{"date-parts":[[2003,4,18]],"date-time":"2003-04-18T13:09:02Z","timestamp":1050671342000},"page":"1473-1485","source":"Crossref","is-referenced-by-count":11,"title":["Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation"],"prefix":"10.1090","volume":"72","author":[{"given":"Nick","family":"Howgrave-Graham","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phong","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2003,2,3]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Kumar and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 6-8, 2001, 601\u2013610.","DOI":"10.1145\/380752.380857"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem","volume":"6","author":"Babai, L.","year":"1986","journal-title":"Combinatorica","ISSN":"https:\/\/id.crossref.org\/issn\/0209-9683","issn-type":"print"},{"issue":"4","key":"3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.4064\/aa-83-4-331-361","article-title":"Shifted primes without large prime factors","volume":"83","author":"Baker, R. C.","year":"1998","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"D. Boneh and R. Venkatesan, Hardness of computing the most significant bits of secret keys in Diffie\u2013Hellman and related schemes, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129\u2013142.","DOI":"10.1007\/3-540-68697-5_11"},{"key":"5","unstructured":"D. Boneh and R. Venkatesan, Rounding in lattices and its cryptographic applications, Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, ACM, NY, 1997, 675\u2013681."},{"key":"6","doi-asserted-by":"crossref","unstructured":"E. El Mahassni, P. Q. Nguyen and I. E. Shparlinski, The insecurity of some DSA-like signature schemes with partially known nonces, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2146 (2001), 97\u2013109.","DOI":"10.1007\/3-540-44670-2_9"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0217016","article-title":"Reconstructing truncated integer variables satisfying linear congruences","volume":"17","author":"Frieze, Alan M.","year":"1988","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"8","doi-asserted-by":"crossref","unstructured":"M. I. Gonz\u00e1lez Vasco and I. E. Shparlinski, On the security of Diffie\u2013Hellman bits, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkh\u00e4user, 2001, 257\u2013268.","DOI":"10.1007\/978-3-0348-8295-8_19"},{"issue":"237","key":"9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1090\/S0025-5718-01-01358-8","article-title":"Security of the most significant bits of the Shamir message passing scheme","volume":"71","author":"Gonz\u00e1lez Vasco, Maria Isabel","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1023\/A:1011214926272","article-title":"Lattice attacks on digital signature schemes","volume":"23","author":"Howgrave-Graham, N. A.","year":"2001","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"R. Kannan, Improved algorithms for integer programming and related lattice problems, Proc. 15th ACM Symp. on Theory of Comput., Boston, MA, May 25-27, 1983, 193\u2013206.","DOI":"10.1145\/800061.808749"},{"key":"12","isbn-type":"print","first-page":"231","article-title":"Algorithmic geometry of numbers","author":"Kannan, Ravi","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0824332024"},{"key":"13","unstructured":"M. Kiwi, F. Magniez and M. Santha, Exact and approximate testing\/coorecting of algebraic functions: A survey, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR2001-014 (2001), 1\u201349."},{"key":"14","doi-asserted-by":"crossref","unstructured":"S. V. Konyagin and I. E. Shparlinski, Character sums with exponential functions and their applications, Cambridge Univ. Press, Cambridge, 1999.","DOI":"10.1017\/CBO9780511542930"},{"key":"15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1090\/psapm\/042\/1095554","article-title":"Pseudorandom number generators in cryptography and number theory","author":"Lagarias, J. C.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0821801554"},{"issue":"4","key":"16","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":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"17","doi-asserted-by":"crossref","unstructured":"P. MacKenzie, On the security of the SPEKE Password-authenticated key exchange protocol, Cryptology ePrint Archive, Report 2001\/57, 2001, 1\u201319.","DOI":"10.1007\/s00145-005-0232-5"},{"key":"18","unstructured":"D. Micciancio, On the hardness of the shortest vector problem, PhD Thesis, MIT, 1998."},{"key":"19","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen, The dark side of the Hidden Number Problem: Lattice attacks on DSA, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkh\u00e4user, 2001, 321\u2013330.","DOI":"10.1007\/978-3-0348-8295-8_23"},{"key":"20","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and I. E. Shparlinski, The insecurity of the Digital Signature Algorithm with partially known nonces, J. Cryptology, 15 (2002), 152\u2013176.","DOI":"10.1007\/s00145-002-0021-3"},{"key":"21","unstructured":"P. Q. Nguyen and I. E. Shparlinski, The insecurity of the elliptic curve Digital Signature Algorithm with partially known nonces, Designs, Codes and Cryptography, (to appear)."},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/10722028_4","article-title":"Lattice reduction in cryptology: an update","author":"Nguyen, Phong Q.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"23","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and J. Stern, The two faces of lattices in cryptology, Cryptology and Lattices (Providence, RI, 2001), Lecture Notes in Computer Sci., vol. 2146, Springer-Verlag, Berlin, 2001, pp. 146\u2013180.","DOI":"10.1007\/3-540-44670-2_12"},{"key":"24","unstructured":"R. L. Rivest, A. Shamir and D. A. Wagner, Time-lock puzzles and timed-release crypto, Preprint, 1996, 1\u20139."},{"key":"25","doi-asserted-by":"crossref","unstructured":"A.-R. Sadeghi and M. Steiner, Assumptions related to discrete logarithms: Why subtleties make a real difference, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2045 (2001), 243\u2013260.","DOI":"10.1007\/3-540-44987-6_16"},{"issue":"2-3","key":"26","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time lattice basis reduction algorithms","volume":"53","author":"Schnorr, C.-P.","year":"1987","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"27","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski, Sparse polynomial approximation in finite fields, Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 6-8, 2001, 209\u2013215.","DOI":"10.1145\/380752.380803"},{"key":"28","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski, Security of most significant bits of \ud835\udc54^{\ud835\udc65\u00b2}, Inform. Proc. Letters, 83 (2002), 109\u2013113.","DOI":"10.1016\/S0020-0190(01)00315-5"},{"key":"29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF02547750","article-title":"The method of successive approximations for functional equations","volume":"71","author":"Kantorovitch, L.","year":"1939","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"key":"30","doi-asserted-by":"publisher","first-page":"82","DOI":"10.2307\/1989993","article-title":"Maximal orders in rational cyclic algebras of composite degree","volume":"46","author":"Perlis, Sam","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2003-72-243\/S0025-5718-03-01495-9\/S0025-5718-03-01495-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-243\/S0025-5718-03-01495-9\/S0025-5718-03-01495-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:20:56Z","timestamp":1776727256000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-243\/S0025-5718-03-01495-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2,3]]},"references-count":30,"journal-issue":{"issue":"243","published-print":{"date-parts":[[2003,7]]}},"alternative-id":["S0025-5718-03-01495-9"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-03-01495-9","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":[[2003,2,3]]}}}