A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs

Yue Qin China University of Geosciences, Wuhan 430074, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China; Ding Lab, Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing, China Chi Cheng China University of Geosciences, Wuhan 430074, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China; Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China Xiaohan Zhang China University of Geosciences, Wuhan 430074, China Yanbin Pan Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China Lei Hu State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China Jintai Ding Ding Lab, Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing, China; Yau Mathematical Sciences Center, Tsinghua University, Beijing, China

TBD mathscidoc:2207.43096

ASIACRYPT 2021, 92–121, 2021.12
Research on key mismatch attacks against lattice-based KEMs is an important part of the cryptographic assessment of the ongoing NIST standardization of post-quantum cryptography. There have been a number of these attacks to date. However, a unified method to evaluate these KEMs’ resilience under key mismatch attacks is still missing. Since the key index of efficiency is the number of queries needed to successfully mount such an attack, in this paper, we propose and develop a systematic approach to find 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 a certain Shannon entropy. The optimal BRT approach also enables us to understand why, for some lattice-based NIST candidate KEMs, there is a big gap between the theoretical bounds and bounds observed in practical attacks, in terms of the number of queries needed. This further leads us to propose a generic improvement method for these existing attacks, which are confirmed by our experiments. Moreover, our proposed method could be directly used to improve the side-channel attacks against CCA-secure NIST candidate KEMs.
No keywords uploaded!
[ Download ] [ 2022-07-15 11:37:55 uploaded by dingjt ] [ 82 downloads ] [ 0 comments ]
@inproceedings{yue2021a,
  title={A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs},
  author={Yue Qin, Chi Cheng, Xiaohan Zhang, Yanbin Pan, Lei Hu, and Jintai Ding},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715113755851309676},
  booktitle={ASIACRYPT 2021},
  pages={92–121},
  year={2021},
}
Yue Qin, Chi Cheng, Xiaohan Zhang, Yanbin Pan, Lei Hu, and Jintai Ding. A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs. 2021. In ASIACRYPT 2021. pp.92–121. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715113755851309676.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved