### Security Analysis Against "A New Encryption Scheme for Multivariate Quadratic Systems"

Yasuhiko Ikematsu and Shuhei Nakamura

##### Abstract

A Gr¥"{o}bner basis algorithm computes a good basis for an ideal of a polynomial ring and appears in various situations of cryptography. In particular, it has been used in the security analysis of multivariate public key cryptography (MPKC), and has been studied for a long time; however, it is far from a complete understanding. We consider the algebraic attack using a Gr¥"{o}bner basis algorithm for a new multivariate encryption scheme proposed by Jiahui Chen et al. at Theoretical Computer Science 2020. Their idea to construct a new scheme was to use the minus and plus modifiers to prevent known attacks, such as linearization attack. Moreover, they discussed to have a resistance to the algebraic attack using a Gr¥"{o}bner basis algorithm. However, in our experiments, the algebraic attack breaks their claimed 80- and 128-bit security parameters in reasonable times. It is necessary to understand whether their scheme can avoid such an attack by introducing a slight modification. In this paper, we theoretically describe why the algebraic attack breaks their scheme and give a precise complexity of the algebraic attack. As a result, we demonstrate that the algebraic attack can break the claimed 80- and 128-bit security parameters in the complexities of approximately 25 and 32 bits, respectively. Moreover, based on our complexity estimation of the algebraic attack, we conclude that Chen et al.'s scheme is not practical.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Multivariate Public-Key Cryptography
Contact author(s)
ikematsu @ imi kyushu-u ac jp
History
2020-11-26: revised
See all versions
Short URL
https://ia.cr/2020/053

CC BY

BibTeX

@misc{cryptoeprint:2020/053,
author = {Yasuhiko Ikematsu and Shuhei Nakamura},
title = {Security Analysis Against  "A New Encryption Scheme for Multivariate Quadratic Systems"},
howpublished = {Cryptology ePrint Archive, Paper 2020/053},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/053}},
url = {https://eprint.iacr.org/2020/053}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.