Score:0

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

eg flag

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

JAAAY avatar
us flag
Can you also post the paper that you are reading cause I want to get more context on this hash function $H$?
user900476 avatar
eg flag
@JAAAY Sure. I have edited my question.
JAAAY avatar
us flag
To be honest, I cannot understand why the use $H$.
user900476 avatar
eg flag
@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.
kelalaka avatar
in flag
Have you ever head the [Kleene Star](https://crypto.stackexchange.com/q/89067/18298) and see in [Wiki page](https://en.wikipedia.org/wiki/Kleene_star)
Score:1
us flag

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.

user900476 avatar
eg flag
Thank you very much! Could you please tell me what the meaning of putting \$ on the left arrow is?
JAAAY avatar
us flag
It is for uniform sampling.
user900476 avatar
eg flag
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.
JAAAY avatar
us flag
Depending on your background this is- were you can start https://toc.cryptobook.us/
user900476 avatar
eg flag
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)?
JAAAY avatar
us flag
No. If he knows $x=g^a$ and $y=g^b$ in a multiplicative prime order group for example, he cannot deduce $x^b$ or $y^a$. This is the whole concept of Computational Diffie Hellman assumption. Be careful here $x \cdot y = g^a \cdot g^b = g^{a+b}$. Also be careful the in your example you have the Decisional Diffie Hellman Assumption which is a similar but a stronger assumption. You can read more [here](https://crypto.stackexchange.com/questions/1493/what-is-the-relation-between-discrete-log-computational-diffie-hellman-and-deci).
user900476 avatar
eg flag
I got it, the adversary only knows $x=g^a$ and $y=g^b$ but it doesn't know $G', g, q, H$, right? I saw the function in step 5 is $M(G', g, q, H, g^a, g^b, s)$ and thought the adversary knew all the parameters.
JAAAY avatar
us flag
No, $G′,g,q,H$ are public parameters. As per the Kerckhoffs's principles he has access to them. The only thing he doesn't know are $a$ and $b$ and hence he cannot deduce $g^{ab}$.
JAAAY avatar
us flag
To put it simply, in $x=g^a$. $x$ is the public key and $a$ is the private key. Adversary has access to the public information.
Manish Adhikari avatar
us flag
I am pretty sure the definition of DDH assumption does not use this hash. This, definition however seems more directly related to the security of DH key exchange than CDH assumption.
JAAAY avatar
us flag
Thanks you for your confirmation because I was a bit worried. Although this is a strange notation and definition it the paper is accepted by IACR :|
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.