doi: 10.3934/amc.2022012
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Finding small roots for bivariate polynomials over the ring of integers

1. 

567 Baekje-daero, Deokjin-gu, Division of Computer Science and Engineering, Jeonbuk National University, Jeonju, Jeollabuk-do, 54896, Republic of Korea

2. 

85, Hoegi-ro, Dongdaemun-gu, Korea Institute for Advanced Study (KIAS), Seoul, 02455, Republic of Korea

*Corresponding author: Changmin Lee

** Most of this work was done when Jiseung Kim was at KIAS

Received  September 2021 Early access March 2022

In this paper, we propose the first heuristic algorithm for finding small roots for a bivariate equation modulo an ideal $ \mathcal{I} $ over the ring of integers $ \mathcal{R} $. Existing algorithms for solving polynomial equations with size constraints only work for bivariate modular equations over integers, and univariate modular equation over number fields.

Both previous algorithms use a relation between the short vector in a skillfully structured lattice and a size constrained solution. Our algorithm also follows this framework, but we additionally use a polynomial factoring algorithm over number fields to recover a 'ring' root of a bivariate polynomial equation.

As a result, when an LLL algorithm is employed to find a short vector, we can recover all small roots of a bivariate polynomial modulo $ \mathcal{I} $ in polynomial time under some constraint.

Citation: Jiseung Kim, Changmin Lee. Finding small roots for bivariate polynomials over the ring of integers. Advances in Mathematics of Communications, doi: 10.3934/amc.2022012
References:
[1]

I. Benzaoui, Studies on Factoring Polynomials Over Global Fields, PhD thesis, Stellenbosch: University of Stellenbosch, 2007.

[2]

J. Blömer and A. May, New partial key exposure attacks on RSA, Advances in cryptology—CRYPTO, 2729 (2003), 27-43.  doi: 10.1007/978-3-540-45146-4_2.

[3]

D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d less than n/sup 0.292, IEEE Trans. Inform. Theory, 46 (2000), 1339-1349.  doi: 10.1109/18.850673.

[4]

D. BonehG. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in cryptology—ASIACRYPT'98, 1514 (1998), 25-34.  doi: 10.1007/3-540-49649-1_3.

[5]

Y. Chen and P. Q. Nguyen, Bkz 2.0: Better lattice security estimates, IAdvances in cryptology—ASIACRYPT 2011, 7073 (2011), 1-20.  doi: 10.1007/978-3-642-25385-0_1.

[6]

H. Cohn and N. Heninger, Ideal forms of coppersmith's theorem and guruswami-sudan list decoding, In Advances in Mathematics of Communications, 9 (2015), 311–339, URL http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/9.html. doi: 10.3934/amc.2015.9.311.

[7]

D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in cryptology—EUROCRYPT, 1070 (1996), 178-189.  doi: 10.1007/3-540-68339-9_16.

[8]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in cryptology—EUROCRYPT, 1070 (1996), 155-165.  doi: 10.1007/3-540-68339-9_14.

[9]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.

[10]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations revisited, Advances in cryptology—EUROCRYPT, 3027 (2004), 492-505.  doi: 10.1007/978-3-540-24676-3_29.

[11]

M. Herrmann and A. May, Solving linear equations modulo divisors: On factoring given any bits, Advances in cryptology—ASIACRYPT, 5350 (2008), 406-424.  doi: 10.1007/978-3-540-89255-7_25.

[12]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and coding, 1355 (1997), 131-142.  doi: 10.1007/BFb0024458.

[13]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, Advances in cryptology—ASIACRYPT, 4284 (2006), 267-282.  doi: 10.1007/11935230_18.

[14]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.

[15]

Y. LuR. ZhangL. Peng and D. Lin, Solving linear equations modulo unknown divisors: Revisited, Advances in Cryptology—ASIACRYPT, 9452 (2015), 189-213.  doi: 10.1007/978-3-662-48797-6_9.

[16]

X.-F. Roblot, Polynomial factorization algorithms over number fields, J. Symbolic Comput., 38 (2004), 1429-1443.  doi: 10.1016/j.jsc.2004.05.002.

[17]

S. Developers, SageMath, the Sage Mathematics Software System (Version 8.6), 2019, https://www.sagemath.org.

[18]

S. Sarkar and S. Maitra, Cryptanalytic results on 'Dual CRT' and 'Common Prime'RSA, Des. Codes Cryptogr., 66 (2013), 157-174.  doi: 10.1007/s10623-012-9675-5.

[19]

A. Takayasu and N. Kunihiro, Partial key exposure attacks on CRT-RSA: General improvement for the exposed least significant bits, In International Conference on Information Security, (2016), 35–47.

[20]

A. Takayasu and N. Kunihiro, A tool kit for partial key exposure attacks on RSA, Topics in cryptology—CT-RSA, 10159 (2017), 58-73.  doi: 10.1007/978-3-319-52153-4_4.

[21]

A. TakayasuY. Lu and L. Peng, Small CRT-exponent RSA revisited, J. Cryptology, 32 (2019), 1337-1382.  doi: 10.1007/s00145-018-9282-3.

show all references

References:
[1]

I. Benzaoui, Studies on Factoring Polynomials Over Global Fields, PhD thesis, Stellenbosch: University of Stellenbosch, 2007.

[2]

J. Blömer and A. May, New partial key exposure attacks on RSA, Advances in cryptology—CRYPTO, 2729 (2003), 27-43.  doi: 10.1007/978-3-540-45146-4_2.

[3]

D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d less than n/sup 0.292, IEEE Trans. Inform. Theory, 46 (2000), 1339-1349.  doi: 10.1109/18.850673.

