×

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.

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