<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>Merkle-Hellman public key cryptosystem is a long-age old algorithm used in cryptography. Despite being computationally fast, for very large input sizes it may operate slower due to thread creation overhead or reaching a deadlock situation. In this paper, we discuss the working principles of the Traditional Merkle-Hellman knapsack cryptosystem, which is an Easy knapsack. The challenges of Hard Knapsack and how it overcomes the shortcomings of the Traditional Easy Knapsack, are also discussed. The Hard knapsack variant of Merkle-Hellman is solved first using plain recursion and then improvised using a dynamic programming approach to the problem. Parallelism and Concurrency has been achieved on the dynamic programming implementation using OpenMP API which further has enhanced the performance time. A comparative study of both variants of Hard Knapsack for messages of different lengths has shown that the latter is faster.</p>
</abstract>

Merkle-Hellman public key cryptosystem is a long-age old algorithm used in cryptography. Despite being computationally fast, for very large input sizes it may operate slower due to thread creation overhead or reaching a deadlock situation. In this paper, we discuss the working principles of the Traditional Merkle-Hellman knapsack cryptosystem, which is an Easy knapsack. The challenges of Hard Knapsack and how it overcomes the shortcomings of the Traditional Easy Knapsack, are also discussed. The Hard knapsack variant of Merkle-Hellman is solved first using plain recursion and then improvised using a dynamic programming approach to the problem. Parallelism and Concurrency has been achieved on the dynamic programming implementation using OpenMP API which further has enhanced the performance time. A comparative study of both variants of Hard Knapsack for messages of different lengths has shown that the latter is faster.

A Recursive and Parallelized Dynamic Programming Implementation of Hard Merkle-Hellman Knapsack System for Public Key Cryptography

Cybernetics and Information Technologies

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Merkle-Hellman public key cryptosystem is a long-age old algorithm used in cryptography. Despite being computationally fast, for very large input sizes it may...

A Recursive and Parallelized Dynamic Programming Implementation of Hard Merkle-Hellman Knapsack System for Public Key Cryptography

Published Online: Jul 01, 2021

Page range: 58 - 69

Received: Dec 29, 2020

Accepted: Mar 30, 2021

DOI: https://doi.org/10.2478/cait-2021-0019

Keywords
Merkle-Hellman public key cryptosystem, Easy knapsack, Hard knapsack, recursion, dynamic programming, parallelism, OpenMP API

© 2021 Vaddadi Sai Rahul et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

A Recursive and Parallelized Dynamic Programming Implementation of Hard Merkle-Hellman Knapsack System for Public Key Cryptography

Published Online: Jul 01, 2021

Page range: 58 - 69

Received: Dec 29, 2020

Accepted: Mar 30, 2021

DOI: https://doi.org/10.2478/cait-2021-0019

KeywordsMerkle-Hellman public key cryptosystem, Easy knapsack, Hard knapsack, recursion, dynamic programming, parallelism, OpenMP API

© 2021 Vaddadi Sai Rahul et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Keywords
Merkle-Hellman public key cryptosystem, Easy knapsack, Hard knapsack, recursion, dynamic programming, parallelism, OpenMP API