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

Igor E.  Shparlinski

doi:10.3934/amc.2015.9.169

Article Contents

2015, Volume 9, Issue 2: 169-176. Doi: 10.3934/amc.2015.9.169

This issue Previous Article Information--bit error rate and false positives in an MDS code Next Article Cyclic orbit codes and stabilizer subfields

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

Igor E. Shparlinski^1,

1.
Department of Pure Mathematics, University of New South Wales, Sydney, NSW 2052

Received: August 31, 2013

Published: April 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11T71; Secondary: 11D85, 94A60.

Citation:

Related Papers

Cited by

References

[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.
[2]	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.
[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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	A. Dubickas, M. Sha and I. E. Shparlinski, Explicit form of Cassels' $p$-adic embedding theorem for number fields, Canad. J. Math., to appear.
[10]	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
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	M. Nair and G. Tenenbaum, Short sums of certain arithmetic functions, Acta Math., 180 (1998), 119-144.doi: 10.1007/BF02392880.
[16]	P. Shiu, A Brun-Titchmarsh theorem for multiplicative functions, J. Reine Angew. Math., 313 (1980), 161-170.doi: 10.1515/crll.1980.313.161.
[17]	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.
[18]	I. E. Shparlinski, Modular hyperbolas, Jap. J. Math., 7 (2012), 235-294.doi: 10.1007/s11537-012-1140-8.
[19]	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.