Left MQQs whose left parastrophe is also quadratic

Simona Samardjiska; Danilo Gligoroski

Commentationes Mathematicae Universitatis Carolinae (2012)

  • Volume: 53, Issue: 3, page 397-421
  • ISSN: 0010-2628

Abstract

top
A left quasigroup ( Q , q ) of order 2 w that can be represented as a vector of Boolean functions of degree 2 is called a left multivariate quadratic quasigroup (LMQQ). For a given LMQQ there exists a left parastrophe operation q ∖ defined by: q ∖ ( u , v ) = w ⇔ q ( u , w ) = v that also defines a left multivariate quasigroup. However, in general, ( Q , q ∖ ) is not quadratic. Even more, representing it in a symbolic form may require exponential time and space. In this work we investigate the problem of finding a subclass of LMQQs whose left parastrophe is also quadratic (i.e. is also an LMQQ), and in the same time can be easily constructed. These LMQQs are affine in the second argument, and their left parastrophe can be easily expressed from the quasigroup operation. We give necessary and sufficient conditions for an LMQQ of this type to have a left parastrophe that is also an LMQQ. Based on this, we distinguish a special class that satisfies our requirements and whose construction is deterministic and straightforward.

How to cite

top

Samardjiska, Simona, and Gligoroski, Danilo. "Left MQQs whose left parastrophe is also quadratic." Commentationes Mathematicae Universitatis Carolinae 53.3 (2012): 397-421. <http://eudml.org/doc/246955>.

@article{Samardjiska2012,
abstract = {A left quasigroup $(Q,q)$ of order $2^w$ that can be represented as a vector of Boolean functions of degree 2 is called a left multivariate quadratic quasigroup (LMQQ). For a given LMQQ there exists a left parastrophe operation $q_\{\backslash \}$ defined by: $q_\{\backslash \}(u,v)= w \Leftrightarrow q(u,w)= v$ that also defines a left multivariate quasigroup. However, in general, $(Q,q_\{\backslash \})$ is not quadratic. Even more, representing it in a symbolic form may require exponential time and space. In this work we investigate the problem of finding a subclass of LMQQs whose left parastrophe is also quadratic (i.e. is also an LMQQ), and in the same time can be easily constructed. These LMQQs are affine in the second argument, and their left parastrophe can be easily expressed from the quasigroup operation. We give necessary and sufficient conditions for an LMQQ of this type to have a left parastrophe that is also an LMQQ. Based on this, we distinguish a special class that satisfies our requirements and whose construction is deterministic and straightforward.},
author = {Samardjiska, Simona, Gligoroski, Danilo},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {left multivariate quadratic quasigroup; left parastrophe; algebraic degree; matrix of Boolean polynomials; multivariate quadratic quasigroups; Boolean polynomials; left parastrophes},
language = {eng},
number = {3},
pages = {397-421},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Left MQQs whose left parastrophe is also quadratic},
url = {http://eudml.org/doc/246955},
volume = {53},
year = {2012},
}

TY - JOUR
AU - Samardjiska, Simona
AU - Gligoroski, Danilo
TI - Left MQQs whose left parastrophe is also quadratic
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2012
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 53
IS - 3
SP - 397
EP - 421
AB - A left quasigroup $(Q,q)$ of order $2^w$ that can be represented as a vector of Boolean functions of degree 2 is called a left multivariate quadratic quasigroup (LMQQ). For a given LMQQ there exists a left parastrophe operation $q_{\backslash }$ defined by: $q_{\backslash }(u,v)= w \Leftrightarrow q(u,w)= v$ that also defines a left multivariate quasigroup. However, in general, $(Q,q_{\backslash })$ is not quadratic. Even more, representing it in a symbolic form may require exponential time and space. In this work we investigate the problem of finding a subclass of LMQQs whose left parastrophe is also quadratic (i.e. is also an LMQQ), and in the same time can be easily constructed. These LMQQs are affine in the second argument, and their left parastrophe can be easily expressed from the quasigroup operation. We give necessary and sufficient conditions for an LMQQ of this type to have a left parastrophe that is also an LMQQ. Based on this, we distinguish a special class that satisfies our requirements and whose construction is deterministic and straightforward.
LA - eng
KW - left multivariate quadratic quasigroup; left parastrophe; algebraic degree; matrix of Boolean polynomials; multivariate quadratic quasigroups; Boolean polynomials; left parastrophes
UR - http://eudml.org/doc/246955
ER -

References

