如何将信息转化为多项式？

Question

我正在做一个必须实现NTRUEncrypt公钥密码系统的项目。根据他们的加密指南，这是第一步-- "Alice，他想向Bob发送一条秘密消息，将她的消息以多项式m的形式，其系数{-1,0,1}“。我想知道我怎样才能把我的信息变成多项式。谢谢。

Answer 1

我在NTRU工作，所以我很高兴看到这种兴趣。

IEEE标准1363.1-2008指定了如何使用最新的参数集实现NTRUEncrypt。它为二进制->三进制转换指定的方法是：

按如下方式将每个三位数量转换为两个三值系数，并将产生的三位量串联起来以获得输出。

{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}

皈依：

将每组两个三元系数转换为三位，如下所示，并将产生的比特量串联起来以获得输出：

{0, 0} -> {0, 0, 0}
{0, 1} -> {0, 0, 1}
{0, -1} -> {0, 1, 0}
{1, 0} -> {0, 1, 1}
{1, 1} -> {1, 0, 0}
{1, -1} -> {1, 0, 1}
{-1, 0} -> {1, 1, 0}
{-1, 1} -> {1, 1, 1}
{-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}

请注意，要安全地加密消息，不能简单地将消息转换为三进制并应用原始NTRU加密。需要在加密之前对消息进行预处理，加密后再对消息进行后处理，以防止活动攻击者修改正在传输的消息。必要的处理在IEEE 1363.1-2008中指定，并在我们2003年的论文"NAEP:存在解密失败时的可证明安全性“(可从http://www.ntru.com/cryptolab/articles.htm#2003_3获得，但请注意此描述是针对二进制多项式而不是三进制)中讨论。

希望这能有所帮助。

@Bert:在不同的时候，我们都推荐二元或三次多项式。三次多项式允许同样的安全性和较短的密钥。然而，在过去，我们认为二元多项式允许q(大模数)为256。这对于8位处理器来说很有吸引力。从那时起，我们就已经确定，取q= 256会降低安全性，这是不可接受的(具体来说，这使得解密失败的可能性太大)。由于我们不再以小Q作为目标，所以我们可以利用三次多项式来给出更小的键。