Birthday type attacks to the Naccache-Stern knapsack cryptosystem

We present a (probabilistic) birthday type attack to Naccache-Stern knapsack cryptosystem. We provide the space and time complexity of this attack alongside with the success probability. Furthermore, we applied successfully the attack for messages of low or large Hamming weight.