Pseudorandom Generator (PRG)

A PRG is a deterministic algorithm that takes a short, truly random seed as input and expands it into a much longer output sequence. Given the exact same seed, the PRG will always produce the exact same output. This determinism is critical for secure aggregation, as it allows clients to generate identical pairwise masks without further communication after an initial key agreement phase.

• Input: A seed of length n bits (e.g., 256 bits).
• Output: A pseudorandom sequence of length l(n) bits, where l(n) > n.
• Mechanism: Applies a one-way function iteratively or in parallel to stretch the seed.

The core security property of a cryptographic PRG is that its output is computationally indistinguishable from a truly random string of the same length. For any efficient adversary (a polynomial-time algorithm), the probability of distinguishing between the PRG's output and a truly random string is negligible. This ensures that the masks used in secure aggregation provide semantic security for the model updates.

• Adversary Model: Probabilistic Polynomial-Time (PPT) Turing machines.
• Negligible Function: A function that shrinks faster than the inverse of any polynomial.

A PRG passes the next-bit test if, given the first i bits of its output, no efficient adversary can predict the (i+1)-th bit with a probability significantly greater than 1/2. This property is equivalent to computational indistinguishability and guarantees that an attacker who observes part of a generated mask cannot infer the remaining bits, preventing partial reconstruction of a client's model update.

• Formal Definition: For all PPT adversaries A, the advantage |Pr[A(G(seed){1..i}) = G(seed){i+1}] - 1/2| is negligible.
• Practical Implication: Forward secrecy for the generated mask stream.

A PRG used in secure aggregation must be forward-secure. This means that even if the internal state of the PRG is compromised at a specific point in time, an adversary cannot compute previous outputs. This is typically achieved by iteratively applying a one-way function and discarding old states. In the context of SecAgg, this prevents a compromised client from retroactively decrypting masks from previous training rounds.

• Mechanism: State update via s_{i+1} = f(s_i), output via o_i = g(s_i), where f is one-way.
• Contrast: A non-forward-secure PRG (like a simple counter-mode construction) would expose all past outputs if the current seed is leaked.

The security of a PRG is entirely dependent on the unpredictability of its seed. The seed must be generated from a high-entropy source, typically using a cryptographically secure True Random Number Generator (TRNG). In secure aggregation protocols like SecAgg, seeds are often derived from Diffie-Hellman key exchanges between pairs of clients, ensuring that each pairwise mask is seeded with a shared secret unknown to the server.

• Minimum Entropy: A seed for a 128-bit security level must have at least 128 bits of min-entropy.
• Common Construction: PRG(seed) = AES-CTR(seed) or ChaCha20(seed).

A standard instantiation of a cryptographic PRG is the Advanced Encryption Standard (AES) block cipher operated in Counter (CTR) mode. The seed is used as the AES key, and a monotonically increasing counter is encrypted to produce a keystream. This construction is highly efficient in hardware and software, making it ideal for the low-latency requirements of mask generation in federated learning rounds.

• Throughput: Modern x86 processors with AES-NI instructions can generate >1 GB/s of pseudorandom output.
• Security: Relies on the assumption that AES is a secure Pseudo-Random Permutation (PRP).