往事随风：NTRU密码方案

陈智罡

尽管NTRU的往事随风，但是NTRU现在依然活跃于密码学的舞台上，而且非常的独特。

这篇博客的内容来自于Jeff  Hoffstein在今年欧密会上的特邀谈话。我觉得非常有趣，因为回顾历史本身就是一件值得回味的事情，看看过去，能够借鉴于今天。

1994年Jeff参加了 Goldfeld举办的一个讲座，这个讲座是关于从数论中获得的一个单向函数问题，该单向函数基于claw-free的置换。Jeff注意到这个问题与特定的L-series相关，于是他开始思考，用这样的构造方法还能够得到什么？是能够构造公钥加密方案还是仅仅是密钥交换协议？至今这个问题他也没有得到答案，但是这个开放问题最终却导致NTRU密码方案的诞生。

Jeff首先思考限制多项式，即将多项式模q，以及如何证明一个多项式的知识不会泄露多项式本身。用线性代数的知识可以解决他最初大部分的想法，但是他最终考虑使用短的多项式，即多项式的系数都是有界的。使用这些短的多项式，打破方案就意味着解决了CVP问题（靠近向量问题）。而解决CVP问题需要用到格基约减算法，当时人们相信LLL算法对于大多数的应用是无能为力的，包括对于一些特殊形式和形状的格。

下一步就是考虑使用一个紧凑的环结构。使用多项式模x^n-1代替多项式模q，于是就获得了NTRU环结构。这样多项式的乘积就对应于卷积，反过来对应于傅里叶变换。基于“短的多项式乘以短的多项式还是短的多项式”的思想，Jeff和他的合作者将短多项式的知识证明融入到数字签名方案中，但是像许多随后的格方案一样，它泄露了信息。直到2009年VadimLyubashevsky使用拒绝取样修复了这个漏洞。

下一个观察结果是，对于大部分多项式f，可以在该环结构中发现一个该多项式的逆。而且对于短多项式f和g，计算f/g的结果，看上去是随机的。有了这些准备，就可以建立NTRU了。Jeff 联合JillPipher和Joe Silverman，考虑如何量化安全和选择参数。他们很清楚使用组合观点能够有效的打破他们的方案，还有Odlyzko的Meet-In-The-Middle攻击方法。但是最大的问题来自于格攻击。例如像LLL和BKZ等格基约减算法能够在实践中工作的很好，但是对这些格基约减算法为什么能够工作的很好却没有一个清楚的认识。96年Crypto的rumpsession会议上，Jeff呈现了他们的NTRU方案，希望得到一些建议以及如何提高方案及参数，还有安全上的隐患。但是他们发现一些密码学家很愤怒，因为他们认为Jeff自己没有做出合适的安全分析却来呈现一个未完成的方案。

在97年的欧密会上，Don Coppersmith 和 AdiShamir发表了对NTRU格攻击的论文，这是历史上仅有的一次，方案的安全性分析先于比方案本身的发表。他们声称LLL很容易解决NTRU所基于的格问题。因为这个原因，NTRU被97年的欧密会拒稿了，谁会接受一个被攻破的方案呢？

但是Jeff并没有被问题吓倒。事实上，他相信LLL算法能够攻破他们的方案是由于格维数低的原因。由于NTRU有效的环结构，所以增长格的维数能够以极低的代价增长密钥尺寸。于是Jeff他们开始测试各种参数，在这期间有大量的关于NTRU的论文出现。在97、98年他们公开发出挑战，然而只有热身的挑战被破解。

后来，Gentry, Peikert and Vaikuntanathan引入了高斯取样算法，然后Stehlé and Steinfeld展示了，对NTRU稍做修改可以获得基于LWE上的可证明安全的方案。

由于NTRU本身的环结构特征，其本身就是一个somewhat同态方案，能够用于构造全同态加密方案。尽管NTRU在以往存在一些问题，但是目前在其相关领域被人们广泛研究。Jeff结束了他的谈话。

最后session主席PhongNguyen问Jeff，如果NTRU以前不存在的话，是否NTRU会被今天的欧密会接受。Jeff回答，可能不会。