New Paradigm to Construct Public Key Cryptographic Schemes for Lightweight Devices with Provable Security against Quantum Attackers

为轻量级设备构建公钥加密方案的新范式，具有可证明的安全性，可抵御量子攻击者

• 批准号: 18K11292
• 负责人: SANTOSO BAGUS
• 金额: $ 2.75万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11292/
• 关键词: post-quantum; identification scheme; MQ polynomials; MinRank problem; encryption scheme; NP-hard; encryption; multivariate polynomials; aggregate signatures; Quantum Adversary; Unbounded Adversary; Encryption; Quantum Random Oracle; Binary S

In FY 2022, we successfully completed our proposed construction of the post-quantum interactive public-key identification (ID) scheme whose security is based on the hardness of MinRank problem. Since MinRank problem is a computational problem based on binary field, our ID scheme is directly representable in binary field. This makes our scheme to be easily implementable in today's real-world hardwares as most of them are constructed based on electronic circuits which execute binary field operation.We also successfully invented a new computational problem based on multivariate quadratic (MQ) polynomials which is proven to be NP-hard. Based on the new computational problem, we constructed a new post-quantum public-key ID scheme which is proven to be secure as long as the new computational problem is hard. Moreover, since the computational problem can be represented directly in binary field, the new ID scheme is also fully representable directly in binary field.In the other line of research, we successfully derived the capacity region for secure symmetric-key encryption under real-time side-channel attacks where the adversary obtains side-channel information on the secret key used during the encryption process.Finally, as a preparation for constructing post-quantum multi-signatures for blockchains, we also proposed a new framework to construct a tightly secure two-round multi-signature scheme. Based on the framework, we built a multi-signature scheme which is easy to implement securely using the standard elliptic curves.

于2022财政年度，我们成功完成了我们所建议的后量子交互式公钥识别（ID）方案的构建，其安全性基于MinRank问题的难度。 由于MinRank问题是一个基于二进制域的计算问题，因此我们的ID方案可以直接在二进制域中表示。这使得我们的计划是很容易实现的，在今天的现实世界中的硬件，因为它们大多数是基于电子电路，执行二进制字段操作。我们还成功地发明了一个新的计算问题的基础上，多元二次（MQ）多项式被证明是NP-难的。基于新的计算问题，我们构造了一个新的后量子公钥ID方案，只要新的计算问题是困难的，我们就证明了该方案是安全的。此外，由于计算问题可以直接用二进制域表示，所以新的ID方案也完全可以直接用二进制域表示。在另一条研究路线中，我们成功地推导出了在实时侧信道攻击下安全的密钥加密的容量域，其中对手获得了加密过程中使用的秘密密钥的侧信道信息。作为构造区块链后量子多重签名的准备，我们还提出了一个新的框架来构造紧安全的两轮多重签名方案。基于该框架，我们利用标准椭圆曲线构造了一个易于安全实现的多重签名方案。

项目成果

事前通信モデルにおけるペアリングを用いない集約署名

预通信模型中无需配对的聚合签名

• 发表时间: 2020
• 作者: 竹牟禮薫;坂井祐介;Bagus Santoso;花岡悟一郎;太田和夫
• 通讯作者: 太田和夫

Generalization of Isomorphism of Polynomials with Two Secrets and Its Application to Public Key Encryption

• DOI: 10.1007/978-3-030-44223-1_19
• 发表时间: 2020-04
• 作者: Bagus Santoso

新たなNP困難な Morphism of Polynomials 問題に基づいた本人確認方式

基于新NP-hard多项式态射问题的身份验证方法

• 发表时间: 2023
• 作者: 横田 明卓,竹牟禮 薫;Bagus Santoso
• 通讯作者: Bagus Santoso

Shannonワンタイムパッド暗号に置ける秘匿性の必要十分条件の再考察

重新考虑香农一次性密码保密的充分必要条件

• 发表时间: 2020
• 作者: Issei Wada;Bagus Santoso
• 通讯作者: Bagus Santoso

Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers

使用签名者之间的预通信实现免配对聚合签名

• DOI: 10.1587/transfun.2020dmp0023
• 发表时间: 2021
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: K. Takemure;Y. Sakai;B. Santoso;G. Hanaoka;K. Ohta
• 通讯作者: K. Ohta