CN103748832A - 签名验证设备、签名验证方法、程序和记录介质 - Google Patents

Abstract

本发明提供了一种签名验证设备，包括：签名获取单元，被配置为获取数字签名，所述数字签名包含：第一信息，基于多阶多元多项式组F=(f₁,...,f_m)、签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要用于基于文件M、所述多阶多元多项式组F和向量y验证所述第一信息是利用签名密钥s生成的；以及签名验证单元，被配置为通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性。所述签名验证单元顺序利用获取的预定条数的第二信息恢复所述第一信息，并在其中第二信息变得不需要的不需要阶段，擦除在恢复处理中不需要的第二信息。

Description

签名验证设备、签名验证方法、程序和记录介质

技术领域

本发明涉及签名验证设备、签名验证方法、程序和记录介质。

背景技术

随着信息处理技术和通信技术的快速发展，文件被快速数字化，无论该文件是公众的还是私人的。通过数字化这些文件，很多个人和公司对电子文件的安全性管理给予较大关注。响应于该关注的增加，在各个领域中已经积极研究了针对诸如窃取或伪造电子文件的篡改行为的措施。关于对电子文件的窃取，例如通过加密电子文件确保安全。另外，关于对电子文件的伪造，例如通过使用数字签名确保安全。然而，当将使用的加密或数字签名不具有高防篡改性时，不能确保足够的安全性。

使用数字签名用于指定电子文件的作者。从而，数字签名应仅能够由电子文件的作者生成。如果恶意第三方能够生成相同的数字签名，该第三方能够冒充电子文件的作者。即，由恶意第三方伪造电子文件。关于用于防止该伪造的数字签名的安全性已经表达了各种意见。作为目前广泛使用的数字签名方案，已知例如RSA签名方案和DSA签名方案。

RSA签名方案采用“大合数的质因数分解（下文中为质因数分解问题）的困难性”作为安全性基础。另外，DSA签名方案采用“求解离散对数问题的困难性”作为安全性基础。这些基础基于不存在通过使用传统计算机有效求解质因数分解问题和离散对数问题的算法。即，上述困难性暗示了传统计算机的计算困难性。然而，据说，当使用量子计算机时，可以有效计算质因数分解问题和离散对数问题的解。

类似于RSA签名方案和DSA签名方案，目前采用的数字签名方案和公共密钥认证方案的多种方案中也采用质因数分解问题或离散对数问题的困难性作为安全性基础。从而，如果量子计算机投入实用，该数字签名方案和公共密钥认证方案的安全性将不能确保。从而，期待实现新的数字签名方案和公共密钥认证方案，其采用不同于可通过量子计算机容易解出的问题（诸如质因数分解问题和离散对数问题）的问题作为安全性基础。作为不能通过量子计算机容易解出的问题，存在关于例如多元多项式的问题。

例如，作为采用多元多项式问题作为安全性基础的数字签名方案，已知基于Matsumoto-Imai(MI)密码、隐藏场方程(HFE)密码、Oil-Vinegar(OV)签名方案、以及Tamed Transformation Method(TTM)密码的数字签名方案。例如，在下面的非专利文献1和2中公开了基于HFE的数字签名方案。

引用列表

非专利文献

非专利文献1：Jacques Patarin,Asymmetric Cryptography witha Hidden Monomial,CRYPTO1996,pp.45-60。

非专利文献2：Patarin,J.,Courtois,N.,and Goubin,L.,QUARTZ,128-Bit Long Digital Signatures,In Naccache,D.,Ed。Topics in Cryptology-CT-RSA2001(San Francisco,CA,USA,April2001),vol.2020of Lecture Notes in Computer Science,Springer-Verlag.,pp.282-297。

发明内容

技术问题

如上所述，多元多项式问题是即使在使用量子计算机时也难于解出的称为NP困难问题的问题示例。通常，使用以HFE为典型的多元多项式问题的公开密钥认证方案等使用具有特殊陷门的多阶多元联立方程。例如，提供关于x₁,…,x_n的多阶多元联立方程F(x₁,…,x_n)=y和线性变换A和B，并秘密地管理线性变换A和B。在该情况中，多阶多元联立方程F和线性变换A和B为陷门。

已知陷门F、A和B的实体可以解出关于x₁,…,x_n的方程B(F(A(x₁,…,x_n)))=y’。另一方面，不知道陷门F、A和B的实体不能解出关于x₁,…,x_n的方程B(F(A(x₁,…,x_n)))=y’。通过使用该机制，可以实现采用求解多阶多元联立方程的困难性作为安全性基础的公开密钥认证方案和数字签名方案。

如上所述，为了实现所述公开密钥认证方案或数字签名方案，需要准备满足B(F(A(x₁,…,x_n)))=y的特殊多阶多元联立方程。另外，在签名生成时，需要解出多阶多元联立方程F。为此，可用的多阶多元联立方程F已经限制于较容易解出的方程。即，在过去的方案中，仅仅使用了可以容易解出的三个函数（陷门）B、F和A的组合形式的多阶多元联立方程B(F(A(x₁,…,x_n)))=y，从而难于确保足够的安全性。

根据上述情况，本发明被设计用于提供一种新颖且改善的签名验证设备、新颖且改善的签名验证方法、新颖且改善的程序、以及新颖且改善的记录介质，其可以通过使用有效求解（陷门）的方式未知的多阶多元联立方程通过小的存储器实现有效并具有高安全性的数字签名方案的签名验证。

解决问题的技术方案

根据本发明的实施例，提供一种签名验证设备，包括：签名获取单元，被配置为获取数字签名，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kn的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式F组和向量y=(f₁(s),...,f_m(s))验证所述第一信息是利用签名密钥s生成的；以及签名验证单元，被配置为通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性。所述多元多项式F组和向量y为公开密钥。所述签名获取单元获取预定条数的第二信息。所述签名验证单元顺序利用获取的预定条数的第二信息恢复所述第一信息，并在其中第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

根据本发明的另一个实施例，提供一种签名验证方法，包括：获取数字签名的步骤，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性的步骤。所述多元多项式组F和向量y为公开密钥。在获取数字签名的步骤中，获取预定条数的第二信息。在验证所述正当性的步骤中，顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

根据本发明的另一个实施例，提供一种使得计算机实现以下功能的程序：获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kn的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性。所述多元多项式组F和向量y为公开密钥。所述签名获取功能获取预定条数的第二信息。所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

根据本发明另一个实施例，提供一种其中记录有程序的计算机可读记录介质，所述程序使得计算机实现：获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性。所述多元多项式组F和向量y为公开密钥。所述签名获取功能获取预定条数的第二信息。所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

发明的有益效果

根据上述本发明，可以利用有效求解（陷门）的方式未知的多阶多元联立方程通过小的存储器实现有效并具有高安全性的数字签名方案的签名验证。

附图说明

图1为描述关于公开密钥认证方案的算法结构的说明图；

图2为描述关于数字签名方案的算法结构的说明图；

图3为描述关于n遍公开密钥认证方案的算法结构的说明图；

图4为描述关于3遍公开密钥认证方案的有效算法的说明图；

图5为描述对关于3遍公开密钥认证方案的有效算法的并行化的说明图；

图6为描述关于5遍公开密钥认证方案的有效算法的示例的说明图；

图7为描述对关于5遍公开密钥认证方案的有效算法的并行化的说明图；

图8为描述将关于3遍公开密钥认证方案的有效算法修改为数字签名方案的算法的方法的说明图；

图9为描述将关于5遍公开密钥认证方案的有效算法修改为数字签名方案的算法的方法的说明图；

图10为描述散列函数结构的示例的说明图；

图11为用于描述关于基于3遍方案的数字签名方案的签名验证方法（通常安装方法）的说明图；

图12为用于描述关于基于3遍方案的数字签名方案的签名验证方法（存储器减少方法）的说明图；

图13为用于描述关于基于5遍方案的数字签名方案的签名验证方法（通常安装方法）的说明图；

图14为用于描述关于基于5遍方案的数字签名方案的签名验证方法（存储器减少方法）的说明图；

图15为描述从二进制随机数提取三进制随机数的方法（提取方法＃1）的说明图；

图16为描述从二进制随机数提取三进制随机数的方法（提取方法＃2）的说明图；

图17为描述从二进制随机数提取三进制随机数的方法（提取方法＃3）的说明图；

图18为描述从二进制随机数提取三进制随机数的方法（提取方法＃3）的说明图；

图19为描述从二进制随机数提取三进制随机数的方法（提取方法＃3）的说明图；

图20为描述用于有效替换多元多项式的系数的数据构造技术（构造技术＃1）的说明图；

图21为描述用于有效替换多元多项式的系数的数据构造技术（构造技术＃2）的说明图；以及

图22为描述能够执行根据本发明每个实施例的算法的信息处理设备的硬件配置示例的说明图。

具体实施方式

下文中，将参照附图详细描述本发明的优选实施例。注意，在该说明书和附图中，以相同的标号表示具有基本相同的功能和结构的元素，并省略重复的说明。

[说明流程]

这里，将简单描述下文说明本发明实施例的流程。首先，将参考图1描述公开密钥认证方案的算法结构。然后，将参考图2描述数字签名方案的算法结构。然后，将参考图3描述n遍公开密钥认证方案。

然后将参考图4和5描述关于3遍公开密钥认证方案的算法结构的示例。然后将参考图6和7描述关于5遍公开密钥认证方案的算法结构的示例。然后将参考图8和9描述将关于3遍和5遍公开密钥认证方案的有效算法修改为数字签名方案的算法的方法。

然后，将参考图10至14描述在执行关于本发明实施例的数字签名方案的算法时减少签名验证所需的存储器量的方法。然后，将参考图15至19描述从二进制随机数有效提取三进制随机数的方法。然后，将参照图20和21描述有效替换多元多项式的系数的方法。然后，将参考图22描述能够实现根据本发明实施例的每个算法的信息处理设备的硬件配置示例。最后，将简单描述本发明实施例的技术主旨的总结和从该技术主旨获得的有利操作效果。

（具体章节）

1.引言

1-1：公开密钥认证方案的算法

1-2：数字签名方案的算法

1-3：N遍公开密钥认证方案

2.关于3遍公开密钥认证方案的算法结构

2-1：具体算法结构的示例

2-2：并行算法结构的示例

3：关于5遍公开密钥认证方案的算法结构

3-1：具体算法结构的示例

3-2：并行算法结构的示例

4：对数字签名方案的修改

4-1：将3遍公开密钥认证方案修改为数字签名方案

4-2：将5遍公开密钥认证方案修改为数字签名方案

5：减少签名验证所需的存储器量的方法

5-1：散列函数的结构

5-2：应用于基于3遍方案的数字签名方案的示例

5-3：应用于基于5遍方案的数字签名方案的示例