[4]

D. BonehG. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in cryptology—ASIACRYPT'98, 1514 (1998), 25-34.  doi: 10.1007/3-540-49649-1_3.

[5]

Y. Chen and P. Q. Nguyen, Bkz 2.0: Better lattice security estimates, IAdvances in cryptology—ASIACRYPT 2011, 7073 (2011), 1-20.  doi: 10.1007/978-3-642-25385-0_1.

[6]

H. Cohn and N. Heninger, Ideal forms of coppersmith's theorem and guruswami-sudan list decoding, In Advances in Mathematics of Communications, 9 (2015), 311–339, URL http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/9.html. doi: 10.3934/amc.2015.9.311.

[7]

D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in cryptology—EUROCRYPT, 1070 (1996), 178-189.  doi: 10.1007/3-540-68339-9_16.

[8]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in cryptology—EUROCRYPT, 1070 (1996), 155-165.  doi: 10.1007/3-540-68339-9_14.

[9]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.

[10]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations revisited, Advances in cryptology—EUROCRYPT, 3027 (2004), 492-505.  doi: 10.1007/978-3-540-24676-3_29.

[11]

M. Herrmann and A. May, Solving linear equations modulo divisors: On factoring given any bits, Advances in cryptology—ASIACRYPT, 5350 (2008), 406-424.  doi: 10.1007/978-3-540-89255-7_25.

[12]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and coding, 1355 (1997), 131-142.  doi: 10.1007/BFb0024458.

[13]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, Advances in cryptology—ASIACRYPT, 4284 (2006), 267-282.  doi: 10.1007/11935230_18.

[14]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.

[15]

Y. LuR. ZhangL. Peng and D. Lin, Solving linear equations modulo unknown divisors: Revisited, Advances in Cryptology—ASIACRYPT, 9452 (2015), 189-213.  doi: 10.1007/978-3-662-48797-6_9.

[16]

X.-F. Roblot, Polynomial factorization algorithms over number fields, J. Symbolic Comput., 38 (2004), 1429-1443.  doi: 10.1016/j.jsc.2004.05.002.

[17]

S. Developers, SageMath, the Sage Mathematics Software System (Version 8.6), 2019, https://www.sagemath.org.

[18]

S. Sarkar and S. Maitra, Cryptanalytic results on 'Dual CRT' and 'Common Prime'RSA, Des. Codes Cryptogr., 66 (2013), 157-174.  doi: 10.1007/s10623-012-9675-5.

[19]

A. Takayasu and N. Kunihiro, Partial key exposure attacks on CRT-RSA: General improvement for the exposed least significant bits, In International Conference on Information Security, (2016), 35–47.

[20]

A. Takayasu and N. Kunihiro, A tool kit for partial key exposure attacks on RSA, Topics in cryptology—CT-RSA, 10159 (2017), 58-73.  doi: 10.1007/978-3-319-52153-4_4.

[21]

A. TakayasuY. Lu and L. Peng, Small CRT-exponent RSA revisited, J. Cryptology, 32 (2019), 1337-1382.  doi: 10.1007/s00145-018-9282-3.

Table 1.  Experimental Results with various k
k m $\left\lfloor \log q \right\rfloor $ # of alg. indep
4 2 70 89
8 2 104 96
16 2 184 97
32 2 336 94
64 2 632 92
k m $\left\lfloor \log q \right\rfloor $ # of alg. indep
4 2 70 89
8 2 104 96
16 2 184 97
32 2 336 94
64 2 632 92
[1]

Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2403-2433. doi: 10.3934/dcdss.2019151

[2]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

[3]

Andrew Best, Andreu Ferré Moragues. Polynomial ergodic averages for certain countable ring actions. Discrete and Continuous Dynamical Systems, 2022, 42 (7) : 3379-3413. doi: 10.3934/dcds.2022019

[4]

Azniv Kasparian, Ivan Marinov. Duursma's reduced polynomial. Advances in Mathematics of Communications, 2017, 11 (4) : 647-669. doi: 10.3934/amc.2017048

[5]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[6]

Anna Chiara Lai, Paola Loreti. Robot's finger and expansions in non-integer bases. Networks and Heterogeneous Media, 2012, 7 (1) : 71-111. doi: 10.3934/nhm.2012.7.71

[7]

John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.

[8]

Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028

[9]

Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223

[10]

Hongguang Xiao, Wen Tan, Dehua Xiang, Lifu Chen, Ning Li. A study of numerical integration based on Legendre polynomial and RLS algorithm. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 457-464. doi: 10.3934/naco.2017028

[11]

Münüse Akçay, Gülen Başcanbaz-Tunca. On bivariate Jain operators. Mathematical Foundations of Computing, 2022, 5 (3) : 173-185. doi: 10.3934/mfc.2021026

[12]

Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[13]

Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086

[14]

Azeddine Elmajidi, Elhoussine Elmazoudi, Jamila Elalami, Noureddine Elalami. Dependent delay stability characterization for a polynomial T-S Carbon Dioxide model. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 143-159. doi: 10.3934/dcdss.2021035

[15]

Bin Han, Qun Mo. Analysis of optimal bivariate symmetric refinable Hermite interpolants. Communications on Pure and Applied Analysis, 2007, 6 (3) : 689-718. doi: 10.3934/cpaa.2007.6.689

[16]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[17]

Stefanella Boatto. Curvature perturbations and stability of a ring of vortices. Discrete and Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 349-375. doi: 10.3934/dcdsb.2008.10.349

[18]

Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545

[19]

Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002

[20]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]