Paper 2024/1520

On the rough order assumption in imaginary quadratic number fields

Abstract

In this paper, we investigate the rough order assumption (\(RO_C\)) introduced by Braun, Damgård, and Orlandi at CRYPTO 23, which posits that class groups of imaginary quadratic fields with no small prime factors in their order are computationally indistinguishable from general class groups. We present a novel attack that challenges the validity of this assumption by leveraging properties of Mordell curves over the rational numbers. Specifically, we demonstrate that if the rank of the Mordell curve \( E_{-16D} \) is at least 2, it contradicts the rough order assumption. Our attack deterministically breaks the \(RO_C\) assumption for discriminants of a special form, assuming the parity conjecture holds and certain conditions are met. Additionally, for both special and generic cases, our results suggest that the presence of nontrivial 3-torsion elements in class groups can undermine the \(RO_C\) assumption. Although our findings are concrete for specific cases, the generic scenario relies on heuristic arguments related to the Birch and Swinnerton-Dyer (BSD) conjecture, a significant and widely believed conjecture in number theory. Attacks against 2-torsion elements in class groups are already well known, but our work introduces a distinct approach targeting 3-torsion elements. These attacks are fundamentally different in nature, and both have relatively straightforward countermeasures, though they do not generalize to higher torsions. While these results do not entirely invalidate the \(RO_C\) assumption, they highlight the need for further exploration of its underlying assumptions, especially in the context of specific torsion structures within class groups.