Cryptanalysis of the Chor-Rivest cryptosystem

DOI10.1007/S001450010005MaRDI QIDQ5934141zbMATH OpenOpenAlexFDO

Authors Serge Vaudenay

Publication date 7 November 2001

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001450010005

zbMATH Keywords

Chor-Rivest cryptosystemfinite fieldsknapsack-based cryptosystemspartial key disclosure attacks

Mathematics Subject Classification ID

Cryptography (94A60)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1302850
• Cryptanalysis of the Sidelnikov Cryptosystem
• Cryptanalysis of the CLR-cryptosystem
• scientific article; zbMATH DE number 1394317
• scientific article; zbMATH DE number 1676629
• Cryptanalysis of Ciminion
• Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
• Cryptanalysis of Chaotic Ciphers
• Cryptanalysis of the Dickson-Scheme
• Cryptanalysis of the CFVZ cryptosystem

Cited in

(10)

• Preimage selective trapdoor function: how to repair an easy problem
• On the Chor-Rivest knapsack cryptosystem
• Low-density attack revisited
• A knapsack-based probabilistic encryption scheme
• Safer parameters for the Chor-Rivest cryptosystem
• New Definition of Density on Knapsack Cryptosystems
• scientific article; zbMATH DE number 1302850 (Why is no real title available?)
• scientific article; zbMATH DE number 6129866 (Why is no real title available?)
• Cryptanalysis of the CFVZ cryptosystem
• Quadratic compact knapsack public-key cryptosystem

This page was built for publication: Cryptanalysis of the Chor-Rivest cryptosystem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5934141)