[ Changed 4th March 1997 ]
We build an original cryptographic toolbox based on error-correcting codes. Having studied the difficulty of the syndrome decoding problem, we define a one-way function and a general setting for its use. Our results allow us to prove the security of Stern's authentication protocol SD; we also construct a provably secure pseudo-random generator and a very efficient and versatile keyed one-way function. These algorithms are used to provide end-to-end security for an analog pay-tv system using smart cards, similar to VideoCrypt.