Informatics and Applications
2018, Volume 12, Issue 4, pp 70-74
AN INFORMATION BASED CRITERION FOR PERFECTLY BALANCED FUNCTIONS
Abstract
The class of perfectly balanced functions is important for some areas of mathematics, e.g., combinatorics, coding theory, cryptography, symbolic dynamics, and automata theory. It turns out that perfectly balanced functions provide a suitable mathematical tool for description and studying of convolutional codes, cryptographic primitives, surjective endomorphisms of discrete dynamical systems, and information-lossless finite-state automata. Previously, Hedlund and Sumarokov proved criteria of perfect balancedness of functions, which are related to the property of being defect zero and information-lossless. The present author proves a new criterion of the perfect balancedness property in terms of average mutual information. The author also describes a polinomial-time inverting algorithm for perfectly balanced functions.
[+] References (6)
- Hedlund, G. A. 1969. Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3:320375.
- Sumarokov, S. N. 1994. Zaprety dvoichnykh funktsiy i obratimost' dlya odnogo klassa kodiruyushchikh ustroystv [Prohibitions of Boolean functions and invertibility for a coding devices class]. Obozrenie prikladnoy i promyshlennoy 6 matematiki [Surveys in Applied and Industrial Mathematics] 1:33-55.
- Feinstein, A. 1958. Foundations of information theory. New
York, NY: Mcgraw-Hill. 137 p.
- Logachev, O.A., A. A. Sal'nikov, S.V. Smyshlyaev, and
V. V. Yashchenko. 2015. Bulevy funktsii v teorii kodirovaniya
i kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Lenand. 576 p.
- Goldreich, O. 2003. Foundations of cryptography. Vol. I:
Basic tools. Cambridge, U.K.: Cambridge University Press.
372 p.
- Kudryavcev, V. B., S. V. Aleshin, and A. S. Podkolzin. 1985.
Vvedenie v teoriyu avtomatov [Introduction to automata
theory]. Moscow: Nauka. 320 p.
[+] About this article
Title
AN INFORMATION BASED CRITERION FOR PERFECTLY BALANCED FUNCTIONS
Journal
Informatics and Applications
2018, Volume 12, Issue 4, pp 70-74
Cover Date
2018-12-30
DOI
10.14357/19922264180410
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
finite alfabet; discrete function; averege mutual information; perfect balancedness; perfectly balanced function; function of defect zero
Authors
O.A. Logachev 
Author Affiliations
Institute of Information Security Issues, M. V. Lomonosov Moscow State University, 1 Michurinsky Pr., Moscow 119192, Russian Federation
|