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&lt;g&lt;p-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&lt;q$, 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.