Abstract:
Cryptosystems based on the knapsack problem
were among the first public-key systems to be invented.
Their high encryption/decryption rate attracted considerable interest
until it was noticed that
the underlying knapsacks often had a low density,
which made them vulnerable to lattice attacks, both in theory and practice.
To prevent low-density attacks, several designers
found a subtle way to increase the density beyond the critical density
by decreasing the weight of the knapsack,
and possibly allowing non-binary coefficients.
This approach is actually a bit misleading:
we show that low-weight knapsacks
do not prevent efficient reductions to lattice problems like the shortest vector problem,
they even make reductions more likely.
To measure the resistance of low-weight knapsacks,
we introduce the novel notion of pseudo-density,
and we apply the new notion to the Okamoto-Tanaka-Uchiyama (OTU)
cryptosystem from Crypto '00.
We do not claim to break OTU and we actually
believe that this system may be secure with an appropriate
choice of the parameters. However, our research indicates that, in its current form, OTU
cannot be supported by an argument based on density. Our results also explain
why Schnorr and H\"orner were able to solve at Eurocrypt '95
certain high-density knapsacks related to the Chor-Rivest cryptosystem,
using lattice reduction.