whose security depends mainly on the hardness of the subset sum problem.
Many of knapsack schemes were broken by low-density attacks,
which are attack methods to use the situation
that a shortest vector or a closest vector in a lattice corresponds to a solution of
the subset sum problem.
For the case when the Hamming weight of a solution for a random instance of the subset sum problem is arbitrary,
if the density is less than 0.9408,
then the instance can be solvable almost surely
by a single call of lattice oracle.
This fact was theoretically shown by Coster et al.
In Crypto 2000, Okamoto, Tanaka and Uchiyama
introduced the concept of quantum public key cryptosystems
and proposed a knapsack cryptosystem, so-called OTU scheme.
However, no known algorithm breaks the OTU scheme.
In this paper, we introduce some combinatorial statements to describe necessary condition for the failure of low density attacks.
More precisely, we give better heuristics
than Gaussian heuristics for minimum norms of orthogonal lattices.
Consequently, we show that the OTU scheme can be broken under these heuristics.