A discrete logarithm implementation of perfect zero-knowledge blobs

Brassard and Crépeau [BCr] introduced a simple technique for producing zero-knowledge proof systems based on blobs. As is to be expected, their implementation rests on an unproven cryptographic assumption, specifically, that it is easy to generate numbers that are difficult to factor. In this paper we present an implementation of blobs based on a different cryptographic assumption, specifically, that it is easy to generate primes p over which it is difficult to compute discrete logarithms. If, in addition, we can produce a generator for Z _p ^* , this implementation then has the advantage that it leads to proof systems which are perfect zeroknowledge, rather than only almost perfect zero-knowledge.The relationship between factoring and finding discrete logarithms is not well understood, although Bach [Bac1] is an important contribution. Given our current state of number theoretic knowlege, there is no reason to prefer the cryptographic assumption required by one of these implementations over that required by the other. In any event, we introduce the notion of a product blob, whose favorable properties depend only on at least one of these assumptions holding.The first author was supported in part by NSA Grant MDA 904-84-H-00171. The second author was supported in part by NSF Grant DCR-8602562.