# What is a cyclic group of prime order q such that the DLP is hard?

On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this:

Let $$G = \langle g\rangle$$ be a cyclic group of prime order $$q$$ such that the underlying discrete logarithm problem (DLP) is hard. Let $$H_1 : \{0, 1\}^∗ \to \mathbb Z_q$$ and $$H_2 : \{0, 1\}^∗ \to G$$ be distinct hash functions viewed as random oracles.

What, specifically, is that group he mentions? Are there many ways to construct such a thing? If so, is there any that is easy to implement, yet hard to attack? Or am I looking for some kind of library? Moreover, how should one make such an $$H_2$$ that can be viewed as a random oracle?

## Cyclic group of prime order q such that the DLP is hard

A simple technique to form a cyclic group $$G$$ of prime order $$q$$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) hard, applicable to large $$q$$ (in the order of a thousand bits), is to pick $$q$$ as a random prime of appropriate size such that $$p=2q+1$$ is prime, and random any integer $$g$$ with $$1 such that $$g^q\bmod p=1$$.

The $$q$$ elements of the cyclic group $$G$$ are $$g^i\bmod p$$ with $$0\le i, under modular multiplication modulo $$p$$.

The search of $$q$$ can be greatly sped up by using sieving techniques removing $$q$$ such that either $$q$$ or $$2q+1$$ is divisible by a small prime. The search of $$g$$ is fast as is (on average two attempts are enough; it is common to use $$g=2$$, and towards that goal pick another $$q$$ and $$p$$ if $$g^q\bmod p\neq1$$).

It is conjectured that the DLP is hard, that is: given $$y=g^x\bmod p$$ for unknown random $$x$$ in $$\mathbb Z_q$$, it is computationally infeasible to find $$x$$. The current public record for solving such problem is for one instance of a 768-bit $$p$$. Current recommendations for a decade of security are 2048 or 3072 bits, but 1024 bit is still widely used. Standard groups with $$p$$ of a slightly special form making modular reduction easier are given in RFC 2409 and RFC 3526.

One way to obtain a speedup without sacrificing security (conjecturally) is to reduce the size of $$q$$, within some limit, with $$q$$ a divisor of $$p-1$$. That's a Schnorr group. See section 3.6.6 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, and their algorithm 11.54. Using a 256-bit $$q$$ for 2048-bit $$p$$ is believed to be about as safe as using a 2047-bit $$q$$, and recommendable. 160-bit $$q$$ is often used when $$p$$ is 1024-bit. Execution time is about in proportion to the bit size of $$q$$, and roughly in proportion to the square of the bit size of $$p$$.

Slowness is a often concern! Common algorithms to compute $$y=g^x\bmod p$$ perform like $$3(\log_2(p)/w)^2\log_2(x)$$ multiplications of $$w$$-bit words and additions of the $$2w$$-bit result. For a software implementation using 32-bit words, 2048-bit $$p$$ and 2047-bit $$x$$, we are talking over 25 million muladds. Careful implementations using assembly language shine, including the GNU Multiple Precision Arithmetic Library (which has wrappers in interpreted languages, including gmpy2). Also: be aware that side channel leakage, including by timing, is a security concern depending heavily on the implementation of modular exponentiation.

There are other constructions using an Elliptic Curve over a finite field, giving another large speedup without sacrificing security (conjecturally); and yet other less common techniques. In the following I'll stick to a $$G$$ a subgroup of $$\mathbb Z_p^*$$ of prime order $$q$$, with $$p=r\cdot q+1$$; and to $$r=2$$ (the simple technique discussed initially) unless otherwise noted.

## Construction of H1

What's wanted is a hash with output in $$\mathbb Z_q$$, (conjecturally) secure in the random oracle model (that is: computationally undistinguishable from a random function with the same input and output domain, knowing the definition of $$H_1$$ except some arbitrary constant part of that public definition).

One problem is, usual cryptographic hashes have limited width; the widest in common use is SHA-512, and a 2047-bit $$q$$ is nearly 4 times as wide. If we processed the message $$\alpha\in\{0, 1\}^*$$ using SHA-512, no matter how we post-process the result, a negligible fraction of the elements of $$\mathbb Z_q$$ would be reachable (less than $$2^{-1534}$$); and in order for $$H_1$$ to be secure in the random oracle model, it must be computationally impossible to recognize elements in $$\mathbb Z_q$$ belonging to that fraction. Another issue is that usual cryptographic hashes have each of their output bits about evenly distributed for random input, but a random element of $$\mathbb Z_q$$ expressed as a bitstring of same size as $$q$$ has its high-order bit quite biased towards 0, unless $$q$$ is just below a power of two.

We can solve the size problem by concatenating several independent hashes, which we can obtain using HMAC-SHA-512 with different public arbitrary keys; and one method to approximate the right distribution in $$\mathbb Z_q$$ (beyond computational detectability) is generating at least (say) 128 more bits than in $$q$$, followed by modular reduction modulo $$q$$ (assimilating bitstrings to integer per big-endian convention).

