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, (2009), 337. 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, (2001), 36. 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, (1996), 129. 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, (1997), 675.

[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. 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. 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. 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. 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., ().

[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, (2014).

[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, (2014), 186. 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. 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. 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. 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. doi: 10.1007/BF02392880.

[16]

P. Shiu, A Brun-Titchmarsh theorem for multiplicative functions,, J. Reine Angew. Math., 313 (1980), 161. 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., 62 (2005), 153. doi: 10.1090/psapm/062/2211876.

[18]

I. E. Shparlinski, Modular hyperbolas,, Jap. J. Math., 7 (2012), 235. 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. 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, (2009), 337. 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, (2001), 36. 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, (1996), 129. 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, (1997), 675.

[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. 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. 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. 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. 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., ().

[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, (2014).

[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, (2014), 186. 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. 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. 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. 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. doi: 10.1007/BF02392880.

[16]

P. Shiu, A Brun-Titchmarsh theorem for multiplicative functions,, J. Reine Angew. Math., 313 (1980), 161. 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., 62 (2005), 153. doi: 10.1090/psapm/062/2211876.

[18]

I. E. Shparlinski, Modular hyperbolas,, Jap. J. Math., 7 (2012), 235. 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. 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]

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
[3]

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
[4]

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

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
[6]

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
[7]

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
[8]

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
[9]

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

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
[11]

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

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

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

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
[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]

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
[18]

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
[19]

Adriana Buică, Jean–Pierre Françoise, Jaume Llibre. Periodic solutions of nonlinear periodic differential systems with a small parameter. Communications on Pure & Applied Analysis, 2007, 6 (1) : 103-111. doi: 10.3934/cpaa.2007.6.103
[20]

Roger Grimshaw, Dmitry Pelinovsky. Global existence of small-norm solutions in the reduced Ostrovsky equation. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 557-566. doi: 10.3934/dcds.2014.34.557

2017 Impact Factor: 0.564

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences