Skip to main content
placeholder image

Lattice reduction for modular knapsack

Journal Article


Download full-text (Open Access)

Abstract


  • In this paper, we present a new methodology to adapt any kind of lattice reduction algorithms to deal with the modular knapsack problem. In general, the modular knapsack problem can be solved using a lattice reduction algorithm, when its density is low. The complexity of lattice reduction algorithms to solve those problems is upper-bounded in the function of the lattice dimension and the maximum norm of the input basis. In the case of a low density modular knapsack-type basis, the weight of maximum norm is mainly from its first column. Therefore, by distributing the weight into multiple columns, we are able to reduce the maximum norm of the input basis. Consequently, the upper bound of the time complexity is reduced.

    To show the advantage of our methodology, we apply our idea over the floating-point LLL (L2) algorithm. We bring the complexity from O(d 3 + ε β 2 + d 4 + ε β) to O(d 2 + ε β 2 + d 4 + ε β) for ε < 1 for the low density knapsack problem, assuming a uniform distribution, where d is the dimension of the lattice, β is the bit length of the maximum norm of knapsack-type basis.

    We also provide some techniques when dealing with a principal ideal lattice basis, which can be seen as a special case of a low density modular knapsack-type basis.

Publication Date


  • 2013

Citation


  • Plantard, T., Susilo, W. & Zhang, Z. (2013). Lattice reduction for modular knapsack. Lecture Notes in Computer Science, 7707 275-286. Windsor, ON Lattice reduction for modular knapsack

Scopus Eid


  • 2-s2.0-84872588075

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=3552&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/2543

Number Of Pages


  • 11

Start Page


  • 275

End Page


  • 286

Volume


  • 7707

Abstract


  • In this paper, we present a new methodology to adapt any kind of lattice reduction algorithms to deal with the modular knapsack problem. In general, the modular knapsack problem can be solved using a lattice reduction algorithm, when its density is low. The complexity of lattice reduction algorithms to solve those problems is upper-bounded in the function of the lattice dimension and the maximum norm of the input basis. In the case of a low density modular knapsack-type basis, the weight of maximum norm is mainly from its first column. Therefore, by distributing the weight into multiple columns, we are able to reduce the maximum norm of the input basis. Consequently, the upper bound of the time complexity is reduced.

    To show the advantage of our methodology, we apply our idea over the floating-point LLL (L2) algorithm. We bring the complexity from O(d 3 + ε β 2 + d 4 + ε β) to O(d 2 + ε β 2 + d 4 + ε β) for ε < 1 for the low density knapsack problem, assuming a uniform distribution, where d is the dimension of the lattice, β is the bit length of the maximum norm of knapsack-type basis.

    We also provide some techniques when dealing with a principal ideal lattice basis, which can be seen as a special case of a low density modular knapsack-type basis.

Publication Date


  • 2013

Citation


  • Plantard, T., Susilo, W. & Zhang, Z. (2013). Lattice reduction for modular knapsack. Lecture Notes in Computer Science, 7707 275-286. Windsor, ON Lattice reduction for modular knapsack

Scopus Eid


  • 2-s2.0-84872588075

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=3552&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/2543

Number Of Pages


  • 11

Start Page


  • 275

End Page


  • 286

Volume


  • 7707