One-Time Involutory Matrix-Based Hill Cipher Modification

Abstract

Hill cipher needs inverse of the key-matrix for decryption. To avoid inversion, involutory matrices can be used. Known Hill cipher variants with involutory matrices have memory and computational complexity quadratic in plaintext size, T. It is known (Chefranov, Dukhnich, 2017) the Kronecker product-based Hill cipher modification, HKP, not calculating the quadratic-size key-matrix. Instead, invertible elementary matrices are iteratively multiplied with the plaintext in O(T.log(2)T) time and O(log(2)T) memory complexity. It can be used in one-time key mode. Modification of the HKP with the involutory key-matrix of the plaintext size represented as the Kronecker product of K elementary involutory matrices is proposed thus avoiding the key-matrix inverting for decryption. Experiments confirm its high performance. It can be further improved in performance, key and message security, and hardware complexity by processing large-bit-size integers and employing the both-sided matrix multiplication.