Provably-Secure Identification Scheme based on Braid Group
Zeen Kim, Kwangjo Kim · Scandinavian Conference on Information Systems · 2004
In this paper we construct a new interactive identiflcation scheme based on the conjugacy problem. We prove that this scheme is secure against passive attacks if the matching triple search problem (MTSP) is intractable. Our proof is based on the fact that the conjugacy search problem (CSP) is hard in braid group, on the other hand, the conjugacy decision problem (CDP) is easy in braid group by Ko et al.'s algorithm.