Solving Generalized Approximate Divisor Multiples Problems
摘要
May et al. (Eurocrypt’22) introduced the problem of finding small solutions to univariate linear equations modulo the product of a known positive integer and an unknown divisor of a composite number, the so-called approximate divisor multiples problem. This problem is a generalized version of the approximate divisor problem introduced by Howgrave-Graham (CaLC’01). Many generalized versions of the approximate divisor problem have been introduced by Cohn and Heninger (ANTS’12), May (2003), Herrmann and May (Asiacrypt’08), and so on. On the other hand, no problem that generalizes the approximate divisor multiples problem has been introduced except for its generalized version to univariate equations of any degree introduced by Blömer and May (Eurocrypt’05). In this paper, we consider three generalized versions of the approximate divisor multiples problems, including the problem introduced by Blömer and May. We construct algorithms for these problems and show their success conditions. As a tool for constructing one of these algorithms, we introduce a method to convert an instance of the approximate divisor multiples problem into an instance of the approximate divisor problem without changing the success condition.