### Problems

```Multivariate Signature Scheme
Takanori Yasuda (ISIT)
Joint work with
Tsuyoshi Takagi (Kyushu Univ.), Kouichi Sakurai (Kyushu Univ.)
Workshop on Solving Multivariate Polynomial Systems and Related Topics
2013/3/3
Contents
1.
2.
3.
4.
5.
Multivariate Signature Schemes
Multivariate System defined by Quadratic Forms
Application to Signature Scheme
Comparison with Rainbow
1.
2.
3.
Efficiency of Signature Generation
Key Sizes
Security
6. Conclusion
1
MPKC Signature
:   →   : multivariate polynomial map
Vector space
Vector space

= − ()
Signature

Inverse function
−1
Message
For any message M, there must exist the corresponding signature.
F is surjective.
6
New Multivariate
Polynomial Map
• We introduce a multivariate polynomial map not
surjective, and apply it to signature.
Multivariate polynomial map
For a symmetric matrix A,
() = . .
where  =  is a matrix of variables of size  × .
is a map which assigns a matrix to a matrix.
G can be regarded as
2
2
a multivariate polynomial map   →   .
2
Problems of G
Is G applicable to signature or not?
Problems
1. Can its inverse map be computed efficiently?
Necessary to compute  −1 M for a message M
in order to generate a signature.
2. Is it surjective or not?
For any message M,
necessary to generate its signature.
3
• Definition 1
: Field with odd characteristic (or 0)
: Natural number
:   →  is a quadratic form
= . .   for some symmetric matrix
• Definition 2
,  : quadratic forms associated to ,
and  are isometric
. .   =  for some  ∈ (, )
Translation of problems of
• Equation
(, : symmetric matrices)
() = . .   =
• Restrict solution  ∈ (, )
o Problem 1’ For  ,  , isometric each other,
find a translation matrix  efficiently.
o Problem 2’ For any  ,  ,
are  and  isometric or not?
How to compute the
inverse map
Simple case
=  =
1
0
⋱
0
1
Problem 1’ is equivalent to
Problem 1’’: Find an orthonormal basis of
with respect to  .
Orthonormal basis: 1 , …  in
= 1 for  = 1, … , ,
,
≔  . .

= 0 for  ≠
5
Real field Case
•  =  : real field
Gram-Schmidt orthonormalization provides an efficient
algorithm to solve Problem 1’’.
It uses special property of  =  .
Fact:  =  is anisotropic.
Definition:
for any  (≠ 0)   , () ≠ 0
We want to apply Gram-Schmidt orthonormalization technique
to the case of finite fields.
Finite Field Case
Fact Let  be a finite field.
Any quadratic form on   ( ≥ 3) is not anisotropic.
We cannot apply Gram-Schmidt orthonormalization directly.
• However, we can extend Gram-Schmidt orthonormalization
by inserting a step:
If   = 0, then find another element ′ such that  ′ ≠ 0.
Solve Problem 1’
Problem 2
• Definition
: quadratic form associated to .
is nondegenerate
det() ≠ 0
Classification theorem (if K has odd characteristic)
Any nondegenerate quadratic form is isometric to either
1 or  .
7
Classification Theorem
• For any (nondegenerate) message , either
•
•
•
•
∙ 1 ∙   =  or  ∙  ∙   =
has a solution.
1 or  is determined by det().
In the degenerate case, both equations have solutions.
=  ∙ 1 ∙   or   =  ∙  ∙   is not surjective.
However, we can apply this map to MPKC signature.
Application to MPKC
Signature Scheme
• Secret Key
1 ,   (, )
1 ≔ 1 . 1 . 1  ,  ≔  .  .   ,
1  = . 1 . ,
:   →   ,
• Public Key
= .  .
:   →   , affine transformations
=
+1
2
,
= 2
1 :   →   defined by 1 = °1 °,
:   →   defined by  = ° °,
Signature Generation
• For any symmetric matrix ,
• Step 1 Apply the extended Gram-Schmidt
orthonormalization to .
o Find a solution  =  of either
∙ 1 ∙   =  or
∙  ∙   =
• Step 2 Compute  = 1 −1 .  or  =  −1 . .
=  is a solution of 1  =  or   = .
Property of Our Scheme
• Respective map 1 or  is not surjective.
• However, the union of images of these maps covers the
whole space.

14
Property of Our Scheme
Multivariate Polynomial Maps
Rainbow
Surjective
HFE
UOV
MI
Not
Surjective
Proposal
4
Security of Our Scheme
• There are several attacks of MPKC signature schemes
which depend on the structure of central map.
• For example, UOV attack is an attack which transforms
public key into a form of central map of UOV scheme.
o Central maps of UOV ara surjective.
o The public key of our scheme cannot be transformed into any
surjective map.
• These attacks is not applicable against our scheme.
（Other example: Rainbow-band-separation attack,
UOV-Reconciliation attack）
• However, attacks which is independent of scheme, like
direct attacks, are applicable to our scheme.
15
Comparison with
Rainbow
Compared in the case that  and  are same
for public key F :   →
• Equivalent with respect to cost of verification and public key
length.
• Cost of signature generation (number of mult.)
o Proposal
(2 )
o Rainbow
(3 )
⇒ 8 or 9 times more efficient at the level of 88-bit security.
• Secret Key Size (number of elements of field)
o Proposal
o Rainbow
16
Conclusion
• We propose a new MPKC signature scheme using quadtaci
forms. The multivariate polynomial map used in the scheme
is not surjective.
• Signature generation uses an extended Gram-Schmidt
orthonormalization. It is 8 or 9 times more efficient than that
of Rainbow at the level of 88-bit security.
Future Work
• Security analysis
• Application to encryption scheme
17
```