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?


1 Answer 1


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

  • 2
    $\begingroup$ @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] $\endgroup$
    – fgrieu
    Sep 10, 2016 at 15:48
  • 1
    $\begingroup$ Yep, I should've thought about it. I'm doing it now. Thanks, @fgrieu $\endgroup$
    – MaiaVictor
    Sep 10, 2016 at 15:52
  • 2
    $\begingroup$ 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. $\endgroup$
    – poncho
    Sep 10, 2016 at 19:01
  • 1
    $\begingroup$ @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] $\endgroup$
    – fgrieu
    Sep 10, 2016 at 22:17
  • 1
    $\begingroup$ @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$. $\endgroup$
    – fgrieu
    Sep 15, 2016 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.