Cryptanalysis of the Chor-Rivest cryptosystem (Q5934141)

The Chor-Rivest cryptosystem was known to be the only knapsack-based public-key cryptosystem that remained unbroken. In the paper, a new attack is presented which breaks the system for all its suggested parameters. The author begins with brief review of the Chor-Rivest system and a short overview of previous work on attacks on subset-sum-based cryptosystems. After outlining lower bounds on the number of equivalent secret keys and some useful properties of the system, the author then presents some attacks that make use of the fact that some part of the secret key is disclosed. By further improvements and generalizations it is then shown how one can attack the Chor-Rivest cryptosystem for all its suggested parameters.