This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4212. Make the round states in [rand.eng.philox] explicit

Section: 29.5.4.5 [rand.eng.philox] Status: New Submitter: Thomas Köppe Opened: 2025-02-12 Last modified: 2025-02-24

Priority: Not Prioritized

View all other issues in [rand.eng.philox].

View all issues with New status.

Discussion:

The current wording that specifies the operation of the Philox random bit generator seems needlessly vague. We can add precision by defining a few more terms, instead of requiring the reader to fill in the blanks.

Concretely, the variable $X\text{'}$ is only vaguely defined at the moment, and the definition of the "r-round network", "rounds", and how they fit together, is somewhat informal and imprecise. The statement that Philox "returns the sequence $Y$ = $X\text{'}$" is needlessly ambiguous (what is $X\text{'}$ here?).

I propose the change that I drafted at draft/pull/7152: Namely, spell out the meaning of the "rounds" and create a distinct name for every value in every round. This allows us to state the result precisely, and makes it clear how each round computes a new value from the values of the previous rounds.

It seems convenient to change the round counter $q$ to be 1-based (and $X^{\left(0\right)}$ is an alias for the initial value, $X$), so that the final result is $X^{\left(r\right)}$.

Proposed resolution:

This wording is relative to N5001.

1. Modify 29.5.4.5 [rand.eng.philox] as indicated:

   -2- The generation algorithm returns $Y_i$, the value stored in the $i^{\text{th}}$ element of $Y$ after applying the transition algorithm.

   -3- The state transition is performed as if by the following algorithm:

   $i=i+1$
   if ($i$ == $n$) {
     $Y=$Philox($K$, $X$) // see below
     $Z=Z+1$         // this updates $X$
     $i=0$
   }
   

   -4- The Philox function maps the length-$n$/2 sequence $K$ and the length-$n$ sequence $X$ into a length-$n$ output sequence $Y$. Philox applies an $r$-round substitution-permutation network to the values in $X$. A single round of the generation algorithm performs the following steps: That is, there are intermediate values $X^{\left(0\right)}$, $X^{\left(1\right)}$, …, $X^{\left(r\right)}$, where $X^{\left(0\right)}:=X$, and for each round $q$ (with $q=1,\dots ,r$), $X^{\left(q\right)}$ is computed from $X^{(q-1)}$ as follows. The output sequence is $X^{\left(r\right)}$.

   1. (4.1) — The output sequence $X\text{'}$ of the previous round ($X$ in case of the first round) is permuted to obtain the intermediate state $V$:

      $V_j=X_{\text{'}}$
      

      An intermediate state $V^{\left(q\right)}$ is obtained by permuting the previous output, $V_j^{\left(q\right)}:=X_{f_n\left(j\right)}^{(q-1)}$, where $j=0,\dots ,n-1$, and $f_n\left(j\right)$ is defined in Table 124.

   2. (4.2) — The following computations are applied to the elements of the $V$ sequence: The next output $X^{\left(q\right)}$ is computed from the elements of the $V^{\left(q\right)}$ as follows. For $k=0,\dots ,n/2-1,$

      1. (4.2.?) — $X_{2k+0}^{\left(q\right)}$ = mulhi($V_{2k}^{\left(q\right)}$,$M_k$,w) xor $K_k^{\left(q\right)}$ xor $V_{2k+1}^{\left(q\right)}$, and$X_{2k+0}$ = mulhi($V_{2k}$,$M_k$,w) xor ${\mathrm{key}}_k^q$ xor $V_{2k+1}$

      2. (4.2.?) — $X_{2k+1}^{\left(q\right)}$ = mullo($V_{2k}^{\left(q\right)}$,$M_k$,w),$X_{2k+1}$ = mullo($V_{2k}$,$M_k$,w)

      where:

      1. (4.2.1) — mullo($a,b,w$) is the low half of the modular multiplication of $a$ and $b$: $(a\cdot b)mod{2}^w$,

      2. (4.2.2) — mulhi($a,b,w$) is the high half of the modular multiplication of $a$ and $b$: $(\lfloor (a\cdot b)/2^w\rfloor )$,

      3. (4.2.3) — $k=0,\dots ,n/2-1$ is the index in the sequences, $K_k^{\left(q\right)}$ is the $k^{\text{th}}$ round key for round $q$, $K_k^{\left(q\right)}:=(K_k+(q-1)\cdot C_k)mod{2}^w$,

      4. (4.2.4) — $q=0,\dots ,r-1$ is the index of the round, $K_k$ is the $k^{\text{th}}$ element of the key sequence $K$,

      5. (4.2.5) — ${\mathrm{key}}_k^q$ is the $k^{\text{th}}$ round key for round $q$, ${\mathrm{key}}_k^q:=(K_k+q\cdot C_k)mod{2}^w$,

      6. (4.2.6) — $K_k$ are the elements of the key sequence $K$,

      7. (4.2.7) — $M_k$ is multipliers[$k$], and

      8. (4.2.8) — $C_k$ is round_consts[$k$].