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

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

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.