6：从二进制随机数序列提取三进制随机数序列的方法

6-1：提取方法＃1（2比特分组）

6-2：提取方法＃2（无分组）

6-3：提取方法＃3（k比特分组）

6-3-1：基本结构

6-3-2：其它提取方法

7：有效替换多元多项式的系数的方法

7-1：基本确定

7-2：构造数据

7-2-1：构造技术＃1

7-2-2：构造技术＃2

7-2-3：构造技术＃3

8：硬件配置的示例

9：总结

<1.引言>

本发明的实施例涉及公开密钥认证方案和数字签名方案，其安全性基于解出多阶多元联立方程的困难性。然而，本文的实施例与诸如HFE数字签名方案的现有技术的技术不同，而是涉及使用缺乏有效解出方法（陷门）的多阶多元联立方程的公开密钥认证方案和数字签名方案。首先，将简要概述用于公开密钥认证方案的算法、用于数字签名方案的算法和n遍公开密钥认证方案。

[1-1：公开密钥认证方案的算法]

首先，将参考图1描述公开密钥认证方案的算法概述。图1为描述公开密钥认证方案的算法结构的说明图。

当一个人（证明者）通过使用公开密钥pk和秘密密钥sk说服另一个人（验证者）她是证明者本人时使用公开密钥认证。例如，使得验证者B知道证明者A的公开密钥pk_A。另一方面，由证明者A秘密管理证明者A的秘密密钥sk_A。根据公开密钥认证方案，认为知道对应于公开密钥pk_A的秘密密钥sk_A的人为证明者本人。

为了使得证明者A利用公开密钥认证设置向验证者B证明她是证明者A本人，证明者A通过交互协议向验证者B展示指示她知道对应于公开密钥pk_A的秘密密钥sk_A的证据。然后向验证者B展示指示证明者A知道秘密密钥sk_A的证据，并且在验证者B能够确认该证据的情况中，证明证明者A的有效性（即，证明者A是她本人的事实）。

然而，公开密钥认证设置要求以下条件以确保安全性。

第一条件为，“尽可能降低由没有秘密密钥sk的伪造者在执行交互协议时建立伪造的可能”。将满足第一条件称为“可靠性”。换句话说，可靠性表示，“在由不具有秘密密钥sk的伪造者以不可忽略的概率执行交互协议期间未建立伪造”。第二条件为，“即使执行交互协议，关于证明者A的秘密密钥sk_A的信息完全未泄漏给验证者B”。将满足第二条件称为“零知识性”。

安全地进行公开密钥认证包括使用同时表现可靠性和零知识性的交互协议。如果假设利用缺乏可靠性和零知识性的交互协议进行认证处理，将存在错误验证的明确机会和泄漏秘密密钥信息的明确机会，从而即使成功完成所述处理自身仍不能证明证明者的有效性。从而，如何确保会话协议的可靠性和零知识性的问题非常重要。

（模型）

在公开密钥认证方案的模型中，如图1所示，存在证明者和验证者两个实体。证明者通过使用密钥生成算法Gen生成对于证明者唯一的一对公开密钥pk和秘密密钥sk。然后，证明者通过使用利用密钥生成算法Gen生成的一对秘密密钥sk和公开密钥pk执行与验证者的交互协议。此时，证明者通过使用证明者算法P执行交互协议。如上所述，在交互协议中，证明者通过使用证明者算法P向验证者证明她拥有秘密密钥sk。

另一方面，验证者通过使用验证者算法V执行交互协议，并验证证明者是否拥有对应于该证明者已经公开的公开密钥的秘密密钥。即，验证者是验证证明者是否拥有对应于公开密钥的秘密密钥的实体。如上所述，从两个实体，即证明者和验证者，以及三个算法，即密钥生成算法Gen、证明者算法P和验证者算法V配置公开密钥认证方案的模型。

另外，尽管在下文中使用“证明者”和“验证者”的表达方式，但是这些表达方式严格表示实体。从而，执行密钥生成算法Gen和证明者算法P的主体是对应于实体“证明者”的信息处理设备。类似地，执行验证者算法V的主体是信息处理设备。这些信息处理设备的硬件配置例如如图10所示。即，通过CPU902基于记录在ROM904、RAM906、存储单元920、可移动记录介质928等上的程序执行密钥生成算法Gen、证明者算法P和验证者算法V。

（密钥生成算法Gen）

由证明者使用密钥生成算法Gen。密钥生成算法Gen是用于生成对于证明者唯一的一对公开密钥pk和秘密密钥sk的算法。通过密钥生成算法Gen生成的公开密钥pk被公开。另外，由验证者使用公开的公开密钥pk。另一方面，由证明者秘密地管理通过密钥生成算法Gen生成的秘密密钥sk。使用通过证明者秘密管理的秘密密钥sk以向验证者证明证明者拥有对应于公开密钥pk的秘密密钥sk。形式地，将密钥生成算法Gen表示为下面的公式（1），作为采用安全性参数1λ（λ为0以上的整数）作为输入并输出秘密密钥sk和公开密钥pk的算法。

[数学式1]

(sk，pk)←Gen(1^λ)

…(1)

（证明者算法P）

由证明者使用证明者算法P。证明者算法P是用于向验证者证明证明者拥有对应于公开密钥pk的秘密密钥sk的算法。换句话说，证明者算法P是采用公开密钥pk和秘密密钥sk作为输入并执行交互协议的算法。

（验证者算法V）

由验证者使用验证者算法V。验证者算法V是在会话协议期间验证证明者是否拥有对应于公开密钥pk的秘密密钥sk的算法。验证者算法V是接受公开密钥pk作为输入并根据会话协议的执行结果输出0或1（1比特）的算法。这里，验证者在验证者算法V输出0的情况中确定证明者无效并在验证者算法V输出1的情况中确定证明者有效。形式上，将验证者算法V表示为下面的公式（2）。

[数学式2]

0/1←V(pk)

…(2)

如上所述，实现有效公开密钥认证包括使交互协议满足可靠性和零知识性两个条件。然而，证明证明者拥有秘密密钥sk涉及，证明者执行依赖于秘密密钥sk的程序，并且在把结果通知给验证者之后，使得验证者基于通知的内容执行验证。执行根据秘密密钥sk的程序以确保可靠性。同时，不应向验证者泄漏任何关于秘密密钥sk的信息。为此，巧妙地设计上述密钥生成算法Gen、证明者算法P和验证者算法V以满足这些要求。

从而前述总结了公开密钥认证方案中的各个算法。

[1-2：数字签名方案的算法]

下面，将参考图2概述数字签名方案的算法。图2为用于概述数字签名方案的算法的说明图。

与纸质文件不同，不可能对数字化数据物理地签名或粘贴封印。为此，证明数字数据的创建者涉及产生类似于对纸质文档物理签名或粘贴封印的效果的电子设置。该设置为数字签名。数字签名指将给定数据与仅数据创建者知道的签名数据关联、将签名数据提供到接收者、并在接收者端验证签名数据的设置。

（模型）

如图2所示，在数字签名方案的模型中存在签名者和验证者的两个本体。另外，数字签名方案的模型由三个算法构成：密钥生成算法Gen、签名生成算法Sig、和签名验证算法Ver。

签名者使用密钥生成算法Gen生成对于签名者唯一的成对的签名密钥sk和验证密钥pk。签名者还使用签名生成算法Sig以生成附到消息M的数字签名q。换句话说，签名者是将数字签名附到消息M的实体。同时，验证者使用签名验证算法Ver以验证附到消息M的数字签名。换句话说，验证者是验证数字签名q以确认消息M的创建者是否是签名者的实体。

注意，虽然在下文中使用术语“签名者”和“验证者”，这些术语最终表示实体。从而，执行密钥生成算法Gen和签名生成算法Sig的主体是对应于“签名者”实体的信息处理设备。类似地，执行签名验证算法Ver的主体是信息处理设备。这些信息处理设备的硬件配置例如如图28所示。换句话说，通过诸如CPU902的装置基于记录在诸如ROM904、RAM906、存储单元920或可移动记录介质928的装置上的程序执行密钥生成算法Gen、签名生成算法Sig和签名验证算法Ver。

（密钥生成算法Gen）

由签名者使用密钥生成算法Gen。密钥生成算法Gen是用于生成对于签名者唯一的成对的签名密钥sk和验证密钥pk的算法。通过密钥生成算法Gen生成的验证密钥pk被公开。同时，签名者对于由密钥生成算法Gen生成的签名密钥sk保密。然后使用签名密钥sk以生成附到消息M的数字签名q。例如，密钥生成算法Gen接受安全性参数1p（其中p是大于或等于0的整数）作为输入，并输出签名密钥sk和验证密钥pk。在该情况中，密钥生成算法Gen可以以下面的公式（3）形式地表示。

[数学式3]

(sk，pk)←Ggn(1^λ)

…(3)

（签名生成算法Sig）

由签名者使用签名生成算法Sig。签名生成算法Sig是生成将被附到消息M的数字签名q的算法。签名生成算法Sig是接受签名密钥sk和消息M为输入并输出数字签名q的算法。签名生成算法Sig可以下面的公式（4）形式地表示。

[数学式4]

σ←Sig(sk，M)

…(4)

（签名验证算法Ver）

由验证者使用签名验证算法Ver。签名验证算法Ver是验证数字签名q对于消息M是否为有效数字签名的算法。签名验证算法Ver是接受签名者的验证密钥pk、消息M和数字签名q为输入并输出0或1（1比特）的算法。签名验证算法Ver可以以下面的公式（5）形式地表示。这里，验证者在签名验证算法Ver输出0的情况中（其中验证密钥pk否定消息M和数字签名q的情况）确定数字签名q无效，并在签名验证算法Ver输出1的情况中（其中验证密钥pk接受消息M和数字签名q的情况）确定数字签名q有效。

[数学式5]

0/1←Ver(pk，M，σ)

…(5)

从而前述概述了数字签名方案中的算法。

[1-3：N遍公开密钥认证方案]

然后，将参考图3描述n遍公开密钥认证方案。图3为示出n遍公开密钥认证方案的说明图。

如上所述，公开密钥认证方案是在交互协议期间向验证者证明证明者拥有对应于公开密钥pk的秘密密钥sk的认证方案。另外，交互协议必须满足可靠性和零知识性的两个条件。为此，如图3所示，在交互协议期间，证明者和验证者在执行各自的处理的同时都n次交换信息。

在n遍公开密钥认证方案的情况中，证明者执行利用证明者算法P的处理（运算＃1），并将信息T₁发送到验证者。随后，验证者执行利用验证者算法V的处理（运算＃2），并将信息T2发送到证明者。对于k=3至n连续执行该执行和处理和对信息Tk的发送，最后，执行处理（运算＃n+1）。将这样n次发送和接收信息称为“n遍”公开密钥认证方案。

