Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2018, Number 42, Pages 18–47
DOI: https://doi.org/10.17223/20710410/42/2
(Mi pdm640)
 

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
Full-text PDF (777 kB) Citations (3)
References:
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.
Bibliographic databases:
Document Type: Article
UDC: 519.714.5
Language: Russian
Citation: I. V. Cherednik, “One approach to constructing a multiply transitive class of block transformations”, Prikl. Diskr. Mat., 2018, no. 42, 18–47
Citation in format AMSBIB
\Bibitem{Che18}
\by I.~V.~Cherednik
\paper One approach to constructing a multiply transitive class of block transformations
\jour Prikl. Diskr. Mat.
\yr 2018
\issue 42
\pages 18--47
\mathnet{http://mi.mathnet.ru/pdm640}
\crossref{https://doi.org/10.17223/20710410/42/2}
\elib{https://elibrary.ru/item.asp?id=36668305}
Linking options:
  • https://www.mathnet.ru/eng/pdm640
  • https://www.mathnet.ru/eng/pdm/y2018/i4/p18
  • This publication is cited in the following 3 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:199
    Full-text PDF :63
    References:36
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024