Defeating Linearization Attacks with Min-Plus-Modulo Digital Signature
S. J. Chavhan *
Department of Mathematics, Shri Vyankatesh Arts, Commerce and Science College, Deulgaon Raja, Buldhana, 443204, Maharashtra, India.
S. R. Chaudhari
Department of Mathematics, Kavayatri Bahinabai Chaudhari North Maharashtra Unversity, Jalgaon, Jalgaon, 425001, Maharashtra, India.
*Author to whom correspondence should be addressed.
Abstract
A novel digital signature method called Min-Plus-Modulo (MPM) uses tropical algebra and modular reduction to make cryptographic security better against linearisation attacks. The Min-Plus-Modulo method uses polynomial operations, such as coefficientwise minima and modular additions, to create and check signatures for messages that are polynomials. We look at how well the MPM technique works for different polynomial degrees in terms of speed and signature size. Our results show that the polynomial degree quadratically scales signing and verification activities, although the sizes of the signatures stay small. When security parameters d=100, 150, and 200 are used, the technique works well on standard hardware, with verification times of less than 5 seconds and signature sizes of about 12-25 kB. Modular reduction makes systems more resistant to attacks like Brown-Monico linearisation without needing more processing or storage space than standard tropical signature systems. The MPM scheme is a promising post-quantum solution that combines small signatures, security, and speed.
Keywords: Tropical cryptography, min-plus modulo algebra, polynomial semirings, digital signatures, np-hard problems, hash-to-polynomial conversion