For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Patarin's Attack against the IC Scheme
Naoki OGURA Shigenori UCHIYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
multivariate public key cryptosystem, -Invertible Cycles (IC), Patarin's attack, Grobner basis algorithm, differential,
Full Text: PDF>>
In 2007, Ding et al. proposed an attractive scheme, which is called the -Invertible Cycles (IC) scheme. IC is one of the most efficient multivariate public-key cryptosystems (MPKC); these schemes would be suitable for using under limited computational resources. In 2008, an efficient attack against IC using Grobner basis algorithms was proposed by Fouque et al. However, they only estimated the complexity of their attack based on their experimental results. On the other hand, Patarin had proposed an efficient attack against some multivariate public-key cryptosystems. We call this attack Patarin's attack. The complexity of Patarin's attack can be estimated by finding relations corresponding to each scheme. In this paper, we propose an another practical attack against the IC encryption/signature scheme. We estimate the complexity of our attack (not experimentally) by adapting Patarin's attack. The attack can be also applied to the IC- scheme. Moreover, we show some experimental results of a practical attack against the IC/IC- schemes. This is the first implementation of both our proposed attack and an attack based on Grobner basis algorithm for the even case, that is, a parameter is even.