Paper 2011/145

Linear Diophantine Equation Discrete Log Problem, Matrix Decomposition Problem and the AA{\beta}-cryptosystem

M. R. K. Ariffin and N. A. Abu

Abstract

The Linear Diophantine Equation Discrete Log Problem (LDEDLP) is a discrete log problem on the linear Diophantine equation U=Vx+Wy. A proper implementation of LDEDLP would render an attacker to search for two private parameters amongst the exponentially many solutions. Embedded within the matrix decomposition problem (MDP) is the LDEDLP. The ability to re-produce the corresponding two square matrices from its product where both matrices are private and one of them is singular is related to solving the LDEDLP (albeit in a stronger setting when compared to the situation where certain parameters are known). Similar to the cryptographic schemes based on the Elliptic Curve Discrete Log Problem (ECDLP), cryptographic schemes based upon the LDEDLP has the potential to produce secure key exchange and asymmetric cryptographic schemes. The AA{\beta}-cryptosystem is one such cryptographic scheme. The AA{\beta}-cryptosystem transmits a two-parameter ciphertext and utilizes only the basic arithmetic operations of multiplication for encryption and decryption. Since the LDEDLP follows a simple mathematical structure, its low computational requirement would enable communication devices with low computing power to deploy secure communication procedures efficiently.

Note: Amendment due to feedback from reader (see eprint.iacr.org/2011/351.pdf)