一次性密碼本的密碼分析
我的問題與此有關： 一次性墊的安全性 $ \bmod $ 手術？ 但是我們屏蔽值的方式在這裡是不同的。
我們考慮一個有限域， $ \mathbb{F}_p $ , 和一個環 $ \mathbb{Z}_N $ ， 在哪裡 $ N $ 是 RSA 模數，這樣 $ p<<N $ . 價值 $ p $ 是一個（大）素數，獨立於用於生成的素數 $ N $ .
讓 $ m_i\in \mathbb{F}_p $ . 我們將其屏蔽為：
$ m’i=m_i+r_i $ ， 在哪裡 $ r_i $ 從環中隨機均勻地挑選，但 $ m_i+r_i \in \mathbb{Z}{N} $ .
請注意，我們不執行 $ \bmod N $ 當我們計算 $ m’_i $ .
問題1： 有什麼方法可以論證給定的 $ m’_i $ , 一個半誠實的對手無法了解任何關於 $ m_i $ ? 例如，它是靜態無法區分的等。
為簡單起見，我們假設所有值都不為零。我們可以選擇足夠大的 $ p $ 和 $ N $ 如果需要，滿足任何安全定義。
是的，我相信你可以在這裡爭論統計上的不可區分性。但是，請注意，這是一個比典型的一次性填充更弱的屬性，後者是完全安全的，因為 XOR 是數學魔法（不會產生 $ \mathsf{negl}(\lambda) $ 大小的統計偏移量如下..)。
高層次的想法：如果 $ N $ 是足夠大的 $ p $ — 即如果 $ N \ge \Omega(p\cdot\lambda^{\omega(1)}) $ — 然後隨機樣本大小 $ \approx N $ 統計上會吞下任何“ $ p $ -有界”**分佈（大小的隨機樣本 $ \approx p $ ).
$$ [Let $\lambda$ be the security parameter. For now, I’ll ignore the factorization of $p$ vs $N$ for this.. $$] 這是分佈之間的統計距離的一些樂趣：
一個分佈 $ \chi $ 是 *$ (B,\epsilon) $ -*如果採樣值的機率大於 $ B $ 不太可能；IE
$$ \Pr_{x\leftarrow\chi}[|x| > B] < \epsilon. $$ （旁白： 實際上，我在這裡的討論也假設 $ B $ 在 $ B $ -對於給定分佈， “選擇盡可能小*”的有界分佈；IE $ B $ 應該是“緊”的 $ \chi $ 漸近地。*)
一個分佈 $ \widetilde{\chi} $ 是 $ (B,\epsilon) $ -如果所有人都吞下 $ y\in [-B, B] $ （分別， $ y\in [0, B] $ )，它認為 $ \widetilde{\chi} $ 和 $ y + \widetilde{\chi} $ 在 $ \epsilon $ 統計距離。
事實證明，（“截斷”，“舍入”）高斯分佈滿足上述性質；即，任何 $ \left(B\cdot\lambda^{\omega(1)}, \epsilon\right) $ -有界分佈 $ \chi $ 也是一個**_** $ \left(B, \epsilon+\mathsf{negl}(\lambda)\right) $ - 吞嚥分佈以及。（高斯人恰好經常具有這樣的“好”幾何特性。）
*例如：*如果 $ \chi $ 是 $ (B, \mathsf{negl}(\lambda)) $ - 有界的，如果 $ \widetilde{\chi} $ 是 $ (B\cdot\lambda^{\omega(1)}, \mathsf{negl}(\lambda)) $ -有界，我們採樣 $ x\leftarrow\chi $ 和 $ \widetilde{x}\leftarrow\widetilde{\chi}, $ 那麼我們有：
$$ \widetilde{x} + x \stackrel{\rm stat}{\approx} \widetilde{x} $$
通常，許多“自然”分佈會表現出這種“吞嚥”特性。整數（範圍）上的均勻分佈由邊界明確定義 $ B $ （或者 $ p, $ 或者 $ N $ )，並在大小上存在超多差距時吞下所有“小的、均勻隨機整數”whp。
請注意，每次使用這種參數時，您都需要為每條新消息“採樣和添加”一個新鮮的、獨立同分佈的“吞嚥術語”。只要超出截斷高斯或整數的有界範圍：使用你的判斷！=）分佈（當然）必須達到相同的（比如說..）子組才能使用這個參數，等等。
..最後，請注意，如果所需的安全屬性是（獨立的）一次性便箋簿，則無需費心統計數據！僅使用標準 OTP 將更有效（為了盲消息而採樣的比特更少；即需要安全/安全地生成/共享更少的隨機性）。此外，標準 OTP 將實現比僅統計不可區分性更強。