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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Generalized Approximate Divisor Multiples Problems

  • Naoki Shimoe,
  • Noboru Kunihiro

摘要

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.