签名及验证方法、签名生成装置及签名验证装置

摘要

提供签名生成装置及签名验证装置，可以对抗在NTRUSign签名方式中，通过分析多个签名文(消息数据和签名的对)来求取私钥的抄本攻击(transcript attack)。签名生成装置计算消息数据的散列值向量H，对消息数据的散列值向量H，加上基于保密分布的向量，计算变换散列值向量H′，在根据私钥基底向量确定的网格上，求取与变换散列值向量H′最接近的网格点，将其作为签名向量S。签名验证装置判断消息数据的散列值向量H和签名向量S之间的距离是否为L′以内，在L′以内时，将消息数据认作合法。

主权项

一种签名生成及签名验证方法，被具备保密存储机构的签名生成装置和签名验证装置使用，该保密存储机构保密地存储私钥向量，并存储表示比第1大小小的多个备选向量所属于的范围的分布，该方法将数据分割为多个并作为多维的向量来表现，以最短向量问题或者近似最短向量问题为安全性的根据，对对象数据签名并进行验证，其特征为，包含：取得步骤，取得对象数据；变换步骤，利用比上述第1大小小的保密的干扰向量，对取得的对象数据进行变换，生成变换向量；签名步骤，在将上述私钥向量确定为基底向量的网格上，求取与上述变换向量最接近的网格点，生成对于上述变换向量的签名向量，将上述签名向量的一部分作为签名数据；验证步骤，使用公钥向量和上述签名数据，将上述签名向量复原，验证由上述对象数据得到的向量与复原后的上述签名向量之间的距离是否为比上述第1大小大的第2大小以下；以及输出步骤，在是第2大小以下时，输出表示验证已成功的成功信息；上述分布包含于以上述第1大小为半径的超球内，上述分布的数据结构通过分布表来表示，各向量通过多项式来表现，上述分布表包含上限值、下限值以及多项式，在上述变换步骤，随机选择上限值以下且下限值以上的值，将选择的值乘到上述多项式，得到多项式，并将得到的多项式作为表示上述干扰向量的多项式而生成。