Efficient cryptographic schemes provably as secure as subset sum
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 236-241
- https://doi.org/10.1109/sfcs.1989.63484
Abstract
Very efficient constructions, based on the intractability of the subset sum problem for certain dimensions, are shown for a pseudorandom generator and for a universal one-way hash function. (Pseudorandom generators can be used for private key encryption, and universal one-way hash functions for signature schemes). The increase in efficiency in the construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function. All the constructions can be implemented in NC using an optimal number of processors.Keywords
This publication has 17 references indexed in Scilit:
- Bit commitment using pseudorandomnessJournal of Cryptology, 1991
- Efficient, Perfect Random Number GeneratorsLecture Notes in Computer Science, 1990
- Universal one-way hash functions and their cryptographic applicationsPublished by Association for Computing Machinery (ACM) ,1989
- Cryptanalysis: a survey of recent resultsProceedings of the IEEE, 1988
- How to Construct Pseudorandom Permutations from Pseudorandom FunctionsSIAM Journal on Computing, 1988
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- How to construct random functionsJournal of the ACM, 1986
- Solving low-density subset sum problemsJournal of the ACM, 1985
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Hiding information and signatures in trapdoor knapsacksIEEE Transactions on Information Theory, 1978