Empirical exploration of lattice attacks for building secure knapsack cryptosystems

Pending the possible realization of quantum computers, the RSA algorithm face critical challenges because of weaknesses under quantum cryptanalysis. A possible replacement may be knapsack cryptosystems, which do not yield any weaknesses to quantum computation. At present, the most significant challenge against knapsack cryptosystems is lattice attack, and public key density has historically been used to measure the security of knapsack cryptosystems against it. In this paper, we demonstrate the compromise of an acceptably dense knapsack cryptosystem using lattice attack. In order to quantify the security of knapsack cryptosystems under lattice attacks, we design experiments to analyze possible affecting factors. We demonstrate that it is not appropriate to assess the security of a knapsack cryptosystem by only considering density. Instead, there exist some other factors in literature which have more significance than density. Building on these results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving knapsack cryptosystems.