本文中的星號和PPT是什麼意思？
我對密碼學很陌生。我需要讀一篇論文。
我完全不明白。首先，中的星號是什麼意思 $ H:{0,1}^*\rightarrow {0,1}^k ? $ .
二、這裡的PPT是什麼意思？（我搜尋了網際網路，但沒有得到滿意的答案。）
三、為什麼如果 $ b=1, s\leftarrow H(g^{ab}) $ ， 別的 $ s\leftarrow {0,1}^k $ ? 我了解第 1、2、3 步，但不了解第 4、5、6 步。
誰能幫我解釋一下？我將不勝感激。
PS：論文是 Practical Secure Aggregation for Privacy-Preserving Machine Learning。 https://eprint.iacr.org/2017/281.pdf
首先，我之前沒見過這個DDH假設的定義。可能它類似於 Hashed-DDH 假設。如果有人有更多資訊要添加或更好的答案，我很樂意閱讀。我會在不考慮存在的情況下回答這個問題 $ H $ . 但是，我將回答用於定義它的符號。
首先，中的星號是什麼意思 $ H:{0,1}^∗→{0,1}^k $ ?
它用於定義雜湊函式 $ H $ 它將任意長度的二進製字元串作為輸入並返回一個恆定長度的二進製字元串。這 $ * $ 符號是克林星。
PPT
這意味著機率多項式時間算法。
三、為什麼如果 $ b=1,s←H(gab) $ ， 別的 $ s←{0,1}^k $ ? 我了解第 1,2,3 步，但不了解第 4,5,6 步
這裡 DDH 是根據不可區分性遊戲 (IND-Game) 定義的。它根據是否生成兩個機率分佈 $ b $ 是 $ 0 $ 或者 $ 1 $ . 如果 $ b=0 $ 那麼對手的 $ M $ 輸入是 $ (\mathcal{G}’, g, q, H, g^{a}, g^{b}, g^{ab}) $ 否則如果 $ b=1 $ 對手的輸入是 $ (\mathcal{G}’, g, q, H, g^{a}, g^{b}, s \overset{\$}{\leftarrow} {0,1}^k) $ . 如您所見，對手輸入的唯一區別是最後一個參數。該定義將對手的輸入視為機率分佈，並假設這些分佈對於 PPT 對手來說是無法區分的，或者等效地，對於 PPT 對手來說，它們的統計距離可以忽略不計。