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
0.8634119629859924
0 references
0.8535424470901489
0 references
0.8415549397468567
0 references
0.8394551277160645
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