Ryukyu Math. J., 31(2018), 1-5

ON THE SECURITY OF ZHANG-TAN’S VARIANTS
OF MULTIVARIATE SIGNATURE SCHEMES ∗Yasufumi HASHIMOTO

Abstract
Until now, various multivariate public key cryptosystems (MPKCs) havebeen proposed but some of them are known to be insecure. In IMACC 2015 andInscrypt 2015, Zhang and Tan proposed new variants of MPKCs for signatures
to enhance the security of the original schemes. However, Zhang-Tan’s variants
are much less secure than expected. In this paper, we describe an attack on
Zhang-Tan’s variants to recover a public key of the original scheme.

1

Introduction

After Shor [6] proposed polynomial-time algorithms to factor integers and to solve
discrete logarithm problems by quantum computers, constructing cryptosystems
secure against quantum attacks is one of big issues in cryptology. Multivariate
public key cryptosystems (MPKCs), public key cryptosystems whose public keys aresets of multivariate quadratic forms over finite fields, have been expected to be such
cryptosystems. While various MPKCs have been proposed until now, some of themwere broken soon after proposed or known to be much less secure than expected.
In IMACC 2015 and Inscrypt 2015, Zhang and Tan [9, 10] proposed a new idea
to repair such insecure MPKCs for signatures. Their idea is adding several variables
and terms for the additional variables on the original polynomials, and hiding several
equations to eliminate the contributions of additional variables in the process ofsignature generation. They actually used this idea on already broken schemes MIT [8] and YTS [7, 2] by adding HFE-like polynomials and claimed that this ideaenhanced the security drastically. However, the hidden equations can be recoveredby suﬃciently many signatures and these equations tell us partial information of thesecret key. In this paper, we describe how to recover the hidden equations and thesecret key partially, and conclude that our attack removes the contributions of theadditional variables and recovers a public key of the original scheme.

∗Received November 30, 2018

－ 1 －

2

Multivariate Public Key Cryptosystem

In this section, we describe the general construction of multivariate public key cryptosystems (MPKCs).
Let n, m ≥ 1 be integers, k a finite field and q := #k. Define a quadratic map
G : k n → k m to be inverted feasibly, i.e. finding x ∈ k n with G(x) = y is feasible
for any (or most) y ∈ k m . The secret key is a tuple of three maps (S, G, T ), where
S : k n → k n , T : k m → k m are invertible aﬃne maps and the quadratic map
G : k n → k m . The public key is the convolution of these three maps
F := T ◦ G ◦ S : k n → k m .
On an encryption scheme, the cipher-text y ∈ km for a given plain-text x ∈ k n
is computed by y = F (x). To decrypt y, find z ∈ k n with G(z) = T −1 (y). Thenthe plain-text is x = S −1 (z). Since G is constructed to be inverted feasibly, one candecrypt y feasibly.
On a signature scheme, a signature x ∈ kn for a given message y ∈ k m isgenerated as follows. Find z ∈ k n with G(z) = y and compute x = S −1 (z). Thesignature x ∈ k n for y is verified if y = F (x) holds.

3

Zhang-Tan’s variant

In this section, we describe Zhang-Tan’s variant [9, 10] on MPKC.
Let n, n0 , m, l ≥ 1 be integers with n = n0 + l and x = t (x1 , . . . , xn ), x1 =t (x , . . . , x ), x = t (x1n0
2n0 +1 , . . . , xn ) are variables. Define the quadratic maps G :k n → k m , H : k n → k l byG(x) =t (g1 (x), . . . , gm (x)),H(x) =t (h1 (x), . . . , hl (x)),
where g1 (x), . . . , gm (x) are quadratic forms of x1 andhi (x) =(homogeneous quadratic form of x2 )!
+xn0 +j · (linear form of x1 ),1 ≤j≤l(1 ≤ i ≤ l).

(1)

Suppose that G, H are inverted feasibly, i.e. finding x1 ∈ k n0 with G(x1 ) = y is
feasible for any (or most) y ∈ k m and finding x2 ∈ k l with H(x1 , x2 ) = 0 is also
feasible for any (or most) x1 ∈ k n0 . In [9, 10], G is the central map of MI-T [8] orYTS [7] and H is given by an HFE-like polynomial.
Zhang-Tan’s variant is given as follows.

－ 2 －Secret key. Two invertible aﬃne maps S : k n → k n , T : k m → k m , a linear map
T1 : k l → k m and the quadratic maps G : k n → k m , H : k n → k l defined above.
Public key. The quadratic map F : k n → k m defined by
F := (T ◦ G + T1 ◦ H) ◦ S.

Signature generation. For a message y ∈ k m to be signed, find z1 ∈ k n0 withG(z1 ) = T −1 (y), and z2 ∈ k l with H(z1 , z2 ) = 0. The signature is w = S −1 (z1 , z2 ).
Signature verification. The signature w is verified if F (w) = y holds.
Since G(x) is a set of quadratic forms of x1 and is constructed to be inverted
feasibly, z1 is found feasibly. Similarly, finding z2 is also feasible. Note that H isconstructed such that H(x1 , 0) = 0 for any x1 . Then z2 = 0 is acceptable in theprocess of signature generation if there are no non-trivial z2 for a given z1 .

4On the security of Zhang-Tan’s variant

In this section, we propose our attack to reduce the problem of solving F (x) = y to
the problem of solving F0 (x1 ) = y1 where F0 := T ◦ G ◦ S0 is a public key of theoriginal scheme derived from G, where S0 : k n0 → k n0 is an invertible aﬃne map.
For simplicity, we assume that S is a linear map.
First, recall that one finds z1 , z2 with H(z1 , z2 ) = 0 in the process of signature
generation, and the signature w satisfies (z1 , z2 ) = S(w). Then H ◦ S(w) = 0
holds for any signature w generated by the corresponding Zhang-Tan’s variant.
This means that there are l-linearly independent quadratic forms u1 (x), . . . , ul (x)with ui (w) = 0 for any signature w and these quadratic forms are linear sums of
h1 (S(x)), . . . , hl (S(x)). Since hi is a quadratic form of n variables, we can recoveru1 (x), . . . , ul (x) by N ≫ 12 n(n + 1) signatures.
By the construction (1) of H, we see that the polynomials ui (x) are written by"#0n0 ∗t t
Sx + (linear form)ui (x) = x S∗ ∗lfor 1 ≤ i ≤ l. This is similar to the quadratic form in UOV [5, 3] and then,the#attacker can recover an invertible linear map
once u1 (x), . . . , ul (x) are given,"∗∗n0
S1 : k n → k n with SS1 =by Kipnis-Shamir’s attack on UOV [4, 3] in0 ∗ltime O(q max(0 ,l−n0 ) · (polyn.)).
"#S0 ∗¯
Since F := F ◦ S1 = (T ◦ G + T1 ◦ H) ◦ (S ◦ S1 ) and SS1 =with0 ∗lsome n0 ×n0 matrix S0 , we see that H ◦ (S ◦ S0 ) is a set of quadratic forms asgiven in (1). Then we have F¯(x1 , 0) = (T ◦ G ◦ S0 )(x1 ), which is a public key of theoriginal scheme derived from G. We thus conclude that Zhang-Tan’s variant does
not protect the original scheme strongly.
Our attack is summarized as follows.

－ 3 －Step 1. Let N be an integer suﬃciently larger than 12 n(n + 1). Choose N messages y1 , . . . , yN ∈ k m randomly, and generate signatures w1 , . . . , wN ∈ k n for
y1 , . . . , yN ∈ k m respectively.
Step 2. Find l linearly independent quadratic forms u1 (x), . . . , ul (x) withui (wj ) = 0 for any 1 ≤ j ≤ N .
Step 3. Find an invertible linear map S1 : k n → k n with"
#0n0 ∗tui (S1 (x)) = xx + (linear form)∗ ∗lfor 1 ≤ i ≤ l by Kipnis-Shamir’s attack [4, 3].
Step 4. Let F¯:= F ◦ S1 . Then F¯(x1 , 0) is a public key of the original scheme.

As already explained, the complexity of Step 3 is O(q max(0 ,l−n0 ) · (polyn.)). Itis easy to see that the complexities of other steps of our attack are in polynomial
time. Then the total complexity of our attack is O(q max(0 ,l−n0 ) · (polyn.)), which ismuch less than O(q l · (polyn.)) expected by Zhang and Tan [9, 10]. This means thatl must be suﬃciently larger than n0 , namely the number n of variables in ZhangTan’s variant must be suﬃciently larger than twice of the number n0 of the variablesin the original scheme. This situation is similar to UOV [3], and we can consider
that Zhang-Tan’s variant does not have an advantage over UOV. Furthermore, thecomplexity O(q max(0 ,l−n0 ) · (polyn.)) might be improved if H has a special structure.
For example, when H is given by an HFE-like polynomial [9, 10], the rank attack[1] will reduce the complexity. We thus conclude that Zhang-Tan’s variant is notpractical at all.
Acknowledgment. This work was supported by JST CREST Grant Number JPMJCR14D6 and JSPS Grant-in-Aid for Scientific Research (C) no. 17K05181.

References[1] L. Bettale, J.C. Faugere, L. Perret, Cryptanalysis of HFE, multi-HFE andvariants for odd and even characteristic, Designs, Codes and Cryptography 69(2013), pp.1-52.
[2] Y. Hashimoto, Cryptanalysis of the multivariate signature scheme proposed in
PQCrypto 2013, PQCrypto’14, LNCS 8772 (2014), pp.108–125, IEICE Trans.
Fundamentals, 99-A (2016), pp.58–65.
[3] A. Kipnis, J. Patarin, L. Goubin, Unbalanced oil and vinegar signatureschemes, Eurocrypt’99, LNCS 1592 (1999), pp.206–222, extended in citeseer/231623.html, 2003-06-11.
[4] A. Kipnis, A. Shamir, Cryptanalysis of the oil and vinegar signature scheme,
Crypto’98, LNCS 1462 (1998), pp.257–266.

－ 4 －[5] J. Patarin, The Oil and Vinegar Signature Scheme, the Dagstuhl Workshop on
Cryptography, 1997.
[6] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer, SIAM J. Computing 26 (1997), pp.1484–1509.
[7] T. Yasuda, T. Takagi, K. Sakurai, Multivariate signature scheme using
quadratic forms. PQCrypto’13, LNCS 7932 (2013), pp.243–258.
[8] W. Zhang, C.H. Tan, A new perturbed Matsumoto-Imai signature scheme,
AsiaPKC’14, Proc. 2nd ACM Workshop on AsiaPKC (2014), pp.43–48.
[9] W. Zhang, C.H. Tan, MI-T-HFE, A new multivariate signature scheme,
IMACC’15, LNCS 9496, (2015), pp.43–56.
[10] W. Zhang, C.H. Tan, A secure variant of Yasuda, Takagi and Sakurai’s signaturescheme, Inscrypt’15, LNCS 9589 (2015), pp.75-89

Department of Mathematical Sciences
Faculty of Science
University of the Ryukyus
Nishihara-cho, Okinawa 903-0213
JAPAN－ 5 －