签名装置、验证装置、签名系统、签名方法、签名程序、验证方法以及验证程序

摘要

秘钥生成装置(10)生成包括元素s1的秘密密钥sk以及包括元素a和元素t1的公开密钥pk的对。签名装置(20)计算消息μ的散列值c和秘密密钥sk的元素s1的中间乘积，生成作为签名σ的元素的签名元素z。另外，验证装置(30)计算作为签名σ的元素的签名元素z和公开密钥pk的元素a的中间乘积，并且计算作为签名σ的元素的散列值c和公开密钥pk的元素t1的中间乘积，验证签名σ。

说明书

技术领域

本发明涉及考虑量子计算机的数字签名。

背景技术

数字签名是能够验证数据的合法性的密码技术。

在经由网络进行通信时，需要确认接受的数据真的是从发送者送来的数据且接受的数据是未被篡改的数据这样的数据的合法性。通过在发送侧对数据附加签名并在接收侧验证附加到数据的签名，能够验证数据的合法性。

格密码是指，使用通过线性独立的整数矢量的线性变换来表示的矢量的集合即格来实现的密码技术。

关于某个格的最短矢量问题是发现包含于该格的最短的矢量的问题。格密码以求解最短矢量问题对于量子计算机来说也困难这一点为安全性的依据，所以格密码是被认为即使实现了量子计算机也是安全的密码方式之一。

高效的格密码以被称为理想格的特殊的格上的最短矢量问题为安全性的依据。已知根据定义理想格的多项式即割圆多项式的性质，在特定的参数下通过量子计算机高效地解读最短矢量问题。

在非专利文献1中，示出了以理想格上的最短矢量问题为安全性的依据的高效的数字签名方式。但是，非专利文献1所示的方法是以通过特定的割圆多项式定义的格上的最短矢量问题为安全性的依据的，所以存在不安全的可能性。

在非专利文献2中，示出了以不依赖于特定的割圆多项式的格上的最短矢量问题为安全性的依据的高效的数字签名方式。

现有技术文献

非专利文献

非专利文献1：Leo Ducas，Eike Kiltz，Tancrede Lepoint，Vadim Lyubashevsky，Peter Schwabe，Gregor Seiler，and Damien Stehle.CRYSTALS-Dilithium：A Lattice-Based Digital Signature Scheme.In CHES，pages 238-268，2018.

非专利文献2：Vadim Lyubashevsky.Digital Signatures Based on theHardness of Ideal Lattice Problems in all Rings.In ASIACRYPT，pages 196-214，2016.

发明内容

关于在非专利文献2中示出的数字签名方式，在如量子计算机计算散列函数这样的安全性模型中并未呈现安全性。关于以格上的最短矢量问题为安全性的依据的数字签名方式，为了生成数字签名而计算散列函数。因此，为了考虑严密的意义下的针对量子计算机的安全性，最好在如量子计算机计算散列函数那样的模型中也呈现安全性。

本发明的目的在于能够构成针对量子计算机也能够保证安全性的数字签名方式。

本发明所涉及的签名装置具备：

签名生成部，计算消息μ的散列值c和秘密密钥的中间乘积(Middle-Product)而生成签名元素z；以及

输出部，输出包括由所述签名生成部生成的所述签名元素z的签名σ。

在本发明中，计算消息μ的散列值c和秘密密钥的中间乘积而生成签名元素z。由此，能够构成在如量子计算机计算散列函数那样的安全性模型中能够呈现安全性的数字签名方式。

附图说明

图1是实施方式1所涉及的签名系统1的结构图。

图2是实施方式1所涉及的秘钥生成装置10的结构图。

图3是实施方式1所涉及的签名装置20的结构图。

图4是实施方式1所涉及的验证装置30的结构图。

图5是实施方式1所涉及的秘钥生成装置10的动作的流程图。

图6是实施方式1所涉及的秘钥生成处理的流程图。

图7是实施方式1所涉及的签名装置20的动作的流程图。

图8是实施方式1所涉及的签名生成处理的流程图。

图9是实施方式1所涉及的验证装置30的动作的流程图。

图10是变形例1所涉及的秘钥生成装置10的结构图。

图11是变形例1所涉及的签名装置20的结构图。

图12是变形例1所涉及的验证装置30的结构图。

