# What's the meaning of asterisk and PPT in this paper?

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

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.

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

• Can you also post the paper that you are reading cause I want to get more context on this hash function $H$? May 8 at 18:08
• @JAAAY Sure. I have edited my question. May 8 at 18:13
• To be honest, I cannot understand why the use $H$. May 8 at 18:28
• @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. May 8 at 18:31
• Have you ever head the Kleene Star and see in Wiki page May 8 at 18:33

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.

PPT

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.

• Thank you very much! Could you please tell me what the meaning of putting \$on the left arrow is? May 8 at 18:34 • It is for uniform sampling. May 8 at 19:10 • 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. May 8 at 19:36 • Depending on your background this is- were you can start toc.cryptobook.us May 8 at 21:09 • 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)? May 9 at 22:26