The knapsack hash function proposed at Crypto’89 can be broken. (English) Zbl 0789.68046

Advances in Cryptology, Proc. Workshop, EUROCRYPT ’91, Brighton/UK 1991, Lect. Notes Comput. Sci. 547, 39-53 (1991).
Summary: [For the entire collection see Zbl 0756.00008.]
I. B. Damgård [Lect. Notes Comput. Sci. 435, 416–427 (1990; Zbl 0724.68029)] suggested at Crypto 1989 concrete examples of hash functions among which a knapsack scheme. We will show that a probabilistic algorithm can break this scheme with a number in the region of \(2^{32}\) computations. That number of operations is feasible in realistic time with modern computers. Thus the proposed hash function is not very secure. Among those computations as substantial number can be performed once for all. A faster result can be obtained since parallelism is easy. Moreover, ways to extend the present algorithm to other knapsacks than the present \((256, 128)\) suggested by Damgård are investigated.


94A60 Cryptography
68W20 Randomized algorithms
Full Text: DOI