All in the XL family : theory and practice

doi:10.1007/11496618_7

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Journal Article > Item 987654321/41373

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/41373

Title:	All in the XL family : theory and practice
Other Titles:	XL (延伸線性化) 類方法的理論和實際的探討
Authors:	Yang, Bo-yin
Contributors:	淡江大學數學學系
Keywords:	algebraic analysis;finite field;Gröbner Bases;multivariate quadratics;multivariate cryptography;XL
Date:	2005-04
Issue Date:	2010-01-28 07:24:44 (UTC+8)
Publisher:	Berlin Heidelberg : Springer-Verlag GmbH
Abstract:	The XL (eXtended Linearization) equation-solving algorithm belongs to the same extended family as the advanced Gröbner Bases methods F4/F5. XL and its relatives may be used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many “algebraic cryptanalysis” used today. We analyze the applicability and performance of XL and its relatives, particularly for generic systems of equations over medium-sized finite fields. In examining the extended family of Gröbner Bases and XL from theoretical, empirical and practical viewpoints, we add to the general understanding of equation-solving. Moreover, we give rigorous conditions for the successful termination of XL, Gröbner Bases methods and relatives. Thus we have a better grasp of how such algebraic attacks should be applied. We also compute revised security estimates for multivariate cryptosystems. For example, the schemes SFLASHv2 and HFE Challenge 2 are shown to be unbroken by XL variants.
Relation:	Lecture Notes in Computer Science 3506,　p.67-86
DOI:	10.1007/11496618_7
Appears in Collections:	[Graduate Institute & Department of Mathematics] Journal Article

Files in This Item:

File	Size	Format
All in the XL Family Theory and Practice.pdf	385Kb	Adobe PDF	1	View/Open
index.html	0Kb	HTML	245	View/Open
index.html	0Kb	HTML	121	View/Open

Loading...