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