On the Hardness of Subset Sum Problem from Different Intervals

Jun KOGURE  Noboru KUNIHIRO  Hirosuke YAMAMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.5   pp.903-908
Publication Date: 2012/05/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.903
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
subset sum problem,  knapsack problem,  low-density attack,  lattice reduction,  

Full Text: PDF(701.5KB)>>
Buy this Article



Summary: 
The subset sum problem, which is often called as the knapsack problem, is known as an NP-hard problem, and there are several cryptosystems based on the problem. Assuming an oracle for shortest vector problem of lattice, the low-density attack algorithm by Lagarias and Odlyzko and its variants solve the subset sum problem efficiently, when the “density” of the given problem is smaller than some threshold. When we define the density in the context of knapsack-type cryptosystems, weights are usually assumed to be chosen uniformly at random from the same interval. In this paper, we focus on general subset sum problems, where this assumption may not hold. We assume that weights are chosen from different intervals, and make analysis of the effect on the success probability of above algorithms both theoretically and experimentally. Possible application of our result in the context of knapsack cryptosystems is the security analysis when we reduce the data size of public keys.