信息处理设备、密钥生成设备、签名验证设备、信息处理方法、签名生成方法和程序

摘要

提供了用于实现能够进行关于选定消息攻击的安全认证的MPKC签名方法的电子签名系统。一种信息处理装置，包括：第一逆变换单元，该第一逆变换单元通过第一秘密多项式T的逆变换T-1将包括由n个数所组成的元素的有限环Kn的元素y变换成有限环Kn的元素y′；元素计算单元，该元素计算单元将通过第一逆变换单元所获得的有限环Kn的元素y′看作有限环K的n次扩展A的元素Y，并且，通过利用元素Y来计算由预定多变量多项式所表示的映射f：A→A的原像的元素X∈{Z∈A|f(Z)＝Y}；元素选择单元，该元素选择单元以与原像的元素数α成正比的概率p选择原像的一个元素X，并且，以概率(1-p)输出异常值；以及第二逆变换单元，该第二逆变换单元将此处所选择的元素X看作有限环Kn的元素x′，并且，通过第二秘密多项式S的逆变换S-1将限环Kn的元素x′变换成限环Kn的元素x。

主权项

一种信息处理装置，包括：第一逆变换单元，该第一逆变换单元通过第一秘密多项式T的逆变换T‑1，将包括由n个数所组成的元素的有限环Kn的元素y变换成所述有限环Kn的元素y′；元素计算单元，该元素计算单元将通过所述第一逆变换单元所获得的有限环Kn的元素y′看作有限环K的n次扩展A的元素Y，并且，通过利用所述元素Y来计算由预定多变量多项式表示的映射f(f：A→A)的原像的元素X∈{Z∈A|f(Z)＝Y}；元素选择单元，该元素选择单元以与所述原像的元素数α成正比的概率p，选择由所述元素计算单元所计算的所述原像的一个元素X，并且，以概率(1‑p)输出异常值；以及第二逆变换单元，该第二逆变换单元将由所述元素选择单元所选择的所述元素X看作所述有限环Kn的元素x′，并且，通过第二秘密多项式S的逆变换S‑1，将所述有限环Kn的元素x′变换成所述有限环Kn的元素x。