Seminar
An Estimate of the Complexity of the Section Finding Problem on Algebraic Surfaces

Hold Date 
20161118 15:00～20161118 16:00 


Place 
Seminar Room W1C716, West Zone 1, Ito campus, Kyushu University 


Object person 



Speaker 
Shinya Okumura (ISIT) 

Abstract:
Researching postquantum cryptography has been an important task in cryptography. The section finding problem on algebraic surfaces (ASSFP) is considered to be intractable also after building quantum computers. Thus ASSFP is used as a basis of the security of the Algebraic Surface Cryptosystem (ASC),which is a candidate of postquantum cryptosystems, and it is important for designing parameters which make ASC secure to estimate the complexity of ASSFP. Solving ASSFP is reduced to solving certain multivariate equation systems (section equation systems) of high degrees, and one can solve such equation systems by using the Grobner basis technique. Although estimating the complexity of computing a Grobner basis associated with an equation system is difficult in general, it becomes easy if the equation system is semiregular. In our work, we experimentally estimate the complexity of ASSFP. From our experimental results, although we see that section equation systems do not become semiregular in most cases for small parameters, we can infer parameters closely related to the difficulty of computing Grobner bases associated with section equation systems. According to our inference, we estimate the complexity of ASSFP and parameters which make ASC 128bit security against the attack by the Grobner basis technique. We also consider a bruteforce attack against ASSFP and conjecture that the bruteforce attack is more efficient than the attack by the Grobner basis technique. Finally, we give parameters and sizes of public keys such that ASC has 128bit security against the bruteforce attack. Its size (876bits) is much smaller than sizes of public keys in other efficient candidates of PQC. This is a joint work with Koichiro Akiyama and Tsuyoshi Takagi.