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.
Section: 29.5.4.5 [rand.eng.philox] Status: New Submitter: Thomas Köppe Opened: 2025-02-12 Last modified: 2025-08-22
Priority: 3
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 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 thatPhilox
"returns the sequence = " is needlessly
ambiguous (what is 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 to be 1-based (and
is an alias for the initial value, ), so that the final result is
.
[2025-06-13; Reflector poll]
Set priority to 3 after reflector poll.
Previous resolution [SUPERSEDED]:
This wording is relative to N5001.
Modify 29.5.4.5 [rand.eng.philox] as indicated:
-2- The generation algorithm returns , the value stored in the element of after applying the transition algorithm.
-3- The state transition is performed as if by the following algorithm:if ( == ) {
Philox
(, ) // see below // this updates }-4- The
Philox
function maps the length-/2 sequence and the length- sequence into a length- output sequence. Philox applies an -round substitution-permutation network to the values in .A single round of the generation algorithm performs the following steps:That is, there are intermediate values , , …, , where , and for each round (with ), is computed from as follows. The output sequence is .
(4.1) —
The output sequence of the previous round ( in case of the first round) is permuted to obtain the intermediate state :An intermediate state is obtained by permuting the previous output, , where , and is defined in Table 124.
(4.2) —
The following computations are applied to the elements of the sequence:The next output is computed from the elements of the as follows. For
(4.2.?) — = mulhi(,,w) xor xor , and
= mulhi(,,w) xor xor(4.2.?) — = mullo(,,w),
= mullo(,,w)where
:
(4.2.1) — mullo() is the low half of the modular multiplication of and : ,
(4.2.2) — mulhi() is the high half of the modular multiplication of and : ,
(4.2.3) —
is the index in the sequences,is the round key for round , ,(4.2.4) —
is the index of the round,is the element of the key sequence ,
(4.2.5) — is the round key for round , ,
(4.2.6) — are the elements of the key sequence ,(4.2.7) — is
multipliers[]
, and(4.2.8) — is
round_consts[]
.
[2025-08-08; Matt Stephanson comments and makes wording improvements with Thomas Köppe]
For what it's worth, I believe the new wording correctly describes the algorithm and does not make any substantive changes.
As for the wording itself:
Paragraphs 1, 2, and 3 still refer to the output sequence as Y
, so I don't think
it should be removed from the end of the first sentence in p4. On the contrary, to maintain the connection
and parallel the "$X^{(0)} := X$" wording, I think the final sentence should also be
"The output sequence is $X^{(r)} := Y$".
I can't explain why, but my intuition is that, in bullet (4.2), "the elements of $V^{(q)}$"
sounds better than "the elements of the $V^{(q)}$". The second "the" worked with the original wording
"the V
sequence", but "sequence" is omitted in the proposed resolution.
The use of K
for both the fixed key sequence and the round keys seems potentially
confusing. Maybe R
for "round key" is better?
After discussion with Thomas Köppe there was agreement that (a) should be applied with the modification
that we should write it as definition of Y
and not the other way around, that (b) should
be applied as suggested, and that there was no real consensus for proposal (c).
Proposed resolution:
This wording is relative to N5014.
Modify 29.5.4.5 [rand.eng.philox] as indicated:
-2- The generation algorithm returns , the value stored in the element of after applying the transition algorithm.
-3- The state transition is performed as if by the following algorithm:if ( == ) {
Philox
(, ) // see below // this updates }-4- The
Philox
function maps the length-/2 sequence and the length- sequence into a length- output sequence. Philox applies an -round substitution-permutation network to the values in .A single round of the generation algorithm performs the following steps:That is, there are intermediate values , , …, , where , and for each round (with ), is computed from as follows. The output sequence is .
(4.1) —
The output sequence of the previous round ( in case of the first round) is permuted to obtain the intermediate state :An intermediate state is obtained by permuting the previous output, , where , and is defined in Table 129.
(4.2) —
The following computations are applied to the elements of the sequence:The next output is computed from the elements of as follows. For
(4.2.?) — = mulhi(,,w) xor xor , and
= mulhi(,,w) xor xor(4.2.?) — = mullo(,,w),
= mullo(,,w)where
:
(4.2.1) — mullo() is the low half of the modular multiplication of and : ,
(4.2.2) — mulhi() is the high half of the modular multiplication of and : ,
(4.2.3) —
is the index in the sequences,is the round key for round , ,(4.2.4) —
is the index of the round,is the element of the key sequence ,
(4.2.5) — is the round key for round , ,
(4.2.6) — are the elements of the key sequence ,(4.2.7) — is
multipliers[]
, and(4.2.8) — is
round_consts[]
.