科学研究 - 【JST事业成果】日本研发的数字签名方案晋级美国标准化竞赛第二轮

高木刚（东京大学研究生院信息理工学系研究科教授）

国立研究开发法人科学技术振兴机构（JST）战略性创造研究推进事业(CREST)
课题：“通过数学、数理科学与信息科学协同融合构建信息应用基础并面向社会问题解决推进拓展”、“后量子社会所需高功能密码的数理基础构建与拓展”研究负责人（2021-2026）

|公布量子计算机时代的新型密码技术

东京大学研究生院信息理工学系研究科的高木刚教授等人的研究团队，公布了面向新一代计算机的新型数字签名方案“QR-UOV”的技术规范。数字签名方案是为互联网上往来传输的文件与数据提供创建者身份以及内容担保的机制。

QR-UOV是抗量子密码的一种。抗量子密码指的是，即便处理速度较传统计算机有飞跃性提升的量子计算机实现实用化，仍极难被破解的密码方案，目前正作为新一代信息安全基础，推进研究与标准化工作。

此次公开的QR-UOV具备安全性高、公钥与签名数据※1尺寸小的优势，实现了安全性与效率的兼顾。该方案在美国国家标准与技术研究院（NIST）主办的抗量子密码标准化竞赛中，是来自日本的方案中唯一晋级第二轮的提案。

※1　公钥与签名数据：公钥是用于验证数据及数字签名是否确为生成者本人发布的数据，具有防范身份冒充的作用。签名数据是与公钥配合使用，用以确认数据由本人生成、内容未遭篡改的数据。

图1 QR-UOV方案的特点：安全性高，所需数据量不到传统方案的一半。

|量子计算机的登场威胁密码通信安全

数字签名被广泛应用于电子合同、软件、个人认证等领域，是支撑信息社会可信度的基础技术。当前，主流数字签名的安全性基于整数分解与离散对数问题的难度得以保障，但有观点指出，当大规模量子计算机成为现实，便可轻松求解这类问题，从而可能导致密码体系被破解并遭到恶意利用。

因此，即便使用了量子计算机仍可保障安全性的密码技术——即所谓抗量子密码，其研发工作正在全球范围内推进。美国国家标准与技术研究院自2016年起推进抗量子密码的标准化工作，正通过分阶段遴选选定可作为国际标准的方案。

|以QR-UOV方式攻克公钥长度难题

借助剩余类环大幅缩减数据量

QR-UOV以1999年提出的数字签名方案UOV为基础，针对该方案此前存在的公钥数据尺寸大小问题进行了改良。传统UOV方案将公钥表示为数值纵横排列的矩阵形式（图2）。矩阵是计算机上数值计算时常用的表达形式，但存在数据尺寸易偏大的缺点。

另一方面，QR-UOV将公钥表示为一种被称为剩余类环※2的代数框架下的多项式。剩余类环是指在仅考虑除以某数所得余数的规则下进行运算的框架，可避免计算结果无限增大。该方案在维持高安全性的同时，大幅削减了公钥的数据尺寸。

※2　剩余类环：常规运算中，反复进行加法与乘法会导致计算结果位数持续增加。而剩余类环遵循“仅处理除以某数所得余数”的规则开展运算。例如，计算除以5的余数时，6按1处理、7按2处理。剩余类环是通过这种方式，将计算结果的数据量限定在一定范围内的机制。

图2 QR-UOV方案示意图

力争成为抗量子密码的标准规格

作为新规格的QR-UOV方案，针对传统UOV方案长期存在的公钥长度问题，重新调整了密码结构的表达形式与计算方法。本成果使得该方案既满足美国国家标准与技术研究院标准化竞赛的性能要求，又同时具备面向实际系统部署的可行设计。

|致力于打造未来安全基础技术

美国国家标准与技术研究院表示，将在未来数年内完成抗量子密码标准方案的遴选。若QR-UOV被采纳为标准规格，则有望作为量子计算机时代仍可安全使用的数字签名方案，在全球范围内得到广泛应用。研究团队今后将继续推进QR-UOV的安全性评估和实现技术改进，开展面向国际标准化与社会应用的研发工作。

原文：JST 事业成果信息通信领域
翻译：JST客观日本编辑部

【论文信息】
会议：NIST Post-Quantum Cryptography: Round 2 Additional Signatures
论文：Post-Quantum Cryptography: Additional Digital Signature Schemes
URL：https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures

【JST事业成果】日本研发的数字签名方案晋级美国标准化竞赛第二轮