题目：Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures

报告人：Prof. Phong Nguyen (INRIA, France and Tsinghua University, China)

摘要：

    There is growing interest in lattice cryptography, but from a practical point of view, only one lattice signature scheme is competitive with standard signatures: NTRUSIGN, designed in 2003. The basic version of NTRUSIGN was broken by Nguyen and Regev in 2006: one can efficiently recover the secret key from about 400 signatures. However, countermeasures have been proposed to repair the scheme, such as the perturbation used in NTRUSIGN standardization proposals, and the deformation proposed by Hu et al. at IEEE Trans. Inform. Theory in 2008. These two countermeasures were claimed to prevent the NR attack. Surprisingly, we show that these two claims are incorrect by revisiting the NR gradient-descent attack: the attack is much more powerful than previously expected, and breaks both countermeasures in practice, after suitable optimization. More precisely, the Nguyen-Regev algorithm for learning a parallelepiped is heuristically able to learn more complex objects, such as zonotopes and deformed parallelepipeds. As a concrete application, we recover the NTRUSIGN secret key in a few hours, using 8,000 signatures for the original NTRUSIGN-251 scheme with one perturbation submitted to IEEE P1363 in 2003, or 6,000 signatures for the latest 80-bit- security parameter set proposed in 2010.

    This is joint work with Leo Ducas (ENS, France). The talk will cover both the Nguyen-Regev EUROCRYPT '06 article and the new Ducas-Nguyen article. No prior knowledge of NTRUSIGN is required.

报告人简介：

    Phong Nguyen obtained his PhD in 1999, and has been a research director at INRIA since 2008, and a guest professor at Tsinghua University since Fall 2011. His main expertise is public-key cryptanalysis and algorithmic number theory, including lattice algorithms and their applications. He received the Best Paper Award at EUROCRYPT '06, the ERCIM Cor Baayen Award in 2001, and has published 18 articles at CRYPTO/EUROCRYPT. He is associate editor of the Journal of Cryptology and the Journal of Mathematical Cryptology, and regularly participates to the Program Committees of CRYPTO, EUROCRYPT and ASIACRYPT: he was invited speaker at EUROCRYPT '11, and will serve as program co-chair of EUROCRYPT '13 and EUROCRYPT '14.

时间：2012年5月14日(星期一) 上午 10:00

地点：中国科学院信息工程研究所3号楼3221室