And So Shamir Cracked Merkle’s Knapsack … But Along Came Naccache and Stern (and it’s uncracked!)
I recommend to any early career researcher that they find a new paper which is having a good impact to read, and also read a classic paper. For this week, my classic paper has been the Naccache Stern Knapsack cryptosystem for public key encryption, and it took me back to the time that Merkle and Hellman created a public key method which was eventually cracked by Adi Shamir. The crack left the field clear for the RSA method to become the de-facto public key method.
David Naccache and Jacques Stern
RSA has survived over four decades and is still going strong. But, there have been other methods for public key encryption that have not quite scaled the levels of RSA. And, so, in 1997, David Naccache and Jacques Stern produced a knapsack method for public key encryption, and which has still to be broken [1][here]:
Before we cover the Naccache-Stern Knapsack cryptosystem, we will first cover the method created by Ralph Merkle and Marty Hellman [2]:
