签名生成装置及签名验证装置

摘要

提供一种能够可靠地防止发生不适当的签名验证错误的签名生成装置及签名验证装置。签名生成装置(110)具备签名生成部(114)，该签名生成部(114)使用私钥计算对于消息m的签名矢量(s，t)，生成签名数据S，该签名数据S表示能够确定多项式s的多项式sl、sh、和作为将多项式t用q除时的商的多项式th。签名验证装置(120)具备签名验证部(124)，该签名验证部(124)使用签名数据S所表示的多项式sl、sh，将利用私钥对消息数据m计算出的签名矢量(s，t)中的多项式s复原，并且使用对签名数据S所表示的多项式th乘以q后的结果，将多项式t复原，来验证该签名矢量(s，t)。

主权项

一种签名生成装置，按照签名方式生成对于消息数据的签名数据，其特征在于，上述签名方式包括：密钥生成步骤，环R是加法、减法、乘法以及表示元的大小的范数已被定义的N维排列的集合，使用环R和正整数q，生成上述环R的元f、g以及f(mod q)的倒数即元Fq，并生成以q为模与上述元g及上述元Fq的积同余的元h，来作为公钥，生成满足f×G-g×F＝q的F、G，并生成由上述4个元f、g、F、G构成的组{f，g，F，G}，来作为私钥，这里，f(mod q)表示将f用q除后的余数，×表示环R的乘法运算；签名生成步骤，使用上述私钥生成对于上述消息数据的、作为上述环R的元的上述签名数据；和签名验证步骤，使用上述公钥验证上述签名数据；上述签名生成装置具备：签名矢量生成单元，利用上述私钥，计算对于上述消息数据的、由上述环R的元s、t构成的签名矢量；和签名数据生成单元，生成上述签名数据，上述签名数据表示能够确定上述元s的上述环R的第1元、和将上述元t用q除时的商即上述环R的第2元。