OFFICIAL COMMENT: HIMQ-3 :Key Recovery Attack

[Ward Beullens]

Dear all, 

I have found a more efficient variant of the Key Recovery attack on HiMQ-3 that was described in the submission (Theorem 1). The main observation is that there are more equivalent keys than those described in Lemma 2. Concretely, the o_1 x o_2 and o_2 x o_1 part of the matrix \Sigma need not be zero. This allows for a better 'Good Key', and results in a more efficient Key Recovery Attack. 

The most expensive step in the attack is solving a system of n − 1 bi-homogeneous equations and m quadratic equations in n variables. An upper bound to the complexity of solving this system is obtained by treating the equations as semi-regular. 

This gives an estimated complexity of 2^124.8 field operations (F_256) for the HiMQ-3(256,31,15,15,14) parameter set, and 2^109.9 field operations for the HiMQ-3F(256,24,11,17,15) parameter set. So these parameters do not seem to reach Security Level 1.

Because of the bi-homogeneous structure of n-1 of the equations the actual complexity will be a bit lower (e.g. see p.11 of [1])

I communicated with the designers and they told me they had independently found a similar attack with the same complexity, and that they will be posting a message to the forum soon.

All the best,

Ward Beullens

[1] https://eprint.iacr.org/2012/223.pdf