Paper 2020/196

Trustless unknown-order groups

Samuel Dobson, Steven D. Galbraith, and Benjamin Smith

Abstract

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.