TY - GEN
T1 - Algebraic attack on HFE revisited
AU - Ding, Jintai
AU - Schmidt, Dieter
AU - Werner, Fabian
PY - 2008
Y1 - 2008
N2 - In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F 4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).
AB - In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F 4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).
KW - Gröbner basis
KW - HFE
KW - Multivariate public key cryptosystem
UR - http://www.scopus.com/inward/record.url?scp=56649111148&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-85886-7_15
DO - 10.1007/978-3-540-85886-7_15
M3 - Conference Proceeding
AN - SCOPUS:56649111148
SN - 3540858849
SN - 9783540858843
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 215
EP - 227
BT - Information Security - 11th International Conference, ISC 2008, Proceedings
T2 - 11th International Conference on Information Security, ISC 2008
Y2 - 15 September 2008 through 18 September 2008
ER -