Research Commons
      • Browse 
        • Communities & Collections
        • Titles
        • Authors
        • By Issue Date
        • Subjects
        • Types
        • Series
      • Help 
        • About
        • Collection Policy
        • OA Mandate Guidelines
        • Guidelines FAQ
        • Contact Us
      • My Account 
        • Sign In
        • Register
      View Item 
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computer Science Working Paper Series
      • 1995 Working Papers
      • View Item
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computer Science Working Paper Series
      • 1995 Working Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      The subset sum problem and arithmetic coding

      Irvine, Sean A.; Cleary, John G.; Rinsma-Melchert, Ingrid
      Thumbnail
      Files
      uow-cs-wp-1995-07.pdf
      1.608Mb
      Find in your library  
      Citation
      Export citation
      Irvine, 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-03
      Type
      Working Paper
      Series
      Computer Science Working Papers
      Report No.
      95/7
      Publisher
      University of Waikato, Department of Computer Science
      Collections
      • 1995 Working Papers [32]
      Show full item record  

      Usage

      Downloads, last 12 months
      72
       
       

      Usage Statistics

      For this itemFor all of Research Commons

      The University of Waikato - Te Whare Wānanga o WaikatoFeedback and RequestsCopyright and Legal Statement