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

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

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

[2]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[3]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

[4]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[5]

Guo-Niu Han, Huan Xiong. Skew doubled shifted plane partitions: Calculus and asymptotics. Electronic Research Archive, 2021, 29 (1) : 1841-1857. doi: 10.3934/era.2020094

[6]

Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007

[7]

Juliana Fernandes, Liliane Maia. Blow-up and bounded solutions for a semilinear parabolic problem in a saturable medium. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1297-1318. doi: 10.3934/dcds.2020318

[8]

Chueh-Hsin Chang, Chiun-Chuan Chen, Chih-Chiang Huang. Traveling wave solutions of a free boundary problem with latent heat effect. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021028

[9]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018

[10]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[11]

Huijuan Song, Bei Hu, Zejia Wang. Stationary solutions of a free boundary problem modeling the growth of vascular tumors with a necrotic core. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 667-691. doi: 10.3934/dcdsb.2020084

[12]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, 2021, 14 (1) : 149-174. doi: 10.3934/krm.2020052

[13]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117

[14]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016

[15]

Yang Liu. Global existence and exponential decay of strong solutions to the cauchy problem of 3D density-dependent Navier-Stokes equations with vacuum. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1291-1303. doi: 10.3934/dcdsb.2020163

[16]

Xueli Bai, Fang Li. Global dynamics of competition models with nonsymmetric nonlocal dispersals when one diffusion rate is small. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3075-3092. doi: 10.3934/dcds.2020035

[17]

Yue-Jun Peng, Shu Wang. Asymptotic expansions in two-fluid compressible Euler-Maxwell equations with small parameters. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 415-433. doi: 10.3934/dcds.2009.23.415

[18]

Azmy S. Ackleh, Nicolas Saintier. Diffusive limit to a selection-mutation equation with small mutation formulated on the space of measures. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1469-1497. doi: 10.3934/dcdsb.2020169

[19]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[20]

Giulio Ciraolo, Antonio Greco. An overdetermined problem associated to the Finsler Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021004

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]