从而上文描述了n遍公开密钥认证方案。

<2.关于3遍公开密钥认证方案的算法结构>

下文将描述关于3遍公开密钥认证方案的算法。注意，在下文的描述中，在一些情况中还可以将3遍公开密钥认证方案表示为“3遍方案”。

[2-1：具体算法结构的示例（图4）]

首先，将参考图4描述关于3遍方案的具体算法结构的示例。图4为描述关于3遍方案的具体算法结构的说明图。这里，将描述其中使用一对二次多项式(f₁(x),...,f_m(x))作为公开密钥pk的一部分的情况。这里，假设如下面的公式（6）表示二次多项式f_i(x)。另外，将向量(x₁,...,x_n)表示为x，并将一对二次多元多项式(f₁(x),...,f_m(x))表示为多元多项式F（x）。

[数学式6]

$f_i(x_1,...,x_n)=\underset{j,k}{\mathrm{\&Sigma;}}{a}_{\mathrm{ijk}}{x}_j{x}_k+\underset{j}{\mathrm{\&Sigma;}}{b}_{\mathrm{ij}}{x}_j...\left(6\right)$

另外，可以以下面的公式（7）表示所述一对二次多项式(f₁(x),…,f_m(x))。另外，A₁,…,A_m为n×n矩阵。另外，b₁,…,b_m的每个为n×1向量。

[数学式7]

$F\left(x\right)=\left(\begin{array}{c}{f}_1\left(x\right)\\ .\\ .\\ .\\ f_m\left(x\right)\end{array}\right)=\left(\begin{array}{c}{x}^T{A}_{1}x+b_1^{T}x\\ .\\ .\\ .\\ x^T{A}_{m}x+b_m^{T}x\end{array}\right)...\left(7\right)$

当使用该表达式时，可以如下面的公式（8）和公式（9）中表示多元多项式F。从下面的公式（10），可以容易地确定满足该表达式。

[数学式8]

F(x+y)=F(x)+F(y)+G(x，y)

…(8)

$G(x,y)=\left(\begin{array}{c}{y}^T(A_1^T+A_1)x\\ .\\ .\\ .\\ y^T(A_m^T+A_m)x\end{array}\right)...\left(9\right)$

$\begin{array}{c}{f}_1(x+y)={(x+y)}^T{A}_l(x+y)+b_l^T(x+y)\\ =x^T{A}_{l}x+x^T{A}_{l}y+y^T{A}_{l}x+y^T{A}_{l}y+b_l^{T}x+b_l^{T}y\\ =f_l\left(x\right)+f_l\left(y\right)+x^T{A}_{l}y+y^T{A}_{l}x\\ =f_l\left(x\right)+f_l\left(y\right)+x^T{\left(A_l^T\right)}^{T}y+y^T{A}_{l}x\\ =f_1\left(x\right)+f_{l}y+{\left(A_l^{T}x\right)}^{T}y+y^T{A}_{l}x\\ =f_l\left(x\right)+f_l\left(y\right)+y^T\left(A_l^{T}x\right)+y^T{A}_{l}x\\ =f_l\left(x\right)+f_l\left(y\right)+y^T(A_l^T+A_l)x\end{array}...\left(10\right)$

当通过这样将F(x+y)分为关于x的第一部分、关于y的第二部分、以及关于x和y二者的第三部分时，对应于第三部分的项G(x,y)变为相对于x和y双线性。下文中，还将项G（x,y）表示为双线性项。使用该特性能够构造有效率的算法。

例如，使用作为集合Kⁿ的元素的向量t₀和作为集合K^m的元素的向量e₀把用于掩蔽（mask）多元多项式F(x+r)的多元多项式F₁(x)表示为F₁(x)=G(x,t₀)+e₀。在该情况中，将多元多项式F(x+r₀)和G（x）的和表示为下面的公式（11）。这里，当t₁=r₀+t₀、e₁=F(r₀)+e₀时，可以通过作为集合Kⁿ的元素的向量t₁和作为集合K^m的元素的向量e₁表示多元多项式F₂(x)=F(x+r₀)+F₁(x)。为此，当设置F₁(x)=G(x,t₀)+e₀时，可以通过使用Kⁿ中的向量和K^m中的向量表示F₁和F₂，从而可以实现其中用于通信所需的数据尺寸较小的有效率的算法。

[数学式9]

$\begin{array}{c}F(x+r_0)+F_1\left(x\right)\\ =F\left(x\right)+F\left(r_0\right)+G(x,r_0)+G(x,t_0)+e_0\\ =F\left(x\right)+G(x,r_0+t_0)+F\left(r_0\right)+e_0\end{array}...\left(11\right)$

另外，从F₂（或F₁）完全未泄漏关于r₀的信息。例如，即使在给定e₁和t₁(或e₀和t₀)时，只要e₀和t₀(或e₁和t₁)未知，则关于r₀的信息完全未知。因此，确保了零知识性。下文中，将描述基于上述逻辑构造的3遍方案的算法。这里将描述的3遍方案的算法由将在下文描述的密钥生成算法Gen、证明者算法P和验证者算法V构成。

（密钥生成算法Gen）

密钥生成算法Gen生成在环k中定义的m个多元多项式f₁(x₁,...,x_n),...,f_m(x₁,...,x_n)和作为集合Kn的元素的向量s=(s1,...,sn)。然后，生成算法Gen计算y=(y₁,...,y_m)←(f₁(s),...,f_m(s))。另外，生成算法Gen把(f₁(x₁,...,x_n),...,f_m(x₁,...,x_n),y)设置到公开密钥pk中，并将s设置为秘密密钥。下文中，将向量(x₁,...,x_n)表示为x，并将一对多元多项式(f₁(x),...,f_m(x))表示为F（x）。

（证明者算法P、验证者算法V）

下文将参考图4描述在交互协议期间通过证明者算法P执行的处理和通过验证者算法V执行的处理。在前述交互协议期间，证明者完全没有将关于秘密密钥s的信息泄漏给验证者并对验证者表示“她本人知道满足y=F(s)的s”。另一方面，验证者验证证明者是否知道满足y=F(s)的s。假设使得验证者知道公开密钥pk。另外，假设由证明者秘密地管理秘密密钥s。将参考图4所示的流程图进行描述。

运算＃1：

如图4所示，证明者算法P首先随机地生成作为集合Kⁿ的元素的向量r₀、t₀、以及作为集合K^m的元素的向量e₀。随后，证明者算法P计算r₁←s-r₀。该计算等同于通过向量r₀掩蔽秘密密钥s。另外，证明者算法P计算t₁←r₀-t₀。随后，证明者算法P计算e₁←F(r₀)-e₀。

运算＃1（继续）：

随后，证明者算法P计算c₀←H(r₁,G(t₀,r₁)+e₀)。随后，证明者算法P计算c₁←H(t₀,e₀)。随后，证明者算法P计算c₂←H(t₁,e₁)。在运算＃1中生成的消息(c₀,c₁,c₂)被发送到验证者算法V。

运算＃2：

在接收到消息（c₀,c₁,c₂）时，验证者算法V从三个验证模式中选择将使用的验证模式。例如，验证者算法V可以从表示验证模式的三个数值{0,1,2}中选择数值，并在要求Ch中设置选择的数值。该要求Ch被发送到证明者算法P。

运算＃3：

在接收到要求Ch时，证明者算法P响应于接收的要求Ch生成将发送到验证者算法V的响应Rsp。在Ch=0的情况中，证明者算法P生成响应Rsp=(r₀,t₁,e₁)。在Ch=1的情况中，证明者算法P生成响应Rsp=(r₁,t₀,e₀)。在Ch=2的情况中，证明者算法P生成响应Rsp=(r₁,t₁,e₁)。在运算＃3中生成的响应Rsp被发送到验证者算法V。

运算＃4：

在接收到响应Rsp时，验证者算法V利用接收的响应Rsp执行下面的验证处理。

在Ch=0的情况中，验证者算法V验证等式c₁=H(r₀-t₁,F(r₀)-e₁)是否成立。另外，验证者算法V验证等式c₂=H(t₁,e₁)是否成立。验证者算法V在这些验证都成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

在Ch=1的情况中，验证者算法V验证等式c₀=H(r₁,G(t₀,r₁)+e₀)是否成立。另外，验证者算法V验证等式c₁=H(t₀,e₀)是否成立。验证者算法V在这些验证都成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

在Ch=2的情况中，验证者算法V验证等式c₀=H(r₁,y–F(r₁)–G(t₁,r₁)–e₁)是否成立。另外，验证者算法V验证等式c₂=H(t₁,e₁)是否成立。验证者算法V在这些验证都成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

上文描述了关于3遍方案的有效率的算法结构的示例。

（2-2：并行算法结构的示例（图5））

下面将参考图5描述并行化图4所示的3遍方案的算法的方法。然而，将省略对密钥生成算法Gen的结构的进一步描述。

实际上，应用上述会话协议使得可以将成功伪造的概率保持在2/3以下。从而，两次执行会话协议使得可以将成功伪造的概率保持在(2/3)²以下。另外，如果执行会话协议N次，成功伪造的概率变为(2/3)^N，并且，如果将N设置为足够大的数（例如，N=140），则成功伪造的概率变的可忽略地小。

多次执行交互协议的可想到的方法包括：串行方法，其中多次顺序重复消息、要求和响应的交换；以及并行方法，其中例如在单个交换中交换多个消息、要求和响应。另外，还可以考虑组合串行方法和并行方法的混合型方法。这里，将参考图5描述并行执行上述关于3遍方案的交互协议的算法（下文表示为并行算法）。

运算＃1：

如图5所示，证明者算法P首先对于i=1至N执行下面的处理（1）至（6）。

处理（1）：证明者算法P随机生成作为集合Kⁿ的元素的向量r_0i、t_0i、以及作为集合K^m的元素的向量e_0i。

处理（2）：证明者算法P计算r_1i←s-r_0i。该计算等同于通过向量r_0i掩蔽秘密密钥s。另外，证明者算法P计算t_1i←r_0i+t_0i。

处理（3）：证明者算法P计算e_1i←F(r_0i)-e_0i。

处理（4）：证明者算法P计算c_0i←H(r_1i,G(r_1i,t_0i)+e_0i)。

处理（5）：证明者算法P计算c_1i←H(t_0i,e_0i)。

处理（6）：证明者算法P计算c_2i←H(t_1i,e_1i)。

运算＃1（继续）：

在对于i=1至N执行上述处理（1）至（6）之后，证明者算法P计算Cmt←H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)。在运算＃1中生成的散列值Cmt被发送到验证者算法V。这样，将消息(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)在被发送到验证者算法V之前转换为散列值，从而使得可以减少通信量。

运算＃2：

在接收到散列值Cmt时，验证者算法V对于i=1至N中的每个从三个验证模式中选择要使用的验证模式。例如，对于i=1至N中的每个，验证者算法V可以从表示验证模式的三个数值{0,1,2}中选择数值，并在要求Ch_i中设置所选择的数值。要求Ch₁,...,Ch_N被发送到证明者算法P。

运算＃3：

在接收要求Ch₁,...,Ch_N时，证明者算法P响应于接收的要求Ch₁,...,Ch_N的每个生成要发送到验证者算法V的响应Rsp₁,...,Rsp_N。在Ch_i=0的情况中，证明者算法P生成响应Rsp_i=(r_0i,t_1i,e_1i,c_0i)。在Ch_i=1的情况中，证明者算法P生成响应Rsp_i=(r_1i,t_0i,e_0i,c_2i)。在Ch_i=2的情况中，证明者算法P生成响应Rsp_i=(r_1i,t_1i,e_1i,c_1i)。

在运算＃3中生成的响应Rsp₁,...,Rsp_N被发送到验证者算法V。

运算＃4：

在接收响应Rsp₁,...,Rsp_N时，验证者算法V使用接收的响应Rsp₁,...,Rsp_N对于i=1至N执行下面的处理（1）至（3）。这里，验证者算法V对于其中Ch_i=0的情况执行处理（1），在其中Ch_i=1的情况中执行处理（2），以及在其中Ch_i=2的情况中执行处理（3）。

处理（1）：在其中Ch_i=0的情况中，验证者算法V从Rsp_i检索(r_0i,t_1i,e_1i,c_0i)。随后，验证者算法V计算c_1i=H(r_0i-t_1i,F(r_0i)-e_1i)。另外，验证者算法V计算c_2i=H(t_1i,e_1i)。验证者算法V然后存储(c_0i,c_1i,c_2i)。

处理（2）：在其中Ch_i=1的情况中，验证者算法V从Rsp_i检索(r_1i,t_0i,e_0i,c_2i)。随后，验证者算法V计算c_0i=H(r_1i,G(t_0i,r_1i)+e_0i)。另外，

验证者算法V计算c_1i=H(t_0i,e_0i)。验证者算法V然后存储(c_0i,c_1i,c_2i)。

处理（3）：在其中Ch_i=2的情况中，验证者算法V从Rsp_i检索(r_1i,t_1i,e_1i,c_1i)。随后，验证者算法V计算c_0i=H(r_1i,y–F(r_1i)–G(t_1i,r_1i)–e_1i)。另外，验证者算法V计算c_2i=H(t_1i,e_1i)。验证者算法V然后存储(c_0i,c_1i,c_2i)。

在对于i=1至N执行上述处理（1）至（3）之后，验证者算法V验证等式Cmt=H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)是否成立。验证者算法V在验证成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

上文描述了关于3遍方案的并行有效率的算法结构的示例。

<3:关于5遍公开密钥认证方案的算法结构>

下文将描述关于5遍公开密钥认证方案的算法。注意，在下文的描述中，在一些情况中还可以将5遍公开密钥认证方案表示为“5遍方案”。

在3遍方案的情况中，每次交互协议的错误验证的概率是2/3。然而，在5遍方案的情况中，每次交互协议的错误验证的概率是1/2+1/q。这里，q为将使用的环（ring）的阶数。从而，当环的阶数足够大时，可以减小5遍方案的每次错误验证的概率，从而可以通过以较少次数执行交互协议而充分减小错误验证的概率。

例如，当期待错误验证的概率小于或等于1/2ⁿ时，在3遍方案中必须执行交互协议n/(log3-1)=1.701n以上次。另一方面，当期待错误验证的概率小于或等于1/2ⁿ时，在5遍方案中必须执行交互协议n/(1-log(1+1/q))以上次。从而，当q=24时，相比于3遍方案，在5遍方案中实现相同的安全级别所需的通信量更少。

[3-1：具体算法结构的示例（图6）]

首先，将参考图6介绍关于5遍方案的具体算法结构的示例。图6为描述关于5遍方案的具体算法结构的说明图。这里，将描述其中使用一对二次多项式(f₁(x),...,f_m(x))作为公开密钥pk的一部分的情况。这里，假设如上述公式（6）表示二次多项式f_i(x)。另外，将向量(x₁,...,x_n)表示为x，并将一对二次多元多项式(f₁(x),...,f_m(x))表示为多元多项式F（x）。

如同在关于3遍方案的有效率的算法中，使用两个向量（即，作为集合Kⁿ的元素的向量t₀和作为集合K^m的元素的向量e₀）把用于掩蔽多元多项式F(x+r₀)的多元多项式F₁(x)表示为F₁(x)=G(x,t₀)+e₀。当使用该表达式时，对于多元多项式F(x+r₀)可获得通过下面的公式（12）表示的关系。

[数学式10]

$\begin{array}{c}{\mathrm{Ch}}_A\&CenterDot;F(x+r_0)+F_1\left(x\right)\\ ={\mathrm{Ch}}_A\&CenterDot;F\left(x\right)+{\mathrm{Ch}}_A\&CenterDot;F\left(r_0\right)+{\mathrm{Ch}}_A\&CenterDot;G(x,r_0)+G(x,t_0)+e_0\\ ={\mathrm{Ch}}_A\&CenterDot;F\left(x\right)+G(x,{\mathrm{Ch}}_A\&CenterDot;r_0+t_0)+{\mathrm{Ch}}_A\&CenterDot;F\left(r_0\right)+e_0\end{array}...\left(12\right)$

为此，当t₁=Ch_A·r₀+t₀,e₁=Ch_A·F(r₀)+e₀时，在掩蔽之后的多元多项式F₂(x)=Ch_A·F(x+r₀)+F₁(x)也可以通过两个向量（即，作为集合Kⁿ的元素的向量t₁和作为集合K^m的元素的向量e₁）来表示。为此，当设置F₁(x)=G(x,t₀)+e₀时，可以通过使用Kⁿ中的向量和K^m中的向量表示F₁和F₂，从而可以实现其中通信所需的数据尺寸较小的有效率的算法。

另外，从F₂（或F₁）完全未泄漏关于r₀的信息。例如，即使在给定e₁和t₁(或e₀和t₀)时，只要e₀和t₀(或e₁和t₁)未知，则关于r₀的信息完全未知。因此，确保了零知识性。下文中，将描述基于上述逻辑构造的5遍方案的算法。这里将描述的5遍方案的算法由将在下文描述的密钥生成算法Gen、证明者算法P和验证者算法V构成。

（密钥生成算法Gen）

密钥生成算法Gen生成在环k中定义的多元多项式f₁(x₁,...,x_n),...,f_m(x₁,...,x_n)和作为集合Kⁿ的元素的向量s=(s₁,...,s_n)。然后，密钥生成算法Gen计算y=(y₁,...,y_m)←(f₁(s),...,f_m(s))。另外，密钥生成算法Gen将(f₁,…,f_m,y)设置到公开密钥pk中，并将s设为秘密密钥。下文中，将向量(x₁,...,x_n)表示为x，并将一对多元多项式(f₁(x),...,f_m(x))表示为F（x）。

（证明者算法P、验证者算法V）

下文将参考图6描述在交互协议期间通过证明者算法P执行的处理和通过验证者算法V执行的处理。在前述交互协议期间，证明者完全没有将关于秘密密钥s的信息泄漏给验证者并对验证者表示“她本人知道满足y=F(s)的s”。另一方面，验证者验证证明者是否知道满足y=F(s)的s。假设使得验证者知道公开密钥pk。另外，假设由证明者秘密地管理秘密密钥s。将参考图6所示的流程图进行描述。

运算＃1：

如图6所示，证明者算法P随机生成作为集合Kn的元素的向量r₀、作为集合Kn的元素向量t₀和作为集合Km的元素的向量e₀。随后，证明者算法P计算r₁←s-r₀。该计算等同于通过向量r₀掩蔽秘密密钥s。随后，证明者算法P计算向量r₀、t₀、e₀的散列值c₀。即，证明者算法P计算c₀←H(r₀,t₀,e₀)。随后，证明者算法P生成G(t₀,r₁)+e₀和r₁的散列值c₁。即，证明者算法P计算c₀←H(r₁,G(t₀,r₁)+e₀)。在运算＃1中生成的消息(c₀,c₁)被发送到验证者算法V。

运算＃2：

当接收到消息(c₀,c₁)时，验证者算法V从q个环K的初始数随机选择一个数Ch_A，并将选择的数Ch_A发送到证明者算法P。

运算＃3：

当接收到数Ch_A时，证明者算法P计算t₁←Ch_A·r₀-t₀。另外，证明者算法P计算e₁←Ch_A·F(r₀)-e₀。证明者算法P将t₁和e₁发送到验证者算法V。

运算＃4：

在接收到t₁和e₁时，验证者算法V从两个验证模式中选择将使用哪个验证模式。例如，验证者算法V可以从表示验证模式的两个数值{0,1}之间选择数值，并在要求Ch_B中设置选择的数值设置。要求Ch_B被发送到证明者算法P。

运算＃5：

在接收到要求Ch_B时，证明者算法P响应于接收的要求Ch_B生成要发送到验证者算法V的响应Rsp。在Ch_B=0的情况中，证明者算法P生成响应Rsp=r₀。在Ch_B=1的情况中，证明者算法P生成响应Rsp=r₁。在运算＃5中生成的响应Rsp被发送到验证者算法V。

运算＃6：

在接收到响应Rsp时，验证者算法V利用接收的响应Rsp执行下面的验证处理。

在Ch_B=0的情况中，验证者算法V执行r₀←Rsp。然后，验证者算法V验证等式c₀=H(r₀,Ch_A·r₀-t₁,Ch_A·F(r₀)-e₁)是否成立。验证者算法V在这些验证都成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

