Following the cryptanalyses of the encryption scheme HFE and of the signature scheme SFLASH, no serious alternative multivariate cryptosystems remained, except maybe the signature schemes UOV and HFE~(--). Recently, two proposals have been made to build highly efficient multivariate cryptosystems around a quadratic internal transformation: the first one is a signature scheme called square-vinegar and the second one is an encryption scheme called square introduced at CT-RSA 2009. In this paper, we present a total break of both the square-vinegar signature scheme and the square encryption scheme. For the practical parameters proposed by the authors of these cryptosystems, the complexity of our attacks is about 2~(35) operations. All the steps of the attack have been implemented in the Magma computer algebra system and allowed to experimentally assess the results presented in this paper.
展开▼
