如何与NTRU签约？

Question

我正在考虑实现NTRU，但我注意到，虽然加密/解密算法似乎比较成熟，并且有很好的文档证明，但关于如何使用NTRU进行签名的信息相对较少(所提议的方法显然泄露了有关私钥的信息)。

我的问题是，为什么我不能用同样的方式签名RSA消息，即发送者用他的私钥“解密”一个已知的数量，这样接收者就可以“加密”签名并容易地验证它。(当然还有任何必要的填充。)

这样做有什么缺点吗？

Answer 1

这不可能。正是因为RSA的独特特性，它才能适用于RSA，但是大多数其他的非对称方案并不是这样工作的。对于其他方案，签名和加密算法可能完全不同，可能没有办法用私钥“加密”或用公钥进行“签名”。

Answer 2

我是安全创新公司的首席科学家，该公司收购了NTRU，同时也是NTRUSign的合著者之一。

NTRUEncrypt和NTRUSign的区别在于它们如何使用晶格。所有的NTRU算法都是以一种称为理想格的特殊形式的闭向量问题为基础的。

对于NTRUEncrypt，加密方法基本上是：

• 选择点阵中的随机点
• 将消息添加到该点，作为一个小扰动。

然后，解密是映射回格点并通过从密文中减去格点来恢复消息的问题。这只是因为消息被选择为具有特定形式的消息，这意味着返回到点阵点的映射总是有效的。嗯，几乎总是--你可能读过NTRU的解密失败。当返回到点阵点的映射不起作用时，就会发生这种情况，但我们可以控制它们的概率。但是保持这个想法。

对于NTRUSign，签名方法是：

• 将消息散列到空间中的一个随机点
• 查找靠近该散列点的格点，并将其发布为签名。

核查是：

• 将消息散列到空间中的同一点
• 验证签名点是一个格点，并且接近消息。

这就是解密和签名的区别。解密只适用于具有一种非常特殊的结构的消息，这种结构是由加密产生的。对于解密，这些消息来自加密，所以这不是一个问题。但是对于签名，“消息”(实际上是散列)来自哈希函数，创建一个具有正确结构但不允许任何人签名的散列函数是非常困难的。要使用的明显的散列函数是将消息随机映射到包含格的整数向量空间，对于这个散列函数，解密根本不起作用。