Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

On the implementation of new symmetric ciphers based on non-bijective multivariate maps

, , , ,

DOI: http://dx.doi.org/10.15439/2018F204

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 397–405 ()

Full text

Abstract. Certain families of graphs can be used to obtain multivariate polynomials for cryptographic algorithms. In particular, in this paper, we introduce stream ciphers based on non-bijective multivariate maps. The presented symmetric encryption algorithms are based on three families of bipartite graphs with partition sets isomorphic to $\mathbb K^n$, where $\mathbb K$ is selected as the finite commutative ring. The plainspace of the algorithm is $\Omega=\{x|\sum x\_i \in \mathbb K^*, x\in \mathbb K^n\}\subset \mathbb K^n,$ $\Omega \cong \mathbb K^*\times \mathbb K^{n-1}.$ We describe the algorithm for the case $\mathbb K=\mathbb Z\_{2^m}$, $m\geq 2$. In fact, we use the relation $d*d\_{dec}\equiv 1 (\textrm{mod }2^{m-1})$, $d, d\_{dec}\in \mathbb Z^*\_{2^{m-1}}$ to obtain encryption polynomial map of degree greater than or equal to $d+2$ and decryption map of degree greater than or equal to $d\_{dec}+2$. We assume $d\_{dec}$ grows with the growth of parameter $m$, because this makes cryptanalysis very difficult task. Symmetric encryption and decryption algorithms for users are numerical recurrent processes, not requiring generation of encryption and decryption maps in their symbolic forms. They use arithmetical operations of addition, subtraction, and multiplication. That's why the algorithms are robust (execution speed is $O(n)$). To break the algorithm an adversary must use linearization attacks for recovering non-bijective ''decryption map'' of degree greater than $d\_{\rm dec}+2$ in its symbolic form. To achieve this, the adversary needs at least $O(n^{d\_{\rm dec}}+2)$ pairs of plaintext and corresponding ciphertext to restore the non-bijective map of degree greater than or equal to $d\_{dec}+2$. We present tables for evaluation of execution time for m = 8 with various length of passwords and sizes of files. Computer simulations demonstrate good mixing properties of the encryption functions.