(附图标记说明)

1：签名系统；10：秘钥生成装置；11：处理器；12：存储器(memory)；13：存储设备(storage)；14：通信接口；15：电子电路；111：受理部；112：秘钥生成部；113：发送部；131：秘钥存储部；20：签名装置；21：处理器；22：存储器；23：存储设备；24：通信接口；25：电子电路；211：受理部；212：签名生成部；213：输出部；231：秘钥存储部；30：验证装置；31：处理器；32：存储器；33：存储设备；34：通信接口；35：电子电路；311：受理部；312：验证部；331：秘钥存储部；40：通信路。

具体实施方式

实施方式1.

＊＊＊结构的说明＊＊＊

参照图1，说明实施方式1所涉及的签名系统1的结构。

签名系统1具备秘钥生成装置10、签名装置20、以及验证装置30。秘钥生成装置10、签名装置20、以及验证装置30经由因特网这样的通信路40连接。通信路40不限于因特网，也可以是LAN(LocalArea Network，局域网)这样的其他类别的通信路。

秘钥生成装置10是PC(Personal Computer，个人计算机)这样的计算机。秘钥生成装置10生成在加密中利用的公开密钥以及秘密密钥，经由通信路40，将秘密密钥发送给签名装置20，并且将公开密钥发送给验证装置30。

签名装置20是PC(Personal Computer，个人计算机)这样的计算机。签名装置20针对在计算机内部保存的文档数据等明文数据，用保管的秘密密钥生成签名，由此生成签名数据，并将签名数据和明文数据发送给验证装置30。

验证装置30是PC(Personal Computer，个人计算机)这样的计算机。验证装置30使用从签名装置20接受的明文数据以及签名数据、和从秘钥生成装置10接受的公开密钥，生成关于明文数据的签名数据的验证结果数据。

此外，也可以在相同的计算机内，同时包括秘钥生成装置10、签名装置20、以及验证装置30中的任意2个以上。

参照图2，说明实施方式1所涉及的秘钥生成装置10的结构。

秘钥生成装置10具备处理器11、存储器12、存储设备13、以及通信接口14的硬件。处理器11经由信号线与其他硬件连接，控制这些其他硬件。

在秘钥生成装置10中，作为功能构成元素，具备受理部111、秘钥生成部112、以及发送部113。秘钥生成装置10的各功能构成元素的功能通过软件实现。

在存储设备13中，储存有实现秘钥生成装置10的各功能构成元素的功能的程序。该程序由处理器11读入到存储器12，由处理器11执行。由此，实现秘钥生成装置10的各功能构成元素的功能。

存储设备13实现秘钥存储部131的功能。

参照图3，说明实施方式1所涉及的签名装置20的结构。

签名装置20具备处理器21、存储器22、存储设备23、以及通信接口24的硬件。处理器21经由信号线与其他硬件连接，控制这些其他硬件。

在签名装置20中，作为功能构成元素，具备受理部211、签名生成部212、以及输出部213。签名装置20的各功能构成元素的功能通过软件实现。

在存储设备23中，储存有实现签名装置20的各功能构成元素的功能的程序。该程序由处理器21读入到存储器22，由处理器21执行。由此，实现签名装置20的各功能构成元素的功能。

存储设备23实现秘钥存储部231的功能。

参照图4，说明实施方式1所涉及的验证装置30的结构。

验证装置30具备处理器31、存储器32、存储设备33、以及通信接口34的硬件。处理器31经由信号线与其他硬件连接，控制这些其他硬件。

在验证装置30中，作为功能构成元素，具备受理部311和验证部312。验证装置30的各功能构成元素的功能通过软件实现。

在存储设备33中，储存有实现验证装置30的各功能构成元素的功能的程序。该程序由处理器31读入到存储器32，由处理器31执行。由此，实现验证装置30的各功能构成元素的功能。

存储设备33实现秘钥存储部331和结果存储部332的功能。

处理器11、21、31是进行运算处理的IC(Integrated Circuit，集成电路)。作为具体例，处理器11、21、31是CPU(Central Processing Unit，中央处理单元)、DSP(DigitalSignal Processor，数字信号处理器)、GPU(Graphics Processing Unit，图形处理单元)。

