On group rings and some of their applications to combinatorics and cryptography

Document Type : Research Paper


1 Universities of Paris 8 and Paris 13

2 University of Waterloo


‎We give a survey of recent applications of group rings to combinatorics and to cryptography‎, ‎including their use in the differential cryptanalysis of block ciphers‎.


Main Subjects

[1] L. D. Baumert, Cyclic Difference Sets, Lecture Notes in Mathematics, 182, Springer-Verlag, Berlin-New York, 1971.

[2] T. Beth, D. Jungnickel and H. Lenz, Design Theory, 1, Cambridge University Press, Cambridge, 1999.

[3] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems , Journal of Cryptology, 4 no. 1 (1991) 3-72.

[4] A. A. Bovdi, Group Algebra, Encyclop edia of Mathematics, Springer, 2001.

[5] K. Browning, J. F. Dillon, R. E. Kibler and M. McQuistan. APN polynomials and related codes . Sp ecial volume of Journal of Combinatorics, Information and System Sciences, honoring the 75-th birthday of Prof. D.K.Ray-Chaudhuri, 34, no. 1-4, (2009) 135-159.

[6] C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes, Chapter of the monography Bo olean Models and Methods in Mathematics, Computer Science, and Engineering, Y. Crama and P. Hammer eds, Cam-bridge University Press, 257-397, 2010. Preliminary version available at http://www- rocq.inria.fr/codes/Claude.Carlet/pubs.html.

[7] C. Carlet, Vectorial Boolean Functions for Cryptography, Chapter of the monograph Boolean Metho ds and Models, Y. Crama and P. Hammer eds, Cambridge University Press, to app ear so on. Preliminary version available at http://www- rocq.inria.fr/codes/Claude.Carlet/pubs.html.

[8] C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Designs, Codes and Cryptography, 15 no. 2 (1998) 125-156.

[9] C. Carlet and C. Ding, Highly nonlinear mappings, Journal of Complexity, 20 no. 2-3 (2004) 205-244.

[10] C. Carlet, G. Gong and Y. Tan, Quadratic zero-difference balanced functions, APN functions and strongly regular graphs, Designs, Codes and Cryptography, DOI 10.1007/s10623-014-0022-x.

[11] Y. M. Chee, Y. Tan and X. Zhang, Strongly regular graphs constructed from p-ary bent functions, Journal of Algebraic Combinatorics, 34 no. 2 (2011) 251-266.

[12] E. R. van Dam and D. Fon-Der-Flaass, Codes, graphs, and schemes from nonlinear functions, European Journal of Combinatorics, 24 no. 1 (2000) 85-98.

[13] C. Ding and Y. Tan, Zero-difference balanced functions with applications , Journal of Statistical Theory and Practice, no. 1 (2012) 3-19.

[14] W. Diffe and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976) 644-654.

[15] Y. Edel and A. Pott, A new almost perfect nonlinear function which is not quadratic , Advances in Mathematical Communications, 3 no. 1 (2009) 59-81.

[16] K. Feng and J. Luo, Value distributions of exponential sums from perfect nonlinear functions and their applications, IEEE Transaction on Information Theory, 53 no. 9 (2007) 3035-3041.

[17] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Graduate Texts in Mathematics, 84, Springer-Verlag, New York, 1990.

[18] D. Kahrobaei, C. Koupparis and V. Shpilrain, Public key exchange using matrices over group rings, arXiv:
1302.1625v1, 2013.

[19] L. Knudsen, Truncated and higher order differentials, Lecture Notes in Computer Science, 1008, FSE 1994, (1995) 196-211.

[20] L. Knudsen and M. Robshaw, The Block Cipher Companion, Information Security and Cryptography, Springer, 2001.

[21] P. V. Kumar, R. A. Scholtz and L. R. Welch, Generalized bent functions and their properties , Journal of Combina-torial Theory, Series A, 40 (1985) 90-107.

[22] S. Lang, Cyclotomic Fields II, Graduate Texts in Mathematics, 69, Springer-Verlag, New York-Berlin, 1980.

[23] S. L. Ma, A survey of partial difference sets, Design, Codes and Cryptography, 4, (1994) 221-261.

[24] M. Matsui, Linear cryptanalysis method for DES cipher , Lecture Notes in Computer Science, 765, EUROCRYPT 93, (1994) 55-64.

[25] W. Meier and O. Staffelbach, Fast correlation attacks on stream cipher, Advances in Cryptology, EUROCRYPT'88, Lecture Notes in Computer Science, 330 (1988) 301-314.

[26] C. Milies and S. Sehgal, An Introduction To Group Rings , Algebras and applications, 1, Springer, 2002.

[27] K. Nyb erg, Differential ly uniform mappings for cryptography, In Advances in cryptology, EUROCRYPT 93 (Lofthus, 1993), LNCS, 765 (1994) 55-64.

[28] A. Pott, Nonlinear functions in abelian groups and relative difference sets, Discrete Applied Mathematics, 138 (2004) 177-193.

[29] A. Pott, Finite Geometry and Character Theory, Lecture Notes in Mathematics, 1601, Springer, 1995.

[30] A. Pott, Y. Tan, T. Feng and S. Ling, Association schemes arising from bent functions , Designs, Codes and Cryp-tography, 59 no. 1-3 (2011) 319-331.

[31] D. S. Passman, The Algebraic Structure of Group Rings, Wiley, New York, 1977.

[32] Y. Tan, A. Pott and T. Feng, Strongly regular graphs associated with ternary bent functions, Journal of Combinatorial Theory, Series A, 117 no. 6 (2010) 668-682.

[33] G. Weng, W. S. Qiu, Z. Wang and Q. Xiang, Pseudo-Paley graphs and skew Hadamard difference sets from pre-semi elds, Designs, Codes and Cryptography, 44 (2007) 49-62.