Skip to Main content Skip to Navigation
Journal articles

Trustless unknown-order groups

Samuel Dobson 1 Steven Galbraith 2 Benjamin Smith 3 
3 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Groups of unknown order are of major interest due to their applications including time-lock puzzles, verifiable delay functions, and accumulators. In this paper we focus on trustless setup: in this setting, the most popular unknown-order group construction is ideal class groups of imaginary quadratic fields. We argue that the full impact of Sutherland's generic group-order algorithm has not been recognised in this context, and show that group sizes currently being proposed in practice (namely, approximately 830 bits) do not meet the claimed security level. Instead, we claim that random group orders should be at least 3300 bits to meet a 128-bit security level. For ideal class groups this leads to discriminants of around 6656 bits, which are much larger than desirable. One drawback of class groups is that current approaches require approximately 2log_2(N) bits to represent an element in a group of order N. We provide two solutions to mitigate this blow-up in the size of representations. First, we explain how an idea of Bleichenbacher can be used to compress class group elements to (3/2)log_2(N) bits. Second, we note that using Jacobians of hyperelliptic curves (in other words, class groups of quadratic function fields) allows efficient compression to the optimal element representation size of log_2(N) bits. We discuss point-counting approaches for hyperelliptic curves and argue that genus-3 curves are secure in the trustless unknown-order setting. We conclude that in practice, Jacobians of hyperelliptic curves are more efficient in practice than ideal class groups at the same security level---both in the group operation and in the size of the element representation.
Complete list of metadata
Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Friday, June 26, 2020 - 2:42:38 PM
Last modification on : Friday, April 1, 2022 - 3:56:15 AM


  • HAL Id : hal-02882161, version 1


Samuel Dobson, Steven Galbraith, Benjamin Smith. Trustless unknown-order groups. Mathematical Cryptology, Florida Online Journals, In press. ⟨hal-02882161⟩



Record views