Geodesic
Semigroups of binary operations and magma-based cryptography
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 26 (2020) no. 1, pp. 23-51
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this article, algebras of binary operations as a special case of finitary homogeneous relations algebras are investigated. The tools of our study are based on unary and associative binary operations acting on the set of ternary relations. These operations are generated by the converse operation and the left-composition of binary relations. Using these tools, we are going to define special kinds of ternary relations that correspond to functions, injections, right- and left-total binary relations. Then we obtain criteria for these properties in terms of ordered semigroups. Note, that there is an embedding of the semigroup of quasigroups operations in the semigroup of magmas operation and further in the semigroup of ternary relations. This is similar to embedding the semigroup of bijections in the semigroup of functions and then in the semigroup of binary relations. Taking a binary operation as the generator of a cyclic semigroup, we can apply an exponential squaring method for the fast computation of its positive integer powers. Given that this is the main method of public key cryptography, we are adapting the Diffie–Hellman–Merkle key exchange algorithm for magmas as a result.
Keywords: algebra of finitary relations, algebra of indicator function, magmas, quasigroups, semigroups, cyclic semigroup of binary operations, public key cryptography, Diffie–Hellman–Merkle key exchange. 
@article{VSGU_2020_26_1_a2,
     author = {V. P. Tsvetov},
     title = {Semigroups of binary operations and magma-based cryptography},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {23--51},
     year = {2020},
     volume = {26},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2020_26_1_a2/}
}
TY  - JOUR
AU  - V. P. Tsvetov
TI  - Semigroups of binary operations and magma-based cryptography
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2020
SP  - 23
EP  - 51
VL  - 26
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VSGU_2020_26_1_a2/
LA  - ru
ID  - VSGU_2020_26_1_a2
ER  - 
%0 Journal Article
%A V. P. Tsvetov
%T Semigroups of binary operations and magma-based cryptography
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2020
%P 23-51
%V 26
%N 1
%U http://geodesic.mathdoc.fr/item/VSGU_2020_26_1_a2/
%G ru
%F VSGU_2020_26_1_a2
V. P. Tsvetov. Semigroups of binary operations and magma-based cryptography. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 26 (2020) no. 1, pp. 23-51. http://geodesic.mathdoc.fr/item/VSGU_2020_26_1_a2/

[1] W. Diffie, M. E. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, IT-22 (1976), 644–654 | DOI | MR | Zbl

[2] R. C. Merkle, “Secure Communications over Insecure Channels”, Communications of the ACM, 21:4 (1978), 294–299 https://nakamotoinstitute.org/static/docs/secure-communications-insecure-channels.pdf | DOI | MR | Zbl

[3] A. Shamir, “How to share a secret”, Communications of the ACM, 22:11 (1979), 612–613 | DOI | MR | Zbl

[4] T. Matsumoto, H. Imai, “Public Quadratic Polynomial-tuples for effcient signature-verification and message-encryption”, Advances in Cryptology — EUROCRYPT'88, EUROCRYPT 1988, Lecture Notes in Computer Science, 330, eds. Barstow D. et al., Springer, Berlin–Heidelberg, 419–453 | DOI | MR

[5] J. Patarin, “Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms”, Advances in Cryptology — EUROCRYPT-96, EUROCRYPT 1996, Lecture Notes in Computer Science, 1070, ed. Maurer U., Springer, Berlin–Heidelberg, 33–48 | DOI | MR | Zbl

[6] P. Shor, “Algorithms for quantum computation: discrete logarithms and factorings”, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, 124–134 | DOI | MR

[7] J. D. Bernstein, J. Buchmann, E. Dahmen (eds.), Post-quantum cryptography, Springer, Berlin, 2009, 245 pp. | DOI | MR

[8] N. Koblitz, “Elliptic Curve Cryptosystems”, Mathematics of Computation, 48:177 (1987), 203–209 https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf | DOI | MR | Zbl

[9] N. Koblitz, “Hyperelliptic Cryptosystems”, Journal of cryptology, 1:3 (1989), 139–150 | DOI | MR | Zbl

