SD at the FS96 parameters ⇒ PRG

Standard model · FS96

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.