Discrete probability for cryptography

Updated 06 Nov 2026

• •

  Probability distributions and events

  • •

    Universe (sample space) $U$ -> a finite set containing all possible outcomes of a random process

  • •

    Probability distribution $P$

    • •

      a function $P: U \to [0, 1]$ satisfying:

      • •
        $$\sum_{x \in U} P(x) = 1$$
    • •

      can be reprsented as a probability vector in $\mathbb{R}^{|U|}$

  • •

    Two canonical distributions

    • •

      Uniform distribution -> every element has equal weight:

      • •
        $$P(x) = \frac{1}{|U|} \quad \forall x \in U$$

        sampling $x$ uniformly from $U$ is denoted $x \xleftarrow{R} U$

    • •

      Point distribution at $x_0$ -> concentrates all probability weight on a single outcome:

      • •
        $$P(x_0) = 1, \quad P(x) = 0 \quad \forall x \neq x_0$$
  • •

    Events

    • •

      an event $A$ is a subset of the universe: $A \subseteq U$

    • •

      Probability of an event -> sum of the weights of outcomes contained in $A$:

      • •
        $$\Pr[A] := \sum_{x \in A} P(x)$$
    • •

      Set operations

      • •

        Complement -> $\Pr[A^c] = 1 - \Pr[A]$.

      • •

        Union -> $\Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B]$.

  • •

    The Union Bound (Boole's inequality)

    • •

      for any events $A_1, A_2, \dots, A_k$ over sample space $U$:

      • •
        $$\Pr\left[\bigcup_{i=1}^k A_i\right] \le \sum_{i=1}^k \Pr[A_i]$$
    • •

      Equality condition -> holds with exact equality if and only if the events are pairwise disjoint ($A_i \cap A_j = \emptyset$ for $i \neq j$).

    • •

      Cryptographic utility -> used to establish upper bounds on adversary success probabilities across multiple attack paths without requiring independence between attack stages.

• •

  Random variables and statistical independence

  • •

    Random variable $X$

    • •

      formally, a function mapping the sample space to a target set: $X: U \to V$.

    • •

      induces a probability distribution on $V$:

      • •
        $$\Pr[X = v] := \Pr[\{u \in U : X(u) = v\}] = \sum_{u \in U, X(u) = v} P(u)$$
    • •

      Uniform random variable -> a variable $R \xleftarrow{R} U$ where $R$ is the identity function on $U$, giving $\Pr[R = u] = 1/|U|$.

  • •

    Independence of events

    • •

      two events $A$ and $B$ are independent if and only if:

      • •
        $$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$$
    • •

      for conditioning events with $\Pr[B] > 0$, independence implies $\Pr[A \mid B] = \Pr[A]$.

  • •

    Independence of random variables

    • •

      Random variables $X$ and $Y$ are independent if and only if for all $x \in V_X$ and $y \in V_Y$:

      • •
        $$\Pr[X = x \wedge Y = y] = \Pr[X = x] \cdot \Pr[Y = y]$$
    • •

      Operational warning -> Unconditional probabilities may only be multiplied when independence is formally verified or rigorously established by design.

• •

  The XOR Uniformity Lemma

  • •

    Theorem statement

    • •

      let $Y$ be a random variable with an arbitrary (potentially biased or adversarially chosen) distribution over $\{0,1\}^n$

    • •

      let $X$ be an independent, uniformly distributed random variable over $\{0, 1\}^n$

    • •

      then the random variable:

      • •
        $$Z := X \oplus Y$$

        is strictly uniformly distributed over $\{0, 1\}^n$, regardless of the distribution of $Y$

  • •

    Proof (1-bit case)

    • •

      let $\Pr[Y=0] = p_0$ and $\Pr[Y = 1] = p_1$, where $p_0 + p_1 = 1$.

    • •

      since $X$ is uniform and independent of $Y$, $\Pr[X = 0] = \Pr[X = 1] = 1/2$.

    • •

      calculating the probability that $Z = 0$:

      • •
        $$\Pr[Z = 0] = \Pr[(X = 0 \wedge Y = 0) \vee (X = 1 \wedge Y = 1)]$$
      • •
        $$= \Pr[X = 0]\Pr[Y = 0] + \Pr[X = 1]\Pr[Y = 1] = \frac{1}{2}p_0 + \frac{1}{2}p_1 = \frac{p_0 + p_1}{2} = \frac{1}{2}$$
    • •

      because probabilities sum to 1, $\Pr[Z = 1] = 1 - 1/2 = 1/2$.

  • •

    $n$-bit generalization

    • •

      for any fixed $y \in${0, 1}^n$, the mapping$x \mapsto x \oplus y$is a bijective permutation on${0, 1}^n$.

    • •

      conditioned on any outcome $Y = y$, $Z$ is uniformly distributed; by the law of total probability, $Z$ is unconditionally uniform.

  • •

    Cryptographic importance

    • •

      explain why the bitwise XOR operation is ubiquitous in symmetric cryptography

    • •

      forms the exact mathematical foundation for why the One-Time Pad and Stream Ciphers completely conceal message content

  • •

    

• •

  Randomized algorithms and probabilistic computation

  • •

    Deterministic algorithm -> Maps an input $m$ to a single, invariable output $y = A(m)$.

  • •

    Randomized algorithm

    • •

      in addition to input $m$, accepts an implicit random string $r \xleftarrow{R} \{0, 1\}^n$ sampled uniformly on every execution:

    • •
      $$y \leftarrow A(m; r)$$
    • •

      running $A$ twice on the identical input $m$ can yield different outputs.

    • •

      a randomized algorithm induces a probability distribution over the output space for each fixed input $m$.

  • •

    Cryptographic application

    • •

      symmetric and public-key encryption schemes often require randomized encryption ($E(k, m; r)$).

    • •

      prevents deterministic ciphertext generation, ensuring that encrypting the identical plaintext multiple times yields distinct, uncorrelated ciphertexts

• •

  The Birthday Paradox and collision bounds

  • •

    Collision theorem

    • •

      when drawing $k$ independent, uniformly distributed random samples from a finite universe $U$ of size $N = |U|$, the probability of at least one collision exceeds $50\%$ when:

      • •
        $$k \approx \sqrt{2 \ln(2) \cdot N} \approx 1.177 \sqrt{|U|} \approx 1.2 \sqrt{|U|}$$
  • •

    The classical birthday problem

    • •

      in a room of people with independent birthdays across $N = 365$ days:

      • •
        $$k \approx 1.2 \sqrt{365} \approx 23 \text{ people}$$
      • •

        yields a $50.7\%$ probability that at least two individuals share a birth date.

  • •

    Implications for cryptography

    • •

      Hash collision resistance -> in a hash function with output size of $n$ bits ($|U| = 2^n$), collisions emerge after evaluating roughly $2^{n/2}$ inputs, not $2^n$.

    • •

      Nonce and IV collision -> generating random $L$-bit nonces without state guarantees collisions after approximately $2^{L/2}$ encryptions.

    • •

      Security parameter scaling -> symmetric security parameters must be dimensioned against the square root of the target space whenever collision resistance is needed.

  • •

    

◌ Explore connections in Graph view