American Institute of Mathematical Sciences

Advanced
May  2015, 9(2): 169-176. doi: 10.3934/amc.2015.9.169

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, Australia

Received  September 2013 Published  May 2015

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: small solutions., hidden number problem, Shifted inversion, congruences.
Mathematics Subject Classification: Primary: 11T71; Secondary: 11D85, 94A6.
Citation: Igor E. Shparlinski. Close values of shifted modular inversions and the decisional modular inversion hidden number problem. Advances in Mathematics of Communications, 2015, 9 (2) : 169-176. doi: 10.3934/amc.2015.9.169
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.

show all references

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.

[1]

Santanu Sarkar. Analysis of Hidden Number Problem with Hidden Multiplier. Advances in Mathematics of Communications, 2017, 11 (4) : 805-811. doi: 10.3934/amc.2017059
[2]

Guglielmo Feltrin, Elisa Sovrano, Andrea Tellini. On the number of positive solutions to an indefinite parameter-dependent Neumann problem. Discrete and Continuous Dynamical Systems, 2022, 42 (1) : 21-71. doi: 10.3934/dcds.2021107
[3]

Mustapha Ait Rami, John Moore. Partial stabilizability and hidden convexity of indefinite LQ problem. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 221-239. doi: 10.3934/naco.2016009
[4]

Salomón Alarcón. Multiple solutions for a critical nonhomogeneous elliptic problem in domains with small holes. Communications on Pure and Applied Analysis, 2009, 8 (4) : 1269-1289. doi: 10.3934/cpaa.2009.8.1269
[5]

E. Muñoz Garcia, R. Pérez-Marco. Diophantine conditions in small divisors and transcendental number theory. Discrete and Continuous Dynamical Systems, 2003, 9 (6) : 1401-1409. doi: 10.3934/dcds.2003.9.1401
[6]

Yang Wang. The maximal number of interior peak solutions concentrating on hyperplanes for a singularly perturbed Neumann problem. Communications on Pure and Applied Analysis, 2011, 10 (2) : 731-744. doi: 10.3934/cpaa.2011.10.731
[7]

G.F. Webb. The prime number periodical cicada problem. Discrete and Continuous Dynamical Systems - B, 2001, 1 (3) : 387-399. doi: 10.3934/dcdsb.2001.1.387
[8]

Zhi-Qiang Shao. Lifespan of classical discontinuous solutions to the generalized nonlinear initial-boundary Riemann problem for hyperbolic conservation laws with small BV data: shocks and contact discontinuities. Communications on Pure and Applied Analysis, 2015, 14 (3) : 759-792. doi: 10.3934/cpaa.2015.14.759
[9]

Batoul Abdelaziz, Abdellatif El Badia, Ahmad El Hajj. Some remarks on the small electromagnetic inhomogeneities reconstruction problem. Inverse Problems and Imaging, 2017, 11 (6) : 1027-1046. doi: 10.3934/ipi.2017047
[10]

Massimo Grossi. On the number of critical points of solutions of semilinear elliptic equations. Electronic Research Archive, 2021, 29 (6) : 4215-4228. doi: 10.3934/era.2021080
[11]

Yonggeun Cho, Tohru Ozawa. On small amplitude solutions to the generalized Boussinesq equations. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 691-711. doi: 10.3934/dcds.2007.17.691
[12]

Feng Ma, Mingfang Ni. A two-phase method for multidimensional number partitioning problem. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 203-206. doi: 10.3934/naco.2013.3.203
[13]

F. D. Araruna, F. O. Matias, M. P. Matos, S. M. S. Souza. Hidden regularity for the Kirchhoff equation. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1049-1056. doi: 10.3934/cpaa.2008.7.1049
[14]

Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149
[15]

Fabio Scalco Dias, Luis Fernando Mello. The center--focus problem and small amplitude limit cycles in rigid systems. Discrete and Continuous Dynamical Systems, 2012, 32 (5) : 1627-1637. doi: 10.3934/dcds.2012.32.1627
[16]

Han Yang. A singular perturbed problem for semilinear wave equations with small parameter. Discrete and Continuous Dynamical Systems, 1999, 5 (3) : 473-488. doi: 10.3934/dcds.1999.5.473
[17]

Sabri Bensid, Jesús Ildefonso Díaz. On the exact number of monotone solutions of a simplified Budyko climate model and their different stability. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1033-1047. doi: 10.3934/dcdsb.2019005
[18]

Paolo Gidoni, Alessandro Margheri. Lower bound on the number of periodic solutions for asymptotically linear planar Hamiltonian systems. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 585-606. doi: 10.3934/dcds.2019024
[19]

Marcello D'Abbicco. Small data solutions for semilinear wave equations with effective damping. Conference Publications, 2013, 2013 (special) : 183-191. doi: 10.3934/proc.2013.2013.183
[20]

Ling-Jun Wang. The dynamics of small amplitude solutions of the Swift-Hohenberg equation on a large interval. Communications on Pure and Applied Analysis, 2012, 11 (3) : 1129-1156. doi: 10.3934/cpaa.2012.11.1129

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (114)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy