使用 DDH 假設的計算不可區分性
這是 Vipul Goyal 在本講稿中對 DDH 承諾方案的解釋的一部分：https ://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture22.pdf
我的問題與pdf的內容沒有直接關係，但在第20-4頁中，它說 $ {g, g^a, g^b, m \cdot g^r |(a, b, r) \leftarrow \mathbb{Z}_q} $ 在計算上無法區分 $ {g, g^a, g^b, g^r |(a, b, r) \leftarrow \mathbb{Z}_q} $ . 為什麼這一定是真的？誰能正式解釋為什麼會這樣？此外，當文本以這種方式描述分佈時，兩個 $ (a, b, r) $ 的兩個分佈相等嗎？或者只是符號相同，但實際上它們是獨立隨機選擇的 $ \mathbb{Z}_q $ ?
謝謝。
那麼這個 $ m $ 是組中的某個元素 $ \mathbb{G} $ 所以存在一些 $ \alpha \in \mathbb{Z}_q $ 這樣 $ m=g^{\alpha} $ ， 因此 $ m \cdot g^r = g^{\alpha+r} $ 並註意到，因為 $ r $ 均勻地隨機選擇 $ \mathbb{Z}_q $ , 那麼分佈 $ \alpha + r $ 在 $ \mathbb{Z}_q $ 也是。
直覺上你可以想到 $ r+\alpha $ 作為服用 $ \alpha $ 某人為您選擇的，然後添加一個隨機數模 $ q $ ，並且它是完全一致的，因為對於每個可能的結果 $ r+\alpha $ 正好有一個 $ r $ 這使它成為結果，因此它是統一的。
至於 (a,b,r) - 請記住，DDH 假設試圖說的是：如果您查看兩個隨機組元素 $ g^a, g^b $ 你有第三組元素 $ h\in\mathbb{G} $ ，那麼你不知道是否 $ h=g^{a\cdot b} $ 或者那個 $ h $ 是一些完全隨機的、不相關的群元素 $ g^r $ 對於一些隨機的 $ r $ . 你寫這個的方式是看兩個發行版，其中 $ g^a, g^b $ 等式兩邊相同，但第三個元素不同（它是 $ g^{a \cdot b} $ 或者 $ g^r $ 你說在 DDH 假設下，不存在一個有效的機率多項式時間圖靈機可以區分 $ g^{a \cdot b} $ 和一個隨機群元素。