A knapsack-type public key cryptosystem based on arithmetic in finite fields. (English) Zbl 0664.94011

Chor, Benny; Rivest, Ronald L.

IEEE Trans. Inf. Theory 34, No. 5, Part I, 901-909 (1989).

A new knapsack-type public key cryptosystem is introduced. The system is based on a novel application of arithmetic in finite fields, following a construction by R. C. Bose and S. Chowla [Comment. Math. Helvet. 37, 141-147 (1962)]. By appropriately choosing the parameters, one can control the density of the resulting knapsack, which is the ratio between the number of elements in the knapsack and their size in bits. In particular, the density can be made high enough to foil “low-density” attacks against our system. At the moment, no attacks capable of “breaking” this system in a reasonable amount of time are known.

MSC:

94A60

Cryptography

Keywords:

attacks