Let $q$ be a given random prime of $2b$-bit for some security parameter $b$ (say $b=128$); let $p$ be a given much larger random prime with $p=q\cdot r+1$. Let $(G,*)$ be the (Schnorr) subgroup of $\mathbb Z_p^*$ with $x\in G\iff x^q\equiv1\pmod p$. Assume $p$ is large enough that the Discrete Logarithm Problem is computationally hard for a(ny) generator of $G$, that is requiring effort $O(2^b)$.

Starting from a given hash $H$ conjectured computationally secure in the random oracle model (say SHA-256 or SHA-512), we want to construct a public, easily computable hash $\hat H$ with result in $G$, computationally secure in the random oracle model, and such that for any generator $g$ of $G$, it is computationally hard to exhibit $m$ and $x$ with $g^x\bmod p\;=\;H(m)$.

Does $\hat H(m)\;=\;H(m)^r\bmod p$ qualify? If yes, what formal argument can we give (perhaps making some plausible hypothesis), and how wide does $H$ needs to be? Otherwise, what's a simple alternative?

Note: I'm willing to tolerate the issue that $H(m)^r\bmod p$ has a small chance to be zero, which is not a member of $G$, since it is computationally impossible to exhibit an $m$ with this property.

Motivation: I'm trying to simplify my laborious construction of $H_2$ in that answer.

  • $\begingroup$ Does $g=H(m)^r$ and $x=1$ count as an attack? If not you may want fix the generator here / "constrain" it. $\endgroup$
    – SEJPM
    Commented Sep 19, 2016 at 8:28
  • $\begingroup$ @SEJPM: in the context of the paper referenced at the beginning of the $H_2$ section of the linked answer, I guess that no: $g=H(m)^r$ and $x=1$ does not count as an attack (since $g$ is fixed before $m$ gets chosen). But that's a good catch, and an ambiguity in the question as I worded it: it is unclear if an adversary is allowed to choose $g$. I'd say, assume that no if that makes things simpler; include that, if it does not make things impossible or overly hairy. $\endgroup$
    – fgrieu
    Commented Sep 19, 2016 at 9:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.