There have been a number of key mismatch attacks on these CPA secure versions when the public key is reused. However, a unified method to evaluate their resilience under key mismatch attacks is still missing. Since the key index of the efficiency of these attacks is the number of queries (matches and mismatches) needed to successfully mount such an attack, in this paper, we propose and develop a systematic approach to find the lower bounds on the minimum average number of queries needed for such attacks. Our basic idea is to transform the problem of finding the lower bound of queries into finding an optimal binary recovery tree (BRT), where the computations of the lower bounds become essentially the computations of certain Shannon entropy. The approach means that one cannot find a better attack with fewer queries than this lower bound. The introduction of the optimal BRT approach enables us to understand why, for some schemes, there is a big gap between the theoretical bounds and practical attacks, in terms of the number of queries needed. This further leads us to improve the existing attacks. Especially, we can reduce the needed queries against Frodo640 by 71.99% , LAC256 by 82.81%, and Newhope1024 by 97.44%.
Category / Keywords: public-key cryptography / Key Mismatch Attacks; Lattice-Based Cryptography; KEMs; NIST standardization Date: received 3 Feb 2021, last revised 3 Feb 2021 Contact author: chengchizz at qq com Available format(s): PDF | BibTeX Citation Version: 20210205:123543 (All versions of this report) Short URL: ia.cr/2021/123