In Advances in Cryptology -- Proceedings of CRYPTO '97
(August 17 -- 21, 1998, Santa Barbara, California, USA),
B. Kaliskik (Ed.),
vol. 1294 of
Lecture Notes in Computer Science,
Springer-Verlag.
Abstract:
Cryptosystems
based on the knapsack problem were among the first public key systems to be
invented and for a while were considered quite promising. Few knapsack-like
cryptosystems have withstood cryptanalysis, among which the Chor-Rivest
scheme and the Qu-Vanstone scheme. The Qu-Vanstone scheme is a public key
scheme based on group factorizations in the additive group of integers modulo
n that generalizes Merkle-Hellman cryptosystems. In this paper, we
present a novel use of lattice reduction, which is of independent interest,
exploiting in a systematic manner the notion of an orthogonal lattice. Using
the new technique, we successfully attack the Qu-Vanstone cryptosystem.