5\XN\X0DWK-  

VULNERABILITY OF
DIENE-THABET-YUSUF’S CUBIC
MULTIVARIATE SIGNATURE SCHEME ∗Yasufumi Hashimoto

Abstract
In 2020, Diene, Thabet and Yusuf proposed a new multivariate signaturescheme whose public key is a set of multivariate “cubic” polynomials overa finite field. In the present paper, we show how to recover its equivalentsecret key.
Keywords. multivariate public-key cryptosystems, cubic polynomials

1Introduction

A multivariate public key cryptosystem is a cryptosystem whose public key is a setof multivariate non-linear polynomials over a finite field, and has been considered
to be a candidate of post-quantum cryptography. In fact, in NIST’s standardization project of post-quantum cryptography, Rainbow [3] and GeMSS [2] wereselected as a finalist and an alternative candidate respectively in the final (third)
round [12].
Most multivariate public key cryptosystems, including these two signatureschemes, are constructed by quadratic polynomials. One of the reasons why there
have been few schemes with (over) cubic polynomials is that the number of coefficients in cubic polynomials is much more than that in quadratic polynomials
and then the key size is much larger. While there might be a cubic type scheme
which is secure enough to compensate for the disadvantage in efficiency, we do
not have such schemes at the present time (see e.g. [9, 4, 10, 1, 11, 6, 7]). Recently, Diene-Thabet-Yusuf [5] proposed a multivariate signature scheme using
cubic polynomials, whose signature generations are fast enough. However, such astructure for speeding up the signature generation has yielded a vulnerability. In
the present paper, we show that how to recover its equivalent secret key of thissignature scheme efficiently.

∗ Received November 30, 2021.

Ƚ!2!Ƚ

2

Diene-Thabet-Yusuf ’s signature scheme

We first describe the construction of Diene-Thabet-Yusuf’s signature scheme [5].
Let q be a power of prime, Fq a finite field of order q and r, m, n ≥ 1 integers
with m := r2 , n := 2r2 = 2m. Denote by k1 (x), . . . , kn (x) linear polynomials of
x = t(x1 , . . . , xn ) and put
k1 (x) · km+1 (x) kr+1 (x) · km+r+1 (x) · · · km−r+1 (x) · kn−r+1 (x)k2 (x) · km+2 (x) kr+2 (x) · km+r+2 (x) · · · km−r+2 (x) · kn−r+2 (x)
P = P (x) := 
.
..
..
..
..

.
.
.
.
kr (x) · km+r (x)k2r (x) · km+2r (x)···km (x) · kn (x)Generate an r × r matrix M = M (x) whose entries are (constants or) linear polynomials of x such that the entries of M −1 are also (constants or) linear polynomialstof x. Define the cubic polynomial map G : Fnq → Fmq , G(x) = (g1 (x), . . . , gm (x))
by
g1 (x) · · · gm−r+1 (x)
 ..
..
..
 = M (x) · P (x).
 .
.
.
gr (x)···

gm (x)

Diene-Thabet-Yusuf’s signature scheme is as follows [5]ɽmSecret key: Two invertible affine maps S : Fnq → Fnq , T : Fm
q → Fq andpolynomial matrices P, M .
Public key: The cubic polynomial map
F := T ◦ G ◦ S : Fnq → Fmq .
Signature generation: For a message m ∈ Fm
q , compute y = (y1 , . . . , ym ) :=T −1 (m). Next choose u1 , . . . , um ∈ Fq randomly and find x ∈ Fnq satisfying
y1−1  ..
M (x) ·  .
yr···
..
.
···

 
ym−r+1
u1 · k1 (x)
 ..
..
=
.
.
ym

ur · kr (x)(km+1 (x), . . . , k2m (x)) = (u1 , . . . , um ).

···
..
.
···

um−r+1 · km−r+1 (x)..
,.
um · km (x)The signature for the message m is s = S −1 (x).
Signature verification: Verify whether F (s) = m holds.
Since M is generated such that the entries of M (x)−1 are (constants or) linear
polynomials, the signature generation requires only solving a system of n linear
equations of n variables. The complexity of the signature generation is thus O(n3 ).

3Key recovery attack on DTY signature scheme

We now propose our key recovery attack on Diene-Thabet-Yusuf’s signature scheme.

Ƚ!3!Ƚ

Let K : Fnq → Fnq be the linear map with K(x) = (k1 (x), . . . , kn (x)),
P̃ : Fnq → Fm
q the quadratic polynomial map withP̃ (x) = t(p1 (x), . . . , pm (x)) := t(x1 · xm+1 , . . . , xm · xn )and M̃ (x) :='M (x)..

