A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack

Over the past decade, the hybrid lattice-reduction and meet-in-the middle attack (called hybrid attack) has been used to evaluate the security of many lattice-based cryptographic 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⁻⁸⁰. 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 is based on more reasonable assumptions. 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.