11
$\begingroup$

I've come across a bunch of "strange" hash function notations, such as the following ones and now I don't know how to choose / instantiate them.

Can you please explain me what this notation means and how I can actually instantiate such a hash function?

The notation in question: $$H_1:\mathcal M \rightarrow \mathbb F_p$$ $$H_2:\mathcal M \rightarrow \mathbb Z_n^*$$ $$H_3:\mathcal M \rightarrow \{0,1\}^l$$ $$H_4:\mathcal M_1\times ...\times \mathcal M_k\rightarrow \mathcal S$$

where $\mathcal M\in\{\mathbb F_p,\mathbb Z_n^*,\{0,1\}^*,\mathbb G,...\}$ where $\mathbb G$ is a generic (but there instantiated) group and $\mathcal S\in\{\mathbb F_p,\mathbb Z_n^*,\{0,1\}^l\}$

$\endgroup$
7
$\begingroup$

Can you please explain me what this notation means?

Of course, $f:A\times B\times C\rightarrow D$ is fancy mathematican's language for saying: "a function f, that takes an element from A, B and C (in this order) and maps this to an element of D" (arbitrarily extend this explanation to as many arguments as you wish).

In this particular instance, the authors of these papers didn't actually care about which hash function should be used as long as it fulfills the usual properties of a hash and maps from the right set(s) to the right set, as the situation requires. For example if you want to derive a key from a shared Diffie-Hellman secret (which is an integer in $\mathbb F_p$ and nothing else) you formally need a hash function $H:\mathbb F_p\rightarrow \{0,1\}^l$, where $l$ is the desired length of the derived secret. The fact that you usually do this by hashing the binary representation of the integer doesn't matter for theoreticans.

How I can actually instantiate such a hash function?

First, I'll discuss the case where you only have one argument from the set of binary strings, then this will be adapted to arbitrary sets for the arguments and finally will extend this result to multiple arguments.

Assume you want to instantiate $H_3:\{0,1\}^*\rightarrow \{0,1\}^l$. For this you take your favorite n-bit hash function $H$ (e.g. SHA-256, SHA-512, SHA3-512, SHA3-256, Skein-512-512, Blake2b-512, ...). Now you use a key derivaton function, such as HKDF to construct an arbitrary hash or KDF2, which just hashes the input and with a counter that increments as long as you need more bits (your zero-based counter will be $\lceil\frac{l}{n} \rceil-1$ at the end).

The next step is to turn this into a hash function that outputs an arbitrary number (from the finite field): $H_1:\{0,1\}^*\rightarrow \mathbb F_p$. To do this you take the generic hash function we just constructed and reduce the output $\bmod p$ and you're done, $l\geq \lceil \log_2(p)\rceil$ in this case. This will be good enough for most uses. If you strongly require a uniform distribution, pick $k\geq 2\cdot \lceil \log_2(p)\rceil$.
Note that if you want to hash into $\mathbb Z_n^*$ with $n$ being composite, then you can in theory get values that are not in this set (like $p$ or $q$ if $n=pq$), but the chance of this happening are negligible if $n$ is sufficiently large.

Expanding on that: If you have a domain (the set you map into), that cannot be trivially converted from a bit-string (like integers) or where membership criteria or non-trivial, you can build a deterministic hash function, that will increase a counter each time the result is not an element. For $\mathbb Z_n^*$ for example this would be $\gcd(r,n)=1$ for membership (given that $r$ is your hash output).

Expanding this approach to arbitrary input sets is straightforward. You basically just convert the set-element in question into a its bit-representation (which you'll have anyways in all practical applications) and then hash this as describe above.

The multi-argument case is a little more interesting. You use the prefix-free pairing function of your choice to combine the bit representation into a large binary string. If all but one of your inputs are fixed-length, simple concatenation will do here. Otherwise you may be able to construct collisions by appropriately choosing the inputs, for example (01,1) and (0,11) would result in the same string after concatenation, yielding an undesirable collision. Another possible construction for this would be to pre-hash each argument independently and concatenating the (fixed-length) outputs for final hashing.

$\endgroup$

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.