top
  1. Albert A.A., 10.1090/S0002-9947-1943-0009962-7, Trans. Amer. Math. Soc. 54 (1943), 507–519. Zbl0063.00039MR0009962DOI10.1090/S0002-9947-1943-0009962-7
  2. Ahlawat R., Gupta K., Pal S.K., Fast generation of multivariate quadratic quasigroups for cryptographic applications, Proceeding of Mathematics in Defence, 2009. 
  3. Belousov V.D., Osnovi teorii kvazigrup i lup (in Russian), Nauka, Moscow, 1967. MR0218483
  4. Carter G., Dawson E., Nielsen L., A latin square version of DES, in Proc. Workshop of Selected Areas in Cryptography, Ottawa, Canada, 1995. 
  5. Chen Y., Knapskog S.J., Gligoroski D., Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity, INSCRYPT, Proceedings of the 6th International Conference on Information Security and Cryptology, 2010. 
  6. Christov A., Kryptografie založená na teorii kvazigrup, Diploma Thesis, Charles University, Prague, 2009, available at: http://artax.karlin.mff.cuni.cz/ chria3am/thesis/. 
  7. Cooper J., Donovan D., Seberry J., Secret sharing schemes arising from Latin Squares, Bull. Inst. Combin. Appl. 4 (1994), 33–43. Zbl0835.05009MR1301402
  8. Gligoroski D., Markovski S., Kocarev L., Gusev M., Edon80 Hardware Synchronous stream cipher, SKEW 2005 - Symmetric Key Encryption Workshop, Aarhus Denmark, 2005. 
  9. Gligoroski D., Markovski S., Knapskog S.J., Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups, MATH’08: Proceedings of the American Conference on Applied Mathematics, pp. 44–49, 2008. Extended version of the paper: , in Cryptology ePrint Archive, Report 2008/320, http://eprint.iacr.org. MR2426887
  10. Gligoroski D., Odegard R.S., Jensen R.E., Perret L., Faugère J.-C., Knapskog S.J., Markovski S., MQQ-SIG, an ultra-fast and provably CMA resistant digital signature scheme, in Proc. of INTRUST 2011, LNCS vol. 7222, 2012, pp. 184–203. 
  11. Gligoroski D., Odegard R.S., Mihova M., Knapskog S.J., Drápal A., Klima V., [unknown], }SHA-3 Algorithm Submission, 2008. 
  12. Gligoroski D., Klima V., Knapskog S.J., El-Hadedy M., Amundsen J., Mjølsnes S.F., Cryptographic Hash Function sc{Blue Midnight Wish, }SHA-3 Algorithm Submission, 2008. 
  13. Klimov A., Shamir A., A new class of invertible mappings, 4th Workshop on Cryptographic Hardware and Embedded Systems CHES 2002, pp. 471-484, Springer, 2002. Zbl1020.94522
  14. Markovski S., Mileva A., Cryptographic Hash Function NaSHA, SHA-3 Algorithm Submission, 2008. 
  15. Matsumoto M., Saito M., Nishimura T., Hagita M., CryptMT Stream Cipher Version 3, in Workshop Record of SASC 2007: The State of the Art of Stream Ciphers, eSTREAM report 2007/028, 2007, available at: http://www.ecrypt.eu.org/stream/papers.html. 
  16. Nguyen D.V., Chilappagari S.K., Marcellin M.W., Vasić B., LDPC codes from latin squares free of small trapping sets, arXiv:1008.4177, 2010, available at: http://arxiv.org/abs/1008.4177. 
  17. Rivest R.L., Permutation polynomials modulo 2 w , Finite Fields Appl. 7 (2001), 287–292. MR1826338
  18. Samardjiska S., Chen Y., Gligoroski D., Algorithms for construction of multivariate quadratic quasigroups (MQQs) and their parastrophe operations in arbitrary Galois fields, Journal of Information Assurance and Security 7 (2012), 164–172. 
  19. Samardjiska S., Markovski S., Gligoroski D., Multivariate quasigroups defined by T-functions, Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, 2010, pp. 117–127. 
  20. Schnorr C.P., Vaudenay S., Black Box Cryptanalysis of hash networks based on multipermutations, in Advances of Cryptology - EUROCRYPT'94, Springer, Berlin, 1995. MR1479648
  21. Shannon C.E., 10.1002/j.1538-7305.1949.tb00928.x, Bell Sys. Tech. J. 28 (1949), 657–715. Zbl1200.94005MR0032133DOI10.1002/j.1538-7305.1949.tb00928.x
  22. Smith J.D.H., An Introduction to Quasigroups and Their Representations, Chapman and Hall/CRC, Boca Raton, FL, 2007. Zbl1122.20035MR2268350
  23. Zhang L., Huang Q., Lin S., Abdel-Ghaffar K., Blake I.F., Quasicyclic LDPC codes on Latin squares and the ranks of their parity-check matrices, in Inf. Theory and Appl. Workshop, 2010. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.