Glasnik Matematicki, Vol. 47, No. 2 (2012), 333-349.

SHAPELESS QUASIGROUPS DERIVED BY FEISTEL ORTHOMORPHISMS

Aleksandra Mileva and Smile Markovski

Faculty of Computer Science, University "Goce Delčev", 2000 Štip, Republic of Macedonia
e-mail: aleksandra.mileva@ugd.edu.mk

Faculty of Computer Science and Engineering, University "Ss Cyril and Methodius", 1000 Skopje, Republic of Macedonia
e-mail: smile.markovski@finki.ukim.mk

Abstract.   Shapeless quasigroups are needed for cryptography purposes. In this paper, we construct shapeless quasigroups by the diagonal method from orthomorphisms over abelian groups. We use generalizations of Feistel networks as orthomorphisms. We introduce parameters into several types of Extended Feistel networks and Generalized Feistel-non linear feedback shift registers and, by suitable choice of the parameter values, different shapeless quasigroup can be used in every application.

2010 Mathematics Subject Classification.   20N05, 94A60.

Key words and phrases.   Shapeless quasigroup, Extended Feistel network, orthomorphism, Generalized Feistel-non linear feedback shift register.

Full text (PDF) (free access)

DOI: 10.3336/gm.47.2.09

References:

  1. J. Choy, G. Chew, K. Khoo, and H. Yap, Cryptographic properties and application of a generalized unbalanced Feistel network structure, in: ACISP 2009 (ed. C. Boyd, J. González Nieto), LNCS 5594 (2009), Springer Berlin Heidelberg, 73-89.

  2. T. P. Cowhig, Constructing monogenic quasigroups with specified properties, PhD thesis, University of London, 2009.

  3. J. Dénes and A. D. Keedwell, Latin squares. New developments in the theory and applications, North-Holland Publishing Co., Amsterdam, 1991.
    MathSciNet    

  4. A. Drápal and T. Kepka, Parity of orthogonal automorphisms, Comment. Math. Univ. Carolin. 28 (1987), 251-259.
    MathSciNet    

  5. A. B. Evans, Orthomorphism Graphs of Groups, J. of Geom. 35 (1989), 66-74.
    MathSciNet     CrossRef

  6. H. Feistel, Cryptography and computer privacy, Sci. Amer. 228 (1973), 15-23.
    http://www.apprendre-en-ligne.net/crypto/bibliotheque/feistel/
    CrossRef

  7. D. Gligoroski, S. Markovski and L. Kocarev, Edon-R, an infinite family of cryptographic hash functions, The Second NIST Cryptographic Hash Workshop, UCSB, Santa Barbara, CA, 2006. http://www.csrc.nist.gov/pki/HashWorkshop/2006/Papers/GLIGOROSKI\_EdonR-ver06.pdf. Accessed 16 June 2009.

  8. D. Gligoroski, R. S. Ødegård, R. E. Jensen, L. Perret, J.-C. Faugère, S. J. Knapskog and S. Markovski, The digital signature scheme MQQ-SIG, Report 527, Cryptology ePrint Archive, 2010.

  9. D. Gligoroski, S. Markovski and S.J. Knapskog, The stream cipher edon80, in: New stream cipher designs: The eSTREAM finalists, Springer-Verlag, 2008, 152-169. CrossRef

  10. D. Gligoroski, R. S. Ødegård, M. Mihova, S. J. Knapskog, L. Kocarev, and A. Drápal, Cryptographic hash function EDON-R. Submission to NIST as first round candidate, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions\_rnd1.html, 2008. Accessed 16 June 2009.

  11. D. F. Hsu, and A. D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs II, Pac. J. Math. 117 (1985), 291-312.
    MathSciNet     CrossRef

  12. V. I. Izbash, Monoquasigroups without congruences and automorphisms, Bul. Acad. Stiinte Repub. Mold. Mat. (4) (1992), 66-76.
    MathSciNet    

  13. D. M. Johnson, A. L. Dulmage and N. S. Mendelsohn, Orthomorphisms of groups and orthogonal latin squares, I, Can. J. Math. 13 (1961), 356-372.
    MathSciNet     CrossRef

  14. A. D. Keedwell, Crossed inverse quasigroups with long inverse cycles and applications to cryptography, Australas. J. Combin. 20 (1999), 241-250.
    MathSciNet    

  15. T. Kepka, A note on simple quasigroups, Acta Univ. Carolin.--Math. Phys. 19 (1978), 59-60.
    MathSciNet    

  16. H. B. Mann, The construction of orthogonal Latin squares, Ann. Math. Statistics 13 (1942), 418-423.
    MathSciNet     CrossRef

  17. S. Markovski and A. Mileva, Generating huge quasigroups from small non-linear bijections via extended Feistel function, Quasigroups Related Systems 17 (2009), 91-106.
    MathSciNet    

  18. S. Markovski and A. Mileva, NaSHA, Submission to NIST as first round candidate, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions\_rnd1.html, 2008. Accessed 16 June 2009.

  19. S. Markovski, S. Samardziska, D. Gligoroski and S. J. Knapskog, Multivariate trapdoor functions based on multivariate left quasigroups and left polynomial quasigroups, in: Proc. of The 2nd international conference on symbolic computation and cryptography (ed. C. Cid and J.-C. Faugère), 2010, Royal Halloway, Egham, UK, 237-251.

  20. K. A. Meyer, A new message authentication code based on the non-associativity of quasigroups, PhD thesis, Iowa State University, 2006.
    MathSciNet     Phd

  21. A. Mileva, Cryptographic primitives with quasigroup string transformations, PhD thesis, University ``Ss Cyril and Methodious" - Skopje, 2010. %nije citirano

  22. L. Mittenthal, Block substitutions using orthomorphic mappings, Adv. in Appl. Math. 16 (1995), 59-71.
    MathSciNet     CrossRef

  23. A. Sade, Groupoïdes automorphes par le groupe cyclique, Can. J. Math. 9 (1957), 321-335.
    MathSciNet     CrossRef

  24. D. G. Sarvate and J. Seberry, Encryption methods based on combinatorial designs, Ars Combinatoria 21A (1986), 237-246.

  25. V. A. Shcherbacov, On linear quasigroups and their automorphism groups, Mat. Issled. 120 (1991), 104-113 (in Russian).

  26. I. M. Wanless, Diagonally cyclic latin squares, European J. Combin. 25 (2004), 393-413.
    MathSciNet     CrossRef

  27. Y. Zheng, T. Matsumoto and H. Imai, On the construction of block provably secure and not relying on any unproved hypotheses, in: Advances in Cryptology - CRYPTO '89 (ed. G. Brassard) , LNCS 435 (1990), Springer Berlin Heidelberg, 461-480.
Glasnik Matematicki Home Page