<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

Pubblicato online: 01 lug 2021

Pagine: 58 - 69

Ricevuto: 29 dic 2020

Accettato: 30 mar 2021

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

Parole chiave
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

Pubblicato online: 01 lug 2021

Pagine: 58 - 69

Ricevuto: 29 dic 2020

Accettato: 30 mar 2021

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

Parole chiaveMerkle-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.

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