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

[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.  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, (1996), 129.  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, (1997), 675.   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.  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.  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.  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.  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, (2014).   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, (2014), 186.  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.  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.  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.  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.  doi: 10.1007/BF02392880.  Google Scholar

[16]

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

[18]

I. E. Shparlinski, Modular hyperbolas,, Jap. J. Math., 7 (2012), 235.  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.  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, (2009), 337.  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, (2001), 36.  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, (1996), 129.  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, (1997), 675.   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.  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.  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.  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.  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, (2014).   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, (2014), 186.  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.  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.  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.  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.  doi: 10.1007/BF02392880.  Google Scholar

[16]

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

[18]

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

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]

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

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]

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

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

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

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

Deconinck Bernard, Olga Trichtchenko. High-frequency instabilities of small-amplitude solutions of Hamiltonian PDEs. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1323-1358. doi: 10.3934/dcds.2017055
[20]

Kosuke Ono. Global existence and asymptotic behavior of small solutions for semilinear dissipative wave equations. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 651-662. doi: 10.3934/dcds.2003.9.651

2018 Impact Factor: 0.879

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences