Paper 2013/771

TOT, a Fast Multivariate Public Key Cryptosystem with Basic Secure Trapdoor

Wuqiang Shen and Shaohua Tang

Abstract

In this paper, we design a novel one-way trapdoor function, and then propose a new multivariate public key cryptosystem called $\mathrm{T}\mathrm{O}\mathrm{T}$, which can be used for encryption, signature and authentication. Through analysis, we declare that $\mathrm{T}\mathrm{O}\mathrm{T}$ is secure, because it can resist current known algebraic attacks if its parameters are properly chosen. Some practical implementations for $\mathrm{T}\mathrm{O}\mathrm{T}$ are also given, and whose security level is at least $2^{90}$. The comparison shows that $\mathrm{T}\mathrm{O}\mathrm{T}$ is more secure than $\mathrm{H}\mathrm{F}\mathrm{E}$, $\mathrm{H}\mathrm{F}\mathrm{E}\mathrm{v}$ and $\mathrm{Q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{z}$ (when $n\ge 81$ and $D_{HFE}\ge 129$, $\mathrm{H}\mathrm{F}\mathrm{E}$ is still secure), and it can reach almost the same speed of computing the secret map by ${\mathrm{C}}^{\ast }$ and $\mathrm{S}\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{s}{\mathrm{h}}^{\mathrm{v}2}$ (even though ${\mathrm{C}}^{\ast }$ was broken, its high speed has been affirmed).