CTR 模式下 PRF 的輸入和輸出大小的相關性
我正在研究 Katz 的書（第 2 版）的練習 3.25：
讓 $ F $ 是一個偽隨機函式，使得對於 $ k \in {0, 1}^n $ 功能 $ F_k $ 地圖 $ \ell_{\text{in}}(n) $ -位輸入到 $ \ell_{\text{out}}(n) $ 位輸出。
**(a)**考慮使用 CTR 模式加密 $ F $ . 適用於哪些功能 $ \ell_{\text{in}} $ , $ \ell_{\text{out}} $ 生成的加密方案是 CPA 安全的嗎？
**(b)**考慮使用 CTR 模式加密 $ F $ ，但僅適用於長度固定的消息 $ \ell(n) $ （這是一個整數倍 $ \ell_{\text{out}}(n) $ ）。為此 $ \ell_{\text{in}} $ , $ \ell_{\text{out}} $ 在存在竊聽者的情況下，該方案是否具有無法區分的加密？
我的回答是，這真的沒關係：任何組合 $ \ell_{\text{in}} $ , $ \ell_{\text{out}} $ 和 $ \ell $ 將產生上述安全性。為什麼我會這樣想？好吧，CTR 模式是 CPA 安全的證明在書中作為定理 3.32 提出，我很確定它只需要 $ F $ 要成為一個 PRF，對輸入和輸出大小沒有限制（即使它帶有保留長度的 PRF），這應該回答**(a)**。
對於**（b）**部分，我認為類似的事情：證明不依賴於消息長度（只要它是多項式 $ n $ ，當然），所以修復一個特定的 $ \ell $ 不應導致 CPA 安全漏洞（更不用說 EAV 安全）。
我哪裡失敗了？直覺告訴我們不是這樣的！例如，如果 $ \ell_{\text{in}}(n) = 1 $ （對所有人 $ n $ )，那麼計數器只能增加一次，然後從那裡循環
$$ {\tt ctr}, {\tt ctr}+1, {\tt ctr}, {\tt ctr}+1,\ldots, $$ 這應該會導致攻擊，不是嗎？證明應該以某種方式取出這些案例，但我只是看不到它，即使在這種情況下它似乎也有效。
我的解決方案
我想我已經找到了解決方案，但缺少評論/答案，因此我將其作為答案發布，以便得出結論。
我將從**(b)**部分開始。
必須避免計數器中的循環，即必須確保 $ {\tt ctr}, {\tt ctr}+1,{\tt ctr}+2,\ldots $ 永遠達不到 $ {\tt ctr} $ 再次。請注意 $ {\tt ctr}\in {0,1}^{\ell_{\text{in}}(n)} $ , 所以必須保證最大塊長度 $ \ell(n) $ 不超過 $ 2^{\ell_{\text{in}}(n)} $ . 這是之間的約束 $ {\ell(n)} $ 和 $ {\ell_{\text{in}}(n)} $ . $ \ ^{1} $
另一方面，在 CTR 模式的 CPA-security 證明中，“生日”一詞 $ 2q(n)^2/2^n $ 與猜測相比，似乎限制了成功攻擊的機率，其中 $ q(n) $ 是最大塊數（所以 $ q(n) = {\ell(n)}/{\ell_{\text{out}}(n)} $ ）。該術語必須可以忽略不計，這是之間的限制 $ {\ell(n)} $ 和 $ {\ell_{\text{out}}(n)} $ .
關於**(a)**部分，我聲稱兩者之間沒有任何限制 $ \ell_{\text{in}} $ 和 $ \ell_{\text{out}} $ 只要 $ \ell(n) $ 滿足上述條件。這可以通過重新審視證明並檢查它是否獨立於多項式來看到 $ \ell_{\text{in}} $ 和 $ \ell_{\text{out}} $ （所以是的，比率 $ \ell_{\text{in}}/\ell_{\text{out}} $ 可以是任何東西）。
$ ^{1} $ Katz 書中的 CPA 安全證明中假設了這一點： $ f({\tt ctr}^∗ + 1),\ldots,f({\tt ctr}^ + \ell^) $ 加密挑戰密文時使用是均勻分佈的，獨立於實驗的其餘部分