Performance of algebraic graphs based stream-ciphers using large finite fields. (English) Zbl 1284.94118

Summary: Algebraic graphs \(D(n, q)\) and their analog graphs \(D(n, K)\), where \(K\) is a finite commutative ring were used successfully in Coding Theory (as Tanner graphs for the construction of LDPC codes and turbo-codes) and in Cryptography (stream-ciphers, public-keys and tools for the key-exchange protocols. Many properties of cryptography algorithms largely depend on the choice of finite field \(F_q\) or commutative ring \(K\). For practical implementations the most convenient fields are \(F\) and rings modulo \(Z\) modulo \(2^m\). In this paper the reader can find the first results about the comparison of \(D(n, 2m)\) based stream-ciphers for \(m\) = 8, 16, 32 implemented in C++. They show that performance (speed) of algorithms gets better when \(m\) is increased.


94A60 Cryptography
05C90 Applications of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
68W30 Symbolic computation and algebraic computation
94B05 Linear codes (general theory)
Full Text: DOI


[1] Lazebnik F., Ustimenko V., Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size, DIMACS series in Discrete Mathematics and Theoretical Computer Science 10 (1993): 75. · Zbl 0798.05034
[2] Kim J. L., Peled U. N., Perepelitsa I., Pless V., Friedland S., Explicit construction of families of LDPC codes with no 4-cycles, Information Theory, IEEE Transactions 50(10) (2004): 2378. · Zbl 1315.94140
[3] Ustimenko V. A., Coordinatisation of regular tree and its quotients, in “Voronoi’s impact on modern science”, eds P. Engel and H. Syta, book 2, National Acad. of Sci, Institute of Matematics (1998): 228.
[4] Kotorowicz J., Ustimenko V. A., On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, Condenced Matters Physics, Special Issue: Proceedings of the international conferences “Infinite particle systems, Complex systems theory and its application”, Kazimerz Dolny, Poland, 2006, 11, 2(54) (2008): 347.
[5] Ustimenko V., Touzene A., CRYPTALL-a System to Encrypt All types of Data, Notices of Kiev Mohyla Academy (2004): 57. · Zbl 1067.68069
[6] Touzene A., Ustimenko V., Graph Based Private Key Crypto System, International Journal on Computer Research, Nova Science Publisher 13(4) (2006): 12. · Zbl 1122.68053
[7] Klisowski M., Ustimenko V., On the public keys based on the extremal graphs and digraphs, International Multi-conference on Computer Science and Informational Technology, October 2010, Wisla, Poland, CANA Proceedings.
[8] Wróblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics 2(3) (2008): 229.
[9] Ustimenko V., Algebraic graphs and security of digital communications, Institute of Computer Science, University of Maria Curie Sklodowska in Lublin (2011): 151 (supported by European Social Foundation), available at the UMCS web.
[10] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, In Lecture Notes in Computer Science, Springer 2227 (2002): 278. · Zbl 1057.94512
[11] Ustimenko V., Graphs with special arcs and Cryptography, Acta Applicandae Mathematicae (1974): 117. · Zbl 1065.68050
[12] Koblitz N., A Course in Number Theory and Cryptography, Second Edition, Springer (1994). · Zbl 0819.11001
[13] Koblitz N., Algebraic Aspects of Cryptograph, Springer (1998).
[14] Hasan M. A., Look-Up Table-Based Large Finite Field Multiplication in Memory Constrained Cryptosystems, IEEE Trans. Comp. 49 (7) (2000): 749. · Zbl 1391.94758
[15] Ustimenko V., Woldar A., Extremal properties of regular and affine generalized polygons as tactical configurations, Europ. J. Com. 24 (2003): 99. · Zbl 1014.05038
[16] Dijkstra E., Note on two problems in connection with graphs, Num. Math. 1 (1959): 269. · Zbl 0092.16002
[17] Plank J. (n.d.), Fast Galois Field Arithmetic Library in C/C++. Retrieved October 28 (2009), from The University of Tennessee, College of Art and Science:
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.