TY - GEN
T1 - Complexity estimates for the F4 attack on the perturbed matsumoto-imai cryptosystem
AU - Ding, J.
AU - Gower, J. E.
AU - Schmidt, D.
AU - Wolf, C.
AU - Yin, Z.
PY - 2005
Y1 - 2005
N2 - Though the Perturbed Matsumoto-Imai (PMI) cryptosystem is considered insecure due to the recent differential attack of Fouque, Granboulan, and Stern, even more recently Ding and Gower showed that PMI can be repaired with the Plus (+) method of externally adding as few as 10 randomly chosen quadratic polynomials. Since relatively few extra polynomials are added, the attack complexity of a Gröbner basis attack on PMI+ will be roughly equal to that of PMI. Using Magma's implementation of the F4 Gröbner basis algorithm, we attack PMI with parameters q = 2, 0 ≤ r ≤ 10, and 14 ≤ n ≤ 59. Here, q is the number of field elements, n the number of equations/variables, and r the perturbation dimension. Based on our experimental results, we give estimates for the running time for such an attack. We use these estimates to judge the security of some proposed schemes, and we suggest more efficient schemes. In particular, we estimate that an attack using F 4 against the parameters q = 2, r = 5, n = 96 (suggested in [7]) has a time complexity of less than 250 3-DES computations, which would be considered insecure for practical applications.
AB - Though the Perturbed Matsumoto-Imai (PMI) cryptosystem is considered insecure due to the recent differential attack of Fouque, Granboulan, and Stern, even more recently Ding and Gower showed that PMI can be repaired with the Plus (+) method of externally adding as few as 10 randomly chosen quadratic polynomials. Since relatively few extra polynomials are added, the attack complexity of a Gröbner basis attack on PMI+ will be roughly equal to that of PMI. Using Magma's implementation of the F4 Gröbner basis algorithm, we attack PMI with parameters q = 2, 0 ≤ r ≤ 10, and 14 ≤ n ≤ 59. Here, q is the number of field elements, n the number of equations/variables, and r the perturbation dimension. Based on our experimental results, we give estimates for the running time for such an attack. We use these estimates to judge the security of some proposed schemes, and we suggest more efficient schemes. In particular, we estimate that an attack using F 4 against the parameters q = 2, r = 5, n = 96 (suggested in [7]) has a time complexity of less than 250 3-DES computations, which would be considered insecure for practical applications.
KW - Gröbner basis
KW - Multivariate
KW - Perturbation
KW - Public-key
KW - Quadratic polynomials
UR - http://www.scopus.com/inward/record.url?scp=33646847187&partnerID=8YFLogxK
U2 - 10.1007/11586821_18
DO - 10.1007/11586821_18
M3 - Conference Proceeding
AN - SCOPUS:33646847187
SN - 354030276X
SN - 9783540302766
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 262
EP - 277
BT - Cryptography and Coding - 10th IMA International Conference, Proceedings
PB - Springer Verlag
T2 - 10th IMA International Conference on Cryptography and Coding
Y2 - 19 December 2005 through 21 December 2005
ER -