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?

et flag

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?

et flag
@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.
et flag
@kelalaka - edit my question & title to make it more clear.
et flag
edited, i mean ***
kelalaka avatar
in flag
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.
et flag
@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
ru flag

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.

kelalaka avatar
in flag
What is the difference of $Q_A$ and $n_A$? The OP used multiplicative notation, it is better to be stick to that.
Daniel S avatar
ru flag
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.
et flag
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$?
et flag
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
Daniel S avatar
ru flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.