In this paper, we propose a novel variant of the Hill cipher based on vector spaces. In the classical Hill cipher, a non-singular matrix is used for encryption but it is well known that this cipher is vulnerable to the known-plaintext attack. In our proposed cryptosystem, we eradicate this problem by encrypting each plaintext block with a new invertible key matrix. This makes our scheme immune to all existing attacks in literature on this type of ciphers and so the resulting cipher can be used as other state-of-art block cipher. To generate the invertible matrices which serve as the dynamic keys, we make use of the vector spaces along with randomly generated basis and non-singular linear transformation. In addition to this, we also study the computational complexity of the proposed cryptosystem and compare this with the computational complexities of other schemes based on Hill cipher.