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 the subset-sum problem for certain dimensions. (Pseudorandom generators can be used for private-key encryption and universal one-way hash functions for signature schemes.) The increase in efficiency in our construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function.All of our constructions can be implemented in NC using an optimal number of processors.Part of this work was done while both authors were at the University of California at Berkeley and part when the second author was at the IBM Almaden Research Center. Research supported by NSF Grant CCR 88-13632. A preliminary version of this paper appeared in Proc. 30th Symposium on Foundations of Computer Science, 1989.Incumbent of the Morris and Rose Goldman Career Development Chair. Research supported by an Alon Fellowship and a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences.