用格说明NTRU

Question

我研究了一些与NTRU有关的论文。这些文献都将NTRU描述为一种基于格的密码体制，但没有找到从格的角度来说明NTRU算法的文献。如果有人用格描述NTRU算法，以及该算法是如何基于最短向量问题(SVP)的，将会有很大的帮助。

Answer 1

目前，还没有关于NTRU是基于格问题的正式证明，但是您可以在Ber09的第5.2节中从格的角度找到NTRU的描述。对于基于格的NTRU攻击，您可以查看HPS98。然而，有一个可以证明的安全变体NTRU，它最终是基于SVP问题SS11的硬度。

参考文献：

Ber09后量子密码学(2009年)。斯普林格柏林海德堡。

HPS98 Hoffstein，J.皮弗，J.，& Silverman，J. H.NTRU:一种基于环的公钥密码体制。算法数论(第267-288页)

SS11 Stehlé，D. & Steinfeld，R. (2011年)。使NTRU与理想格上的最坏情况问题一样安全。“密码学进展-欧洲密码”，2011年(第27-47页)。