Title: An attack on improved algebraic surface public-key cryptosystem (abstract only)
Abstract: Public key cryptography is widely used because it enables secure communication with a party accessing the site for the first time. But it is widely known that the quantum computers become available then the public key cryptosystems based on the discrete logarithm probrem such as RSA cryptosystem and Elliptic Curve cryptosystem will no longer be secure. To address these issues, Akiyama-Goto algebraic Surface Public-key Cryptosystem (ASC) was developed [1], and opened to general public at website as a research news of Toshiba corporation in 2005. Its security is based on a decision randomizing polynomial problem which is related to a problem of finding sections on fibered algebraic surfaces. This problem can be reduced to solving a multivariate equation system and it is known to be NP-complete. In 2007, in the case that public-key is in a certain form, Uchiyama and Tokunaga successed to attack in the sense of getting plain text from cipher text using reductions efficiently without solving section finding problem [2].And the abstract is introduced in CRYPTREC report 2006 [3] in the Appendix Chapter, which is known to be the important report related to e-Government recommended ciphers in Japan. Note that, at this point, the cryptosystem can be used safely if only we avoid to adopt using public key with vulnerability in the key generation step. However, the author suggested two algorithms applicable to all cases [5] i.e. the cryptosystem is completely broken. One is the generalization of Uchiyama-Tokunagas attack from polynomial ring over IFp to polynomial ring over rational function field. And the other takes advantages of Grobner base techniques so as to deal with in the polynomial ring over IFp. And in [6], the author also suggested methods for calculating zero point of the algebraic surface and a new attack utilizing it, and the approach resulted in the difficulty of making a suggestion of the invulnerable algebraic surface public-key cryptosystem without changing ideas progressively. On the other hand, Inanov-Volochs attack using trace map [9] was developed. In these background, Akiyama-Goto developed improved version of their Algebraic surface public-key cryptosystem (improved ASC) [8] on January 2008 [8] which has tolerance to Uchiyama-Gotos attack using reduction and Volochs attack using the trace map. Ivanov and Voloch suggested the substitution attack briefly on improved ASC in section 3 in [9], but the details are unspecified. In section 2, the improved ASC is described, and then, in section 3, a new reduction attack on the improved ASC is presented.
Publication Year: 2008
Publication Date: 2008-07-25
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot