Український математичний конгрес - 2009

Дмитро Міндра (Інститут телекомунікацій і глобального інформаційного простору, НАН України, Київ, Україна)

On new tools for security of data

The aim of the current talk is a presentation of new software products for encryption of data in different formats, such as: text, image and sound files, in the form of the library of software packages and special chips. Proposed symmetric algorithms are not block ciphers. Proposed tool changes the entire data: a change of a single bite of information or of a single symbol of the key leads to a drastic change of the entire cipher data (99 percents of characters, not a particular block). The algorithms are fast, their speed linearly depends on the data size. If the adversary has access only to encrypted data, then breaking the key by him is equivalent to the exponential brut force search via the entire key-space. It is mathematically proven that different keys produce distinct ciphertexts, which always differ from the plaintexts. The length of the key is up to a free choice by the customer, so the resistance to attacks is governed by the size of the key space. The encryption function is nonlinear, it is resistant to active attacks on the key when the adversary have many pairs of original and encrypted data. The algorithms can be used as stream cipher, but they can be converted into polynomial public keys, because of the algebraic nature of basic graphs.

For evaluating the quality of the "seeming chaos" theoretically, one can use certain dynamic and stochastic models from the theory of complex systems on graphs with good expanding properties.

Our methods are directly based on the theory of finite automata (roughly speaking, graphs) employed for encryption. It turns out that algebraic graphs of large girth are good models for encryption automata.

REFERENCES: [1] V. Ustimenko, On the extremal graph theory for directed graphs and its cryptographical applications, In: T. Shaska, W. C. Huffman, D. Joener and V. Ustimenko, Advances in Coding Theory and Cryptography, Series on Codin Theory and Cryptology, vol. 3, 181-200 (2007).
[2] V. A. Ustimenko, On the graph based cryptography and symbolic computations, Serdica Journal of Computing, Proceedings of International Conference on Application of Computer Algebra, ACA-2006, Varna, N1 (2007).