To the task of description minimal by inclusion perfect ciphers

N. V. Medvedeva ; S. S. Titov

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 91-95

Résumé

This work is dealing with the problem of description Shannon perfect ciphers (which are absolutely immune against the attack on ciphertext, according to Shannon), minimal by inclusion. A graph approach to the description of perfect ciphers and their modern analogues and generalizations is proposed. The equivalence graph of the keys of the cipher is defined. Key equivalence refers to the following: two different keys are equivalent in cipher-value $x_i$, if the cipher-value $x_i$ on these keys is encrypted to the same code designation. In this case, pairwise different keys $k_1, k_2, k_3,\ldots , k_{n-1}, k_n$ form a cycle of length $n$, if there is such a sequence of cipher-values that: 1) the neighboring cipher-values are different; 2) the keys $k_1, k_2, k_3,\ldots , k_{n-1}, k_n, k_1$ are sequentially equivalent in the corresponding cipher-values. If $n$ is an odd number, then the keys $k_1, k_2,\ldots , k_n$ form an odd-length cycle. A sufficient minimum inclusion condition of the cipher has been proven: let some inhomogeneously connected component of the equivalence graph of the keys of the cipher have an odd-length cycle, then the cipher is minimal by inclusion. Examples are given to illustrate the effectiveness of the proposed approach. The results can be used to study almost-perfect ciphers.

Détail

Keywords: perfect ciphers, endomorphic ciphers, non-endomorphic ciphers.