如何完成統計上不可區分分佈的證明？
鑑於：
$$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n) $$
在哪裡 $ SD $ 代表統計距離， $ r $ 是隨機均勻的 $ {0,1}^n $ , $ s $ 是隨機均勻的 $ S \subseteq {0,1}^n $ 和 $ b $ 是一個均勻分佈的位。
看起來很直覺，給定一個抗碰撞雜湊函式 $ h $ ，它還應該認為：
$$ SD\bigg( \big(h(s), r, \langle r, s \rangle \oplus 0\big),\big(h(s), r, \langle r, s \rangle \oplus 1\big) \bigg) < \mathrm{negl}(n) $$
但我似乎無法證明這一點。我試過使用的正式定義 $ SD $ ，但我不知道如何處理存在元組的事實，所以我什至還沒有達到可以合併第一個聲明的地步。
有沒有辦法從第一個索賠中證明這一點？還是我錯了，有辦法反駁這一點？（對於上下文 - 我試圖證明這一點 $ \big(h(s), r, \langle r, s \rangle \oplus b\big) $ 是一個統計隱藏的承諾方案）。
謝謝。
我不確定這是否能回答你的問題，但這裡有一個證據，證明在計算上顯示抗原像雜湊函式的兩個分佈之間的統計距離應該是不可行的。讓 $ h $ 和 $ r_0 $ 是兩個值，使得 $$ \left|\mathbb P(h(s)=h, r=r_0, \langle r,s\rangle=0)- \mathbb P(h(s)=h, r=r_0, \langle r,s\rangle=1)\right|>\mathrm{negl} $$這相當於可區分性標準。這告訴我們 $$ \left|\mathbb P(\langle r_0,s\rangle=0|h(s)=h)-\mathbb(\langle r_0,s\rangle=1|h(s)=h)\right|>\mathrm{negl} $$ 請注意，總機率定律上述兩個機率之和為 1。讓我們假設 $$ \mathbb P(\langle r_0,s\rangle=0|h(s)=h)>1/2+\delta $$ 對於一些不可忽視的 $ \delta $ （另一種情況非常相似）。我們將使用這個 $ h $ 和 $ r_0 $ 半窮舉地建構一個原像 $ s $ 這樣 $ h(s)=h $ .
我們限制自己評估 $ h(s) $ 關於統計的輸入 $ \langle r_0,s\rangle =0 $ ，然後由貝氏定理 $$ \mathbb P(h(s)=h|\langle r_0,s\rangle=0)=\frac{\mathbb P(\langle r_0,s\rangle=0|h(s)=h)\mathbb P(h(s)=h)}{\mathbb P(\langle r_0,s\rangle=0}=(1+ \frac 2\delta)\mathbb P(h(s)=h) $$ 並且我們將成功的可能性提高了一個因素 $ (1+2 delta) $ 過度疲勞。如果多個 $ r_i $ 值不可忽略且獨立地偏離，我們可以通過選擇耗盡滿足多個線性約束的輸入來提高優勢。