Paper 2020/196

Trustless unknown-order groups

Samuel Dobson, Steven D. Galbraith, and Benjamin Smith


Groups whose order is computationally hard to compute have important applications including time-lock 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 $\approx 2\log_2(N)$ to $\approx \tfrac{3}{2}\log_2(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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.MathCrypt 2021
hyperelliptic curvesunknown order groupsideal class groups
Contact author(s)
samuel dobson nz @ gmail com
s galbraith @ auckland ac nz
smith @ lix polytechnique fr
2022-03-01: last of 5 revisions
2020-02-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Samuel Dobson and Steven D.  Galbraith and Benjamin Smith},
      title = {Trustless unknown-order groups},
      howpublished = {Cryptology ePrint Archive, Paper 2020/196},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.