Cryptanalysis of Merkle-Hellman cipher using parallel genetic algorithm
This work addresses cryptanalysis for security applications, but it is incremental as it applies an existing metaheuristic to a known cipher.
The paper tackled the problem of breaking the Merkle-Hellman cipher by proposing a Parallel Genetic Algorithm to explore its large search space, achieving performance comparable to the LLL algorithm in experimental comparisons.
In 1976, Whitfield Diffie and Martin Hellman introduced the public key cryptography or asymmetric cryptography standards. Two years later, an asymmetric cryptosystem was published by Ralph Merkle and Martin Hellman called MH, based on a variant of knapsack problem known as the subset-sum problem which is proven to be NP-hard. Furthermore, over the last four decades, Metaheuristics have achieved a remarkable progress in solving NP-hard optimization problems. However, the conception of these methods raises several challenges, mainly the adaptation and the parameters setting. In this paper, we propose a Parallel Genetic Algorithm (PGA) adapted to explore effectively the search space of considerable size in order to break the MH cipher. Experimental study is included, showing the performance of the proposed attacking scheme and finally concluding with a comparison with the LLL algorithm attack.