EFFICIENT CRYPTOGRAPHIC SCHEMES PROVABLY AS SECURE AS SUBSET SUM

We show very efficient constructions for a pseudorandom generator and for a universal one-way hash function based on the intractability of t he subset-sum problem for certain dimensions. (Pseudorandom generators can be used for private-key encryption and universal one-way hash fun ctions for signature schemes.) The increase in efficiency in our const ruction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function. All of our construct ions can be implemented in NC using an optimal number of processors.