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)

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. To be submitted to Journal of Mathematical Cryptology
Keywords
linear diophantine equationdiscrete log problem (DLP)matrix decomposition problem (MDP)asymmetric cryptographysecure key exchangepassive adversary attack
Contact author(s)
rezal @ math upm edu my
History
2011-08-15: withdrawn
2011-03-27: received
See all versions
Short URL
https://ia.cr/2011/145
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.