A fast identification scheme
Pascal Véron · 2002
Many cryptographic protocols depend on one and only problem, the one of factoring. This paper presents a new identification scheme whose security depends on an NP-complete problem from the theory of error correcting codes: the syndrome decoding problem. The computation complexity of the proposed scheme is smaller than those of the other schemes based on SD problem. Moreover the amount of memory needed by the prover is very small.