On the Complexity of Specifying a Symmetric Group of Permutations of Degree 2n in a Threshold Basis on a Promising Element Base


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

The appeal to the threshold method of setting substitutions reflects the current trends towards increasing the speed of information processing and transmission connected with the possibility of implementing threshold functions directly in the signal carrier medium, primarily in optics or on other carriers related to the field of nanotechnology. In addition, the actively developing direction of building neurocomputers also requires the development of information protection systems using the basic operations of neurocomputers-threshold elements. The aim of the study was to find a way to construct a symmetric group of substitutions of degree 2n in the threshold basis. For this purpose, a method for implementing transpositions is proposed, with the help of which any transposition can be constructed, which allows us to say that it is possible to implement the entire symmetric group of substitutions of degree 2n. From a computational point of view, the provisions of the article are of exceptional interest due to the simplicity of the algorithm for implementing substitutions.

Full Text

Restricted Access

About the authors

Vladimir G. Nikonov

Russian Academy of Natural Sciences

Dr. Sci. (Eng.), Full Professor, Member of the Presidium RANS. Moscow, Russian Federation

Anton I. Zobov

Secure Information Technology Assistance Foundation

Email: zobowai@gmail.com
research employee Moscow, Russian Federation

Nikolay V. Nikonov

Technical Committee for Standardization TC26

Cand. Sci. (Phys.-Math.), Assoc. Prof.; expert Moscow, Russian Federation

References

  1. Huffman D.A. Canonical forms for information lossless finite-state logical machines // IRE Trans. Circ. Theory. 1959. No. 6. Pp. 41-59.
  2. Nikonov V.G., Litvinenko V.S. About bijectivity of transformations determined by quasi-hadamard matrixes. Comp. nanotechnol. 2016. No. 1. Pp. 6-13. (In Rus.)
  3. Nikonov V.G., Nikonov N.V. Features of threshold representations of k-valued functions. Transactions on Discrete Athematics. 2008. Vol. 11. No. 1. Pp. 60-85. (In Rus.)
  4. Nikonov V.G. Classification of minimal basic representations of all Boolean functions in four variables. Review of Applied and Industrial Mathematics. Ser. Discrete Math. 1994. Vol. 1. No. 3. Pp. 458-545. (In Rus.)
  5. Dertouzos М.L. Threshold logic: A synthesis approach. Cambridge, Massachusetts: MIT Press, 1965.
  6. Butakov E.A. Methods of synthesis of linear devices from threshold elements. Moscow: Energy. 1970.
  7. Zuev Yu.A. Threshold functions and threshold representations of Boolean functions. Mathematical Problems of Cybernetics. Issue 5. Moscow: Nauka, 1994. (In Rus.)
  8. Nikonov V.G., Zobov A.I., Geometric approach to estimating the complexity of Boolean functions. Comp. nanotechnol. 2018. No. 3. Pp. 32-43. (In Rus.)
  9. Kudryavtsev V.A. Summation of powers of natural numbers and Bernoulli numbers. Leningrad: United Scientific and Technical Publishing House of the NKTP USSR, 1936, 37 p.
  10. Logachev O.A., Salnikov A.A., Smyshlyaev S.V., Yashchenko V.V. Boolean functions in coding theory and cryptology. 2nd ed., suppl. Moscow: MTsNMO, 2012. 584 p.
  11. Logachev O.A., Fedorov S.N., Yashchenko V.V. Boolean functions as points on a hypersphere in euclidean space. Discrete Mathematics. 2018. Vol. 30. No. 1. Pp. 39-55. (In Rus.)
  12. Nikonov V.G., Sarantsev A.V. Methods for compact realization of bijective mappings given by regular systems of the same type of Boolean functions. Bulletin of the Russian University of Friendship of Peoples. Series: Applied and Industrial Mathematics. 2003. Vol. 2. No. 1. Pp. 94-105. (In Rus.)
  13. Yablonsky S.V. Introduction to discrete mathematics: Study guide for universities. 2nd ed., revised. and add. Moscow: Science. Ch. Ed. Physical-Mat. Lit. 384 p.
  14. Agievich S.V., Afonenko A.A., On the properties of exponential substitutions. Vesti NAN Belarusi. 2005. No. 1. Pp. 106-112. (In Rus.)
  15. Agievich S.V., Galinsky B. A., Mikulich N.D., Kharin U.S. Algorithm of block encryption BelT (In Rus.) URL: http://apmi.bsu.by/assets/files/agievich/BelT.pdf
  16. Barreto P., Rijmen V. The ANUBIS block cipher. In: NESSIE submission. 2000.
  17. Barreto P., Rijmen V. The KHAZAD block cipher. In: NESSIE submission. 2000.
  18. Chabaud F., Vaudenay S. Links between differential and linear cryptanalysis // EUROCRYPT, Lect. Notes Comput. Sci. 1994. No. 950. Pp. 356-365.
  19. Daemen J., Rijmen V. Probability distributions of correlations and differentials in block ciphers // J. Math. Crypt. 2007. No. 1. Pp. 221-242.
  20. Menyachixin A.V. Spectral-linear and spectral-differential methods for constructing S-boxes with close to optimal values of cryptographic parameters. Mathematical Questions of Cryptography. 2017. Vol. 8. No. 2. Pp. 97-116.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download