On Patarin's Attack against the IC Scheme

Naoki OGURA  Shigenori UCHIYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.1   pp.34-41
Publication Date: 2010/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.34
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
Keyword: 
multivariate public key cryptosystem,  -Invertible Cycles (IC),  Patarin's attack,  Grobner basis algorithm,  differential,  

Full Text: PDF>>
Buy this Article




Summary: 
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.