Cryptology ePrint Archive: Report 2020/196

Trustless Groups of Unknown Order with Hyperelliptic Curves

Samuel Dobson and Steven D. Galbraith and Benjamin Smith

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 $2\log_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 $\tfrac{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.

Category / Keywords: cryptographic protocols / hyperelliptic curves, unknown order groups, ideal class groups

Date: received 16 Feb 2020, last revised 25 Jun 2020

Contact author: samuel dobson nz at gmail com,s galbraith@auckland ac nz, smith@lix polytechnique fr

Available format(s): PDF | BibTeX Citation

Version: 20200625:230941 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]