Efficient DDH Distinguishers in Class Groups of Orders in $ℚ(√(-3))$

We give an explicit algorithm to evaluate an efficiently computable cubic genus invariant on ideal class groups of non-maximal imaginary quadratic orders in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>=</mml:mo> <mml:mi>ℚ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> . Concretely, we consider the order <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>𝒪</mml:mi> <mml:mrow> <mml:mi>Δ</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> of discriminant <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>=</mml:mo> <mml:mo>−</mml:mo> <mml:mn>3</mml:mn> <mml:msup> <mml:mi>f</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> with conductor <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . We assume that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> </mml:mrow> </mml:math> is known as an integer, but its prime factorization is not; instead, we are given only a single nontrivial factor <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>a</mml:mi> <mml:mo>∣</mml:mo> <mml:mi>f</mml:mi> </mml:mrow> </mml:math> arising in Dedekind's parametrization of these discriminants (so that the complementary factor needed in the cubic-residuosity test can be recovered as an integer from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo>,</mml:mo> <mml:mi>a</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , without factoring it). Under these assumptions, our method computes a nontrivial two-valued genus invariant on the ideal class group of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>𝒪</mml:mi> <mml:mrow> <mml:mi>Δ</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> , taking values <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , whose <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> -fiber is a distinguished index- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> subgroup singled out by classical work of Dedekind; equivalently, the invariant takes the value <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> if and only if the ideal class lies in that subgroup. The construction is inspired by work of Dedekind and Shanks on index- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> subgroups of quadratic form class groups and their characterization via cubic residuosity of primes represented by form classes. We prove correctness and analyze the running time of the resulting evaluation procedure, and we validate the approach with a SageMath implementation. As an application, we obtain an explicit Decisional Diffie–Hellman (DDH) distinguisher in cyclic subgroups of the class group generated by an element outside the distinguished index- <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> subgroup, under the same partial-factorization assumption.