Total Break of the IC Signature Scheme

Description

Total Break of the -IC Signature Scheme Pierre-Alain Fouque1, Gilles Macario-Rat2, Ludovic Perret3, and Jacques Stern1 1 ENS/CNRS/INRIA , 2 Orange Labs 3 UMPC/LIP6/SPIRAL & INRIA/SALSA Abstract. In this paper, we describe efficient forgery and full-key re- covery attacks on the -IC? signature scheme recently proposed at PKC 2007. This cryptosystem is a multivariate scheme based on a new internal quadratic primitive which avoids some drawbacks of previous multivari- ate schemes: the scheme is extremely fast since it requires one exponen- tiation in a finite field of medium size and the public key is shorter than in many multivariate signature schemes. Our attacks rely on the recent cryptanalytic tool developed by Dubois et al. against the SFLASH sig- nature scheme. However, the final stage of the attacks require the use of Grobner basis techniques to conclude to actually forge a signature (resp. to recover the secret key). For the forgery attack, this is due to the fact that Patarin's attack is much more difficult to mount against -IC. The key recovery attack is also very efficient since it is faster to recover equivalent secret keys than to forge.

• can perform


• f4 can


• linear mappings


• scheme


• public key


• ic? scheme


• grobner basis


• f5 algorithms


• algebra problems

Sujets

• Fouqué
• Perret
• Orange Labs
• Scheme

Informations

• Publié par: pefav
• Nombre de lectures: 17
• Langue: English

Extrait

TotalBreakofthe`-ICSignatureScheme Pierre-AlainFouque 1 ,GillesMacario-Rat 2 ,LudovicPerret 3 ,and JacquesStern 1 1 ENS/CNRS/INRIA [e-mail] , [e-mail] 2 OrangeLabs [e-mail] 3 UMPC/LIP6/SPIRAL&INRIA/SALSA [e-mail] Abstract.Inthispaper,wedescribeefficientforgeryandfull-keyre- − coveryattacksonthe`-ICsignatureschemerecentlyproposedatPKC 2007.Thiscryptosystemisamultivariateschemebasedonanewinternal quadraticprimitivewhichavoidssomedrawbacksofpreviousmultivari- ateschemes:theschemeisextremelyfastsinceitrequiresoneexponen- tiationinafinitefieldofmediumsizeandthepublickeyisshorterthan inmanymultivariatesignatureschemes.Ourattacksrelyontherecent cryptanalytictooldevelopedbyDuboisetal.againsttheSFLASHsig- naturescheme.However,thefinalstageoftheattacksrequiretheuse ofGro¨bnerbasistechniquestoconcludetoactuallyforgeasignature (resp.torecoverthesecretkey).Fortheforgeryattack,thisisdueto thefactthatPatarin’sattackismuchmoredifficulttomountagainst `-IC.Thekeyrecoveryattackisalsoveryefficientsinceitisfasterto recoverequivalentsecretkeysthantoforge. 1Introduction Multivariatecryptographyproposesefficientcryptographicschemeswell-suited forlowcomputationaldevices.Sincetheunderlyingproblemisnotknowntobe easyinthequantummodel,theseschemeshavebeenconsideredbystandard- izationbodiesasalternativestoRSAorDLogbasedschemes.Forinstance,in 2003,onepromisingsignaturescheme,calledSFLASH,hasbeenselectedbythe NESSIEproject.SFLASHisbasedontheC ∗ cryptosystem[20]proposedby MatsumotoandImaiin1988andbrokenbyPatarinin1995[21].Followingan ideaofShamir[25],Patarin,GoubinandCourtoisproposedSFLASH[24]by removingsomeequationsofthesystem.TheschemeisalsocalledC ∗− andthe generictransformationofremovingequationsiscalledthe“Minus”transforma- tionwhichcanbeappliedtomanymultivariateschemes. Multivariatecryptographyprovidespublic-keycryptosystemswhosesecurity isrelatedtotheproblemofsolvingsystemsofquadraticorhigherdegreeequa- tionsinmanyvariables.Thisproblemisknowntobe NP -hardanditseemsto bealsodifficultonaverage.Thetodaymostefficientalgorithmstosolvethis genericproblemareGro¨bnerbasisalgorithmswhosecomplexityisexponential 4 4 forsystemswithafinitenumberofsolutions.