No label defined (Q3689090)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3912270
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3912270

      Statements

      1984
      0 references
      cryptography
      0 references
      knapsack public-key cryptosystem
      0 references
      Algorithm S
      0 references
      The basic knapsack public-key cryptosystem was presented by \textit{R. C. Merkle} and \textit{M. E. Hellman} [IEEE Trans. Inf. Theory 24, 525--530 (1978; Zbl 1487.94132)]. In this paper, a variant of a Shamir's attack [\textit{A. Shamir}, ibid. 30, 699--704 (1984; Zbl 0552.94007)] on the basic Merkle-Hellman knapsack cryptosystem, Algorithm S, is given. A performance analysis of Algorithm S is presented. The main result is: Let \(R\) be the information rate and \(n\) be the block size of a plain text, then for any fixed \(R\), Algorithm S runs to completion in time polynomial in \(n\) on all knapsacks with rate \(R'\geq R\), and it successfully breaks at least the fraction \(1-c/n\) of such knapsack cryptosystems as \(n\to \infty\), where \(c\) is a constant depending on \(R\). [For the entire collection see Zbl 0543.00014.]
      0 references

      Identifiers