[10] O. Goldreich, S. Goldwasser, S. Halevi, “Public-key cryptosystems from lattice reduction problems”, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO 97, 1997, 112–131 | DOI | MR | Zbl

[11] O. Regev, “Lattice-based cryptography”, Advances in Cryptology – CRYPTO 2006, CRYPTO 2006, Lecture Notes in Computer Science, 4117, ed. Dwork C., Springer, Berlin–Heidelberg, 131–141 | DOI | MR | Zbl

[12] G. Maze, C. Monico, J. Rosenthal, “Public key cryptography based on semigroup actions”, Advances in Mathematics of Communications, 1:4 (2007), 489–507 | DOI | MR | Zbl

[13] R. Ebrahimi Atani, S. Ebrahimi Atani, S. Mirzakuchaki, “Public key cryptography using semigroup actions and semirings”, Journal of Discrete Mathematical Sciences Cryptography, 4 (2008) | MR

[14] S. Carter, M. N. Wegman, “Universal Class of Hash Function”, J. Computer and System Sciences, 18:2 (1979), 143–154 https://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/universalclasses.pdf | DOI | MR | Zbl

[15] J. Denes, A. D. Keedwell, Latin Squares. New Developments in the Theory and Applications, Nord-Holland Publishing Co, Amsterdam, 1981, 469 pp. http://lib.mexmat.ru/books/191480

[16] S. Bakhtiari, R. Safavi-Naini, J. Pieprzyk, “A message Authentication Code based on Latin Squares”, Proc. Australasian on Information Security and Privacy, 1997, 194–203 | DOI | Zbl

[17] E. Dawson, D. Donovan, A. Offer, “Quasigrops, isotopism and authentication schemes”, Australasian Journal of Combinatorics, 13 (1996), 75–88 | MR | Zbl

[18] M. M. Glukhov, “O primeneniyakh kvazigrupp v kriptografii”, Prikladnaya diskretnaya matematika, 2008, no. 2, 28–32 | Zbl

[19] A. V. Cheremushkin, “Partially invertible strongly dependent n-ary operations”, Sbornik: Mathematics, 211:2 (2020), 291–308 | DOI | MR | Zbl

[20] G. Hessenberg, “Grundbegriffe der Mengenlehre”, Abhandlungen der Friesschen Schule, 1:4 (1906), 478–706 https://archive.org/details/grundbegriffede00hessgoog/page/n1/mode/2up

[21] F. Hausdorff, Grundzlige der Mengenlehre, Verlag von Veit Comp., Leipzig, 1914, 500 pp. https://archive.org/details/grundzgedermen00hausuoft

[22] A. Tarski, “On the calculus of relations”, Journal of Symbolic Logic, 6:3 (1941), 73–89 | DOI | MR

[23] R. Fraisse, Theory of Relations, Studies in Logic and the Foundations of Mathematics, Elsevier, 2011, 410 pp. https://readli.net/theory-of-relations/

[24] N. L. Biggs, Discrete Mathematics, Oxford University Press, Oxford, 2002, 425 pp. https://archive.org/details/discretemathemat00norm_0/mode/2up | Zbl

[25] B. M. Schein, “Relation algebras and function semigroups”, Semigroup Forum, 1:1 (1970), 1–62 | DOI | MR | Zbl

[26] N. Bruijn, P. Erdos, “A colour problem for infinite graphs and a problem in the theory of relations”, Proc. Nederl. Akad. Wetensch. Indag. Math. Ser. A, 54:5 (1951), 371–373 https://research.tue.nl/files/4237754/597497.pdf | DOI | Zbl

[27] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics A foundation for computer science, Advanced Book Program, Addison-Wesley, 1989, 625 pp. https://notendur.hi.is/pgg/(ebook-pdf) - Mathematics - Concrete Mathematics.pdf | MR | Zbl

[28] V. P. Tsvetov, “Algebras of finitary relations”, CEUR Workshop Proceedings, 2416, 2019, 119–125 | DOI