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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

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

[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 Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

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

[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 Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[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 & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021107
[3]

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

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

E. Muñoz Garcia, R. Pérez-Marco. Diophantine conditions in small divisors and transcendental number theory. Discrete & 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 & 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 & 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 & 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 & 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, , () : -. doi: 10.3934/era.2021080
[11]

Yonggeun Cho, Tohru Ozawa. On small amplitude solutions to the generalized Boussinesq equations. Discrete & 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 & Optimization, 2013, 3 (2) : 203-206. doi: 10.3934/naco.2013.3.203
[13]

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

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

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

Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149
[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 & 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 & 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 & Applied Analysis, 2012, 11 (3) : 1129-1156. doi: 10.3934/cpaa.2012.11.1129

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences