信息处理设备、信息处理方法、程序和记录介质

摘要

[问题]实现高度安全并且允许高通信效率的公开秘钥认证方案。[解决方案]提供了一种信息处理设备：基于在环（K）上定义的多元多项式集合（F=(f1,…,fm)）和向量s（s∈Kn）生成消息；将所述消息提供给验证者，验证者知道多元多项式集合（F）和向量y（y=(y1,…,ym)=(f1(s),…,fm(s))）；以及向所述验证者提供响应信息，响应信息对应于验证者从k（k≥3）个验证模式中选择的验证模式。当向验证者发送多个消息时，该信息处理设备将所述多个消息和多个信息组合为哈希值并且发送所述哈希值。

主权项

一种信息处理设备，包括：消息生成单元，基于在环K上定义的多阶多元多项式集合F=(f1,…,fm)和作为集合Kn的元素的向量s生成N次消息（其中N≥2），并且基于N次消息计算单个第一散列值；消息提供单元，将第一散列值提供到验证者，所述验证者保持所述多阶多元多项式集合F和向量y=(y1,…,ym)=(f1(s),…,fm(s))；中间信息生成单元，利用由验证者关于各个N次消息随机选择的第一信息和在生成消息时获得的N次第二信息来生成N次第三信息，并且基于N次第三信息生成单个第二散列值；中间信息提供单元，向所述验证者提供第二散列值；以及响应提供单元，向验证者提供N次响应信息、一部分消息和一部分第三信息，其中，所述N次响应信息对应于由验证者关于各个N次消息从k（其中k≥2）个验证模式中选择的验证模式，一部分消息和一部分第三信息即使在利用多阶多元多项式集合F、向量y和响应信息执行预先针对与响应信息对应的验证模式准备的运算时也未被获得，其中，所述向量s为秘密密钥，其中，所述多阶多元多项式集合F和向量y为公开密钥，以及其中，所述消息和第三信息为通过利用公开密钥、第一信息和响应信息执行预先针对与响应信息对应的验证模式准备的运算而获得的信息，或者是基于响应信息而获得的信息。