Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group.
$H: \{0,1\}^*\rightarrow \{0,1\}^\lambda$, where $\lambda$ is fixed, is a collision resistant hash function.

  • I have a symmetric encryption key $k\leftarrow H(X+Y)$, with $X,Y \in E(\mathbb{F}_q)$
  • Let's suppose after a certain time, the value $\alpha = X+Y$ is leaked, and I decide to update $k$ as follows: $k\leftarrow H(X+Y+Z)$ where $Z\in \mathbb{F}_q$ is a point sampled at random
  • Then (ElGamal Encryption) I sample at random $r\in \mathbb{Z}^*_n$ and compute $c_1 = r.G$ and $c_2 = X+Y+Z+r.pk_R$, where $pk_R$ is the public key of the receiver. Then, I send $c_1, c_2$ to the receiver over an authenticated line.

My question is the following: if a polynomial-time bounded adversary $\mathcal{A}$ obtains $\alpha, c_1, c_2$, what will be its probability to find/compute the new symmetric key $k\leftarrow H(X+Y+Z)$?

  • $\begingroup$ Well, you have asked an easy question in a long way. Isn't is simply $H(a +b)$ is secure if $a$ is known? That depends on the size of $b$, if it is less than the output size of the hash function than, the pre-image search is faster theoretically but not necessarily practically broken if $len(b)>112$. $\endgroup$ – kelalaka Feb 7 at 21:07
  • $\begingroup$ Thank you for the comment. $\endgroup$ – vxek Feb 7 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.