2012/01/13 by Andrew Shallue, Shallue, Andrew
Computer Science · Engineering · Mathematics · #11T71 #Coding theory and cryptography #Combinatorics (math.CO) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #graph theory and CDMA systems #math.CO #msc:11T71
paper · pdf · doi:10.48550/arxiv.1201.2739
arxiv created 2012/01/13 · openalex publication_date 2012/01/13 · arxiv updated 2012/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given positive integers a1,..., an, t, the fixed weight subset sum problem is to find a subset of the ai that sum to t, where the subset has a prescribed number of elements. It is this problem that underlies the security of modern knapsack cryptosystems, and solving the problem results directly in a message attack. We present new exponential algorithms that do not rely on lattices, and hence will be applicable when lattice basis reduction algorithms fail. These algorithms rely on a generalization of the notion of splitting system given by Stinson. In particular, if the problem has length n and weight ℓ then for constant k a power of two less than n we apply a k-set birthday algorithm to the splitting system of the problem. This randomized algorithm has time and space complexity that satisfies T ⋅ S^logk = O(n \choose ℓ) (where the constant depends uniformly on k). In addition to using space efficiently, the algorithm is highly parallelizable.