Advanced Search
Article Contents
Article Contents

Close values of shifted modular inversions and the decisional modular inversion hidden number problem

Abstract Related Papers Cited by
  • We give deterministic polynomial time algorithms for two different decision version the modular inversion hidden number problem introduced by D. Boneh, S. Halevi and N. A. Howgrave-Graham in 2001. For example, for one of our algorithms we need to be given about $1/2$ of the bits of each inversion, while for the computational version the best known algorithm requires about $2/3$ of the bits and is probabilistic.
    Mathematics Subject Classification: Primary: 11T71; Secondary: 11D85, 94A60.


    \begin{equation} \\ \end{equation}
  • [1]

    A. Akavia, Solving hidden number problem with one bit oracle and advice, in Adv. Crypt. - CRYPTO 2009, Springer-Verlag, Berlin, 2010, 337-354.doi: 10.1007/978-3-642-03356-8_20.


    D. Boneh, S. Halevi and N. A. Howgrave-Graham, The modular inversion hidden number problem, in Adv. Crypt. - ASIACRYPT 2001, Springer-Verlag, Berlin, 2001, 36-51.doi: 10.1007/3-540-45682-1_3.


    D. Boneh and R. Venkatesan, Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, in Adv. Crypt. - CRYPTO '96, Springer-Verlag, Berlin, 1996, 129-142.doi: 10.1007/3-540-68697-5_11.


    D. Boneh and R. Venkatesan, Rounding in lattices and its cryptographic applications, in Proc. 8th Annual ACM-SIAM Symp. Discr. Algorithms, SIAM, 1997, 675-681.


    M.-C. Chang, J. Cilleruelo, M. Z. Garaev, J. Hernández, I. E. Shparlinski and A. Zumalacárregui, Points on curves in small boxes and applications, Michigan Math. J., 63 (2014), 503-534.doi: 10.1307/mmj/1409932631.


    J. Cilleruelo and M. Z. Garaev, Concentration of points on two and three dimensional modular hyperbolas and applications, Geom. Funct. Anal., 21 (2011), 892-904.doi: 10.1007/s00039-011-0127-6.


    J. Cilleruelo, M. Z. Garaev, A. Ostafe and I. E. Shparlinski, On the concentration of points of polynomial maps and applications, Math. Zeit., 272 (2012), 825-837.doi: 10.1007/s00209-011-0959-7.


    J. Cilleruelo, I. E. Shparlinski and A. Zumalacárregui, Isomorphism classes of elliptic curves over a finite field in some thin families, Math. Res. Letters, 19 (2012), 335-343.doi: 10.4310/MRL.2012.v19.n2.a6.


    A. Dubickas, M. Sha and I. E. Shparlinski, Explicit form of Cassels' $p$-adic embedding theorem for number fields, Canad. J. Math., to appear.


    O. Garcia-Morchon, D. Gómez-Pérez, J. Gutierrez, R. Rietman, B. Schoenmakers and L. Tolhuizen, HIMMO: A lightweight collusion-resistant key predistribution scheme, Cryptology ePrint Archive: Report 2014/698, available at http://eprint.iacr.org/2014/698


    O. Garcia-Morchon, D. Gómez-Pérez, J. Gutierrez, R. Rietman and L. Tolhuizen, The MMO problem, in Proc. 39th Int. Symp. Symbol. Algebr. Comput. - ISSAC'14, ACM, 2014, 186-193.doi: 10.1145/2608628.2608643.


    O. Garcia-Morchon, R. Rietman, I. E. Shparlinski and L. Tolhuizen, Interpolation and approximation of polynomials in finite fields over a short interval from noisy values, Experim. Math., 23 (2014), 241-260.doi: 10.1080/10586458.2014.890918.


    A. Granville, I. E. Shparlinski and A. Zaharescu, On the distribution of rational functions along a curve over $\mathbbF_p$ and residue races, J. Number Theory, 112 (2005), 216-237.doi: 10.1016/j.jnt.2005.02.002.


    S. Ling, I. E. Shparlinski, R. Steinfeld and H. Wang, On the modular inversion hidden number problem, J. Symb. Comp., 47 (2012), 358-367.doi: 10.1016/j.jsc.2011.09.002.


    M. Nair and G. Tenenbaum, Short sums of certain arithmetic functions, Acta Math., 180 (1998), 119-144.doi: 10.1007/BF02392880.


    P. Shiu, A Brun-Titchmarsh theorem for multiplicative functions, J. Reine Angew. Math., 313 (1980), 161-170.doi: 10.1515/crll.1980.313.161.


    I. E. Shparlinski, Playing "Hide-and-Seek'' with numbers: The hidden number problem, lattices and exponential sums, Proc. Symp. Appl. Math., Amer. Math. Soc., 62 (2005), 153-177.doi: 10.1090/psapm/062/2211876.


    I. E. Shparlinski, Modular hyperbolas, Jap. J. Math., 7 (2012), 235-294.doi: 10.1007/s11537-012-1140-8.


    M. Vâjâitu and A. Zaharescu, Distribution of values of rational maps on the $\mathbbF_p$-points on an affine curve, Monatsh. Math., 136 (2002), 81-86.doi: 10.1007/s006050200035.

  • 加载中

Article Metrics

HTML views() PDF downloads(126) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint