Score:1

# What is the problem with having a hash to group function where you can find a discrete log relation between 2 different hashes?

I was reading some notes on a naive hash to a group function.

Consider a cryptographic Hash function $$H: \{0,1\}^{*}\to \{0,1\}^{k}$$

Consider a Discrete Log Hard Group $$G$$ with a generator $$g$$. We can build a Hash to group function $$HG(a) = g^{H(a)}$$

(We raise $$g$$ to the numerical representation of the Hash output)

Apparently, the problem with this is that it's easy to find a relation between 2 hash outputs of this Hash to the group function.

Assume two inputs, $$a_1 \& a_2$$

Let numerical representation of $$H(a_ 1)$$ in $$Z_n$$ be $$n_1$$

Let numerical representation of $$H(a_2)$$ be $$Z_n$$ be $$n_2$$

$$HG(a_1) = g^{n_1}$$

$$HG(a_2) = g^{n_2}$$

Let $${n_1}^{-1}$$ be inverse of $$n_1$$ in $$Z_n$$.

Let $$c = n_2 \cdot {n_1}^{-1}$$

Now $${HG(a_1)}^c = {g^{n_1}}^c = g^{n_1\cdot {n_1}^{-1}.n2} = g^{n_2} = HG(a_2)$$

So we can now find a relation between Hash to Group of $$a_1$$ & $$a_2$$.

$$HG(a_2) = {HG(a_1)}^c$$

I understood up to this. However what is the problem if you can find a relationship like this? Can this be used to attack the Hash to Group function in some way?

@kelalaka - I didn't say there is a problem with the cryptographic hash function. I am asking what is the problem with a Hash to Group function built this way.
@kelalaka - edit my question & title to make it more clear.
edited, i mean ***
You should add the context where this attack makes sense especially for I was reading some notes on a naive hash to a group function. part.
@kelalaka - that's my question - why is it a problem having a hash to group function built like this? Why is it problematic if one can find a relation. The notes I am reading use this example as motivation for using a Pedersen Hash for building a Hash to group function because then one cannot find such a relation if you use a Pedersen hash
Score:2

Many schemes that use a hash to group function will be broken if such a relationship can be found. A good example of the problem might be the Boneh-Franklin IBE scheme where $$H_1$$ is required to be a secure hash to group function.

Public keys in this scheme are computed as $$H_1(ID)$$ so for example Alice's public key might be $$Q_A=H_1({\tt"Alice"})$$ and Bob's might be $$Q_B=H_1({\tt"Bob"})$$. Note that $$Q_A$$, $$Q_B$$, $$n_A$$ where $$H_1({\tt"Alice"})=n_AG$$ and $$n_B$$ where $$H_1({\tt"Bob"})=n_BG$$ are known to everyone.

Now, Alice's private key is supposed to be $$d_A=sQ_A$$ where $$s$$ is a secret known only to the central authority. However, Bob with knowledge of $$d_B=sQ_B$$ can compute $$d_A$$ because $$d_A=sQ_A=s(cQ_B)=c(sQ_B)=cd_B$$ where $$c=n_A/n_B$$ modulo the group order.

What is the difference of $Q_A$ and $n_A$? The OP used multiplicative notation, it is better to be stick to that.
Apologies the definitions of $n_A$ and $n_B$ were typed in haste and now corrected. I've used additive notation to make comparison with the B-F article easier.
What exactly does $H_1({\tt"Alice"})=n_AG$ mean? How do I calculate $n_A$? Do I find $H_1({\tt"Alice"})$ & then scalar multiply it by the inverse of the generator to get $n_A$?
I am confused because when one introduces a new term like $n_A$, one first introduces it in the left hand side of an equation but here you directly use it in the right hand side
@user93353 The conditions of your question says that I can find the discrete log relation of a hash. $n_A$ is computed by whatever means the discrete log is found in your assumption.
I sit in a Tesla and translated this thread with Ai: