General Fault Attacks on Multivariate Public Key Cryptosystems - Post-Quantum Cryptography - page 6

Kipnis-Shamir's attack on UOV [33,31] also finds (a part) of S with the com-
plexity O ( q n− 2 n 1 n 1 ).
In TTM [35] and TTS [46], G is given by a convolution of two (or more) STS
type special invertible non-linear maps. The current examples of TTS ( e.g. [46])
are special (sparse) versions of Rainbow. The advantages of TTS compared to
Rainbow are its eciency, faster signature generation and smaller sized G .

2.2 Variations of Basic G

Several variations have been proposed to enhance the security of the basic
schemes given in the previous subsection. We now describe the major ones.

2.2.1 )” and “Plus( + )”

The “minus” method is given by removing several polynomials in G .If G ( x ):=
( g 1 ( x ) ,

“Minus( −

··· ,g m ( x )) t , the central map G − : k n → k n−u ( u<m )of“minus”is

G − ( x ):=( g 1 ( x ) , ··· ,g m−u ( x )) , (12)

namely the polynomials g m−u +1 ( x ) , ,g m ( x ) are hidden in the “minus”. This

is used for signature schemes. The signature generation process is as follows. For
a message y

···

k m−u ,choose r k u

∈ ∈ randomly. The signature is then generated

by

x = S − 1 ( G − 1 ( T − 1 ( y ) ,r )) .

This is usually used in the BF type, because the “minus” of STS is also described
as the STS type. MI [41,21] are examples of the “minus” of

BF type. Note that Sflash [1] is a further modification of MI

− ,HFE − and l IC −

.Byremoving u
polynomials in G , they prevents the attacks on the original schemes. However,
a differential attack recover the hidden polynomials in MI

−

and Sflash [26,22].
The “plus” method is given by adding several polynomials, namely the central
map of “plus” is G + =( g 1 ( x ) ,

−

1isa
small integer and h l is a randomly chosen quadratic forms. The decryption is
about q r times slower than the original one. Note that the security of MI

··· ,g m ( x ) ,h 1 ( x ) , ··· ,h u 1 ( x )) where u 1 ≥

± (the

“plus” of MI − ) is still open (further discussed by Patarin et al. [41]).

2.2.2 “Vinegar”
The “vinegar” method is given by adding several variables. For the original
scheme G ( x ):=( g 1 ( x ) ,

··· ,g m ( x )) with

a ij x i x j +
1 ≤i≤n

g l ( x ):= b i x i + c,

1 ≤i≤j≤n

the “vinegar” G v ( x ):=( g 1 ( x ) , ··· ,g m ( x )) is given by

a ij x i x j +
1

v ( l )
i

,x n + u ) x i + w ( l )

g l ( x ):= ( x n +1 , ··· ( x n +1 , ··· ,x n + u ) ,

i

1 ≤i≤j≤n ≤i≤n