# On the Hardness of Subset Sum Problem from Different Intervals

@article{Kogure2012OnTH, title={On the Hardness of Subset Sum Problem from Different Intervals}, author={Jun Kogure and Noboru Kunihiro and Hirosuke Yamamoto}, journal={IEICE Trans. Fundam. Electron. Commun. Comput. Sci.}, year={2012}, volume={95-A}, pages={903-908} }

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… Expand

#### 2 Citations

Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from Szemerédi-type statements

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2021

This paper introduced Szemerédi-type assumptions, which are the imitations of the statement of SzemerÉdi’s theorem on arithmetic progressions, and shows that the OTU scheme can be broken under some heuristic assumptions. Expand

Improvement on a Knapsack-Based Probabilistic Encryption Scheme

- Mathematics, Computer Science
- IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
- 2014

#### References

SHOWING 1-10 OF 14 REFERENCES

Solving low density subset sum problems

- Computer Science, Mathematics
- 24th Annual Symposium on Foundations of Computer Science (sfcs 1983)
- 1983

This method gives a polynomial time attack on knapsack public key cryptosystems that can be expected to break them if they transmit information at rates below dc (n), as n → ∞. Expand

Low-density attack revisited

- Materials Science, Mathematics
- Des. Codes Cryptogr.
- 2007

This paper improves the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension, and shows that the success probability of the attack can be higher than that of Coster et al. Expand

New Definition of Density on Knapsack Cryptosystems

- Mathematics, Computer Science
- AFRICACRYPT
- 2008

A new notion of density D is introduced, which naturally unifies the previous two densities, and conditions for the authors' density are derived so that a knapsack scheme is vulnerable to lattice attack. Expand

Improved low-density subset sum algorithms

- Mathematics, Computer Science
- computational complexity
- 2005

Two modifications of the Lagarias-Odlyzko algorithm, either one of which would solve almost all problems of density<0.9408 ... if it could find shortest non-zero vectors in lattices if they were combined with known lattice basis reduction algorithms. Expand

Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

- Computer Science, Mathematics
- EUROCRYPT
- 1995

Algorithms for lattice basis reduction that are improvements of the famous L3-algorithm are introduced that solve random subset sum problems of arbitrary density with 74 and 82 many weights and by breaking Damgard's hash function. Expand

Quantum Public-Key Cryptosystems

- Computer Science
- CRYPTO
- 2000

A concrete scheme for quantum public-key encryption scheme or quantum trapdoor one-way function, based on the computational assumption (over QPT machines) that a class of subset-sum problems is intractable against any QPT machine. Expand

Lattice basis reduction: Improved practical algorithms and solving subset sum problems

- Mathematics, Computer Science
- Math. Program.
- 1994

Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC1 + computer. Expand

A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields

- Mathematics, Computer Science
- CRYPTO
- 1984

A new knapsack type public key cryptosystem based on a novel application of arithmetic in finite fields, following a construction by Bose and Chowla, which can be made high enough to foil “low density” attacks against this system. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

Breaking Iterated Knapsacks

- Mathematics, Computer Science
- CRYPTO
- 1984

An outline of an attack that is used successfully to break iterated knapsacks is presented, although it is not provided that the attack almost always works. Expand