存储器12、22、32是临时地存储数据的存储装置。作为具体例，存储器12、22、32是SRAM(Static Random Access Memory，静态随机存取存储器)、DRAM(Dynamic RandomAccess Memory，动态随机存取存储器)。

存储设备13、23、33是保管数据的存储装置。作为具体例，存储设备13、23、33是HDD(Hard Disk Drive，硬盘驱动器)。另外，存储设备13、23、33也可以是SD(注册商标、SecureDigital)存储卡、CF(CompactFlash、注册商标)、NAND闪存、软盘、光盘、紧凑盘、蓝光(注册商标)盘、DVD(Digital Versatile Disk)这样的可移动存储介质。

通信接口14、24、34是用于与外部的装置进行通信的接口。作为具体例，通信接口14、24、34是Ethernet(注册商标)、USB(Universal Serial Bus，通用串行总线)、HDMI(注册商标、High-Definition Multimedia Interface，高清晰度多媒体接口)的端口。

在图2中，处理器11仅示出1个。但是，秘钥生成装置10也可以具备代替处理器11的多个处理器。同样地，签名装置20也可以具备代替处理器21的多个处理器。验证装置30也可以具备代替处理器31的多个处理器。

这些多个处理器分担实现各功能构成元素的功能的程序的执行。各个处理器与处理器11、21、31同样地，是进行运算处理的IC。

＊＊＊动作的说明＊＊＊

参照图5至图9，说明实施方式1所涉及的签名系统1的动作。

实施方式1所涉及的签名系统1的动作与实施方式1所涉及的签名方法相当。另外，实施方式1所涉及的签名系统1的动作与实施方式1所涉及的签名程序的处理相当。

＊＊准备＊＊

说明实施方式1所涉及的签名系统1的动作的说明所需的信息。

<记法>

说明在以下的说明中使用的记法。

用式11表示自然数的集合，用式12表示整数的集合。以下，在文章中，将自然数的集合表示为N，将整数的集合表示为Z。

[式11]

[式12]

针对任意的整数a，b，(a，b)表示式13所示的集合，[a，b]表示式14所示的集合。

[式13]

[式14]

针对任意的正的整数d＞0，[d]表示集合{1，2，...，d}。

将S设为某个集合，将P设为集合S上的概率分布。此时，式15表示从集合S均匀随机地选择a∈S。另外，式16表示依照概率分布P选择b∈S。

[式15]

[式16]

negl(λ)表示关于自然数λ可忽略的函数的集合。

<数字签名＞

数字签名包括KeyGen算法、Sign算法、以及Verify算法这3个算法。

KeyGen算法将保密参数λ作为输入，输出秘密密钥sk和公开密钥pk的对(sk，pk)。

Sign算法将秘密密钥sk和消息μ作为输入，输出签名σ。

Verify算法将公开密钥pk、消息μ、以及签名σ作为输入，如果签名σ是消息μ的有效的签名，则输出1，否则输出0。

MPLWE记载于文献(Miruma Rosca，Amin Sakzad，Damien Stehle，and RonSteinfeld.Middle-Product Learning with Errors.In CRYPTO，pages 283-297，2017.)。

次数最高为k-1＞0，系数为Z的多项式的集合用R

[式17]

||r||

针对自然数α，用S

[式18]

||w||

针对某个多项式r

[式19]

