Copy
Naoki OGURA, Shigenori UCHIYAMA, "On Patarin's Attack against the IC Scheme" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 1, pp. 34-41, January 2010, doi: 10.1587/transfun.E93.A.34.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.34/_p
Copy
@ARTICLE{e93-a_1_34,
author={Naoki OGURA, Shigenori UCHIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Patarin's Attack against the IC Scheme},
year={2010},
volume={E93-A},
number={1},
pages={34-41},
abstract={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.},
keywords={},
doi={10.1587/transfun.E93.A.34},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - On Patarin's Attack against the IC Scheme
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 34
EP - 41
AU - Naoki OGURA
AU - Shigenori UCHIYAMA
PY - 2010
DO - 10.1587/transfun.E93.A.34
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2010
AB - 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.
ER -
IC Scheme
English