在Ch_B=1的情况中，验证者算法V执行r₁←Rsp。然后，验证者算法V验证等式c₁=H₁(r₁,Ch_A·(y-F(r₁)-G(t₁,r₁)-e₁)是否成立。验证者算法V在这些验证都成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

上文描述了关于5遍方案的有效率的算法结构的示例。

[3-2：并行算法结构的示例（图7）]

下面将参考图7描述并行化图6所示的5遍方案的算法的方法。然而，将省略对密钥生成算法Gen的结构的进一步描述。

如上所述，通过应用上述关于5遍方案的交互协议使得可以将成功伪造的概率保持为(1/2+1/q)以下。从而，两次执行交互协议使得可以将成功伪造的概率保持在(1/2+1/q)²以下。另外，如果N次执行交互协议，成功伪造的概率变为(1/2+1/q)^N，并且，如果将N设置为足够大的数（例如，N=80），则成功伪造的概率变的可忽略地小。

多次执行交互协议的可想到的方法包括：串行方法，其中多次顺序重复交换消息、要求和响应；以及并行方法，其中例如在单个交换中交换多个消息、要求和响应。另外，还可以考虑组合串行方法和并行方法的混合型方法。这里，现在将描述并行执行上述关于5遍方案的交互协议的算法（下文表示为并行算法）。

运算＃1：

如图7所示，证明者算法P首先对于i=1至N执行下面的处理（1）至（4）。

处理（1）：证明者算法P随机生成作为集合Kn的元素的向量r_0i、t_0i、以及作为集合Km的元素的向量e_0i。

处理（2）：证明者算法P计算r_1i←s-r_0i。该计算等同于通过向量r_0i掩蔽秘密密钥s。

处理（3）：证明者算法P计算c_0i←H(r_0i,t_0i,e_0i)。

处理（4）：证明者算法P计算c_1i←H(r_1i,G(t_0i,r_1i)+e_0i)。

在对于i=1至N执行上述处理（1）至（4）之后，证明者算法P执行散列值Cmt←H(c₀₁,c₁₁,...,c_0N,c_1N)。在运算＃1中生成的散列值Cmt被发送到验证者算法V。

运算＃2：

当接收到散列值Cmt时，验证者算法V对于i=1至N从q个环K的初始数随机选择一个数Ch_Ai，并将选择的数Ch_Ai（i=1至N）发送到证明者算法P。

运算＃3：

在接收到数Ch_Ai（i=1至N）时，证明者算法P对于i=1至N计算t_1i←Ch_Ai·r_0i-t_0i。另外，证明者算法P对于i=1至N计算e_1i←Ch_Ai·F(r_0i)-e_0i。另外，证明者算法P计算散列值d←H(t₁₁,e₁₁,...,t_1N,e_1N)。然后，证明者算法P将散列值发送到验证者算法V。

运算＃4：

在接收到散列值时，验证者算法V对于i=1至N从两个验证模式中选择使用哪种验证模式。例如，验证者算法V可以从表示验证模式的两个数值{0,1}中选择数值，并在要求Ch_Bi中设置选择的数值。该要求Ch_Bi（i=1至N）被发送到证明者算法P。

运算＃5：

在接收到要求Ch_Bi（i=1至N）时，证明者算法P对于i=1至N响应于接收的要求Ch_Bi生成将发送到验证者算法V的响应Rsp_i。在Ch_Bi=0的情况中，证明者算法P生成响应Rsp_i=(r_0i,c_1i)。在Ch_Bi=1的情况中，证明者算法P生成响应Rsp_i=(r_0i,t_0i,e_0i,c₁t_1i,e_1i,c_0i)。在运算＃5中生成的响应Rsp_i（i=1至N）被发送到验证者算法V。

运算＃6：

在接收到响应Rsp_i(i=1至N)时，验证者算法V利用接收的响应Rsp_i(i=1至N)执行下面的处理（1）和（2）。

处理（1）：在其中Ch_Bi=0的情况中，验证者算法V执行(r_0i,t_0i,e_0i,c_1i)←Rsp_i。然后，验证者算法V计算c_0i=H(r_0i,t_0i,e_0i)。另外，验证者算法V计算t_1i←Ch_Ai·r_0i+t_0i、和e_1i←Ch_Ai·F(r_0i)-e_0i。验证者算法V然后存储(c_0i,c_1i,t_1i,e_1i)。

处理（2）：在其中Ch_Bi=1的情况中，验证者算法V执行(r_1i,t_1i,e_1i,c_0i)←Rsp_i。然后，验证者算法V计算c_1i=H(r_1i-Ch_Ai·(y-F(r_1i))-G(t_1i,r_1i)-e_1i)。验证者算法V然后存储(c_0i,c_1i,t_1i,e_1i)。

在对于i=1至N执行上述处理（1）和（2）之后，验证者算法V验证等式Cmt=H(c₀₁,c₁₁,...,c_0N,c_1N)是否成立。另外，验证者算法V验证等式d=H(t₁₁,e₁₁,...,t_1N,e_1N)是否成立。然后，验证者算法V在这些验证成功的情况中输出值1以指示认证成功，并在验证失败的情况中输出值0以指示认证失败。

上文描述了关于5遍方案的并行有效率的算法结构的示例。

<4:对数字签名方案的修改>

下文将介绍将上述公开密钥认证方案修改为数字签名方案的方法。

当公开密钥认证方案的模型中的证明者与数字签名方案中的签名者匹配时，可以容易地理解与数字签名方案的模型近似之处在于，仅证明者可以使验证者相信。基于该构思，下文将说明将上述公开密钥认证方案修改为数字签名方案的方法。

[4-1：将3遍公开密钥认证方案修改为数字签名方案（图8）]

首先，将描述将3遍公开密钥认证方案修改为数字签名方案。

如图8所示，通过三次交互和四个运算（即，运算＃1至运算＃4）表示关于3遍方案的有效率的算法（例如，参考图5）。

运算＃1包括生成a_i=(r_0i,t_0i,e_0i,r_1i,t_1i,e_1i,c_0i,c_1i,c_2i)的处理（1）和计算Cmt←H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)的处理（2）。通过证明者算法P在运算＃1中生成的Cmt被发送到验证者算法V。

运算＃2包括选择Ch₁,...,Ch_N的处理。通过验证者算法V在运算＃2中选择的Ch₁,...,Ch_N被发送到证明者算法P。

运算＃3包括利用Ch₁,...,Ch_N和a₁...,a_N生成Rsp₁,...,Rsp_N的处理。该处理被表示为Rsp_i←Select(Ch_i,a_i)。通过证明者算法P在运算＃3中生成的Rsp₁,...,Rsp_N被发送到验证者算法V。

运算＃4包括利用Ch₁,...,Ch_N和Rsp₁,...,Rsp_N再现c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N的处理（1）、以及利用再现的c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N验证Cmt=H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)的处理（2）。

由上述运算＃1至运算＃4表示的公开密钥认证方案的算法被修改为如图8所示的签名生成算法Sig和签名验证算法Ver。

（签名生成算法Sig）

首先，将描述签名生成算法Sig的结构。签名生成算法Sig包括下面的处理（1）至（5）。

处理（1）：签名生成算法Sig生成a_i=(r_0i,t_0i,e_0i,r_1i,t_1i,e_1i,c_0i,c_1i,c_2i)。

处理（2）：签名生成算法Sig计算Cmt←H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)。

处理（3）：签名生成算法Sig计算(Ch₁,...,Ch_N)←H(M,Cmt)。这里，M为附有签名的文档。

处理（4）：签名生成算法Sig计算Rsp_i←Select(Ch_i,a_i)。

处理（5）：签名生成算法Sig将(Cmt,Rsp₁,...,Rsp_N)设为签名。

（签名验证算法Ver）

下面将描述签名验证算法Ver的结构。签名验证算法Ver包括下面的处理（1）至（3）。

处理（1）：签名验证算法Ver计算(Ch₁,...,Ch_N)←H(M,Cmt)。

处理（2）：签名验证算法Ver利用Ch₁,...,Ch_N和Rsp₁,...,Rsp_N生成c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N。

处理（3）：签名验证算法Ver利用再现的c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N验证Cmt=H(c₀₁,c₁₁,c₂₁,...,c_0N,c_1N,c_2N)。

如上所述，通过将公开密钥认证方案的模型中的证明者与数字签名方案中的签名者匹配，可以将公开密钥认证方案的算法修改为数字签名方案的算法。

[4-2：将5遍公开密钥认证方案修改为数字签名方案（图9）]

下面，将描述将关于5遍的公开密钥认证方案修改为数字签名方案。

如图9所示，通过五次交互和六个运算（即，运算＃1至运算＃6）表示关于5遍方案的有效率的算法（例如，参考图7）。

运算＃1包括对于i=1至N生成a_i=(r_0i,t_0i,e_0i,r_1i,t_1i,e_1i,c_0i,c_1i)的处理（1）和计算Cmt←H(c₀₁,c₁₁,...,c_0N,c_1N)的处理（2）。通过证明者算法P在运算＃1中生成的Cmt被发送到验证者算法V。

运算＃2包括选择Ch_A1,...,Ch_AN的处理。通过验证者算法V在运算＃2中选择的Ch_A1,...,Ch_AN被发送到证明者算法P。

运算＃3包括对于i=1至N生成b_i=(t_1i,e_1i)的处理和生成d=H(t₁₁,e₁₁,...,t_1N,e_1N)的处理。这里，通过证明者算法P在运算＃3中生成的d被发送到验证者算法V。

运算＃4包括选择Ch_B1,...,Ch_BN的处理。通过验证者算法V在运算＃4中选择的Ch_B1,...,Ch_BN被发送到证明者算法P。

运算＃5包括利用Ch_B1,...,Ch_BN,a₁...,a_N,b₁...,b_N生成Rsp₁,...,Rsp_N的处理。该处理被表示为Rsp_i←Select(Ch_Bi,a_i,b_i)。通过证明者算法P在运算＃5中生成的Rsp₁,...,Rsp_N被发送到验证者算法V。

运算＃6包括利用Ch_A1,...,Ch_AN,Ch_B1,...,Ch_BN,Rsp₁,...,Rsp_N再现c₀₁,c₁₁,...,c_0N,c_1N,t₁₁,e₁₁,...,t_1N,e_1N的处理、和利用再现的c₀₁,c₁₁,...,c_0N,c_1N验证Cmt=H(c₀₁,c₁₁,...,c_0N,c_1N)的处理、以及验证d=H(t₁₁,e₁₁,...,t_1N,e_1N)的处理。

由上述运算＃1至运算＃6表示的公开密钥认证方案的算法被修改为如图9所示的签名生成算法Sig和签名验证算法Ver。

（签名生成算法Sig）

首先，将描述签名生成算法Sig的结构。签名生成算法Sig包括下面的处理（1）至（7）。

处理（1）：签名生成算法Sig生成a_i=(r_0i,t_0i,e_0i,r_1i,t_1i,e_1i,c_0i,c_1i)。

处理（2）：签名生成算法Sig计算Cmt←H(c₀₁,c₁₁,...,c_0N,c_1N)。

处理（3）：签名生成算法Sig计算(Ch_A1,...,Ch_AN)←H(M,Cmt)。这里，M为附有签名的文档。

处理（4）：签名生成算法Sig对于i=1至N生成b_i=(t_1i,e_1i)。另外，签名生成算法Sig计算d=H(t₁₁,e₁₁,...,t_1N,e_1N)。

处理（5）：签名生成算法Sig计算(Ch_B1,...,Ch_BN)←H(M,Cmt,Ch_A1,...,Ch_AN,d)。另外，可以执行到(Ch_B1,...,Ch_BN)←H(Ch_A1,...,Ch_AN,d)的修改。

处理（6）：签名生成算法Sig计算Rsp_i←Select(Ch_Bi,a_i,b_i)。

处理（7）：签名生成算法Sig将(Cmt,d,Rsp₁,...,Rsp_N)设为数字签名。

（签名验证算法Ver）

下面将描述签名验证算法Ver的结构。签名验证算法Ver包括下面的处理（1）至（4）。

处理（1）：签名验证算法Ver计算(Ch_A1,...,Ch_AN)=H(M,Cmt)。

处理（2）：签名验证算法Ver计算(Ch_B1,...,Ch_BN)=H(M,Cmt,Ch_A1,...,Ch_AN,d)。当在通过签名验证算法Ver执行的处理（5）中执行到(Ch_B1,...,Ch_BN)=H(Ch_A1,...,Ch_AN,d)的修改时，签名验证算法Ver计算(Ch_B1,...,Ch_BN)=H(Ch_A1,...,Ch_AN,d)。

处理（3）：签名验证算法Ver利用Ch_A1,...,Ch_AN,Ch_B1,...,Ch_BN,Rsp₁,...,Rsp_N生成t₁₁,e₁₁,...,t_1N,e_1N,c₀₁,c₁₁,...,c_0N,c_1N。

处理（4）：签名验证算法Ver利用再现的c₀₁,c₁₁,...,c_0N,c_1N和d=H(t₁₁,e₁₁,...,t_1N,e_1N)验证Cmt=H(c₀₁,c₁₁,...,c_0N,c_1N)。

如上所述，通过将公开密钥认证方案的模型中的证明者与数字签名方案中的签名者匹配，可以将公开密钥认证方案的算法修改为数字签名方案的算法。

<5:减少签名验证所需的存储器量的方法>

另外，在上述数字签名方案的算法中，在签名验证算法Ver接收全部数字签名后已经执行签名验证。然而，在上述数字签名方案的情况中，数字签名的数据大小较大。为此，当利用诸如仅具有小存储器容量的的装置（比如射频识别（RFID））执行认证时，需要关注存储器的空闲容量、在认证处理期间的存储器使用率等。另外，当使用具有不足的存储器容量的装置时，在一些情况中假设不执行认证。因此，本发明发明人设计了签名验证所需的用于减少存储器量的方法。

[5-1：散列函数的结构（图10）]

首先，本发明发明人聚焦于散列函数的结构。在多种情况中，散列函数具有以块为单位将输入分组中并以块为单位顺序执行处理的结构。例如，在SHA-1的情况中，散列函数具有图10所示的结构。图10所示的散列函数通过将填充输入M分组到Z个块m₁,…,m_Z中并在索引j增大的同时顺序将块m_j连同初始值IV或中间值CV_j一起操作至预定函数CF来生成散列值。从而，当获得中间值CV_j时，之前使用的块变得不需要。因此，基于所述特征，已经设计了用于有效减少用于执行算法所需的存储器量的结构（下文称为存储器减少方法）。下文将描述用于将该结构应用于上述数字签名方案的方法。

[5-2：应用于基于3遍方案的数字签名方案的示例（图12）]

首先，将描述将上述存储器减少方法应用于基于图8所示的3遍方案的数字签名方案的算法的方法。

（通常安装方法：图11）

通常，如图11所示，关于上述数字签名方案的签名验证算法Ver一次性接收数字签名中包括的(Cmt,Rsp₁,…,Rsp_N)（S101）。随后，签名验证算法Ver执行(Ch₁,…,Ch_N)←H(M,cmt)(S102)。随后，签名验证算法Ver执行(c₀₁,c₁₁,c₂₁,…,c_0N,c_1N,c_2N)←Reproduce(Ch₁,…,Ch_N;Rsp₁,…,Rsp_N)(S103)。随后，签名验证算法Ver验证Cmt=H(c₀₁,c₁₁,c₂₁,…,c_0N,c_1N,c_2N)(S104)，并结束关于签名验证的一系列处理。

（存储器减少方法：图12）

在通常安装方法的情况中，当如图11中的步骤S101在一次接收数字签名时，需要用于存储(Rsp₁,…,Rsp_N)直到完成步骤S103的处理的存储器。然而，从图5的算法结构可以理解，除了在步骤S103中执行的再现(c_0i,c_1i,c_2i)中使用的(Ch_i;Rsp_i)，不使用其它信息。另外，当考虑图10所示的散列函数结构时，在步骤S104中执行的散列函数的计算应理解为被分组并以块为单位执行。因此，关于签名验证的结构被改善为图12所示的结构。

在图12所示的结构的情况中，签名验证算法Ver首先仅接收数字签名中包括的Cmt（S111）。随后，签名验证算法Ver执行(Ch₁,…,Ch_N)←H(M,cmt)(S112)。随后，签名验证算法Ver在对于i=1至N增加i时顺序执行步骤S113至S115的处理。

在步骤S113，签名验证算法Ver接收Rsp_i（S113）。随后，签名验证算法Ver利用接收的Rsp_i执行(c_0i,c_1i,c_2i)←Reproduce(Ch_i;Rsp_i)（S114）。在执行步骤S114的处理之后，Ch_i和Rsp_i变得不需要。因此，签名验证算法Ver在执行步骤S114的处理之后从存储器擦除Ch_i和Rsp_i。

随后，签名验证算法Ver执行tmp_i←H_i(tmp_i-1;c_0i,c_1i,c_2i)（步骤S115）。另外，散列函数H_i是这样的函数，其输出直到在散列函数H中计算c_0i,c_1i,c_2i时生成的中间值。在实际中，由于函数H_i的输入尺寸根据选择的函数不同，从而根据需要执行对输入长度的适当校正，诸如添加比特。当使用函数Hi时，将散列函数H表示为包括将在下文描述的处理（1）至（3）的算法。然后，tmp_N是散列函数H的最终输出（散列值）。在实际中，在根据散列函数的规定的最后处理中执行填充的添加处理。

处理（1）：tmp₀←空字符串

处理（2）：

For i=1to N

tmp_i←H_i(tmp_i-1;c_0i,c_1i,c_2i)

end for

处理（3）：输出tmp_N

在对于i=1至N执行步骤S113至S115的处理之后，签名验证算法Ver验证Cmt=tmp_N是否成立（S116），并结束关于签名验证的一系列处理。如上所述，签名验证算法Ver从存储器擦除在重复执行步骤S113至S115的处理期间变得不需要的信息。为此，将签名验证所需的存储器量控制为尽可能小。从而，即使在仅具有小存储器容量的装置中也可以执行上述签名验证。

[5-3：应用于基于5遍方案的数字签名方案的示例（图14）]

下面，将描述将上述存储器减少方法应用于基于图9所示的5遍方案的数字签名方案的算法的方法。

（通常安装方法：图13）

通常，如图13所示，关于上述数字签名方案的签名验证算法Ver一次性接收数字签名中包括的(Cmt,d,Rsp₁,…,Rsp_N)（S121）。随后，签名验证算法Ver执行(Ch_A1,…,Ch_AN)←H(M,cmt)(S122)。随后，签名验证算法Ver执行(Ch_B1,…,Ch_BN)←H(M,Cmt,Ch_A1,…,Ch_AN,d)（S123）。随后，签名验证算法Ver执行(c₀₁,c₁₁,…,c_0N,c_1N,d₁₁,e₁₁,…,d_1N,e_1N)←Reproduce(Ch_A1,…,Ch_AN,Ch_B1,…,Ch_BN;Rsp₁,…,Rsp_N)（S124）。随后，签名验证算法Ver验证Cmt=H(c₀₁,c₁₁,…,c_0N,c_1N)和d=H(d₁₁,e₁₁,…,d_1N,e_1N)（S125），并结束关于签名验证的一系列处理。

（存储器减少方法：图14）

当如图13中的步骤S121在一次接收数字签名时，需要用于存储(Rsp₁,…,Rsp_N)直到完成步骤S124的处理的存储器。然而，从图7的算法结构可以理解，除了在步骤S124中执行的再现(c_0i,c_1i,d_1i,e_1i)中使用的(Ch_Ai,Ch_Bi;Rsp_i)，不使用其它信息。另外，当考虑图10所示的散列函数结构时，在步骤S125中执行的散列函数的计算应理解为分组并在以块为单位执行。因此，关于签名验证的结构被改善为图14所示的结构。

在图14所示的结构的情况中，签名验证算法Ver首先仅接收数字签名中包括的Cmt（S131）。随后，签名验证算法Ver执行(Ch_A1,…,Ch_AN)←H(M,cmt)(S132)。

随后，签名验证算法Ver接收d（S133）。随后，签名验证算法Ver利用接收的d执行(Ch_B1,…,Ch_BN)←H(M,Cmt,Ch_A1,…,Ch_AN,d)（S134）。在执行步骤S134的处理之后，d变得不需要。因此，签名验证算法Ver在执行步骤S134的处理之后从存储器擦除d。随后，签名验证算法Ver在对于i=1至N增加i时顺序执行步骤S135至S137的处理。

在步骤S135，签名验证算法Ver接收Rsp_i（S135）。随后，签名验证算法Ver利用接收的Rsp_i执行(c_0i,c_1i,t_1i,e_1i)←Reproduce(Ch_Ai,Ch_Bi;Rsp_i)（S136）。在执行步骤S136的处理之后，Ch_Ai、Ch_Bi和Rsp_i变得不需要。因此，签名验证算法Ver在执行步骤S136的处理之后从存储器擦除Ch_Ai、Ch_Bi和Rsp_i。

随后，签名验证算法Ver执行tmp_i←H_i(tmp_i-1;c_0i,c_1i)and tmp_i’←H_i(tmp_i-1’;t_1i,e_1i)（步骤S137）。在对于i=1至N执行步骤S135至S137的处理之后，签名验证算法Ver验证Cmt=tmp_N以及d=tmp_N’是否成立（S138），并结束关于签名验证的一系列处理。如上所述，签名验证算法Ver从存储器擦除在重复执行步骤S135至S137的处理期间变得不需要的信息。为此，将用于签名验证所需的存储器量控制为尽可能小。从而，即使在仅具有小存储器容量的装置中也可以执行上述签名验证。

上文描述了减少签名验证所需的存储器量的方法。

<6:从二进制随机数序列提取三进制随机数序列的方法>

另外,存在这样的情况，其中在基于3遍方案的公开密钥认证方案的算法中生成N个或更多个三进制均匀随机数。然而，生成三进制均匀随机数的优良随机数生成器不是典型的。为此，需要考虑利用生成二进制均匀随机数的优良随机数生成器生成三进制均匀随机数的方法。因此，本发明的发明人设计了从二进制均匀随机数有效生成三进制均匀随机数的方法。下文将详细描述这些方法。在下文中，假设将基l（其中l为2或3）中表示的一个数计数为1个符号。

[6-1：提取方法＃1（2比特分组）（图15）]

首先，将参考图15介绍将M比特二进制数分别按照两比特一组进行分组并提取三进制数的方法（下文称为提取方法＃1）。如图15所示，当将二进制表示中的随机数串按照两比特一组分组时，可以获得M/2个2比特随机数。例如，当“00”与三进制数“0”匹配、“01”与三进制数“1”匹配、以及“10”与三进制数“2”匹配时，可以从以2比特为单位的二进制表示的随机数获得三进制随机数串。然而，2比特值“11”不在内。即，提取方法＃1是这样的方法，其中从由2个二进制符号表示的2²个数提取由1个三进制符号表示的3¹个数。从而，如下面公式（13）表示不可提取的N或更多三进制数的概率P₁。

[数学式11]

$P_1=\underset{M/2-N<i\&le;M/2}{{\mathrm{\&Sigma;}}_{M/2}}{C}_i{(1/4)}^i{(3/4)}^{M/2-i}...\left(13\right)$

[6-2：提取方法＃2（无分组）（图16）]

下面，将参考图16介绍不分组地利用M个二进制符号的随机数提取L个三进制符号的随机数的方法（下文称为提取方法＃2）。这里，L是满足3^L≤2^M的最大整数。存在可由M个二进制符号表示的数2^M。另一方面，仅存在可由L个三进制符号表示的数3^L。为此，在可由M个二进制符号表示的2^M中，不使用2^M-3^L作为三进制表示的随机数。从而，如下面公式（14）表示不可提取的N或更多三进制数的概率P₂。

[数学式12]

P₂=1-3^L/2^M

…（14）

[6-3：提取方法＃3（k比特分组）（图17）]

上述提取方法＃1是以最小分组为单位分组二进制表示的随机数串的方法。另一方面，上述提取方法＃2是以最大分组为单位分组二进制表示的随机数串的方法（由于考虑M比特分组）。从上述公式（13）和（14）可以理解，根据分组长度，不能提取N或更多三进制数的概率不同。另外，当以k比特为单位分组M个二进制符号的随机数串时，如图17所示，如下面的公式（15）表示不可提取的N或更多三进制数的概率P₃。

[数学式13]

$P_3=\underset{M/k-N/L<i\&le;M/k}{{\mathrm{\&Sigma;}}_{M/k}}{C}_i{(1-3^L/2^k)}^i{(3^L/2^k)}^{M/k-i}$

$...\left(15\right)$

当可以使得不可提取的N或更多三进制数的概率P₃最小时，可以最有效地提取三进制表示的随机数串。例如，当M=512且N=140时，当k=8时，概率P₃最小。

（6-3-1：基本结构（图18））

这里，将参考图18描述从M个二进制符号的随机数串提取L个三进制符号的随机数串的处理流程。如图18所示，首先生成M个二进制符号的随机数串（S201）。随后，以k比特为单位对M个二进制符号的随机数串分组（S202）。随后，从以k比特为单位分组的比特串X_2k提取满足X_2k≤3^L的比特串（S203）。随后，输出具有三进制表示的提取的比特串（S204），并且一系列处理结束。

（6-3-2：其它提取方法（图19））

通过计算使得在上述公式（15）中表示的概率P₃最小的分组的长度k并执行图18所示的算法，可以从二进制表示的随机数串提取三进制表示的随机数串。然而，本发明发明人已经设计了通过关注在图18的步骤S204中不使用满足X_2k>3^L的比特串的事实而更有效地提取三进制表示的随机数串的方法。下文将参考图19描述了该方法。

该方法为利用在图18的步骤S204中未提取的比特串提取三进制表示的符号串的方法。如图19所示，首先提取在图18的步骤S204中未提取的一组比特串并且满足X_2k>3^L（例如，当一组比特串被表示为y₁y₂…y_N，单个比特串y_i满足3^L≤y_i<2^k）（S211）。随后，从每个提取的比特串y_i减去3^L并计算一组新的比特串（例如，当一组新的比特串被表示为z₁z₂…z_N’时，单个比特串z_i=y_i-3^L满足0≤z_i<2^k-3^L）（S212）。

随后，从该组新的比特串提取满足X<3^L’的比特串X（S213）。这里，L'是满足3^L’≤2^k-3^L的最大整数。随后，输出具有三进制表示的在步骤S213提取的比特串（S214），并且该处理序列结束。通过应用该算法，可以以3^L’/(2^k-3^L)的概率新提取L'个三进制数。另外，通过递归地使用该方法，可以提取更多的三进制数。即，可以在步骤S213中从满足X≥3^L’的比特串类似地提取三进制数。

上文已经描述了从二进制均匀随机数有效生成三进制均匀随机数的方法。

<7:有效替换多元多项式的系数的方法>

然而，上文还未具体描述在证明者（或签名者）和验证者之间共享多元多项式的方法。共享多元多项式的可想到的方法包括在证明者和验证者之间共享在生成多元多项式的系数（随机数）时使用的种子。然而，只要在证明者和验证者之间没有共享将利用共享种子生成的随机数应用于系数的序列，则多元多项式未共享。

[7-1：基本确定]

因此，关于将利用在证明者（或签名者）和验证者之间共享的种子生成随机数串的序列应用于多元多项式执行基本确定。然后，当使用多元多项式时，根据该基本确定对多元多项式应用随机数串。当使用该方法时，在证明者（或签名者）和验证者之间共享多元多项式。

[7-2：构造数据]

然而，可考虑多元多项式的多个系数。当以1比特为单位表示一个系数时，需要至少几万比特的数据表示多元多项式。为此，替换多元多项式的系数的处理的负荷非常大。因此，本发明发明人设计了通过以预定单位构造多元多项式的系数实现替换系数的处理的效率的技术（构造技术＃1和＃2）。另外，本发明发明人设计了用于当在相同的多元多项式的系数上多次执行替换处理时改善处理效率的技术（构造技术＃3）。下面将具体描述这些技术。

（7-2-1：构造技术＃1（图20））

首先将描述构造技术＃1。如图20所示，构造技术＃1是用于收集多元多项式中包括的相同类型项的系数作为一个数据结构的技术。在图20的示例中，收集系数a_1IJ至a_MIJ作为数据结构A，并收集系数b_1I至b_MI作为数据结构B。

当未应用构造技术＃1时，通过下面的算法执行对m个n变量多项式的系数的替换（示例1）。在（示例1的）情况中，需要执行1比特“和”运算（&）2×N×(N-1)×M/2次。另外，需要执行1比特“异或”运算（^）N×(N-1)×M/2次。

（示例1）

另一方面，如图20所示，当构造系数并逐次应用一部分生成的随机数作为多元多项式的系数时，如（示例2）中表示系数替换算法。在（示例2）的情况中，仅执行L比特“和”运算（&）2×N×(N-1)/2次，并仅执行M比特“异或”运算（^）N×(N-1)/2次。另外，在每个循环的定时生成a IJ(1到M)。所述系数可以反向使用。例如，当执行N(N-1)/2次循环时，[a _IJ(1到M)]不必每次都生成，而是可以每M次仅生成一次。另外，在L次循环期间，[a _IJ(1到M)]可以在对其逐比特轮转时被使用。

（示例2）

如图20所示，可以构造系数，并且可以将通过应用多元多项式的系数获得的中间结果存储在表中。在该情况中，如（示例3）表示系数替换算法。另外，分别在阵列a_IJ[0][0]到a_IJ[2^k-1][2^k-1]中存储a_IJ[x₁,…,x_k][z₁,…,z_k]=(a_{(k(I-1)+1)(k(J-1)+1)}&x₁&z₁)^…^(a_{(k(I-1)+1)(k(J-1)+k)}&x₁&z_k)^…^(a_{(k(I-1)+k)(k(J-1)+1)}&x_k&z₁)^…^(a_{(k(I-1)+k)(k(J-1)+k)}&x_k&z_k)。在示例3的情况中，仅执行L比特“异或”运算（^）(N/k)(N/k-1)/2次。然而，需要的存储器量是（示例2）的算法的存储器量的2^2k/k²倍。

例如，当k=1时，执行L比特“异或”运算120*119/2=7140次，需要的存储器量是（示例2）的存储器量的2²=4倍，并且循环数未变。另外，当k=2时，执行L比特“异或”运算60*59/2=1770次，需要的存储器量是2⁴/4=4倍，并且循环数是1/4。当k=4时，执行L比特“异或”运算30*29/2=435次，需要的存储器量是2⁸/4²=16倍，并且循环数是1/16.4。当k=6时，执行L比特“异或”运算20*19/2=190次，需要的存储器量是2¹²/6²=114倍，并且循环数是1/37.6。当k=8时，执行L比特“异或”运算15*14/2=135次，需要的存储器量是2¹⁶/8²=1024倍，并且循环数是1/52.9。

（示例3）

上文已经描述了根据构造技术＃1的系数替换算法。在该构造中，当在执行算法时可以期望高速执行处理。

（7-2-2：构造技术＃2（图21））

下面将描述构造技术＃2。如图21所示，构造技术＃2是以二次形式表示多元多项式并收集二次形式的行和列作为数据结构的技术。在图21的示例中，在行方向收集数据结构。

如图21所示，当构造系数并依次应用一部分生成的随机数作为多元多项式的系数时，如（示例4）中表示系数替换算法。在示例4的情况中，仅执行N比特“和”运算（&）(N+1)×M次，仅执行N比特“异或”运算（^）N×M次，并仅执行函数Q运算M次。

（示例4）

如图21所示，当构造系数时，可以将通过应用多元多项式的系数获得的中间结果存储在表中。在该情况中，如（示例5）表示系数替换算法。另外，将A_I[x₁,…,x_k]=(A_(k(I-1)+1)&x₁)^…^(A_{(k(I-1)+ k)}&x_k)分别存储在A_I[0]至A_I[2^k-1]中。在示例5的情况中，仅执行N比特“异或”运算（^）(N/k)×M次，并仅执行N比特函数Q的运算M次。然而，需要的存储器量是（示例4）的算法的存储器量的2^2k/k倍。

例如，当k=1时，执行N比特“异或”运算120次，需要的存储器量是（示例4）的存储器量的两倍，并且循环数未变。另外，当k=4时，执行N比特“异或”运算30次，需要的存储器量是2⁴/4=4倍，并且循环数是1/4。另外，当k=8时，执行N比特“异或”运算15次，需要的存储器量是2⁸/8=32倍，并且循环数是1/8。另外，当k=16时，执行N比特“异或”运算8次，需要的存储器量是2¹⁶/16=4096倍，并且循环数是1/15。

