Division algorithms for the fixed weight subset sum problem

Publication date 12 January 2012

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Abstract: Given positive integers

a_{1}, ..., a_{n}, t

, the fixed weight subset sum problem is to find a subset of the

a_{i}

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

e l l

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 c d o t S^{l o g k} = O (n c h o o s e e l l)

(where the constant depends uniformly on

k

). In addition to using space efficiently, the algorithm is highly parallelizable.

This page was built for publication: Division algorithms for the fixed weight subset sum problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6230231)