(. It is easy to see that.
M (x)G(x) = M̃ (x)P̃ (K(x)),
and then
F (x) = (T M̃ (x))P̃ ((K(S(x))).
Since T, K, S are affine maps and the entries of M̃ −1 are (constants or) linear polynomials of x, there exist an m × m matrix L = L(x) whose entries are (constantsor) linear polynomials and quadratic polynomials h1 (x), . . . , hm (x) such that
L(x)F (x) = t(h1 (x), . . . , hm (x)).
We can easily check that one can find such an L in polynomial time and thequadratic polynomials h1 (x), . . . , hm (x) are linear sums of p1 ((K(S(x))), . . . ,pm ((K(S(x))). Then the coefficient matrices of h1 (x), . . . , hm (x) are in the forms*)0m ∗t(KS).
(KS)∗0mThis means that the polynomials h1 (x), . . . , hm (x) are the balanced oil-vinegar
type and then that Kipnis-Shamir’s attack on the (balanced) oil-vinegar signaturescheme [13, 8, 9] is available for (h1 (x), . . . , hm (x)). We can recover a linear map
S1 : Fnq → Fnq satisfying(KS)S1 =)

∗m0∗
∗m

*

in polynomial time. It is easy to see that the quadratic polynomials in L(x)F (S1 (x))
are in the forms*)
0m ∗tx + (linear polynomial of x).
x∗∗mThis is equivalent to the polynomials in the balanced oil-vinegar signature scheme[13]. We thus conclude that the attacker can generate dummy signatures forarbitrary messages feasibly and this signature scheme is not secure at all.

Acknowledgments.

The author was supported by JST CREST no. JPMJCR2113 and JSPS Grant-in-Aid for Scientific Research (C) no. 17K05181.

Ƚ!4!Ƚ

References[1] J. Baena, D. Cabarcas, D.E. Escudero, K. Khathuria, J. Verbel, Rank analysis
of cubic multivariate cryptosystems, PQCrypto’18, LNCS 10786 (2018), pp.
355–374.
[2] A. Casanova, J.C. Faugère, G. Macario-Rat, J. Patarin, L. Perret, J. Ryckeghem, GeMSS: A Great Multivariate Short Signature, Rainbow Signature,https://www-polsys.lip6.fr/Links/NIST/GeMSS.html.
[3] J. Ding, M.-S. Chen. A. Petzoldt, D. Schmidt, B.-Y. Yang, M. Kannwischer
J. Patarin, Rainbow Signature, https://www.pqcrainbow.org/.
[4] J. Ding, A. Petzoldt, L.-C. Wang, The cubic simple matrix encryption scheme,
PQCrypto’14, LNCS 8772 (2014), pp. 76–87.
[5] A. Diene, S.A. Thabet, Y. Yusuf, A multivariate signature based on block
matrix multiplication, https://www.preprints.org/manuscript/202004.
0392/v1, 2020.
[6] D.H. Duong, A. Petzoldt, Y. Wang, T. Takagi, Revisiting the cubic UOVsignature scheme, ICISC’16, Springer LNCS 10157 (2016), pp. 223–238.
[7] Y. Hashimoto, Weaknesses of cubic UOV and its variants, Ryukyu Mathematical Journal 30 (2017), pp. 1–7.
[8] A. Kipnis, A. Shamir, Cryptanalysis of the oil and vinegar signature scheme,
Crypto’98, LNCS 1462 (1998), pp. 257–267.
[9] A. Kipnis, J. Patarin, L. Goubin, Unbalanced oil and vinegar signatureschemes, Eurocrypt’99, LNCS 1592 (1999), pp. 206–222, extended in http://www.goubin.fr/papers/OILLONG.PDF, 2003.
[10] D. Moody, R. Perlner, D. Smith-Tone, Improved attacks for characteristic-2
parameters of the cubic ABC simple matrix encryption scheme, PQCrypto’17,
LNCS 10346 (2017), pp. 255–271.
[11] X. Nie, B. Liu, H. Xiong, G. Lu, Cubic unbalance oil and vinegar signaturescheme, Inscrypt 2015, Springer LNCS 9589 (2015), pp. 47–56.
[12] NIST, Post-Quantum Cryptography Standardization, Round 3 Submissions, https://csrc.nist.gov/projects/post-quantum-cryptography/
round-3-submissions.
[13] J. Patarin, The Oil and Vinegar Signature Scheme, the Dagstuhl Workshop
on Cryptography, 1997.

Department of Mathematical Sciences,
Faculty of Science,
University of the Ryukyus,
Senbaru 1, Nishihara, Okinawa 903-0213
JAPANȽ!5!Ƚ