Information Set Decoding with Soft Information and some cryptographic applications
The class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. Stern's algorithm is the origin of the most efficient algorithms in this class. In this paper we consider the same decoding problem but for a channel with soft information. We give a version of Stern's algorithm for a channel with soft