Technical Summary: A Novel Public Key Cryptography Based on Generalized Lucas Matrices

Problem Statement

The paper addresses the need for enhanced public key cryptography schemes that offer larger key spaces, reduced transmission complexity, and robust security based on number theory and linear algebra. While matrix theory and recursive sequences (such as Fibonacci and Lucas sequences) have been utilized in cryptography (e.g., Hill Cipher, ElGamal), existing methods often involve exchanging large key matrices or rely on standard sequence properties. The authors propose a system that minimizes the data exchanged during key agreement while maximizing the complexity of the encryption key space through the use of generalized recursive matrices.

Methodology

1. Mathematical Foundations

The core of the proposed scheme relies on the construction of Generalized Lucas Matrices (GLM) derived from Generalized Fibonacci Matrices (GFM).

• Generalized Fibonacci Matrices (GFM): The authors utilize the $k$-th order generalized Fibonacci sequence $\{f_{k,n}\}$ and its corresponding matrix representation $Q^k_n$. These matrices satisfy standard properties such as $Q^n_k Q^l_k = Q^{n+l}_k$ and specific determinant rules based on the order $k$.
• Generalized Lucas Sequences: A new sequence $\{l_{k,n}\}$ is defined where the initial values are derived from the trace of the first $k$ GFM matrices ($l_{k,r} = \text{trace}(Q^r_k)$). The recurrence relation mirrors the generalized Fibonacci sequence: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Generalized Lucas Matrices (GLM): A recursive matrix $L^{(n)}_k$ is constructed using linear combinations of terms from the generalized Lucas sequence. The authors establish a fundamental relationship between GLM and GFM:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  where $L^{(0)}_k$ is the initial Lucas matrix.

2. Cryptographic Scheme

The proposed system integrates these matrices into a modified Affine-Hill Cipher combined with the ElGamal public key infrastructure.

• Key Exchange (ElGamal-based):

  • Receiver (Bob): Selects a prime $p$, a primitive root $\alpha$, and a secret integer $D$. He publishes $E_1 = \alpha$ and $E_2 = \alpha^D \pmod p$.
  • Sender (Alice): Chooses a random integer $e$. She computes a signature $s = E_1^e \pmod p$ and a shared secret $\lambda = E_2^e \pmod p$.
  • Transmission: Alice sends the ciphertext and the signature $s$ to Bob. She does not send the full key matrix or the secret $\lambda$.

• Encryption (Affine-Hill with GLM):

  • Using the shared secret $\lambda$ (order of the matrix) and the signature $s$ (exponent), Alice constructs the encryption key matrix $K = L^{(s)}_\lambda \pmod p$.
  • A shift vector $B$ is generated using terms from the Lucas sequence: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Plaintext blocks $P$ are encrypted as $C = (P \cdot K + B) \pmod p$.

• Decryption:

  • Bob recovers $\lambda$ using his private key: $\lambda = s^D \pmod p$.
  • He constructs the inverse matrix $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, where $H = (L^{(0)}_\lambda)^2$. The paper proves that $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, ensuring the existence of an inverse.
  • Decryption is performed as $P = (C - B) \cdot K^* \pmod p$.

Key Contributions

1. Definition of Generalized Lucas Matrices: The paper formally defines GLM of order $k$ and establishes their algebraic properties, including determinant formulas, product rules ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$), and the explicit construction of their inverses.
2. Parameter-Based Key Generation: Unlike traditional matrix-based ciphers where the entire matrix must be shared or generated from a large seed, this scheme allows the key matrix to be reconstructed by both parties using only two parameters: $\lambda$ (derived from the discrete logarithm problem) and $s$ (the signature).
3. Integration with Affine-Hill and ElGamal: The authors propose a hybrid scheme that utilizes the efficiency of the Affine-Hill cipher (block encryption with a shift vector) secured by the hardness of the discrete logarithm problem inherent in the ElGamal setup.
4. Inverse Construction: The paper provides a specific method for calculating the inverse of the GLM without relying on standard Gaussian elimination, utilizing the relationship $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Results and Analysis

• Implementation Example: The authors demonstrate the scheme with $p=37$, order $k=3$, and specific integer values for $D$ and $e$. They successfully encrypt the plaintext "NOBLE2022" into ciphertext blocks and recover the original message, verifying the mathematical correctness of the matrix operations and modular arithmetic.
• Complexity Reduction: The scheme claims to reduce time and space complexity for key transmission. Instead of transmitting an $n \times n$ matrix, only the pair $(\lambda, s)$ is exchanged.
• Security Analysis:
  • Discrete Logarithm: Recovering $\lambda$ from $s$ requires solving the discrete logarithm problem, which is computationally infeasible for large primes.
  • Key Space: The security against brute-force attacks depends on the size of the General Linear Group $|GL(\lambda)|$. The authors calculate that for $p=37$ and $\lambda=50$, the key space is approximately $3.105 \times 10^{3920}$, which is exponentially large.
  • Signature Independence: The analysis suggests that the signature $s$ does not compromise security even if known, as the security relies primarily on the difficulty of determining $\lambda$ and the vastness of the matrix space defined by $\lambda$.

Significance and Claims

The paper concludes that the proposed method offers a mathematically simple yet strong cryptographic framework for authorized parties while presenting a significant barrier to intruders. The significance lies in:

• Enlarged Key Space: The use of generalized Lucas matrices significantly expands the available key space compared to standard implementations.
• Efficiency: By reducing key transmission to a pair of numbers, the scheme improves efficiency in terms of bandwidth and storage.
• Robustness: The combination of the discrete logarithm problem (for key agreement) and the complexity of the matrix structure (for encryption) creates a multi-layered defense.

The authors assert that the method is "mathematically simple for the authorized party and tedious for an intruder," relying on the established difficulty of the discrete logarithm problem and the large combinatorial space of the generalized Lucas matrices.