2010 | OriginalPaper | Buchkapitel
The Characterization of Luby-Rackoff and Its Optimum Single-Key Variants
verfasst von : Mridul Nandi
Erschienen in: Progress in Cryptology - INDOCRYPT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Luby and Rackoff provided a construction (LR) of 2
n
-bit (strong) pseudo-random permutation or (S)PRP from
n
-bit pseudorandom function (PRF), which was motivated by the structure of DES. Their construction consists of four rounds of Feistel permutations (or three rounds, for PRP), each round involves an application of an independent PRF (i.e. with an independent round key). The definition of the LR construction can be extended by reusing round keys in a manner determined by a
key-assigning
function. So far several key-assigning functions had been analyzed (e.g. LR with 4-round keys
K
1
,
K
2
,
K
2
,
K
2
was proved secure whereas
K
1
,
K
2
,
K
2
,
K
1
is not secure). Even though we already know some key-assigning functions which give secure and insecure LR constructions, the exact characterization of all secure LR constructions for arbitrary number of rounds is still unknown. Some characterizations were being conjectured which were later shown to be wrong. In this paper we solve this long-standing open problem and (informally) prove the following:
LR is secure iff its key-assigning is
not palindrome
(i.e. the order of key indices is not same with its reverse order).
We also study the class of LR-variants where some of its round functions can be tweaked (our previous characterization would not work for the variants). We propose a single-key LR-variant SPRP, denoted by
LRv
, making only four invocations of the PRF. It is exactly same as single-key, 4-round LR with an additional operation (e.g. rotation) applied to the first round PRF output. So far the most efficient single-key LR construction is due to Patarin, which requires five invocations. Moreover, we show a PRP-distinguishing attack on a wide class of single-key, LR-variants with three PRF-invocations. So,
4 invocations of PRF is minimum for a class of a single-key LR-variants SPRP and
LRv
is
optimum
in the class
.