Commitments
證明 ROM 中簡單承諾方案的統計隱藏
眾所周知，可以通過設置在隨機預言模型（ROM） 中構造一個簡單的承諾方案 $ \mathsf{Commit}(m;r) = H(r||m) $ ， 在哪裡 $ m \in {0,1}^k $ , $ r \in {0,1}^{2k} $ 和 $ H: {0,1}^* \to {0,1}^k $ 被建模為隨機預言機。我的問題是：我怎樣才能正式證明這個方案在統計上是隱藏的？直覺地說，RO 正在“壓縮”，因此會有足夠的隨機字元串 $ r, r’ $ 這樣一個挑戰承諾 $ c $ 在隱藏實驗中可以有形式的原像 $ r||m_0 $ 或者 $ r’||m_1 $ 具有相似的高機率，因此即使是無界的對手在實驗中的優勢也可以忽略不計。但這只是一種直覺，而不是正式的證明。對於如何證明該陳述的一些建議，我將非常感謝。
（另外我想知道是否隨機字元串 $ r $ 長度 $ 2k $ 足以實現統計隱藏。也許可以在證明中看到我們需要更長的隨機字元串。）
承諾的統計隱藏不是關於與給定承諾輸出相關的輸入的分佈，而是與給定消息對相關的承諾輸出的分佈。
您需要證明的是，對於任何兩個固定消息，輸出的兩個分佈之間的總變化距離很小。現在，統計距離是一個度量，因此適用三角不等式。第三種分佈的一個好的選擇是均勻分佈 $ 2^k $ 輸出。隨機預言模型意味著固定消息的輸出分佈的總變化與均勻的總變化距離很小，因此通過三角不等式，兩個固定的不同消息的輸出分佈的總變化距離很小。