如何在不透露內容的情況下可驗證地宣布選擇？
這是簡化的問題：
- Alice 從一小組可能的值中進行選擇。
- Bob 猜測 Alice 選擇了哪個值。
- 愛麗絲揭示了她選擇的價值。
愛麗絲的選擇最初必須保密，直到鮑勃做出他的猜測。然而，為了確保愛麗絲不會作弊，她的選擇一旦被披露就必須是可驗證的。
我的想法是首先發布選擇的鹽漬雜湊，然後將鹽與選擇一起發布。據我了解，對此有兩種可能的攻擊方式：
- Bob 可以嘗試使用散列找到秘密選擇：鹽應該彌補一小部分有效選擇，因此這應該等於正常的原像攻擊。
- Alice 可以選擇兩個值並蒐索兩個鹽，這樣每一對都會生成相同的散列。由於選擇的數量很少，這應該類似於生日攻擊。
據我所知，這兩種攻擊都不會對例如 SHA 512 造成實際風險。這會是一種有效的方法嗎？我錯過了什麼嗎？有更好的解決方案嗎？
這是承諾方案的前提。這個場景中的戲劇人物是證明者佩吉，他希望證明對資訊的預知 $ m $ 給驗證者維克多，但後來才透露 $ m $ ，此時維克多可以確認佩吉在此期間沒有改變主意。
留言 $ m $ , Peggy可以承諾 $ m $ 通過選擇隨機化 $ r $ 併計算承諾 $ c = C_r(m) \in \mathcal C $ 她在保留的同時給了維克多 $ m $ 和 $ r $ 秘密。後來，當佩吉想要透露消息時，她給了維克多 $ m $ 和 $ r $ ，以便維克多可以驗證 $ c = C_r(m) $ . 承諾 $ C_r(m) $ 應該有兩個屬性：它應該基本上不顯示關於 $ m $ 給任何不知道的人 $ r $ , 但應該基本上不可能找到 $ m’ \ne m $ 和 $ r’ $ 這樣 $ C_r(m) = C_{r’}(m’) $ 從而打破承諾。
第一個屬性是hide，可以通過限制任何（可能是成本有限的）對手的優勢來形式化 $ D(c) $ 區分承諾 $ C_r(m) $ 任何消息的 $ m $ 對於均勻隨機 $ r $ ，來自一個統一的隨機承諾 $ c \in \mathcal C $ : $ \left|\Pr[D(C_r(m))] - \Pr[D(c)]\right| $ . 如果分佈 $ C_r(m) $ 和分佈完全一樣 $ c $ ，那麼這個優勢正好為零，並且承諾方案據說是資訊理論隱藏的；否則它是計算隱藏的。
第二個屬性是具有約束力的，可以通過對任何（可能是成本有限的）對手的機率進行限制來形式化 $ F() $ 去尋找 $ (r, m, r’, m’) $ 和 $ m’ \ne m $ 這樣 $ C_r(m) = C_{r’}(m’) $ . （如果在 $ F $ ，那是因為我們通常用隨機預言機實例化它 $ H $ 或公共參考字元串 $ \sigma $ 並問 $ F(H) $ 或者 $ F(\sigma) $ .) 如果每個承諾恰好有一條消息可能，那麼這個機率正好為零，並且承諾方案被認為是資訊論綁定的；否則它是計算綁定的。
標準範例：
雜湊承諾。 $ C_r(m) = H(r \mathbin| m) $ ， 或者 $ C_r(m) = \operatorname{HMAC-}!H_r(m) $ ， 在哪裡 $ H $ 是預先選擇的統一隨機函式，因此 Peggy 和 Victor 對其沒有影響，在證明中被建模為隨機預言機，並由原像和抗碰撞雜湊實現 $ H $ 像 SHAKE128。
- 雜湊承諾只是計算隱藏，但對此的區分可以轉化為原像攻擊 $ H $ ， 因此，如果 $ H $ 是抗原像的，則隱藏雜湊承諾；相反，原像攻擊 $ H $ 可以使對手了解秘密承諾值。
- 雜湊承諾僅在計算上具有約束力，但在此上破壞承諾可以轉化為對 $ H $ ， 因此，如果 $ H $ 是抗碰撞的，那麼雜湊承諾是綁定的；相反，碰撞攻擊 $ H $ 可能使對手破壞承諾。因此，例如，MD5 和 HMAC-MD5 不適用於 $ H $ 儘管 HMAC-MD5 似乎仍然是一個很好的 PRF。人們有時會在 Twitter 上使用雜湊承諾，因為它很方便，而且每個人都知道如何計算 SHA-256 來驗證它們。
佩德森的承諾。 $ C_r(m) = g^r h^m $ ， 在哪裡 $ g $ 和 $ h $ 是素數群的元素 $ G $ 其中離散對數是困難的——預先均勻隨機選擇的元素，這樣 Peggy 和 Victor 對它們沒有影響，在證明中建模為公共參考字元串，並由FIPS 186-4等協議實現，附錄 A.2.3使用雜湊SHAKE128 等功能。在這裡，與散列承諾不同，消息不是位串，而是 $ \mathbb Z/\ell\mathbb Z $ 在哪裡 $ \ell $ 是組的順序 $ G $ .
- Pedersen 承諾在理論上是隱藏的，因為 $ r \mapsto g^r h^m $ 是逆雙射 $ c \mapsto \log_g (c/h^m) $ , 所以分佈 $ g^r h^m $ 制服 $ r $ 是均勻的 $ G $ .
- Pedersen 承諾在計算上具有約束力，因為任何能夠計算離散對數的人 $ G $ 可以找到 $ x = \log_g h $ 以便 $ g^r h^m = g^{r + x m} $ 從而可以用任意消息打破承諾 $ m’ $ 通過選擇 $ r’ = r + x (m - m’) $ . 更具體地說：如果 Pedersen 承諾破壞者 $ F(g, h) $ 可以找到 $ (r, m, r’, m’) $ 和 $ m \ne m’ $ 這樣 $ g^r h^m = g^{r’} g^{m’} $ ， 然後 $ \log_g h = \frac{r’ - r}{m - m’} $ ，因此任何可以在此方案中違反承諾的人都可以計算離散對數 $ G $ .Pedersen 承諾也是同態的：如果 $ c_0 = C_{r_0}(m_0) $ 和 $ c_1 = C_{r_1}(m_1) $ ， 然後 $ c_0 c_1 = C_{r_0 + r_1}(m_0 + m_1) $ ，因此對於零知識證明系統中的花哨密碼學很方便。人們有時會使用 Pedersen 承諾（意外地？）在電子投票中設置後門，以試圖證明因匿名而改組的選票不是在此過程中偽造的。 如果 Peggy 可以選擇**元素，****Pedersen 承諾有一個後門 $ g $ 和 $ h $ :**如果佩吉選擇他們有一個已知的關係 $ h = g^x $ ，然後她可以像上面那樣偽造承諾並進行無限制的投票欺詐。
Elgamal 的承諾。 $ C_r(m) = (g^r, h^r m) $ ， 在哪裡 $ g $ 和 $ h $ 是素數群的元素 $ G $ 其中離散對數是困難的——隨機均勻選擇的元素作為公共參考字元串等，如 Pedersen 承諾。
- Elgamal 承諾在計算上是隱藏的，因為任何可以計算離散對數的人 $ G $ 可以，給予承諾 $ (u, v) $ ， 恢復 $ r = \log_g u $ 和 $ m = v/h^r $ . 更具體地說：一個 Elgamal 承諾區分器可以變成一個決定性的 Diffie-Hellman 攻擊 $ G $ , 所以如果DDH 很難， Elgamal 承諾在計算上是隱藏的，儘管可以想像 DDH 可能很容易，而 DLOG 很難 $ G $ .
- Elgamal 承諾在資訊理論上具有約束力，因為每個承諾都有一個可能的消息。Elgamal 承諾也是同態的：如果 $ c_0 = C_{r_0}(m_0) = (u_0, v_0) $ 和 $ c_1 = C_{r_1}(m_1) = (u_1, v_1) $ ，然後是元素乘積 $ c_0 c_1 = (u_0 u_1, v_0 v_1) $ 是 $ C_{r_0 + r_1}(m_0 m_1) $ . 我不知道誰在實踐中使用 Elgamal 承諾。 **如果 Victor 可以選擇，Elgamal 承諾有一個後門 $ g $ 和 $ h $ ：**如果維克多可以選擇他們有一個已知的關係 $ h = g^x $ ，然後從一個承諾 $ (u, v) = (g^r, h^r m) = (g^r, g^{x r} m) $ , 維克多可以恢復 $ m $ 經過 $ v/u^x = g^{x r} m / (g^r)^x = m $ .