access icon free Efficient methods to generate cryptographically significant binary diffusion layers

© The Institution of Engineering and Technology
Received 16/02/2016, Accepted 26/07/2016, Revised 30/06/2016, Published 03/08/2016

In this study, the authors propose new methods using a divide-and-conquer strategy to generate n × n binary matrices (for composite n) with a high/maximum branch number and the same Hamming weight in each row and column. They introduce new types of binary matrices: namely, ( BHwC ) t, m and ( BCwC ) q, m types, which are a combination of Hadamard and circulant matrices, and the recursive use of circulant matrices, respectively. With the help of these hybrid structures, the search space to generate a binary matrix with a high/maximum branch number is drastically reduced. By using the proposed methods, they focus on generating 12 × 12, 16 × 16 and 32 × 32 binary matrices with a maximum or maximum achievable branch number and the lowest implementation costs (to the best of their knowledge) to be used in block ciphers. Then, they discuss the implementation properties of binary matrices generated and present experimental results for binary matrices in these sizes. Finally, they apply the proposed methods to larger sizes, i.e. 48 × 48, 64 × 64 and 80 × 80 binary matrices having some applications in secure multi-party computation and fully homomorphic encryption.

Inspec keywords: Hadamard matrices; search problems; divide and conquer methods; cryptography

Other keywords: hybrid structures; implementation costs; divide-and-conquer strategy; circulant matrices; maximum achievable branch number; high-branch number; fully-homomorphic encryption; search space; binary matrices; Hamming weight; cryptographically significant binary diffusion layers; block ciphers; secure multiparty computation; Hadamard matrices

Subjects: Knowledge engineering techniques; Combinatorial mathematics; Optimisation techniques; Data security; Linear algebra (numerical analysis)

References

    1. 1)
      • 12. Albrecht, M.R., Driessen, B., Kavun, E.B., et al: ‘Block ciphers – focus on the linear layer (feat. PRIDE)’. CRYPTO (1), 2014(LNCS, 8616), pp. 57–76.
    2. 2)
      • 5. Biham, E., Shamir, A.: ‘Differential cryptanalysis of DES-like cryptosystems’. Proc. of CRYPTO'90, 1990 (LNCS, 537), pp. 2–21.
    3. 3)
      • 14. Albrecht, M.R., Rechberger, C., Schneider, T., et al: ‘Ciphers for MPC and FHE’. Proc. of EUROCRYPT 2015 Part I, 2015 (LNCS, 9056), pp. 430–454.
    4. 4)
      • 6. Flajolet, P., Sedgewick, R.: ‘Analytic combinatorics’ (Cambridge University Press, Cambridge, 2009).
    5. 5)
      • 2. Shannon, C.E.: ‘Communication theory of secrecy systems’, Bell Syst. Tech. J., 1949, 28, (7), pp. 656–715.
    6. 6)
      • 10. Aoki, K., Ichikawa, T., Kanda, M., et al: ‘Camellia: a 128 bit block cipher suitable for multiple platforms-design and analysis’. Proc. of Selected Areas in Cryptography, SAC 2000, 2001 (LNCS, 2012), pp. 39–56.
    7. 7)
      • 15. Koo, B.W., Jang, H.S., Song, J.H.: ‘On constructing of a 32 × 32 binary matrix as a diffusion layer for a 256 bit block cipher’. Proc. of Int. Conf. on Information Security and Cryptology, 2006 (LNCS, 4296), pp. 51–64.
    8. 8)
      • 7. Z'aba, M.R.: ‘Analysis of linear relationships in block ciphers’. PhD thesis, Queensland University of Technology, Brisbane, Australia, 2010.
    9. 9)
      • 8. Barreto, P.S.L.M., Rijmen, V.: ‘The ANUBIS legacy-level block cipher’. Proc. First Open NESSIE Workshop, Leuven, 2000.
    10. 10)
      • 18. Sakallı, M.T., Akleylek, S., Aslan, B., et al: ‘On the construction of 20 × 20 and 24 × 24 binary matrices with good implementation properties for lightweight block ciphers and hash functions’, Math. Prob. Eng., doi: 10.1155/2014/540253.
    11. 11)
      • 19. Kwon, D., Sung, S.H., Song, J.H., et al: ‘Design of block ciphers and coding theory’, Trends Math., 2005, 8, (1), pp. 13–20.
    12. 12)
      • 4. Matsui, M.: ‘Linear cryptanalysis method for DES cipher’. Proc. of EUROCRYPT'93, 1994 (LNCS, 765), pp. 386–397.
    13. 13)
      • 11. Kwon, D., Kim, J., Park, S., et al: ‘New block cipher: ARIA’. Proc. of Int. Conf. on Information Security and Cryptology, 2004 (LNCS, 2971), pp. 432–445.
    14. 14)
      • 1. Daemen, J., Rijmen, V.: ‘The design of Rijndael, AES – the advanced encryption standard’ (Springer, Heidelberg, 2002).
    15. 15)
      • 13. Nakahara, J.Jr., Abrahão, É.: ‘A new involutory MDS matrix for the AES’, Int. J. Netw. Sec., 2009, 9, (2), pp. 109–116.
    16. 16)
      • 16. Aslan, B., Sakallı, M.T.: ‘Algebraic construction of cryptographically good binary linear transformations’, Sec. Commun. Netw., 2014, 7, (1), pp. 53–63.
    17. 17)
      • 3. Daemen, J.: ‘Cipher and hash function design’. PhD thesis, Katholieke Universiteit Leuven, Belgium, 1995.
    18. 18)
      • 17. Sakallı, M.T., Aslan, B.: ‘On the algebraic construction of cryptographically good 32 × 32 binary linear transformations’, J. Comput. Appl. Math., 2014, 259, (Part B), pp. 485–494.
    19. 19)
      • 20. Koo, B.W., Jang, H.S., Song, J.H.: ‘Constructing and cryptanalysis of a 16 × 16 binary matrix as a diffusion layer’. Proc. of Information Security Applications Fourth Int. Workshop (WISA 2003), 2003 (LNCS, 2908), pp. 489–503.
    20. 20)
      • 9. Barreto, P.S.L.M., Rijmen, V.: ‘The Khazad legacy-level block cipher’. Proc. First Open NESSIE Workshop, Leuven, 2000.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2016.0085
Loading

Related content

content/journals/10.1049/iet-ifs.2016.0085
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading