Presentation title (on one or two lines)

An Estimation of Computational Complexity
for the Section Finding Problem on
Algebraic Surfaces
Chiho Mihara (TOSHIBA Corp.)
2013/03/02
© 2013 Toshiba Corporation
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


Main talk
ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
2
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
3
1. Section Finding Problem (SFP)
Security of Algebraic Surface Cryptosystems(ASC) is
based on the difficulty of Section Finding Problem(SFP)
Section Finding Problem(SFP)
Given
, find
C
X ( x, y , t )
Find
such that
： Algebraic Surface (Public Key)
：Section on
(Secret Key)
To find Section is Too difficult!!
© 2013 Toshiba Corporation
4
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
5
How to solve SFP(General solution)
We can write down a section
as
degree of
And substitute these into
So the SFP is reduced to a multivariate equation system
If you solve
,
then you can get
(SME(*))
(*)Section multivariate equations
© 2013 Toshiba Corporation
6
Relation between MPKC and ASC
Quadratic multivariate equations
c1 ( x1 , x2 ,


c ( x , x ,
 m 1 2
MPKC
, xn )  y1
O(n3 )
, xn )  ym
which is MPKC based on.
More general multivariate equations ASC
c0 ( 0 ,  ,  d ,  0 ,  ,  d )  0
More 3 dimensional





polynomials
c ( ,  ,  ,  ,  ,  )  0
d
0
d
 r 0
Public key includes multiwhich is ASC based on.
variable equations implicitly
Difficulty of SFP on algebraic surface
X ( x, y, t )  0
O ( n)
© 2013 Toshiba Corporation
7
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


Main talk
ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
8
ASC Security parameters
cardinality of the base field
How to solve SFP
degree of the secret section
degree in
of the public surface
X ( x, y , t )
(SME)
Number of distinct monomials in
We propose a new security parameter!
(SME)
Gröbner basis
C
X ( x, y , t )
© 2013 Toshiba Corporation
9
Example of NonRed_Monos
How to solve SFP
Algerbraic surface
:grand field
Solve
Sample image
ASC security
parameter
This
example
p
11
d
1
w
3
NonRed_Monos
6
Section
© 2013 Toshiba Corporation
10
Complexity parameters in general case
The Complexity of
Solving Multivariable Polynomial Equations
The Complexity ( in general case ) : NP-hard
Parameters related to the complexity :
1. Size of Finite Field : p
Complexity
2. Number of variables : n
Multivariable
Equation
Parameter Polynomial
ASC
security
over finite field
in general case
parameter
 f1 ( xp1 , x2 ,  , xn ) p 0

n
2d+2


 f (mx , x ,  , x wd+dc
n)  0
 m 1 2
Complexity
3. Number of equations : m
Complexity
Sparseness
NonRed_Monos
4. Sparseness
“Sparseness” describe simplicity of equations.
Complexity
© 2013 Toshiba Corporation
11
“Sparseness” and NonRed_Monos
“Dense”
“Sparse”
NonRed_Monos
19
NonRed_Monos
hard
easy
7
We consider that NonRed_Monos is a parameter of Sparseness.
© 2013 Toshiba Corporation
12
How to calculate “NonRed_Monos” from surface
We can calculate “NonRed_Monos” from “Algebraic form”
Algebraic form
If
is max (full size),
NonRed_Monos is also max.
Maximal NonRed_Monos and d
How to calculate “NonRed_Monos”
Data exist
d
(w=3:fix)
© 2013 Toshiba Corporation
13
Necessity of NonRed_Monos
Even if p,d,w has been fixed,
there are many surface variations….
Question
For given 2 surfaces X1,X2,
(same p,d,w)
𝐶1
𝑋1 𝑥, 𝑦, 𝑡
𝑋2 𝑥, 𝑦, 𝑡
𝐶2
which is more difficult to calculate Section?
We can answer this question,
because we can calculate NonRed_Monos!
© 2013 Toshiba Corporation
14
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
15
Experiment
OS : centos(Linux) version 2.6
CPU : AMD Opteron (tm) 848 (2.00GHz)
Memory : 64GByte
Software: Magma version 2.15-11
p = 11
d = 2, 3, 4
w = 3, 4, 5
# Λ𝑋 = 40
size of finite field
degree of
Form of Algebraic surface
(random generate)
© 2013 Toshiba Corporation
16
Experimental result
Process time(left) & Memory use(right) to calculate Groebner basis of
w
log(Memory)
log(time)
NonRed_Monos
NonRed_Monos
© 2013 Toshiba Corporation
17
Experimental result (statistical)
Regression formula
d
2
3
4
log(time)
Prediction interval
of 99.9999％(★)
Prediction interval
of 99.9999％(★)
＝： BEST of Computational
Complexity!
NonRed_Monos
© 2013 Toshiba Corporation
18
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
19
Key size estimation (Gröbner basis)
Prediction interval
of 99.9999％(★)
FIX
128bit security
Securer Data
Max NonRed_Mono
Data exist
We can choose secure data ,
d = 8, NonRed_Monos≧29000
1 2 3 4 5 6 7 8 9 10
d
© 2013 Toshiba Corporation
20
Key size estimation (Exaustive search)
• We estimate Computational Complexity of
exhaustive search for (SME)
/
.
(SME(*))
 You can reduce to half of variables(by Ogura-Mihara) , so the
number of variables in (SME) is d+1.
 To satisfy 128bit security(＝RSA(3072bit)), d>36 .
Algorithms
D
w
dc
nx*
Public Key Size
Gröbner basis
8
5
5
20
640 bit
Ogura-Mihara
8
5
5
20
640 bit
Exhaustive search
37
5
5
20
1220 bit
(*)nx: number of terms of algebraic surface (Note: count full terms version in this table)
© 2013 Toshiba Corporation
21
Outline
1. Section Finding Problem(SFP)
2. General Solution

How to solve SFP, Relation between MPKC and ASC
3. Security parameters


ASC security parameters
Complexity parameters in general case
4. Experimental result
5. Key Size Estimation
6. Conclusion
© 2013 Toshiba Corporation
22
Conclusion
• We propose new security parameter NonRed_Monos.
 We express “Sparseness” as NonRed_Monos.
• We can derive an estimation of computational
complexity for the Section Finding Problem on
Algebraic Surfaces with high accuracy.
• Recommended Public Key Size of ASC is 1220 bit
(128bit security = RSA 3072bit).
© 2013 Toshiba Corporation
23
Last talk (my failure story)
• When I saw the “section finding problem" for the first
time , I think this problem is easy to solve.
• So, we tried to develop a more efficient analysis (over
Gröbner basis computation), named Ogura-Mihara
algorithm.
• I introduce a concept of Ogura-Mihara algorithm.
© 2013 Toshiba Corporation
24
Property of Section multivariate equations(SME
)
Proposition
CAT FACE!!
© 2013 Toshiba Corporation
25
Concept of Ogura-Mihara algorithm
Idea! : Reduce “number of valuables” by pseudo division
Vanish!
Vanish!
Gröbner basis
© 2013 Toshiba Corporation
26
Failure and Conclusion
• Indeed, the number of variables is reduced to half, and
in the small parameter, Ogura-Mihara algorithm solves
faster than Gröbner basis computation.
• But we found that degrees of section and surface are
higher and higher, Ogura-Mihara’ NonRed_Monos
significantly bigger and bigger more than the original
(SME)’s NonRed_Monos. So it’s not efficient algorithm.
• So when you want to estimate computational
complexity such as using Gröbner basis, you need to
see NonRed_Monos.
© 2013 Toshiba Corporation
27
© 2013 Toshiba Corporation
28

Download Report