One-Time Kronecker Product-Based Hill Cipher Modification

Abstract

Modifications of the Hill cipher with the key matrix of the plaintext size, T=2(K) bytes, represented as the Kronecker product (KP) of K invertible elementary matrices (IEM) is considered in a number of works. They have quadratic in T memory and computational complexities. We propose KP-based Hill cipher modification, HKP, where quadratic-sized key matrix is actually not calculated. Instead, IEM-s are iteratively multiplied with the plaintext in O(Tlog(2)T) time and linear memory complexity. HKP, similar to one-time pad (OTP), is unconditionally secure but contrary to OTP, key size for which is 8T bits, HKP key size is only 15log(2)T bits providing security comparable to that of 128-bit key AES for K>7. Encryption time estimate of HKP is similar to that of AES and RC4.