|
This article is cited in 3 scientific papers (total in 3 papers)
Theoretical Backgrounds of Applied Discrete Mathematics
One approach to constructing a multiply transitive class of block transformations
I. V. Cherednik Russian Technological University (MIREA), Moscow, Russia
Abstract:
In this work, we continue to study the cryptographic properties of block transformations of a new type, which can be used to construct hash functions and block ciphers.
Let $\Omega$ be an arbitrary finite set, $\mathcal Q(\Omega)$ be the collection of all binary quasigroups defined on the set $\Omega$, and $\Sigma^F\colon\Omega^n\to\Omega^n$ be a mapping that is implemented by a network $\Sigma$ of width $n$ with one binary operation $F\in\mathcal Q(\Omega)$.
The network $\Sigma$ is called bijective if the mapping $\Sigma^F$ is bijective for each $F\in\mathcal Q(\Omega)$ and all finite sets $\Omega$.
The networks $\Sigma_1,\Sigma_2$ are called equivalent if the map $\Sigma_1^F$ of $\Sigma_1$ coincides with the map $\Sigma_2^F$ of $\Sigma_2$ for each $F\in\mathcal Q(\Omega)$ and for all finite sets $\Omega$.
It is not difficult to define the elementary networks by analogy with the elementary matrices and prove that every bijective network $\Sigma$ is equivalent to a unique product of elementary networks. This product is called the canonical representation of $\Sigma$ and its length is denoted by $\|\Sigma\|$.
A bijective network $\Sigma$ is called $k$-transitive for $\Omega$ if the family $\{\Sigma^F: F\in\mathcal Q(\Omega)\}$ is $k$-transitive.
We prove that the bijective network $\Sigma$ is $k$-transitive for all sufficiently large finite sets iff $\Sigma$ is \linebreak$k$-transitive for some finite set $\Omega$ such that $|\Omega|\ge k\|\Sigma\|+kn$.
In addition, we propose an effective method for verifying the network's $k$-transitivity for all sufficiently large finite sets, namely, the bijective network $\Sigma$ is $k$-transitive for $\Omega$ such that $|\Omega|\ge k\|\Sigma\|+kn$ whenever it is $k$-transitive for some $(k+1)$-element subset of $\Omega$.
Also, we describe an algorithm for constructing $k$-transitive networks.
For a given bijective network $\Sigma$ of a width $n$, the algorithm adds $6n-7$ elementary networks to the canonical representation of $\Sigma$ without changing the existing contents.
As a result of these modifications, we obtain a bijective network $\widehat{\Sigma}$ that is $k$-transitive for every sufficiently large finite set $\Omega$, namely for $|\Omega|\ge k\|\widehat{\Sigma}\|+kn$.
Keywords:
network, quasigroup, block transformation, $k$-transitive class of block transformations.
Citation:
I. V. Cherednik, “One approach to constructing a multiply transitive class of block transformations”, Prikl. Diskr. Mat., 2018, no. 42, 18–47
Linking options:
https://www.mathnet.ru/eng/pdm640 https://www.mathnet.ru/eng/pdm/y2018/i4/p18
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 63 | References: | 36 |
|