MEME - Multi Entity Matrix Encryption

Table of Contents

• Introduction
• Matrix Properties
  • Matrix Multiplication
  • Matrix Inversion
• Matrix Encryption
  • Key Generation
  • Public Key Generation
  • Encryption
  • Decryption
  • Example
• Enhancements and Future Directions

Introduction

MEME (Multi Entity Matrix Encryption) is a matrix-based encryption algorithm that leverages matrix properties such as multiplication and inversion for secure data encryption. To further enhance security, we integrate a substitution box (SBox), based on the AES SBox, to add an additional layer of obfuscation to the ciphertext.

Matrix Properties

Matrix Multiplication

Matrix multiplication is a binary operation that produces a matrix from two matrices. For two matrices $A$ and $B$ to be multiplied, the number of columns in $A$ must be equal to the number of rows in $B$.

$$A_{m \times n} \times B_{n \times p} = C_{m \times p}$$

$$C_{ij} = \sum_{k=1}^{n} A_{ik} \times B_{kj}$$

Matrix Inversion

The inverse of a matrix $A$ is denoted as $A^{-1}$ and is defined as the matrix that, when multiplied by $A$, gives the identity matrix $I$.

$$A \times A^{-1} = I$$

$$A^{-1} = \frac{1}{\det(A)} \times \text{adj}(A)$$

Matrix Encryption

Key Generation

We generate a secure invertible matrix $A$ by using the following algorithm:

$$A = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{bmatrix}, \quad a_{ij} \in \mathbb{Z}_{\text{m}}$$

$$\det(A) \mod \text{m} \neq 0, \quad \gcd(\det(A), \text{m}) = 1$$

$$\text{where } a_{ij} \text{ is sampled randomly }$$

Public Key Generation

The public key is generated by multiplying the private key with a random matrix $P$, called the Perturbation matrix, and then applying the modulus:

$$K = (A \times P) \mod \text{m}$$

Encryption

The ciphertext is generated by multiplying the plaintext with the public key and applying the modulus:

$$C = (M \times K) \times \text{m}$$

We then apply a substitution box operation to the resulting ciphertext:

$$C' = \text{SBox}(C)$$

where $\text{SBox}(C)$ denotes the byte-wise substitution operation using the predefined SBox.

Decryption

The plaintext can be recovered by multiplying the ciphertext with the inverse of the private key, the inverse of the Perturbation matrix, and then applying the modulus:

$$M = ((C \times A^{-1}) \times P^{-1}) \mod \text{m}$$

After decryption, we apply the inverse SBox operation to retrieve the original ciphertext:

$$C = \text{SBox}^{-1}(C')$$

Example

Consider the following example where the key matrices are of size $2 \times 2$ and the modulus is 13:

$$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad P = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}, \quad M = \begin{bmatrix} 9 & 10 \\ 11 & 12 \end{bmatrix} \quad \text{mod} = 13$$

First, compute the public key:

$$K = A \times P = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \times \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix} \mod 13 = \begin{bmatrix} 6 & 9 \\ 4 & 11 \end{bmatrix}$$

Now, encrypt the message:

$$C = (M \times K) \times \text{m} = \begin{bmatrix} 9 & 10 \\ 11 & 12 \end{bmatrix} \times \begin{bmatrix} 6 & 9 \\ 4 & 11 \end{bmatrix} \times 13 = \begin{bmatrix} 7813 & 9074 \\ 9425 & 10946 \end{bmatrix} \mod 13$$

After applying the SBox substitution:

$$C' = \text{SBox}(C)$$

where $\text{SBox}$ substitutes each byte of the matrix $C$ according to the AES SBox table.

Finally, to decrypt:

$$A^{-1} = \begin{bmatrix} -2 & 1 \\ 1.5 & -0.5 \end{bmatrix}$$

$$P^{-1} = \begin{bmatrix} -4 & 3 \\ 3.5 & -2.5 \end{bmatrix}$$

$$M = ((C' \times A^{-1}) \times P^{-1}) \mod 13 = \begin{bmatrix} 9 & 10 \\ 11 & 12 \end{bmatrix}$$

Enhancements and Future Directions

While MEME provides a strong foundation for matrix-based encryption, several enhancements can be explored:

• Variable Key Sizes: Currently, MEME uses a fixed-size key of 2048 bits. Future work can include support for flexible key sizes.

• Substitution Box Variants: The current AES-based SBox can be replaced with other cryptographically secure SBoxes for different security requirements.

• Performance Optimization: The encryption and decryption process can be optimized for better performance. Currently, the algorithm is slow due to the matrix inversion and the SBox operation.

• Advanced Padding Schemes: Exploring other padding schemes like ISO/IEC 9797-1 could improve the handling of variable-length messages.