SD at the FS96 parameters ⇒ PRG
Statement
If syndrome decoding is hard at the FS96 parameters , there is a PRG as secure as syndrome decoding at those parameters, each application of which yields a linear number of output bits in quadratic time — FS96.
Notes
- A generator mapping a seed , with of weight encoded in bits, to stretches only if , below the Gilbert–Varshamov bound, where, except with probability at most over , is the unique weight- preimage of — standard.