Evolution of Knapsack Ciphersystems

Abstract

The knapsack problem is known to be used in numerous public key ciphersystems designs. These ciphersystems have been receiving increased attention from analytics, resulting in many being compromised. Therefore, modern systems incorporate new algorithms making them at least partially immune to known attacks. In this paper, three types of knapsack ciphersystems are introduced. The difference between types is how the keys are generated and used. Classical systems, being the first type, use superincreasing sequences and low-density knapsacks and are therefore vulnerable. Modern cryptosystems are based on high-density knapsacks. That makes them difficult to analyze. Hybrid cryptosystems incorporate several security mechanisms (not only trapdoor knapsacks) that makes analysis, as well as implementation, even more complicated.

Keywords

• knapsack problem
• knapsack ciphersystems