The subset sum problem and arithmetic coding
Citation
Export citationIrvine, S. A., Cleary, J. G. & Rinsma-Melchert, I. (1995). The subset sum problem and arithmetic coding. (Working paper 95/7). Hamilton, New Zealand: University of Waikato, Department of Computer Science.
Permanent Research Commons link: https://hdl.handle.net/10289/1085
Abstract
The security offered by symmetric cryptosystems based on the arithmetic coding algorithm is examined. It is shown that this can be reduced naturally to the subset sum problem. The subset sum problem is NP-complete, however, the cases which arise in practical cryptosystems based on this problem tend to be solvable in polynomial time because the sums formed are either superincreasing or of low density. Our attack is therefore similar to attacks on public-key cryptosystems based on the subset sum problem (knapsack systems).
Date
1995-03Type
Report No.
95/7
Publisher
University of Waikato, Department of Computer Science
Collections
- 1995 Working Papers [32]