辨識兩個隨機值是否提升到相同的冪
Alice 從有限域中選擇兩個隨機數 $ Z_p $ : $ a $ 和 $ b $ .
Bob 隨機執行以下兩個步驟之一（有時他執行第 1 步；有時執行第 2 步）：
- 他選擇一個隨機數 $ r $ 從 $ Z_p $ 併計算 $ a^r;mod;p $ 和 $ b^r;mod;p $ 並將這兩個值給愛麗絲
- 他選擇了兩個不同的隨機數 $ r $ 和 $ r’ $ 從 $ Z_p $ 併計算 $ a^r;mod;p $ 和 $ b^{r’};mod;p $ 並將這兩個值給愛麗絲
是否有任何有效的算法 Alice 可以用來辨識 Bob 完成了哪一步？
這裡小 $ a $ 和 $ b $ 應選自 $ \mathbb{Z}^*_p $ 和 $ r $ 之間 $ 1 $ 和 $ p-1 $ 獨家的
看起來像這樣，它似乎與 DDH 問題直接相關，至少如果存在一些 $ w $ 這樣要麼 $ a = b^w $ 或者 $ b = a^w $ . 也就是說，如果至少有一個 $ a $ 或者 $ b $ 生成包含另一個給定 if 的子組 $ p $ 是一個安全的素數
$$ if both are quadratic residues/non-residues either exists otherwise whichever is a non-residue is a generator $$，不確定其他情況。在這種情況下 $ a, b^{r’}, a^{r} $ 使 DDH 三元組生成自 $ b $ 或者 $ b,a^r,b^{r’} $ 製作 DDH 三元組 $ a $ . 在您的情況下，DDH 問題是否難以解決不取決於選擇 $ a $ 和 $ b $ . 如果兩者 $ a $ 和 $ b $ 生成具有大素數階的相同子組，則 DDH 問題在經典電腦中被認為是困難的。因此，在這種情況下沒有已知的有效經典算法。在許多其他情況下，DDH 問題的解決機率明顯高於隨機猜測。例如，如果兩者 $ a $ , $ b $ 是非殘差模組 $ p $ 和當中 $ a^r, b^{r’} $ 一個是二次餘數，另一個是非餘數，你可以看出其中一個 $ r,r’ $ 是奇數，另一個是偶數，因此 $ r \neq r’ $ . 在你的問題中 $ a $ 和 $ b $ 是隨機生成的，所以我會說它是可區分的。並非在所有情況下，但在我之前提到的情況下有優勢，在電腦科學中被認為是重要的，被認為是不可區分的
我不確定兩者都不是的情況 $ a $ 也不 $ b $ 生成包含另一個的子組，因為我想不出一種將它與 DDH 相關聯的方法，至少不是在我的腦海中。在這種情況下也可能有一些具有優勢的子案例
更新：您已聲明您正在嘗試設計一個協議。首先，在沒有深入了解密碼學的情況下嘗試這樣做是不明智的。假設系統的整個安全性都依賴於此，那麼您應該使用 $ g $ 用於生成 $ a $ 和 $ b $ 成為大素數階子群的某個生成器 $ q $ 並選擇 $ r,r’ $ 之間 $ 1 $ 和 $ q $ 以確保 DDH 問題在經典電腦中被推測為困難。或者使用已知的非配對友好 EC 組，其中 DDH 問題被推測為經典難題。但我仍然不知道協議的細節。並且實施它仍然存在諸如側通道攻擊等問題。
如果 Bob 願意幫助 Alice 辨識案例 1，他可以執行類似 Schnorr 的協議作為證明者。他會產生反應治療 $ r $ 作為協議指定的私鑰。Alice 將驗證這個響應是否適合兩個隨機數，被視為兩個公鑰。