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$
    – JAAAY
    May 8 at 18:08
  • $\begingroup$ @JAAAY Sure. I have edited my question. $\endgroup$
    – user900476
    May 8 at 18:13
  • $\begingroup$ To be honest, I cannot understand why the use $H$. $\endgroup$
    – JAAAY
    May 8 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 at 18:31
  • $\begingroup$ Have you ever head the Kleene Star and see in Wiki page $\endgroup$
    – kelalaka
    May 8 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 at 18:34
  • $\begingroup$ It is for uniform sampling. $\endgroup$
    – JAAAY
    May 8 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 at 19:36
  • $\begingroup$ Depending on your background this is- were you can start toc.cryptobook.us $\endgroup$
    – JAAAY
    May 8 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 at 22:26

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.