r＝(r

针对矢量r∈Z

(Toeplitz矩阵的定义)

针对任意的d、k＞0和a∈R

(中间乘积的定义)

将d

[式20]

middle-product⊙

[式21]

在此，针对d

[式22]

⊙

如以下所述，能够使用Toeplitz矩阵来表示中间乘积。Toeplitz矩阵与矢量之积能够用O(nlogn)计算。

(引理1)

设为d、k＞0。设为式23。

[式23]

r∈R

a∈R

b：＝r⊙

此时，式24成立。

[式24]

(推论1)

式24能够变换为如式25。

[式25]

A＝[a[1；k+1]||a[2；k+2]||...||a[d；k+d]]

针对具有对应的维度的多项式，中间乘积与多项式之积满足如结合律那样的以下的性质。

(引理2)

设为d、k、n＞0。针对所有r∈R

[式26]

r⊙

关于具有与引理2相同的次数的多项式，能够根据多项式的积的可换性，表示中间乘积部分性地具有可换性。

(推论2)

针对与引理2相同的r∈R

[式27]

r⊙

(MPLWE分布的定义)

将n、d＞0、q≥2、χ设为R

[式28]

[式29]

(a，b)：＝a⊙

说明决定性的MPLWE问题的定义。MPLWE问题是识别出从MPLWE分布和均匀分布中的哪一个概率分布采样的元素的问题。决定性的MPLWE假设是指，难以通过任意的高效的算法求解MPLWE问题这样的假设。

(MPLWE问题的定义)

将n、d＞0、q≥2、χ设为R

针对任意的攻击者A，关于MPLWE

[式30]

在此，概率是在式31和攻击者的随机数上取的。

[式31]

在针对任意的概率的多项式时间算法A，难以求解MPLWE

<附加算法>

说明在通过实施方式1所涉及的签名系统1实现的数字签名中使用的算法。

(记法)

说明在算法中使用的记法。

关于任意的整数r和作为任意的偶数(或者奇数)的整数α＞0，将r’＝r mod

用式32表示如果B是真，则成为1，否则成为0的比特。

[式32]

(算法)

该算法记载于文献(Leo Ducas，Eike Kiltz，Tancrede Lepoint，VadimLyubashevsky，Peter Schwabe，Gregor Seiler，and DamienStehle.CRYSTALS-Dilithium：A Lattice-based Digital SignatureScheme.In CHES，pages 238-268，2018.)。

算法是在整数上定义的。但是，通过针对每个系数应用算法，针对多项式也能够简单地一般化。

(Prower2Round

Prower2Round

具体而言，在Prower2Round

(Decompose

Decompose

具体而言，在Decompose

(HighBits

HighBits

具体而言，在HighBits

(LowBits

LowBits

具体而言，在LowBits

(UseHint

UseHint

具体而言，在UseHint

(MakeHint

MakeHint

具体而言，在MakeHint

[式33]

(引理3)

设q和α满足q＞2a和式34，α是作为偶数的正的整数。设r和z是R

[式34]

q≡1(modα)

[式35]

||z||

此时，HighBits

性质1：UseHint

性质2：设v

[式36]

||r-v

性质3：针对任意的h、h’，如果UseHint

(引理4)

如果式37有效并且式38有效，则成为式39。

[式37]

||s||

[式38]

||LowBits

[式39]

HighBits

＊＊签名系统1的动作＊＊

以下，C是多项式的集合。元素的L∞范数是1，L

<秘钥生成装置10的动作>

参照图5，说明实施方式1所涉及的秘钥生成装置10的动作。

实施方式1所涉及的秘钥生成装置10的动作与实施方式1所涉及的秘钥生成方法相当。另外，实施方式1所涉及的秘钥生成装置10的动作与实施方式1所涉及的秘钥生成程序的处理相当。

秘钥生成装置10实现数字签名的3个算法中的KeyGen算法。

(步骤S11：受理处理)

受理部111受理保密参数λ的输入。

具体而言，受理部111受理由秘钥生成装置10的利用者操作输入装置而输入的保密参数λ。受理部111将保密参数λ写入到存储器12。

(步骤S12：秘钥生成处理)

秘钥生成部112从存储器12读出保密参数λ。秘钥生成部112将保密参数λ作为输入，生成秘密密钥sk和公开密钥pk的对。

参照图6，说明实施方式1所涉及的秘钥生成处理。

(步骤S121：参数设定处理)

秘钥生成部112从存储器12读出保密参数λ。秘钥生成部112设定n＝n(λ)、d＝d(λ)、k＝k(λ)、q＝q(λ)。即，n、d、k、q是通过保密参数λ决定的值。

(步骤S122：随机数生成处理)

秘钥生成部112均匀随机地生成a∈R

具体而言，秘钥生成部112如式40所示随机地选择种子(seed)ρ。

[式40]

然后，秘钥生成部112将种子ρ作为输入，通过伪随机数生成算法，生成a∈R

(步骤S123：秘密密钥元素生成处理)

秘钥生成部112如式41所示，均匀随机地生成秘密密钥sk的元素s

[式41]

(步骤S124：公开密钥元素生成处理)

秘钥生成部112如式42所示，生成公开密钥pk的元素t

[式42]

t

t

(步骤S125：秘钥设定处理)

秘钥生成部112设定秘密密钥sk：＝(a，s

(步骤S13：发送处理)

发送部113从存储器12读出秘密密钥sk以及公开密钥pk。发送部113将秘密密钥sk经由通信接口14以及通信路40秘密地发送给签名装置20。于是，签名装置20的受理部211受理秘密密钥sk，写入到秘钥存储部231。另外，发送部113将公开密钥pk经由通信接口14以及通信路40发送给验证装置30。于是，验证装置30的受理部311受理公开密钥pk，写入到秘钥存储部331。

在此，秘密地发送是指，例如，在通过既存的加密方式加密的基础上发送。此外，秘密密钥sk以及公开密钥pk也可以在存储到可移动存储介质的基础上通过邮寄等直接发送。公开密钥和秘密密钥也可以由外部的装置生成。

<签名装置20的动作>

参照图7，说明实施方式1所涉及的签名装置20的动作。

实施方式1所涉及的签名装置20的动作与实施方式1所涉及的签名生成方法相当。另外，实施方式1所涉及的签名装置20的动作与实施方式1所涉及的签名生成程序的处理相当。

签名装置20实现数字签名的3个算法中的Sign算法。

(步骤S21：受理处理)

受理部211受理消息μ的输入。

具体而言，受理部211受理由签名装置20的利用者操作输入装置而输入的消息μ。受理部211将消息μ写入到存储器22。

(步骤S22：签名生成处理)

签名生成部212从秘钥存储部231读出秘密密钥sk，并且从存储器22读出消息μ。签名生成部212将秘密密钥sk以及消息μ作为输入，生成针对消息μ的签名σ。

参照图8，说明实施方式1所涉及的签名生成处理。

(步骤S221：随机数生成处理)

签名生成部212如式43所示，生成随机数y。

[式43]

(步骤S222：散列值c生成处理)

签名生成部212如式44所示，生成元素w。

[式44]

签名生成部212如式45所示，生成元素w

[式45]

w

签名生成部212将元素w

(步骤S223：元素z生成处理)

签名生成部212将散列值c、秘密密钥sk的元素s

[式46]

z：＝c⊙

即，签名生成部212计算消息μ的散列值c和秘密密钥sk的元素s

(步骤S224：元素h生成处理)

签名生成部212判定是否式47和式48中的任意的式有效。

[式47]

||z||

[式48]

||LowBits

签名生成部212在式47和式48中的任意的式有效的情况下，对签名元素z以及签名元素h设定表示不可生成签名的⊥。即，(z，h)：＝(⊥，⊥)。

另一方面，签名生成部212在式47和式48中的哪一个都不是有效的情况下，如式49所示，生成签名元素h。

[式49]

h：＝MakeHint

(步骤S225：签名设定处理)

签名生成部212设定签名σ：＝(h，z，c)。签名生成部212将签名σ写入到存储器22。

(步骤S23：输出处理)

输出部213输出包括由签名生成部212生成的签名元素h、签名元素z、以及散列值c的签名σ及消息μ。

具体而言，输出部213经由通信接口24以及通信路40，将签名σ以及消息μ发送给验证装置30。于是，验证装置30的受理部311受理签名σ以及消息μ，写入到存储器32。

<验证装置30的动作>

参照图9，说明实施方式1所涉及的验证装置30的动作。

实施方式1所涉及的验证装置30的动作与实施方式1所涉及的验证方法相当。另外，实施方式1所涉及的验证装置30的动作与实施方式1所涉及的验证程序的处理相当。

验证装置30实现数字签名的3个算法中的Verify算法。

(步骤S31：读出处理)

验证部312从秘钥存储部331读出公开密钥pk，并且从存储器32读出签名σ以及消息μ。

(步骤S32：元素w’

验证部312如式50所示生成元素w’

[式50]

w′

即，验证部312计算包含于签名σ的签名元素z和公开密钥pk的元素a的中间乘积，并且计算包含于签名σ的散列值c和公开密钥pk的元素t

(步骤S33：范数判定处理)

验证部312判定式51是否成立。

[式51]

||z||

如果式51成立则验证部312使处理进入到步骤S34。另一方面，如果式51不成立则验证部312使处理进入到步骤S36。

(步骤S34：散列值判定处理)

验证部312将元素w’

验证部312在散列值c和散列值c’相等的情况下，使处理进入到步骤S35。另一方面，验证部312在散列值c和散列值c’不相等的情况下，使处理进入到步骤S36。

(步骤S35：合法判定处理)

验证部312判定为消息μ合法。消息μ合法是指，消息μ未被篡改且消息μ是由秘密密钥sk的拥有者发送的这样的含义。

然后，验证部312输出表示消息μ合法的值1。

(步骤S36：非法判定处理)

验证部312判定为消息μ非法。消息μ非法是指，处于消息μ被篡改的情况、和消息μ是由秘密密钥sk的拥有者以外者发送的情况中的至少任意一个情况这样的含义。

然后，验证部312输出表示消息μ非法的值0。

说明验证装置30的动作的合法性。

如果在图8的步骤S222中生成的元素w

式50的UseHint

[式52]

a⊙

＝a⊙

＝a⊙

＝a⊙

＝a⊙

＝a⊙

＝w+c⊙

在此，根据式53所示的z以及t

[式53]

z＝(c⊙

t

通过将括弧展开，从式52的第2行变形为第3行。

通过代入式54所示的t，从式52的第3行变形为第4行。

[式54]

t＝a⊙

通过将括弧展开，从式52的第4行变形为第5行。

通过删除式52中的式55以及式56，从式52的第5行变形为第6行。在此，根据引理2，式55以及式56能够删除。

[式55]

a⊙

[式56]

-c⊙

根据式57，从式52的第6行变形为第7行。

[式57]

w＝a⊙

接下来，式50成为如式58所示。

[式58]

w′

＝HighBits

＝HighBits

＝HighBits

＝w

在此，引理3的性质1所示的UseHint

[式59]

z＝-c⊙

r＝w-c⊙

α＝2β′

其原因为，如式52所示，UseHint

[式60]

a0

[式61]

MakeHint

由此，从式58的第1行变形为第2行。

通过删除式62和式63，从式58的第2行变形为第3行。

[式62]

-c⊙

[式63]

c⊙

式58的第3行中的式64是小的值。因此，在输出上位比特的HighBits

＊＊＊实施方式1的效果＊＊＊

如以上所述，在实施方式1所涉及的签名系统1中，签名装置20计算消息μ的散列值c和秘密密钥sk的元素s

由此，能够将MPLWE假设作为安全性的依据，能够构成针对量子计算机也能够保证安全性的数字签名方式。

＊＊＊其他结构＊＊＊

<变形例1>

在实施方式1中，各功能构成元素用软件实现。但是，作为变形例1，各功能构成元素也可以用硬件实现。关于该变形例1，说明与实施方式1的不同点。

参照图10，说明变形例1所涉及的秘钥生成装置10的结构。

在用硬件实现各功能构成元素的情况下，秘钥生成装置10具备电子电路15来代替处理器11、存储器12、以及存储设备13。电子电路15是实现各功能构成元素、存储器12以及存储设备13的功能的专用的电路。

参照图11，说明变形例1所涉及的签名装置20的结构。

在用硬件实现各功能构成元素的情况下，签名装置20具备电子电路25来代替处理器21、存储器22、以及存储设备23。电子电路25是实现各功能构成元素、存储器22以及存储设备23的功能的专用的电路。

参照图12，说明变形例1所涉及的验证装置30的结构。

在用硬件实现各功能构成元素的情况下，验证装置30具备电子电路35来代替处理器31、存储器32、以及存储设备33。电子电路35是实现各功能构成元素、存储器32以及存储设备33的功能的专用的电路。

作为电子电路15、25、35，可设想单一电路、复合电路、程序化的处理器、并行程序化的处理器、逻辑IC、GA(Gate Array，门阵列)、ASIC(Application Specific IntegratedCircuit，专用集成电路)、FPGA(Field-Programmable Gate Array，现场可编程门阵列)。

既可以用1个电子电路15、25、35实现各功能构成元素，也可以将各功能构成元素分散到多个电子电路15、25、35而实现。

<变形例2>

作为变形例2，也可以是一部分的各功能构成元素用硬件实现，其他各功能构成元素用软件实现。

将处理器11、21、31、存储器12、22、32、存储设备13、23、33、以及电子电路15、25、35称为处理电路。即，各功能构成元素的功能通过处理电路实现。