Two variable polynomial congruences and capacity theory
PDF

Keywords

Congruence
Lattice
Capacity

How to Cite

Chinburg, T., Hemenway Falk, B., Heninger, N., & Scherr, Z. (2023). Two variable polynomial congruences and capacity theory. Mathematical Cryptology, 3(1), 11–28. Retrieved from https://ojs.test.flvc.org/mathcryptology/article/view/130242

Abstract

Coppersmith's method for finding small solutions of multivariable congruences uses lattice techniques to find sufficiently many algebraically independent polynomials that must vanish on such solutions. We apply adelic capacity theory in the case of two variable linear congruences to determine when there is a second such auxiliary polynomial given one such polynomial. We show that in a positive proportion of cases, no such second polynomial exists, while in a different positive proportion one does exist. This has applications to learning with errors and to bounding the number of small solutions.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2023 Ted Chinburg, Brett Hemenway Falk, Nadia Heninger, Zachary Scherr