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

在2022财年，我们成功地完成了我们提出的基于MinRank问题硬度的后量子交互式公钥身份（ID）方案的构建。由于MinRank问题是一个基于二进制域的计算问题，因此我们的ID方案在二进制域中可以直接表示。这使得我们的方案很容易在当今现实世界的硬件中实现，因为大多数硬件都是基于执行二进制字段运算的电子电路构建的。我们还成功地发明了一个新的基于多元二次多项式的计算问题，该问题被证明是np困难的。基于新的计算问题，我们构造了一个新的后量子公钥身份方案，该方案被证明只要新的计算问题是困难的，该方案是安全的。此外，由于计算问题可以直接表示为二进制域，因此新的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.