1
$\begingroup$

I read papers about cloud storage data integrity audit, which needs PBC library and GMP library.

The author define encryption hash function $H:\{0,1\}^* \times G \times \{0,1\}^* \to \Bbb Z_q$, used as $H(ID,R,RN) \bmod q$, $G$ is a cyclic multiplicative group with order $q$ ,$q$ is a large prime, $R, ID,RN$ are elements of $G$.

I don't know how to compute $H(ID,R,RN) \bmod q$ ,they may multiply or do exponent arithmetic ?or use hash function like SHA1 ? How can I construct this function?

$\endgroup$
1
  • $\begingroup$ Welcome to Cryptography.SE. When someone asked about some read papers, usually we want the links and maybe a little summary of them so that your question can be correctly answerable. Also, in our site we have $\LaTeX / MathJax$ is enables. I've edited some. Note hash functions are not encryption. Maybe you want to say. cryptographic hash function? $\endgroup$
    – kelalaka
    Sep 6 '20 at 10:18
5
$\begingroup$

If elements $R$ of $G$ can uniquely be expressed as a bitstring $\overline R$ (e.g. by taking the two components in a finite field of the affine coordinates of $R$, each uniquely representable as a fixed-size bitstring, and these are concatenated to form $\overline R$), then it is easy to construct a generic hash $H:\{0,1\}^* \times G \times \{0,1\}^* \to \mathbb Z_q$ from a standard $b$-bit hash $F:\{0,1\}^* \to \{0,1\}^b$, say SHA-512 with $b=512$, as follows:

  • $h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$, which is a hash of $(\text{ID},R,\text{RN})$ in the set $\{0,1\}^b$
  • if $\log_2q>b/2\,$, expand $h$ as follows:
    • $g\gets h$
    • for $i$ from $1$ to $\big\lceil(\log_2q-b/2)/b\big\rceil\,$
      • $h\gets h\mathbin\|F(g\mathbin\|\overline i)\,$, where $\overline i$ is a bitstring uniquely representing the integer $i\,$ (e.g. encoding $i$ in big-endian base 256 as a minimal number of bytes, then converted to binary)
  • $r\gets \underline h\bmod q\,$, where $\underline h$ is the integer coded by the bitstring $h$ per big-endian binary

The result $r$ is the desired hash of $(\text{ID},R,\text{RN})$ in the set $\mathbb Z_q$.

This hash has nearly the same security as $F$ or an ideal hash in $\mathbb Z_q$, whichever is lower. Argument (or lack of a reference), under a model of the hash $F$ as a random oracle (and any security reduction is is with respect to that):

  • The step "$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$" is a generic composition of hashes, in order to hash multiple inputs of variable size (while maintaining collision resistance contrary to mere concatenation), and allowing a security reduction.
  • The step "if $\log_2q>b/2\,$, expand $h$" does that essentially as in MGF1, again allowing a security reduction.
  • The step "$r\gets \underline h\bmod q\,$" insures the output is in the desired range. It create a bias towards low values, but since at least $b/2$ bits are discarded this bias is low, and it's possible to upper-bound the advantage a distinguisher can obtain.
$\endgroup$
5
  • $\begingroup$ Can you please link a paper that estimates the security of H? $\endgroup$ Mar 18 '21 at 15:06
  • $\begingroup$ @Mikhail Kudinov: sorry I don't have a reference. I have added a security argument, and will think about making it more rigorous; but don't hold your breath. $\endgroup$
    – fgrieu
    Mar 19 '21 at 10:33
  • 1
    $\begingroup$ That last step makes assumptions about F beyond collision resistance. $\endgroup$
    – Maeher
    Mar 19 '21 at 11:04
  • $\begingroup$ @Maeher: Agreed in full. I put myself "under a model of the hash $F$ as a random oracle", and any later "security reduction" is w.r.t. that [update: added that to the answer]. My "while maintaining collision resistance" is not meant as an intermediary step in a proof (rather, as a rationale for multiple hashes), and the whole thing is not intended to be a proper proof. $\endgroup$
    – fgrieu
    Mar 19 '21 at 11:28
  • 1
    $\begingroup$ Sure, for a random oracle that should work. $\endgroup$
    – Maeher
    Mar 19 '21 at 12:10

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.