Cryptology ePrint Archive: Report 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.

Category / Keywords: linear diophantine equation, linear diophantine equation discrete log problem (LDEDLP), discrete log problem (DLP), matrix decomposition problem (MDP), asymmetric cryptography, secure key exchange, passive adversary attack

Publication Info: To be submitted to Journal of Mathematical Cryptology

Date: received 22 Mar 2011, last revised 13 Jul 2011, withdrawn 14 Aug 2011

Contact author: rezal at math upm edu my

Available format(s): (-- withdrawn --)

Note: Amendment due to feedback from reader (see

Version: 20110815:034022 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]