In Advances in Cryptology -- Proceedings of CRYPTO '99
(August 15 -- 19, 1999, Santa Barbara, California),
M. Wiener (Ed.),
vol. 1666 of
Lecture Notes in Computer Science,
Springer-Verlag.
Abstract:
At Eurocrypt'98, Boyko, Peinado and Venkatesan presented
simple and very fast methods for generating
randomly distributed pairs of the form $(x,g^x \mod p)$ using precomputation.
The security of these methods relied on the potential hardness of a new problem,
the so-called hidden subset sum problem.
Surprisingly, apart from exhaustive search,
no algorithm to solve this problem was known.
In this paper, we exhibit a security
criterion for the hidden subset sum problem,
and discuss its implications on the practicability
of the precomputation schemes.
Our results are twofold. On the one hand,
we present an efficient lattice-based attack
which is expected to succeed if and only if the parameters satisfy
a particular condition that we make explicit. Experiments have validated the theoretical analysis,
and show the limitations of the precomputation methods.
For instance, any realistic smart-card implementation
of Schnorr's identification scheme using these precomputations methods
is either vulnerable to the attack, or less efficient than with traditional precomputation methods.
On the other hand, we show that, when another condition is satisfied,
the pseudo-random generator based on the hidden subset sum problem is strong
in some precise sense which includes attacks {\em via} lattice reduction.
Namely, using the discrete Fourier transform,
we prove that the distribution of the generator's output
is indistinguishable from the uniform distribution.
The two conditions complement each other quite well,
and therefore form a convincing picture of the security level.