Isotopy of latin squares in cryptography

Otokar Grošek; Marek Sýs

doi:10.2478/v10127-010-0003-z

Abstract

We present a new algorithm for a decision problem if two Latin squares are isotopic. Our modification has the same complexity as Miller’s algorithm, but in many practical situations is much faster. Based on our results we study also a zero-knowledge protocol suggested in [3]. From our results it follows that there are some problems in practical application of this protocol.

References

[1] COLBOURN, C. J.-DINITZ, J. H., (eds.): The CRC Handbook of Combinatorial Designs. in: CRC Press Ser. Discrete Math. Appl., CRC Press, Boca Raton, FL, 1996.
Search in Google Scholar
[2] DÉNES, J.-KEEDWELL, A. D.: Latin Squares and Their Applications. Academic Press, New York, NY, 1974.
Search in Google Scholar
[3] DÉNES, J.-DÉNES, T.: Non-associative algebraic systems in cryptology. Protectionagainst “meet in the middle” attack, Quasigroups Related Systems 8 (2001), 7-14.
Search in Google Scholar
[4] FERGUSON, M.: The Determinants of Latin Squares of Order 7. Honours Undergraduate Thesis, Iowa State University, 1989.
Search in Google Scholar
[5] FORD, W.-JOHNSON, K. W.: Determinants of latin squares of order 8, Experiment. Math. 5 (1996), 317-325.10.1080/10586458.1996.10504596
Search in Google Scholar
[6] GLIGOROSKI, D.-MARKOVSKI, S.-KOCAREV, L.-GUSEV, M.: eSTREAM,ECRYPT Stream Cipher Project, Report 2005/007, 2005, http://www.ecrypt.eu.org/stream.
Search in Google Scholar
[7] GLIGOROSKI, D.-ODEGARD, R. S.-MIHOVA, M.-KNAPSKOG, S. J.-KOCAREV, L.- DRÁPAL, A.: Cryptographic Hash Function EDON-R, http://people.item.ntnu.no/~danilog/Hash/Edon-R/Supporting Documentation/ /EdonRDocumentation.pdf.
Search in Google Scholar
[8] GOLDREICH, O.-MICALI, S.-WIGDERSON, A.: Proofs that yield nothing but theirvalidity or all languages in NP have zero-knowledge proofs systems, J. Assoc. Comput. Mach. 38 (1991), 691-729.10.1145/116825.116852
Search in Google Scholar
[9] GROŠEK, O.-SATKO, L.-NEMOGA, K.: Ideal difference tables from an algebraic point of view, in: Cryptology and Information Security, Proc. of VI RECSI, Teneriffe, Spain, 2000, pp. 51-58; Ammendment to Criptolog´ıa y Seguridad de la Informaci´on (P. Caballero-Gil, C. Hern´andez-Goya), RA-MA, Madrid, 2000, pp. 453-454.
Search in Google Scholar
[10] GROŠEK, O.-SATKO, L.-NEMOGA, K.: Generalized perfectly nonlinear functions, Tatra Mt. Math. Publ. 20 (2000), 121-131.
Search in Google Scholar
[11] GROŠEK, O.-HORÁK, P.-TRUNG VAN TRAN: On non-polynomial Latin squares, Des. Codes Cryptogr. 32, (2004), 217-226.10.1023/B:DESI.0000029224.20896.8b
Search in Google Scholar
[12] KAPLANSKY, I.: Abraham Adrian Albert. A biographical memoir, http://citeseerx.ist.psu.edu/
Search in Google Scholar
[13] KOŚCIELNY, C.-MULLEN, G. L.: A quasigroup-based public-key cryptosystem, Int. J. Appl. Math. Comp. Sci. 9 (1999), 955-963.
Search in Google Scholar
[14] LAI, X.-MASSEY, J. L.: A proposal for a new block encryption standard, in: Advances in Cryptology-EUROCRYPT ’90, Aarhaus, Denmark, 1990 (I. B. Damg˚ard, ed.), Lecture Notes in Comput. Sci., Vol. 473, Springer-Verlag, Berlin, 1991, pp. 389-404.10.1007/3-540-46877-3_35
Search in Google Scholar
[15] MARKOVSKI, S.-GLIGOROSKI, D.-STOJCEVSKA, B.: Secure two way on-line communication by using quasigroups enciphering with almost public key, Novi Sad J. Math. 30 (2000), 43-49.
Search in Google Scholar
[16] MILLER, G. L.: On the n log n isomorphism technique, in: Proc. 10th Annual ACM Symposium on Theory of Computing-STOC ’78, San Diego, California, 1978, ACM, New York, NY, 1978, pp. 51-58.10.1145/800133.804331
Search in Google Scholar
[17] Miller’s private communication with Tarjan.
Search in Google Scholar
[18] ROBINSON, D. J. S.: An Introduction to Abstract Algebra. in: de Gruyter Textbook, Berlin, 2003.
Search in Google Scholar
[19] SHCHERBACOV, V.: On some known possible applications of quasigroups in cryptology, http://www.karlin.mff.cuni.cz/~drapal/krypto.pdf.
Search in Google Scholar
[20] SADE, A.: Autotopies des quasigroupes et des systmes associatifs, Arch.Math. (Brno) 4 (1968), 1-23.
Search in Google Scholar
[21] SÝS, M.: Latin Squares in Cryptography. Honours PhD Thesis, Slovak Technical University, Bratislava, 2009.
Search in Google Scholar
[22] VOJVODA, M.-SÝS, M.-J ´OKAY, M.: A Note on Algebraic Properties of Quasigroups in Edon80, in: The State of the Art of Stream Ciphers-SASC ’07, ECRYPT Network of Excelence in Cryptology, Bochum, Germany, 2007, pp. 307-315.
Search in Google Scholar

Isotopy of latin squares in cryptography

Abstract

Paradigm

My account