Imaginary Quadratic Class Groups and a Survey of Time-Lock Cryptographic Applications

Imaginary quadratic class groups have been proposed as one of the main hidden-order group candidates for time-lock cryptographic applications such as verifiable delay functions (VDFs). They have the advantage over RSA groups that they do \emph{not} need a trusted setup. However, they have historically been significantly less studied by the cryptographic research community. This survey provides an introduction to the theory of imaginary quadratic class groups and discusses several considerations that need to be taken into account for practical applications. In particular, we describe the relevant computational problems and the main classical and quantum algorithms that can be used to solve them. From this discussion, it follows that choosing a discriminant $\Delta=-p$ with $p\equiv 3\mod{4}$ prime is one of the most promising ways to pick a class group $\CL(\Delta)$ without the need for a trusted setup, while simultaneously making sure that there are no easy to find elements of low order in $\CL(\Delta)$. We provide experimental data on class groups belonging to discriminants of this form, and compare them to the Cohen-Lenstra heuristics which predict the average behaviour of $\CL(\Delta)$ belonging to a random \emph{fundamental} discriminant. Afterwards, we describe the most prominent constructions of VDFs based on hidden-order groups, and discuss their soundness and sequentiality when implemented in imaginary quadratic class groups. Finally, we briefly touch upon the post-quantum security of VDFs in imaginary quadratic class groups, where the time on can use a fixed group is upper bounded by the runtime of quantum polynomial time order computation algorithms.