（示例5）

上文已经描述了关于构造技术＃2的具体系数替换算法。在该构造中，当在执行算法时可以期望高速执行处理。

（7-2-3：构造技术＃3）

下面将描述构造技术＃3。构造技术＃3是用于当对相同的多元多项式执行N次替换处理时通过以多个单位设置“用于生成一部分系数并对一部分系数上执行N次替换处理的”部分（而不是N次从随机数生成多项式并执行替换处理）而并行地顺序执行N次处理（其中N≥2）的技术。当应用该技术时，在其中随机数生成的成本不可忽略的情况中在全部N次处理中改善了处理能力。

例如，在图5所示的算法中，当更新运算＃1中的因子时，重复执行N次对多元多项式F和G的计算。因此，在这样的计算部分中，计算被配置为重复使用相同的系数进行。当利用上述（示例2）的算法计算多元多项式F(r_0i)（其中i=1至N）时，全部N个r_0i被配置为应用于曾经生成的[a_IJL]，然后关于后续[a_IJL]的处理被配置为被执行。在该配置中，相同的系数[a_IJL]最终未被生成N次。

上文已经描述了关于构造技术＃3的具体系数替换算法。在该配置中，在执行N次的全部处理中改善了处理能力。

<8:硬件设备的示例（图22）>

可通过使用例如图22所示的信息处理设备的硬件配置执行上述每个算法。即，可利用计算机程序控制图22所示的硬件实现每个算法的处理。另外，该硬件的模式任意，可以是个人计算机、移动信息终端，诸如移动电话、PHS或PDA、游戏机、接触或非接触IC芯片、接触或非接触IC卡、或各种信息装置。另外，PHS是个人手持电话系统的缩写。另外，PDA是个人数字助理的缩写。

如图22所示，该硬件主要包括CPU902、ROM904、RAM906、主机总线908、以及桥910。另外，该硬件包括外部总线912、接口914、输入单元916、输出单元918、存储单元920、驱动器922、连接端口924以及通信单元926。另外，CPU是中央处理单元的缩写。另外，ROM是只读存储器的缩写。另外，RAM是随机存取存储器的缩写。

CPU902用作例如算术处理单元或控制单元，并基于记录在ROM904、RAM906、存储单元920或可移动记录介质928上的各个程序控制每个结构元件的全部操作或部分操作。ROM904为用于存储例如将被加载到CPU902上的程序或用于算术运算中的数据等的装置。RAM906临时或永久存储例如将被加载到CPU902上的程序或在执行程序中任意变化的各个参数等。

通过例如主机总线908将这些结构元件相互连接，该主机总线908能够执行高速数据传输。对于其部分，主机总线908通过桥910与例如外部总线912连接，所述外部总线912的数据传输速度较低。另外，输入单元916例如为鼠标、键盘、触摸屏、按钮、开关或杠杆。另外，输入单元916可以为远程控制装置，其通过使用红外线或其它无线电波传输控制信号。

输入单元918例如为诸如CRT、LCD、PDP或ELD的显示装置、诸如扬声器或耳机的音频输出装置、打印机、移动电话、或传真机，其可以视频或音频地向用户通知获取的信息。另外，CRT是阴极射线管的缩写。LCD是液晶显示器的缩写。PDP是等离子体显示面板的缩写。另外，ELD是电致发光显示器的缩写。

存储单元920是用于存储各个数据的装置。存储单元920例如为诸如硬盘驱动器（HDD）的磁存储装置、半导体存储装置、光学存储装置、或磁光存储装置。HDD是硬盘驱动器的缩写。

驱动器922是这样的装置，其读取记录在诸如磁盘、光盘、磁光盘或半导体存储器的可移动记录介质928上的信息，或在所述可移动记录介质928中写入信息。可移动记录介质928例如为DVD介质、蓝光介质、HD-DVD介质、各种半导体存储介质等。当然，可移动记录介质928例如可以是电子装置或者其上安装非接触IC芯片的IC卡。IC为集成电路的缩写。

连接端口924是诸如USB端口、IEEE1394端口、SCSI、RS-232C端口的端口，或者用于连接外部连接装置930的端口，诸如光学音频端口。外部连接装置930例如为打印机、移动音乐播放器、数字相机、数字视频相机、或IC记录器。另外，USB是通用串行总线的缩写。另外，SCSI是小型计算机系统接口的缩写。

通信单元926是将与网络932连接的通信装置，并且例如是用于无线或有限LAN的通信卡、蓝牙（注册商标）、或WUSB、光学通信路由器、ADSL路由器、或者用于接触或非接触通信的装置。与通信单元926连接的网络932由有线连接或无线连接的网络构成，例如为互联网、家用LAN、红外通信、可见光通信、广播、或卫星通信。另外，LAN是局域网的缩写。另外，WUSB是无线USB的缩写。另外，ADSL是非对称数字用户线路的缩写。

<9:概要>

最后，将简要描述根据该技术实施例的技术内容。这里陈述的技术内容可应用于各种信息处理设备，诸如个人计算机、移动电话、游戏机、信息终端、信息装置、汽车导航系统等。另外，可通过使用单个信息处理设备或使用多个信息处理设备实现下述的信息处理设备的功能。另外，可以将用于执行通过下述的信息处理设备的处理的数据存储装置和算术处理装置安装在信息处理设备上、或者安装在经网络连接的装置上。

如下实现上述信息处理设备的功能配置。例如，如下述（1）所述的信息处理设备具有执行关于有效公开密钥认证方案或数字签名方案的算法的功能，所述公开密钥认证方案或数字签名方案将其安全性基于求解多阶多元联立方程的难度上。

（1）一种签名验证设备，包括：

签名获取单元，被配置为获取数字签名，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式F组和向量y=(f₁(s),...,f_m(s))验证所述第一信息是利用签名密钥s生成的；以及

签名验证单元，被配置为通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式F组和向量y为公开密钥，

其中所述签名获取单元获取预定条数的第二信息，以及

其中所述签名验证单元顺序利用获取的预定条数的第二信息恢复所述第一信息，并在其中第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

（2）根据（1）所述的签名验证设备，

其中通过利用以块为单位对将输入的信息进行分组而处理将输入的信息的单向函数生成所述第一信息，以及

其中所述签名验证单元通过重复执行以下处理来恢复所述第一信息：输出利用获取的预定条数的第二信息通过以块为单位的处理的单向函数生成的中间值的处理，和利用生成的中间值和预定条数的后续获取的第二信息生成后续的中间值的处理。

（3）根据（2）所述的签名验证设备，其中在完成生成中间值的阶段擦除所述预定条数的第二信息。

（4）根据（2）或（3）所述的签名验证设备，

其中所述预定条数是1，以及

其中在所述第二信息中包括的并且用于从单向函数生成中间值的信息的大小大于或等于块单位的数据大小。

（5）一种签名验证方法，包括：

获取数字签名的步骤，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性的步骤，

其中所述多元多项式组F和向量y为公开密钥，

其中，在获取数字签名的步骤中，获取预定条数的第二信息，以及

其中，在验证所述正当性的步骤中，顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

（6）一种使得计算机实现以下功能的程序：

获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kn的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式组F和向量y为公开密钥，

其中，所述签名获取功能获取预定条数的第二信息，以及

其中，所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

（7）一种计算机可读记录介质，其上记录有程序，所述程序使得计算机实现：

获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K中定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式组F和向量y为公开密钥，

其中，所述签名获取功能获取预定条数的第二信息，以及

其中，所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

（备注）

上述签名验证算法Ver是签名获取单元和签名验证单元的示例。

已经参考附图描述了本发明的优选实施例，但是显然，本发明不限于上述实例。本领域技术人员可以在所附权利要求的范围内获得各种可选方案和修改方案，并且可以理解，其自然地落入本发明的技术范围内。

在上文中，已经介绍了使用散列函数H的算法，但是可以使用任务函数COM代替散列函数H。任务函数COM是其中使用字符串S和随机数ρ作为因子的函数。任务函数的示例包括由Shai Halevi和Silvio Micali在国际会议CRYPTO1996中提出的方案。

附图标记列表

Gen密钥生成算法

P证明者算法

V验证者算法

Sig签名生成算法

Ver签名验证算法

Claims (7)

1.一种签名验证设备，包括：

签名获取单元，被配置为获取数字签名，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kn的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证所述第一信息是利用签名密钥s生成的；以及

签名验证单元，被配置为通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式F组和向量y为公开密钥，

其中所述签名获取单元获取预定条数的第二信息，以及

其中所述签名验证单元顺序利用获取的预定条数的第二信息恢复所述第一信息，并在其中第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

2.根据权利要求1所述的签名验证设备，

其中通过利用以块为单位对将输入的信息进行分组而处理将输入的信息的单向函数生成所述第一信息，以及

其中所述签名验证单元通过重复执行以下处理来恢复所述第一信息：输出利用获取的预定条数的第二信息通过以块为单位的处理的单向函数生成的中间值的处理，和利用生成的中间值和预定条数的后续获取的第二信息生成后续的中间值的处理。

3.根据权利要求2所述的签名验证设备，其中在完成生成中间值的阶段擦除所述预定条数的第二信息。

4.根据权利要求2所述的签名验证设备，

其中所述预定条数是1，以及

其中在所述第二信息中包括的并且用于从单向函数生成中间值的信息的大小大于或等于块单位的数据大小。

5.一种签名验证方法，包括：

获取数字签名的步骤，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性的步骤，

其中所述多元多项式组F和向量y为公开密钥，

其中，在获取数字签名的步骤中，获取预定条数的第二信息，以及

其中，在验证所述正当性的步骤中，顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

6.一种使得计算机实现以下功能的程序：

获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kn的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式组F和向量y为公开密钥，

其中，所述签名获取功能获取预定条数的第二信息，以及

其中，所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

7.一种计算机可读记录介质，其上记录有程序，所述程序使得计算机实现以下功能：

获取数字签名的签名获取功能，所述数字签名包含：第一信息，基于在环K上定义的多阶多元多项式组F=(f₁,...,f_m)、作为集合Kⁿ的元素的签名密钥s、和文件M生成所述第一信息；以及多条第二信息，需要所述多条第二信息来基于文件M、所述多阶多元多项式组F和向量y=(f₁(s),...,f_m(s))验证第一信息是利用签名密钥s生成的；以及

签名验证功能，通过利用所述数字签名中包括的多条第二信息确定第一信息是否是可恢复的而验证文件M的正当性，

其中所述多元多项式组F和向量y为公开密钥，

其中，所述签名获取功能获取预定条数的第二信息，以及

其中，所述签名验证功能顺序利用获取的预定条数的第二信息恢复所述第一信息，并在第二信息变得不需要的不需要阶段擦除在恢复处理中不需要的第二信息。

Images