Naor於1990年建構的Bit承諾方案的安全問題
在 Boneh 和 Shoup 所寫的書的第 3.12 節中，來自安全 PRG 的比特承諾如下所示：
鮑勃承諾咬 $ b_0\in_R{0,1} $ :
第 1 步：Alice 隨機選擇一個 $ r\in R $ 並發送 $ r $ 給鮑勃。
第 2 步：Bob 隨機選擇一個 $ s\in S $ 併計算 $ c=com(s,r,b_0) $ ， 在哪裡 $ com(s,r,b_0) $ 是ollowing函式： $ c=com(s,r,b_0):=\left{ \begin{array}{rcl}G(s) & \mbox{if}& b_0=0 \ G(s)\oplus r & \mbox{if} & b_0=1 \ \end{array}\right. $ ， 在哪裡 $ G:S\to R $ 是一個安全的 PRG 並且 $ |R|\geq |S|^3 $ .
鮑勃輸出 $ c $ 作為承諾字元串並使用 $ s $ 作為開場字元串。
在揭示階段，當接收 $ s $ 和 $ b_0 $ 從 Bob 那裡，Alice 確實可以檢查 $ c=com(s,r,b_0) $ .
所以，我的問題是，如果我們刪除值 $ r $ 從上述方案，這意味著：
- 在第 1 步中，Alice 不必向 Bob 發送隨機值，這使得該方案非互動式。
- 在步驟 2。如果 $ b_0=1 $ 然後 Bob 計算 $ c=G(s)\oplus k $ ， 在哪裡 $ k=0…01\in R $ 是一個眾所周知的常數和第一個 $ |k|-1 $ 位 $ k $ 都是零。
修改後的版本是否仍然安全？或者換句話說，鮑勃可以欺騙愛麗絲嗎？
您是在專門詢問綁定屬性（“Bob 可以欺騙 Alice 嗎？”）。回憶一下 Naor 方案中如何證明綁定是有幫助的。
假設對手產生了一些承諾 $ c $ . 如果他們可以將承諾打開為 0 則必須存在 $ s_0 $ 這樣 $ G(s_0) = c $ . 如果他們可以打開對 1 的承諾，那麼必須存在 $ s_1 $ 這樣 $ G(s_1) \oplus r = c $ . 因此，如果他們能打開 $ c $ 對於這兩個值，那麼必須存在 $ s_0, s_1 $ 這樣 $ G(s_0) \oplus G(s_1) = r $ . 如果對手可以模棱兩可，那麼它反映了一些有趣的事情 $ r $ 它不僅反映了一些有趣的事情 $ c $ .
如果一個值為 $ r $ 具有上述屬性，我們稱其為“有問題的”。有 $ 2^{2\lambda} $ 對 $ (s_0,s_1) $ , 所以最多 $ 2^{2\lambda} $ 有問題的價值觀 $ r $ . 如果 $ G $ 是長度的三倍，那麼有 $ 2^{3\lambda} $ 的可能值 $ r $ 愛麗絲可以選擇。所以當愛麗絲選擇 $ r $ 一致地，她得到一個有問題的機率可以忽略不計 $ 1/2^\lambda $ . 只要她避免出現問題 $ r $ ，承諾將具有完全約束力。
現在你提議修復一個特定的 $ r $ ，例如作為 $ r=0\cdots01 $ . 問題是這是否 $ r $ 可能有問題。是否存在 $ s_0, s_1 $ 這樣 $ G(s_0) \oplus G(s_1) = 0\cdots 01 $ ? 當然！帶上你最喜歡的 PRG 和你最喜歡的兩個琴弦 $ s_0 $ 和 $ s_1 $ , 並重新定義 PRG 的輸出 $ s_0 $ 和 $ s_1 $ 擁有上述財產。修改後的函式仍然是 PRG，但您修改後的 Naor 方案對於此 PRG 是不安全的（攻擊者可以依賴 $ s_0 $ 和 $ s_1 $ 因為對手當然可以取決於 PRG 的選擇）。
所以不，Naor 的方案在一般情況下是不安全的 $ r $ 是固定的。對於任何 $ r $ 你想修復，我可以建構一個安全的 PRG，導致這個修改後的 Naor 方案不安全。為了獲得額外的信用，建構一個安全的 PRG $ G $ 這樣，對於每個可能的輸出 $ G(s) $ ， 價值 $ G(s)\oplus 0\cdots01 $ 也是一個可能的輸出 $ G $ .