Paper 2016/733

Revisiting the Hybrid Attack: Improved Analysis and Refined Security Estimates

Thomas Wunderer

Abstract

Over the past decade, the hybrid lattice reduction and meet-in-the middle attack (called the Hybrid Attack) has been used to evaluate the security of many lattice-based cryprocraphic schemes such as NTRU, NTRU prime, BLISS, and more. However, unfortunately none of the previous analyses of the Hybrid Attack is entirely satisfactory: they are based on simplifying assumptions that may distort the security estimates. Such simplifying assumptions include setting probabilities equal to $1$, which, for the parameter sets we analyze in this work, are in fact as small as $2^{-80}$. Many of these assumptions lead to underestimating the scheme's security. However, some lead to security overestimates, and without further analysis, it is not clear which is the case. Therefore, the current security estimates against the Hybrid Attack are not reliable and the actual security levels of many lattice-based schemes are unclear. In this work we present an improved runtime analysis of the Hybrid Attack that gets rid of incorrect simplifying assumptions. Our improved analysis can be used to derive reliable and accurate security estimates for many lattice-based schemes. In addition, we reevaluate the security against the Hybrid Attack for the NTRU, NTRU prime, and R-BinLWEEnc encryption schemes as well as for the BLISS and GLP signature schemes. Our results show that there exist both security over- and underestimates in the literature. Our results further show that the common claim that the Hybrid Attack is the best attack on all NTRU parameter sets is in fact a misconception based on incorrect analyses of the attack.