Details:
Title  Algebraic cryptanalysis of the PKC  Author(s)  Faug`ere JeanCharles, PierreJean Spaenlehauer  Type  Book, Chapter in Book, Conference Proceeding  Abstract  In this paper, we fully break the Algebraic Surface Cryptosystem (ASC for short) proposed at PKC’2009 [3]. This system is based on an unusual problem in multivariate cryptography: the Section Finding Problem. Given an algebraic surface X(x,y,t)∈𝔽p[x,y,t] such that degxyX(x,y,t)=w, the question is to find a pair of polynomials of degree d, u x (t) and u y (t), such that X(u x (t),u y (t),t) = 0. In ASC, the public key is the surface, and the secret key is the section. This asymmetric encryption scheme enjoys reasonable sizes of the keys: for recommended parameters, the size of the secret key is only 102 bits and the size of the public key is 500 bits. In this paper, we propose a message recovery attack whose complexity is quasilinear in the size of the secret key. The main idea of this algebraic attack is to decompose ideals deduced from the ciphertext in order to avoid to solve the section finding problem. Experimental results show that we can break the cipher for recommended parameters (the security level is 2102) in 0.05 seconds. Furthermore, the attack still applies even when the secret key is very large (more than 10000 bits). The complexity of the attack is ˜(w7dlog(p)) which is polynomial with respect to all security parameters. In particular, it is quasilinear in the size of the secret key which is (2 d + 2) log(p). This result is rather surprising since the algebraic attack is often more efficient than the legal decryption algorithm.  Keywords  Multivariate Cryptography, Algebraic Cryptanalysis, Section Finding Problem (SFP), Gröbner bases, Decomposition of ideals  ISBN  9783642130120/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642130137_3 
Language  English  Pages  3552  Publisher  Berlin: Springer  Year  2010  Edition  0  Translation 
No  Refereed 
No 
