zbMATH — the first resource for mathematics

Efficient cryptographic schemes provably as secure as subset sum. (English) Zbl 0862.94015
Summary: 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.

94A60 Cryptography
65C10 Random number generation in numerical analysis
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
Full Text: DOI