Trustless unknown-order groups
PDF

Keywords

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 https://ojs.test.flvc.org/mathcryptology/article/view/130579

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 ≈ 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.

PDF
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