是否存在無法並行化的安全流密碼？
是否有任何無法並行化的流密碼（或確定性隨機數生成器，我猜應該也可以工作？）？例如，如果我用一個特定的值播種它，然後“執行”它一年，產生越來越多的比特，最後從它得到一個比特流，那麼這個比特流將是不可能的（除非有人“破解”密碼) 在不同步完成所有工作且至少需要類似時間的情況下獲得保留。（這樣就沒有人能夠讓 100 倍的核心在 100 倍的時間內完成所有工作。他們總是可以獲得更快的處理器，或者建構一個專用晶片或其他東西，但它仍然會以單執行緒、同步方式執行計算需要大量時間才能從初始種子值獲取所需的比特流。）
是否存在具有相似屬性的算法？或者一切都可以並行化？
正如 Thomas 所指出的，大多數流密碼不能並行化（從某種意義上說，使用多個處理器生成單個密鑰流會比使用一個處理器快得多）或隨機訪問（從某種意義上說，計算 $ k $ -密鑰流的第一個位將是次線性的 $ k $ ).
無法並行化的流密碼範例包括：
- 據我所知，沒有已知的方法可以以任何有用的方式並行化RC4流密碼。
- OFB 模式中使用的分組密碼不可並行化，除非底層分組密碼本身可以並行化。我懷疑甚至有可能證明這一點，給定分組密碼的適當不可區分性假設，儘管我個人並不知道這樣的證明。
儘管如此，確實存在一些可以並行化甚至隨機訪問的流密碼。其中特別值得注意的是CTR 操作模式，它將分組密碼轉換為隨機可訪問（因此也是完全可並行化）的流密碼。
一些現代流密碼也被設計成在硬體中表現出至少有限程度的並行性。例如，Trivium流密碼的設計使其可用於並行生成從 1 位到 64 位的任意位。然而，任何合理的 Trivium 軟體實現都已經通過對 32 位或 64 位數據塊進行操作來高度利用這種並行性，因此，出於所有實際目的，軟體中的 Trivium 不是（進一步）可並行化的。
更一般地說，本質上所有的同步流密碼（包括上面提到的所有密碼）都可以寫成以下形式：
$$ \begin{aligned} x_0 &= i \ x_n &= f(x_{n-1}) &\forall n \in {1,2,3,\dotsc} \ o_n &= g(x_n) &\forall n \in {1,2,3,\dotsc} \end{aligned} $$ 在哪裡
- $ i $ 是密碼的初始狀態（基於並可能包括密鑰以及任何 IV、調整等），
- $ x_n $ 表示密碼在步驟的內部狀態 $ n $ ,
- $ o_n $ 是步驟中的密鑰流輸出 $ n $ ,
- $ f $ 是在每一步更新內部狀態的函式，並且
- $ g $ 是將內部狀態映射到輸出的函式。
對於大多數不能有效並行化的流密碼，密碼強度來自內部更新函式 $ f $ , 而輸出函式 $ g $ 相當簡單（通常只是提取內部狀態的一部分）。另一方面，為了允許隨機訪問密鑰流（與 CTR 模式一樣），更新函式 $ f $ 必須是微不足道的（對於 CTR 模式，只需將計數器加一），這樣 $ x_n $ 可以快速計算出 $ x_0 $ 對於任何 $ n $ ，而密碼強度必須完全來自函式 $ g $ （對於 CTR 模式，它是底層分組密碼）。
流密碼設計的隨機訪問類型沒有得到更廣泛使用的一個原因是依賴於 $ g $ 代替 $ f $ 因為力量對它提出了更高的要求：事實上 $ f $ 被迭代地應用於它自己的輸出允許它的力量在許多步驟中逐漸建立，而任何安全來自於 $ g $ 必須來自它的一個單一應用程序。大部分更新功能 $ f $ 用於像 RC4 這樣的傳統流密碼，如果用作 $ g $ 用微不足道的 $ f $ .
（此外，如果您確實設法設計了一個可以安全地用作 $ g $ 用微不足道的 $ f $ ，你所擁有的基本上是一個安全的分組密碼或非常接近的東西。因此，從這個意義上說，CTR 模式構造是通用的隨機訪問流密碼，任何其他隨機訪問流密碼本質上都是相同的，只是外觀不同。）
但是，我應該注意到，還有另一種可能更相關的並行性：如果攻擊者想通過暴力破解密碼，他通常會通過從不同的密鑰生成多個密鑰流並查看其中哪個產生有意義的解密來實現. 在這種情況下，即使單個密鑰流的生成不可並行化，攻擊者也可以只使用多個處理器（或者說，GPGPU 中的核心）並將它們中的每一個設置為生成不同的密鑰流。
這種並行性很難避免，因為從根本上說，許多獨立密鑰流的生成是一個令人尷尬的並行任務，無論每個單獨的密鑰流是如何生成的。嘗試減緩此類攻擊的一種方法是使密鑰流生成（或其他計算）需要大量記憶體，基於目前技術，建構大量簡單的並行處理器比提供他們每個人都有大量的記憶體可以使用。
這種設計的一個例子是scrypt密鑰派生函式，它被設計為以一種基本的方式使用可調整數量的隨機存取儲存器，因此，希望任何使用顯著更少的儲存器來計算函式的嘗試只能在計算時間大幅增加的代價。
實際上，閱讀scrypt論文，scrypt中使用的ROMix構造是首先使用非隨機訪問流密碼（實際上是一個迭代的雜湊函式）構造一個大的（偽）隨機查找表，然後使用該查找表來擾亂流密碼的狀態，同時生成實際的密鑰流（在 ROMix 中，密鑰流的結尾將作為輸出）。將類似的構造應用於實際的流密碼當然似乎是可行的，儘管如 scrypt 論文中所述，需要考慮各種微妙的細節。