zbMATH — the first resource for mathematics

An efficient pseudo-random generator provably as secure as syndrome decoding. (English) Zbl 1304.94056
Maurer, Ueli (ed.), Advances in cryptology – EUROCRYPT ’96. International conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12-16, 1996. Proceedings. Berlin: Springer (ISBN 3-540-61186-X). Lect. Notes Comput. Sci. 1070, 245-255 (1996).
Summary: We show a simple and efficient construction of a pseudo-random generator based on the intractability of an NP-complete problem from the area of error-correcting codes. The generator is proved as secure as a hard instance of the syndrome decoding problem. Each application of the scheme generates a linear amount of bits in only quadratic computing time.
For the entire collection see [Zbl 0847.00051].

94A60 Cryptography
Full Text: DOI