基於 DLP 的鍵控單向功能

我試圖了解是否可以使用 DLP 建構具有以下屬性的鍵控單向函式：

1. $ H_a(H_b(M)) = H_c(M) $ ， 在哪裡 $ a $ 和 $ b $ 是鍵，並且 $ c=a*b $
2. 該函式的輸出相對較小——例如 256 位

函式本身可以是 $ h_a=M^a $ 反對 $ p $ ， 在哪裡 $ p $ 是 256 位素數。但是，鑑於素數很小，我不確定這會有多安全。具體來說，我想了解以下是否成立：

1. 給定 $ h_a $ 和 $ p $ , 計算是不切實際的 $ M $
2. 給定 $ h_a $ , $ M $ , $ c $ ， 和 $ p $ , 計算是不切實際的 $ a $

我需要處理的消息相對較小（256 - 512 位），但如果這樣可以提高安全性，可以進行填充。

可以計算離散對數模的對手 $ p $ , 給定 oracle 訪問權限 $ H_a $ 對於未知 $ a $ , 可以計算 $ \log_2 H_a(2) \equiv \log_2 2^a \equiv a \pmod p $ 對 oracle 進行一次查詢。

之後，給定 $ h = H_a(M) $ 對於未知 $ M $ , 他們可以計算

$$ h^{a^{-1}} \equiv (M^a)^{a^{-1}} \equiv M^{a\cdot a^{-1}} \equiv M \pmod p, $$在哪裡 $ a^{-1} $ 是的倒數 $ a $ 模組 $ \phi(p) = p - 1 $ . 如果 $ p $ 是 256 位，攻擊者可以計算離散對數模 $ p $ 今天。你需要 $ p \gg 1024 $ 是安全的，除其他標準外。

更詳細地了解為什麼需要這些屬性以及更普遍地嘗試實現的目標可能會有所幫助。

引用自：https://crypto.stackexchange.com/questions/58169