I'm very new to cryptography. I'm required to read a paper.

enter image description here

enter image description here

I totally don't understand. First, what's the meaning of the asterisk in $H:\{0,1\}^*\rightarrow \{0,1\}^k ?$.

Second, what does PPT mean here? (I searched the Internet but didn't get satisfying answer.)

Third, why if $b=1, s\leftarrow H(g^{ab})$, else $s\leftarrow \{0,1\}^k$? I understand step 1,2,3 but don't understand step 4,5,6.

Could anyone please help me to explain it? I will greatly appreciate it.

PS: The paper is Practical Secure Aggregation for Privacy-Preserving Machine Learning. https://eprint.iacr.org/2017/281.pdf

enter image description here

  • $\begingroup$ Can you also post the paper that you are reading cause I want to get more context on this hash function $H$? $\endgroup$
    – tur11ng
    May 8, 2022 at 18:08
  • $\begingroup$ @JAAAY Sure. I have edited my question. $\endgroup$
    – user900476
    May 8, 2022 at 18:13
  • $\begingroup$ To be honest, I cannot understand why the use $H$. $\endgroup$
    – tur11ng
    May 8, 2022 at 18:28
  • $\begingroup$ @JAAAY It says traditionally the Diffie-Hellman assumption does not directly involve a hash function H on page 3. But I am very new to cryptography. $\endgroup$
    – user900476
    May 8, 2022 at 18:31
  • $\begingroup$ Have you ever head the Kleene Star and see in Wiki page $\endgroup$
    – kelalaka
    May 8, 2022 at 18:33

1 Answer 1


First of all, I haven't seen this definition of DDH assumption before. Probably it is something like a Hashed-DDH assumption. If anyone has more information to add or a better answer I would be happy to read about it. I will answer the question without considering the existence of $H$. However, I will answer the notation used to define it.

First, what's the meaning of the asterisk in $H:\{0,1\}^∗→\{0,1\}^k$?

It is used to define a hash function $H$ which takes as input an arbitrary length binary string and return a constant length binary string. The $*$ symbol is the Kleene star.


It means Probabilistic Polynomial Time algorithm.

Third, why if $b=1,s←H(gab)$, else $s←{0,1}^k$? I understand step 1,2,3 but don't understand step 4,5,6

Here DDH, is defined in terms of Indistinguishability Game (IND-Game). It produces two probability distributions based on whether $b$ is $0$ or $1$. If $b=0$ then the adversary's $M$ input is $(\mathcal{G}', g, q, H, g^{a}, g^{b}, g^{ab})$ else if $b=1$ the adversary's input is $(\mathcal{G}', g, q, H, g^{a}, g^{b}, s \overset{\\\$}{\leftarrow} \{0,1\}^k)$. As you can see the only difference on the adversary's inputs is the last argument. The definition considers the adversary's input as probability distributions and assumes that these distributions are indistinguishable for PPT adversaries or equivalently that their statistical distance is negligible for PPT adversaries.

  • $\begingroup$ Thank you very much! Could you please tell me what the meaning of putting \$ on the left arrow is? $\endgroup$
    – user900476
    May 8, 2022 at 18:34
  • $\begingroup$ It is for uniform sampling. $\endgroup$
    – tur11ng
    May 8, 2022 at 19:10
  • $\begingroup$ Thank you very much! I can understand concepts like Diffie–Hellman Key Exchange. But this seems to be way more difficult, including some new concepts such as adversary to me. $\endgroup$
    – user900476
    May 8, 2022 at 19:36
  • $\begingroup$ Depending on your background this is- were you can start toc.cryptobook.us $\endgroup$
    – tur11ng
    May 8, 2022 at 21:09
  • $\begingroup$ Thank you very much, May I ask why the adversary knows G', g, q, H, $g^a$ and $g^b$? And if he knows g, q, $g^a$ and $g^b$, shouldn't he knows $g^{ab}$ (which is different from a random s)? $\endgroup$
    – user900476
    May 9, 2022 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.