Public-Key
低熵見證的零知識
對於任何 PPT 證明者（ $ p $ ) 和驗證者 ( $ v $ )，假設我有一個低熵證人，說小於 $ 2^8 $ . 現在，假設我有一個 dlog 語句，形式為 $ y = g^w $ . 理論說我可以使用 sigma 協議，這樣 $ p $ 可以證明 $ v $ 它知道 $ w $ . 我還可以利用法定 shamir 變換使其非互動式。
當見證人的熵像本例中那樣低時，情況並非如此。在這兩種情況下，我都可以簡單地列舉 $ 256 $ 可能的見證人並使用響應和承諾來檢查它可能對應於哪一個，即：
對於承諾：
$ t = g^v $
一個挑戰 $ c $ 和回應：
$ r = t + c \times x $
很明顯，如果我有 $ r, \space c $ 和 $ t $ 我可以恢復 $ x $ . 如果我們改用 Pedersen 承諾，也會發生同樣的情況。
我認為這是所有基於 dlog 的 ZKPoK 的常見問題，但我不確定，也不知道應該改用什麼。
在這種情況下，唯一的一條線是：當證人熵那麼低時，我如何證明知識？
Pedersen 的承諾似乎可以解決您的問題。
Pedersen 的承諾是一種價值 $ t = g^w h^r $ （對於見證值 $ w $ 和一個隨機值 $ r $ ); 有人無法恢復 $ w $ 從該值（實際上，即使是計算無界的對手也無法做到這一點）。這是真的，即使 $ w $ 是低熵。
並且，提出某人知道某項知識的知識證明是直截了當的。 $ (w, r) $ 構成 $ t $ ， 如：
- 證明者隨機選擇 $ x, y $ , 併計算 $ s = g^x h^y $ , $ u = x + w \cdot H(s) $ , $ v = y + r \cdot H(s) $
- 證明者發布 $ s, u, v $
- 驗證者接受如果 $ g^u h^v = s t^{H(s)} $
在哪裡 $ H $ 是適當範圍內的散列函式。
這是 Schnorr 證明的簡單擴展。