證明一個決定是隨機做出的
愛麗絲和鮑勃想在一點上達成一致 $ 0 $ 或者 $ 1 $ . 兩人都知道隨機選擇是公平的，但他們不可能會面擲骰子，也沒有他們可以信任的第三方。是否有已知的協議允許任何一方證明他們沒有操縱結果？
我的想法是：隨機選擇（或不隨機選擇——但這符合他們的最大利益） $ 0 $ 或者 $ 1 $ ，寫下來，裝進信封，寄給對方。那麼這兩個位的 XOR 不可能被任何一方不公平地操縱。
我看到的問題是：愛麗絲如何向鮑勃證明她在做出選擇之前沒有打開他的信封？
也許可以改為選擇一個初始字元串 $ n $ 並使用第一個 $ k $ 和 $ f^k(n) < a $ 作為選擇的值。現在如果 $ f $ 是一個密碼散列函式，並且 $ a $ 是小愛麗絲如果要預測的話會花很長時間 $ k $ 在發送她自己的選擇之前。
你很接近使用信封的想法；標準答案是使用承諾方案；這是一種方案，有人可以發布對某個值的“承諾”，然後再揭示該值是什麼。承諾的兩個基本屬性是：
- 只看承諾的人無法說出秘密是什麼
- 有承諾的人不能透露承諾的價值以外的價值。
這在這種情況下的工作原理與您的信封方法完全相似；Alice 選擇一個隨機位，並發布對該位的承諾。Bob 然後選擇了一點（那裡不需要承諾）並發布它；然後，愛麗絲透露了她承諾的那一點；Alice 和 Bob 的位的異或是輸出。
現在，有許多已知的實際承諾方案。最簡單的是使用加密安全的散列函式；愛麗絲選擇一個大的隨機值 $ A $ 並發布雜湊值 $ hash(A) $ . Bob 然後選擇他的比特並發布它；愛麗絲然後發布 $ A $ （他們使用，比如說， $ A $ 是愛麗絲的位）。
看著 $ hash(A) $ , Bob 沒有得到關於 lsbit 是什麼的資訊 $ A $ 是（假設 Alice 選擇了一個足夠大的位串）。這不是加密安全散列函式的正式要求，而是對真實散列的合理假設（特別是如果 Alice 選擇一個 $ A $ 比散列函式輸出長）。
並且，假設我們使用加密安全的雜湊函式，Alice 無法決定揭示不同的值 $ A’ $ ; 如果可以，那意味著 Alice 發現了一個雜湊衝突 $ hash(A) = hash(A’) $ ，我們假設 Alice 做不到。