A fast identification scheme

摘要

Many cryptographic protocols depend on one and only problem, theone of factoring. This paper presents a new identification scheme whosesecurity depends on an NP-complete problem from the theory of errorcorrecting codes: the syndrome decoding problem. The computationcomplexity of the proposed scheme is smaller than those of the otherschemes based on SD problem. Moreover the amount of memory needed by theprover is very small