We propose a new, efficient nondeterministic decoding algorithm for square-free Goppa codes over Fpfor any prime p. If the code in question has degree t and the average distance to the closest codeword is at least (4/p)t + 1, the proposed decoder can uniquely correct up to (2/p)t errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching t errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.

This paper presents a batch version of the lattice-based identification scheme known as CLRS. Our version consists of a method for allowing a user to authenticate himself with different levels of clearance upon the choice of a subset of keys in his possession. It bears similarity with the Schnorr batch scheme, in the sense that the communication costs are kept constant, regardless of the number of keys involved. We use the hardness of a lattice problem, namely the Inhomogeneous Small Integer Solution problem (I-SIS), as security assumption.