Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	吴保峰，中国科学院信息工程研究所
Inviter:	潘彦斌
Title:	Solving hidden number problem with lattice sieving
Language:	Chinese
Time & Venue:	2023.04.27 09:00-10:00 思源楼713
Abstract:	Lattice reduction algorithms have been proved to be one of the most powerful and versatile tools in public key cryptanalysis. In this talk, we primarily concentrate on lattice attacks against (EC)DSA with nonce leakage via some side-channel analysis. In fact, the main task lies in solving the hidden number problem (HNP). Previous works relying on lattice reduction algorithms such as LLL and BKZ will finally lead to the “lattice barrier”: lattice algorithms become infeasible when only fewer nonce is known. Recently, Albrecht et al. introduced lattice algorithms augmented with a predicate and broke the lattice barrier (Eurocrypt 2021). We improve their work in several aspects. Our algorithm outperforms the state-of-the-art lattice attacks for existing records such as 3-bit nonce leakage for a 256-bit curve and 2-bit nonce leakage for a 160-bit curve and breaks some lattice records which are thought infeasible previously. We also give the first lattice attack against ECDSA with a single-bit nonce leakage.