Mathematical Methods of Cryptography

Two ways of calculating of differential transition probabilities in Luby — Rackoff scheme

O. V. Denisov, M. M. Glukhov


Abstract: We describe two ways of deriving formulas for elements of the transition probabilities matrix of differences for $r$ rounds in the Luby — Rackoff scheme for arbitrary $r$. The first way (for a scheme with an alphabet of semi-blocks $\mathbb{Z}_2^m$) is the direct derivation of formulas from Patarin's theorems on the transition probabilities of bigram differences. The second path (for the more general case of a scheme with a commutative operation of adding half-blocks from an arbitrary alphabet) consists of 5 stages, the second of which is the lumping of the states of the Markov chain formed by differences. The maximum probabilities and their location in the transition probabilities matrix are described. Two typos made by the authors in 2024 in the formulas for 8-round probabilities have been corrected.

Keywords: Luby — Rackoff scheme, transition probabilities matrix of differences, lumped Markov chain.

UDC: 519.24

DOI: 10.17223/2226308X/18/25