Trustless unknown-order groups


unknown order groups
ideal class groups
hyperelliptic curves

How to Cite

Dobson, S., Galbraith, S., & Smith, B. (2022). Trustless unknown-order groups. Mathematical Cryptology, 1(2), 25–39. Retrieved from


Groups whose order is computationally hard to compute have important applications including timelock puzzles, verifiable delay functions, and accumulators. Many applications require trustless setup: that is, not even the group’s constructor knows its order. We argue that the impact of Sutherland’s generic group-order algorithm has been overlooked in this context, and that current parameters do not meet claimed security levels. We propose updated parameters, and a model for security levels capturing the subtlety of trustless setup. The most popular trustless unknown-order group candidates are ideal class groups of imaginary quadratic fields; we show how to compress class-group elements from ≈ 2log2(N) to ≈ (3/2)log2(N) bits, where N is the order. Finally, we analyse Brent’s proposal of Jacobians of hyperelliptic curves as unknown-order groups. Counter-intuitively, while polynomial-time order-computation algorithms for hyperelliptic Jacobians exist in theory, we conjecture that genus-3 Jacobians offer shorter keylengths than class groups in practice.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2022 Samuel Dobson, Steven Galbraith, Benjamin Smith