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

Antonio Sanso

doi:10.62056/a66chevtw

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

Authors

Antonio Sanso

Ethereum Foundation, Switzerland
antonio dot sanso at ethereum dot org

Abstract

We give an explicit algorithm to evaluate an efficiently computable cubic genus invariant on ideal class groups of non-maximal imaginary quadratic orders in $K=\mathbb{Q}(\sqrt{-3})$. Concretely, we consider the order $\mathcal{O}_{\Delta}$ of discriminant $\Delta=-3f^{2}$ with conductor $f>1$. We assume that $f$ is known as an integer, but its prime factorization is not; instead, we are given only a single nontrivial factor $a\mid f$ 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 $(f,a)$, without factoring it).

Under these assumptions, our method computes a nontrivial two-valued genus invariant on the ideal class group of $\mathcal{O}_{\Delta}$, taking values $+1$ and $-1$, whose $+1$-fiber is a distinguished index-$3$ subgroup singled out by classical work of Dedekind; equivalently, the invariant takes the value $+1$ if and only if the ideal class lies in that subgroup.

The construction is inspired by work of Dedekind and Shanks on index-$3$ 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-$3$ subgroup, under the same partial-factorization assumption.

References

[BBF19]

Dan Boneh, Benedikt Bünz, and Ben Fisch. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 561–586, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-26948-7_20

Google Scholar ePrint

[BW88]

Johannes Buchmann and Hugh C. Williams. A Key-Exchange System Based on Imaginary Quadratic Fields. J. Cryptology, 1:107-118, 1988. DOI: 10.1007/BF02351719

Google Scholar ePrint

[CL15]

Guilhem Castagnos and Fabien Laguillaumie. Linearly Homomorphic Encryption from DDH. In Kaisa Nyberg, editor, Topics in Cryptology — CT-RSA 2015, pages 487–505, Cham. 2015. Springer International Publishing. DOI: 10.1007/978-3-319-16715-2_26

Google Scholar ePrint

[CLT18]

Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker. Practical Fully Secure Unrestricted Inner Product Functional Encryption Modulo p. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, pages 733–764, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-030-03329-3_25

Google Scholar ePrint

[Cox89]

David A. Cox. Primes of the form x² + ny². A Wiley-Interscience Publication. John Wiley & Sons Inc., New York 1989. Fermat, class field theory and complex multiplication DOI: 10.1002/9781118400722

Google Scholar ePrint

[Ded00]

R. Dedekind. Ueber die Anzahl der Idealklassen in reinen kubischen Zahlkörpern.. Journal für die reine und angewandte Mathematik, 121:40-123, 1900. DOI: https://doi.org/10.1515/crll.1900.121.40

Google Scholar ePrint

[Lip12]

Helger Lipmaa. Secure Accumulators from Euclidean Rings without Trusted Setup. In Feng Bao, Pierangela Samarati, and Jianying Zhou, editors, Applied Cryptography and Network Security - 10th International Conference, ACNS 2012, Singapore, June 26-29, 2012. Proceedings, volume 7341 of Lecture Notes in Computer Science, pages 224–240. 2012. Springer. DOI: 10.1007/978-3-642-31284-7_14

Google Scholar ePrint

[Pie19]

Krzysztof Pietrzak. Simple Verifiable Delay Functions. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1–60:15, Dagstuhl, Germany. 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ITCS.2019.60

Google Scholar ePrint

[Sha71]

D. Shanks. Class Number, a Theory of Factorization, and Genera. In Proceedings of Symposia in Pure Mathematics. 1971. DOI: 10.1090/pspum/020/0316385

Google Scholar ePrint

[Wes19]

Benjamin Wesolowski. Efficient Verifiable Delay Functions. In Advances in Cryptology – EUROCRYPT 2019, volume 11478 of Lecture Notes in Computer Science, pages 379–407, Cham. 2019. Springer. DOI: 10.1007/978-3-030-17659-4_13

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a66chevtw

History

Submitted: 2026-04-27
Accepted: 2026-06-30
Published: 2026-08-03

How to cite

Antonio Sanso, Efficient DDH Distinguishers in Class Groups of Orders in $ℚ(√(-3))$. IACR Communications in Cryptology, vol. 3, no. 2, Aug 03, 2026, doi: 10.62056/a66chevtw.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a66chevtw,
         author={Antonio Sanso},
         title={Efficient {DDH} Distinguishers in Class Groups of Orders in $ℚ(√(-3))$},
         volume={3},
         number={2},
         year={2026},
         date={2026-08-03},
         issn={3006-5496},
         doi={10.62056/a66chevtw},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Antonio Sanso
PY  - 2026
TI  - Efficient DDH Distinguishers in Class Groups of Orders in $ℚ(√(-3))$
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 3
IS  - 2
DO  - 10.62056/a66chevtw
UR  - https://doi.org/10.62056/a66chevtw
AB  - <p>We give an explicit algorithm to evaluate an efficiently computable cubic genus invariant on ideal class groups of non-maximal imaginary quadratic orders in $K=\mathbb{Q}(\sqrt{-3})$. Concretely, we consider the order $\mathcal{O}_{\Delta}$ of discriminant $\Delta=-3f^{2}$ with conductor $f&gt;1$. We assume that $f$ is known as an integer, but its prime factorization is not; instead, we are given only a single nontrivial factor $a\mid f$ 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 $(f,a)$, without factoring it).</p><p>Under these assumptions, our method computes a nontrivial two-valued genus invariant on the ideal class group of $\mathcal{O}_{\Delta}$, taking values $+1$ and $-1$, whose $+1$-fiber is a distinguished index-$3$ subgroup singled out by classical work of Dedekind; equivalently, the invariant takes the value $+1$ if and only if the ideal class lies in that subgroup.</p><p>The construction is inspired by work of Dedekind and Shanks on index-$3$ 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-$3$ subgroup, under the same partial-factorization assumption. </p>
ER  -

Antonio Sanso, Efficient DDH Distinguishers in Class Groups of Orders in $ℚ(√(-3))$. IACR Communications in Cryptology, vol. 3, no. 2, Aug 03, 2026, doi: 10.62056/a66chevtw.