Trustless unknown-order groups

Abstract

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 ≈ 2log₂(N) to ≈ (3/2)log₂(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.