References

  1. V. Ustimenko, Coordinatisation of Trees and their Quotients, in the Voronoj’s Impact on Modern Science, Kiev, Institute of Mathematics, 1998, vol. 2, 125-152.
  2. D. Sharma, V. Ustimenko, Special Graphs in Cryptography, The Poster Papers Collection,Third International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000), Melbourne Exhibition Centre, Australia, January 2000, p. 16- 19.
  3. V. Ustimenko, CRYPTIM: Graphs as Tools for Symmetric Encryption, Lecture Notes in Computer Science, Springer, LNCS 2227, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, November 2001, p. 278 - 286.
  4. V. Ustimenko, Graphs with special arcs and cryptography , Acta Applicandae Mathematicae (Kluwer) 2002, 74,117-153
  5. Yu, Khmelevsky, V. Ustimenko, Walks on graphs as symmetric and asymmetric tools for encryption, 2002, South Pacific Journal of Natural Studies, 2002, vol. 20, 23-41. www.usp.ac.fj/spjns
  6. Yu.Khmelevsky, M. Govorov, P. Sharma, V.Ustimenko, S. Dhanjal, Security Solutions for Spatial Data in Storage (Implementation Case within Oracle 9iAS), Proceedings of 8th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2004) Orlando, USA, in July 18-21, 2004, pp 318-323.
  7. M. Govorov, Yu Khmelevsky, A. Khorev, V. Ustimenko, Security Control for Spatial Warehouses, Proceedings ofthe 21th International Cartographic Conference (ICC), Durban, South Africa, 2003, 1784-1794.
  8. Yu Khmelevsky, V Ustimenko, Practical aspects of the Informational Systems reengineering, The South Pacific Journal of Natural Science, volume 21, 2003, p.75-21 (www.usp.ac.fj/spjns/volume21).
  9. A. Tousene, V. Ustimenko, CRYPTALL - a System to Encrypt All types of Data, Notices of Kiev - Mohyla Academy , v. 23, 2004, pp 12-15.
  10. A. Tousene, V. Ustimenko,Graph based private key crypto-system, International Journal on Computer Research, Nova Science Publisher, vol.13, issue 4, 2005, 12p.
  11. V. Ustimenko, On the extremal graph theory for directed graphs and its cryptographical applications, Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptology, vol. 3, World Scientific, 181-200 (2007).
  12. V. Futorny, V. Ustimenko, On small world semiplanes with generalised Schubert cells, Acta Applicandae Mathematicae, 98, N1 (2007) 47–61 (with V. Futorny).
  13. V. Ustimenko, On the graph based cryptography and symbolic computations, Serdica Journal of Computing, Proceedings of International Conference on Applications of Computer Algebra 2006, Varna, N1 (2007).
  14. J. Kotorowicz, V. A. Ustimenko, 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 (no. 2(54)) (2008) 347360.
  15. V. Ustimenko, On the hidden discrete logarithm for some polynomial stream ciphers, International Multiconference on Computer Science and Informational Technology, 20-22 October 2008, Wisla, Poland, CANA Proceedings. 13 pp.
  16. S. Kotorowicz, V. Ustimenko, On the properties of Stream Ciphers Based on Extremal Directed graphs, In “Cryptography Research Perspectives”, Nova Publishers, Ronald E. Chen (the editor), 2008.
  17. A. Touzene, V. Ustimenko, Private and Public Key Systems Using Graphs of High Girth,In “Cryptography Research Perspectives”, Nova Publishers, Ronald E. Chen (the editor), 2008, pp.205-216.
  18. M. Klisowski, V. Ustimenko, On the public keys based on the extremal graphs and digraphs, International Multiconference on Computer Science and Informational Technology, October 2010, Wisla, Poland, CANA Proceedings, 12 pp.
  19. Y. Khmelevsky, Gaetan Hains, E. Ozan, Chris Kluka, V. Ustimenko and D. Syrotovsky) International Cooperation in SW Engineering Research Projects, Proceedings of Western Canadien Conference on Computing Education, University of Northen British Columbia,Prince George BC, May 6-7, 2011, 14pp.
  20. A. Touzene, V. Ustimenko, Marwa AlRaisi, Imene Boude-lioua, Performance of Algebraic Graphs Based Stream-Ciphers Using Large Finite Fields, Annalles UMCS Informatica AI X1, 2 (2011), 81-93.
  21. M. Klisowski, V. Ustimenko, On the implementation of cubic public rules based on algebraic graphs over the finite commutative ring and their symmetries, MACIS 2011: Fourth International Conference on Mathematical Aspects of Computer and Information Sciences, Beijing, 2011, 13 pp.
  22. M. Klisowski, U. Romanczuk, V. Ustimenko,On public keys based on a new family of algebraic graphs , Annalles UMCS Informatica AI X1, 2 (2011), 127 -141.
  23. J. Kotorowicz, U. Romanczuk, V. Ustimenko, Implementation of stream ciphers based on a new family of algebraic graphs, Proceedings of Federated Conference on Computer Science and Information Systems (FedCSIS), 2011, 13 pp.
  24. M. Klisowski, V. Ustimenko, On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator, Mathematics in Computer Science, 2012, Volume 6, Number 2, Pages 181-198.
  25. M. Polak, V. Ustimenko, On stream cipher based on a family of graphs D(n, q) of increasing girth, Albanian J. Math. 8 (2014), no. 2, 37-44.
  26. F. Lazebnik and V. Ustimenko, Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size, DIMACS series in Discrete Math- ematics and Theoretical Computer Science, V. 10 (1993), 75-93.
  27. F. Lazebnik, V. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. , 60, (1995), 275 - 284.
  28. R. Wenger, Extremal graphs with no C4, C6 and C10s, 1991, J. Comb. Theory, Ser. B, 52(1),113-116.
  29. Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Springer, Advances in Information Security, V. 25, 2006.
  30. Polak M., Romańczuk U., Ustimenko V. and Wróblewska A., On the applications of Extremal Graph Theory to Coding Theory and Cryptography, Erdős Centennial, Proceedings of Erdős Centennial (EP 100), Electronic Notes in Discrete Mathematics,V43, P. 329–342 2013.
  31. Ustimenko V. A., Explicit constructions of extremal graphs and new multivariate cryptosystems Studia Scientiarum Mathematicarum Hungarica, Special issue “Proceedings of The Central European Conference, 2014, Budapest”.
  32. V. A. Ustimenko, On the cryptographical properties of extreme algebraic graphs, in Algebraic Aspects of Digital Communications, IOS Press (Lectures of Advanced NATO Institute, NATO Science for Peace and Security Series - D: Information and Communication Security, Volume 24, July 2009, 296 pp.
  33. Ustimenko V. A., On the flag geometry of simple group of Lie type and Multivariate Cryptography, Algebra and Discrete Mathematics. V. 19. No 1. 2015. P. 130-144.
  34. Louis Goubin, Jacques Patarin, Bo-Yin Yang,Multivariate Cryptography. Encyclopedia of Cryptography and Security, (2nd Ed.) 2011, 824-828.
  35. Patarin J., The Oil i Vinegar digital signatures, Dagstuhl Workshop on Cryptography. 1997.
  36. Kipnis A., Shamir A., Cryptanalisis of the Oil and Vinegar Signature Scheme Advances in Cryptology - Crypto 96, Lecture Notes in Computer Science, V. 1462, 1996, P. 257–266.
  37. Bulygin S., A. Petzoldt A., and Buchmann J, Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks, In Guang Gong and KishanChand Gupta, editors, “Progress in Cryptology - INDOCRYPT”, Guang Gong and Kishan Chand Gupta, editors, Lecture notes in Computer Science, V. 6498, 2010. P. 1732.
  38. Romańczuk-Polubiec U., Ustimenko V, On two windows multivariate cryptosystem depending on random parameters Algebra and Discrete Mathematics. 2015. V. 19. No. 1. P. 101–129.
  39. V. Ustimenko, On algebraic graph theory and non-bijective maps in cryptography, Algebra and Discrete Mathematics, Volume 20 (2015). Number 1, pp. 152-170.
  40. A. Wrblewska, On some properties of graph based public keys, Albanian Journal of Mathematics, Volume 2, Number 3, 2008, 229-234, NATO Advanced Studies Institute: “New challenges in digital communications”.
  41. U. Romańczuk, V. Ustimenko, On regular forests given in terms of algebraic geometry, new families of expanding graphs with large girth and new multivariate cryptographical algorithms, Proceedings of International conference “Applications of Computer Algebra”, Malaga, 2013, p. 135-139.
  42. M. Klisowski, Zwiekszenie bezpieczeństwa kryptograficznych algorytmów wielu zmiennych bazujacych na algebraicznej teorii grafów, PhD thesis, Czestochowa, 2014.
  43. V. Ustimenko,Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, vol.140, N3 (2007) pp. 412-434.
  44. V. Ustimenko, U. Romańczuk, On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in “Artificial Intelligence, Evolutionary Computing and Metaheuristics ”, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Volume 427/January 2013, pp. 231-256.
  45. V. Ustimenko, U. Romańczuk, On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in “Artificial Intelligence, Evolutionary Computing and Metaheuristics “, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Volume 427/January 2013, pp. 257-285.
  46. U. Romańczuk, V. Ustimenko, On the key exchange with matrices of large order and graph based nonlinear maps, Albanian Journal of Mathematics, Volume 4, Number 4, pp. 203211 (2010).
  47. V. Ustimenko, Division algebras and Tits geometries, DNAUSSR 296, No. 5 (1987), 1061-1065 (Russian)
  48. V. Ustimenko, A linear interpretation of the flag geometries of Chevalley groups, Kiev University, Ukrainskii Matematicheskii Zhurnal 42, No. 3 (March, 1990), 383-387; English transl.
  49. M. Polak, On the applications of algebraic graph theory to coding, PhD thesis, Maria Curie-Skłodowska, 2016.