Cryptanalysis of RGB, a mixed multivariate signature scheme
산업수학전략연구부

KyungAh Shim, CheolMin Park, Namhun Koo

Finite fields and their applications
45
(2017)
PublicKey Cryptography (PKC) based on multivariate quadratic equations is one of the most promising alternatives for classical PKC after the eventual coming of quantum computers. Recently, Shen and Tang proposed a new MQsignature scheme, RGB, based on three types of variables, Red(r), Green(g) and Blue(b). They claimed that signing for RGB is faster than that of UOV and Rainbow. At ACISP 2016, Tang et al. implemented RGB on S5PV210 and MT6582 microprocessors at 64, 80, 96, 118 and 128bit security levels for practical use. Their results are much more efficient than other MQsignature schemes, so RGB is very appealing for resourcelimited devices. We show that RGB with their suggested parameters at 64, 80, 96, 118 and 128 security levels are entirely broken by key recovery attacks using good keys. From a practical point of view, we are able to break their parameters at 64, 80, 96, 118 and 128 security levels in less than 0.48 seconds, 1.7 seconds, 90.68 seconds, 11 minutes and 6.82 hours, respectively. Consequently, we show that signing and the key sizes for RGB with secure parameter sets are much slower and larger than those of UOV and Rainbow.
 초록
PublicKey Cryptography (PKC) based on multivariate quadratic equations is one of the most promising alternatives for classical PKC after the eventual coming of quantum computers. Recently, Shen and Tang proposed a new MQsignature scheme, RGB, based on three types of variables, Red(r), Green(g) and Blue(b). They claimed that signing for RGB is faster than that of UOV and Rainbow. At ACISP 2016, Tang et al. implemented RGB on S5PV210 and MT6582 microprocessors at 64, 80, 96, 118 and 128bit security levels for practical use. Their results are much more efficient than other MQsignature schemes, so RGB is very appealing for resourcelimited devices. We show that RGB with their suggested parameters at 64, 80, 96, 118 and 128 security levels are entirely broken by key recovery attacks using good keys. From a practical point of view, we are able to break their parameters at 64, 80, 96, 118 and 128 security levels in less than 0.48 seconds, 1.7 seconds, 90.68 seconds, 11 minutes and 6.82 hours, respectively. Consequently, we show that signing and the key sizes for RGB with secure parameter sets are much slower and larger than those of UOV and Rainbow.
 초록
PublicKey Cryptography (PKC) based on multivariate quadratic equations is one of the most promising alternatives for classical PKC after the eventual coming of quantum computers. Recently, Shen and Tang proposed a new MQsignature scheme, RGB, based on three types of variables, Red(r), Green(g) and Blue(b). They claimed that signing for RGB is faster than that of UOV and Rainbow. At ACISP 2016, Tang et al. implemented RGB on S5PV210 and MT6582 microprocessors at 64, 80, 96, 118 and 128bit security levels for practical use. Their results are much more efficient than other MQsignature schemes, so RGB is very appealing for resourcelimited devices. We show that RGB with their suggested parameters at 64, 80, 96, 118 and 128 security levels are entirely broken by key recovery attacks using good keys. From a practical point of view, we are able to break their parameters at 64, 80, 96, 118 and 128 security levels in less than 0.48 seconds, 1.7 seconds, 90.68 seconds, 11 minutes and 6.82 hours, respectively. Consequently, we show that signing and the key sizes for RGB with secure parameter sets are much slower and larger than those of UOV and Rainbow.
More