With that method and $$q$$ of 2047 bits, we need $$\lceil(2047+128)/512\rceil=5$$ concatenated HMAC-SHA-512. For message $$\alpha\in\{0, 1\}^*$$ the hash could be $$H_1(\alpha)=\big(HMAC(\text{0x01},\alpha)\|HMAC(\text{0x02},\alpha)\|\dots \|HMAC(\text{0x05},\alpha)\big)\bmod q$$

Note: when using $$q$$ of up to 384 bits, which is fine if $$p$$ is still large enough, we won't need the complexity of concatenating multiple hashes.

## Construction of H2

What's wanted is a hash with output in the group $$G$$ constructed in the first section, (conjecturally) secure in the random oracle model. But there's a catch!

The quote in the question precisely matches section 3.1 of Joseph K. Liu and Duncan S. Wong's Linkable ring signature: security models and new schemes, in proceedings of ICCSA 2005, which I located by asking Google Books for distinct hash functions viewed as random oracles. Right after the question's quote is:

Assume that for any $$\alpha\in\{0, 1\}^*$$, the discrete-log of $$H_2(\alpha)$$ to the base $$g$$ is intractable.

The reasonable way to interpret this additional requirement is that knowing the definition of $$H_2$$, and given $$\alpha$$, one should be computationally unable to find $$x$$ with $$g^x=H_2(\alpha)$$.

Adapting Poncho's great suggestion so that it works regardless of $$r$$, for 2048-bit $$p$$ we can use $$H_2(\alpha)=\Big(\big((HMAC(\text{0x11},\alpha)\|\dots\|HMAC(\text{0x15},\alpha))\bmod(p-1)\big)+1\Big)^r\bmod p$$

This works by generating a random element $$u$$ of $$\mathbb Z_p^*$$, and computing $$v=u^r\bmod p$$. The result is in $$\mathbb Z_q$$, because $$v^q\equiv{(u^r)}^q\equiv u^{rq}\equiv u^{p-1}\bmod p\equiv 1\pmod p$$, with the last step using Fermat's little theorem. With $$u$$ essentially uniform on $$\mathbb Z_p^*$$, $$v$$ is essentially uniform on $$G$$.

I wish I had proof of my intuition that, for general $$r$$, solving $$g^x\bmod p=v$$ for $$x$$ is hard including with knowledge of $$u$$; and that we could get away with generating $$u$$ in $$\mathbb Z_q^*$$ rather than in $$\mathbb Z_p^*$$. Poncho proved both for $$r=2$$.

Words of caution: Many papers on ring signatures and e-voting that I have attempted to follow have lost me; I was often left wondering what exactly is assumed and proven about security, and what that means in practice. Some use a bilinear pairing; while there are libraries for that, I advise to dive into this stuff only if all the math above has been striking one as evidence.

I'm sure that only a small fraction of the voting population can form an informed opinion on these topics. I conclude that using such methods for voting goes straight against a major goal: that voters trust the result.

• @Viclib: You get the idea for "under modular multiplication modulo $p$". Notice the two expressions that you wrote yield the same result (assuming the first ends in % pand they have the same number of terms); and that there are shortcuts to drastically reduce the number of operations. My advise is to drop the paper that you are reading for a while, and work thru chapter 3 of the HAC, referring to chapter 2 when you find something that you do not yet know, and chapter 14 if you want to try making a computer implementation (but do not need resistance to attacks like side-channels). [edited]
– fgrieu
Sep 10, 2016 at 15:48
• Yep, I should've thought about it. I'm doing it now. Thanks, @fgrieu Sep 10, 2016 at 15:52
• BTW: $g$ doesn't need to be random, if you can solve the DLog problem (or the cDH problem) for a nonrandom $g$, you can solve it for any $g$ of the same order. Hence, if $g=2$ makes computation simpler, you can use that. Sep 10, 2016 at 19:01
• @Viclib: Admitting that the DLP is conjecturally hard with the construction that I give, or another classic one, won't harm or invalidate your work. But not understanding the requirements of a scheme that you implement is likely to result in something unsafe. Given the short timeframe, using a bigum package (GMP), or one built in Java or python, is a necessity for any implemnetation. [edited]
– fgrieu
Sep 10, 2016 at 22:17
• @Viiclib: I do understand how you can get the equality that you asked there standing; but I can't make sense of what checking the equality proves. I'll leave that to you. Just to understand: when you say "naive H2 version" is that the one with $H_2(\alpha)=g^{H(\alpha)}\bmod p$? Or one with a $p$ that you generate rather than a given? In the later case, my guess is that you got $p$ mixed up: the Oakley/MODP groups of RFC 2409 and RFC 3526 match all the necessary conditions; just check that you got $p$ right by checking $2^{(p-1)/2}\bmod p=1$.
– fgrieu
Sep 15, 2016 at 4:53