承諾方案的具體通信複雜度是多少？
假設你想送出一個 $ n $ -位明文， $ x \leftarrow ^ r {0,1}^n $ .
具體的溝通成本是多少？ $ n $ ， 以下的：
- 驗證者發送的初始化數據（適用於 Pedersen，可能不適用於其他方案）。
- 承諾
- 解除承諾
我閱讀了 Pedersen 計劃的描述。由於該方案只允許您承諾 $ Z_q $ , 我假設，為了避免處理巨大的素數，在實踐中你會將你的輸入分解成 $ b $ -位塊使得 $ q > 2^b $ . 在我看來是合理的選擇 $ b=128 $ , $ q $ 選擇一個 129 位素數，使得 $ p=2q+1 $ ， 製造 $ p $ 一個 130 位素數。我假設 $ p $ , $ q $ 和 $ g $ （生成器）是眾所周知的，並且是事先計算好的。在這種情況下，發送 128 位的成本為：
- 驗證者發送的數據： $ h =g^a\mod p $ , 一個 130 位的數字
- 承諾： $ c = g^m h^r \mod p $ ，另一個 130 位數字。
- 解除承諾： $ m, r \in Z_q $ , 兩個 129 位數字。
所以總的通信成本是 $ \frac{518 n}{128} $ 位。
這是正確的嗎？
如果還有其他更好的承諾方案，請隨意提供具體數字。但是，我希望承諾方案是自包含的，因此本文雖然對其具體安全性提供了非常清晰的解釋，但不符合我的要求，因為它需要一個通用的參考字元串。
最簡單的承諾方案是基於散列的承諾；承諾一個價值 $ M $ ，送出者選擇一個固定長度的值 $ R $ 並發表 $ \operatorname{Hash}(R \mathbin\Vert M) $ ; 為了解除承諾，他發布了價值觀 $ R $ 和 $ M $ .
如果雜湊函式是抗衝突的，那麼送出者就不能送出兩個不同的消息；如果 $ R $ 足夠長，那麼恢復是不可行的 $ M $ 從承諾。
考慮到這一點，假設我們使用 256 位散列（例如 SHA256）作為散列函式，並且使用 128 位 $ R $ :
- 驗證者發送的數據：無
- 承諾：256 位
- 解除承諾：128+n 位
這總共是 384+n 位。
我相信可以證明，如果不將系統的實際安全性降低到“128位”級別以下，您將無法做得更好