多変数多項式暗号の安全性評価と効率的な実装方法の確立

多元多项式密码的安全性评估及高效实现方法的建立

基本信息

批准号：
18J20866
负责人：
王亜成
金额：
$ 1.41万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-25 至 2021-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18J20866/
关键词：
公開鍵暗号多変数多項式暗号安全性分析暗号方式の構築多項式系の解法 minrank問題 Weil降下法署名方式耐量子計算機暗号安全性評価効率改善新しい暗号システムの構築連立多変数多項式の解き方効率的な復号安全パラメータグレブナー基底ハイブリッド攻撃

项目摘要

本研究は耐量子計算機公開鍵暗号である多変数多項式暗号の安全性評価、新しい多変数多項式暗号の構築と連立多変数多項式方程式の効率的な解法に関する研究に取り組んでいた。1.安全性評価においては前年度にMinrank問題の効率的な解法について研究に取り組み、既存手法であるKipnis-Shamir法とMinors法のハイブリッド手法を提案した。しかし、その計算量解析は完全に行なっておらず、既存の多変数多項式方式の安全性評価に適用することができなかった。今年度ではその課題を解決ができ、研究成果をまとめて国際会議WISA2020に投稿し、採択された。2.連立多変数多項式方程式の効率的な解法において、Weil降下法を考えた。その手法は拡大体上の多変数多項式系を部分体の新たな多変数多項式系に変形し、部分体の変数の自明な関係式を付け加えてから多項式系を解く手法である。この手法において計算量はまだ完全に研究されていない。本研究はまずWeil降下法から得られる多項式系はSemi-regularではないことを証明した。また、その多項式系の正則性次数を上界である正則性指数と下界である初降次数で見積もることができる。本研究は主にWeil降下法から得られる多項式系の初降次数を調べて、その見積もり方を明らかにした。この結果を国内会議CSS2020に論文発表を行い、国際会議CECC2021に論文投稿をした。3.新しい暗号方式の構築に関して、東京大学の殷昌澤氏と共同研究を行い、新しい署名方式Simple Matrixを提案した。この署名方式は暗号方式ABCと署名方式UOVから閃きを得て提案した。この二つの方式の欠点を補うために、融合して新しい署名方式Simple Matrixを考えた。この署名方式は全ての既存攻撃に耐性を持ち、公開鍵長もUOVより短い。この結果を国際会議IWSEC2021に投稿した。

这项研究正在研究多个多项式密码学的安全评估，该密码是量子耐药的公共密钥密码学，新的多变量多项式加密图的构建以及同时多变量多元方程的有效解决方案。 1。在安全评估中，我们致力于研究上一年对缩小性问题的有效解决方案，并提出了一种现有方法，kipnis-shamir和Minors方法的混合方法。但是，计算复杂性分析尚未完全执行，也不能应用于现有多元多项式方法的安全评估。今年，该问题得到了解决，研究结果已汇编并提交给国际会议WISA 2020，并被选中。 2。在有效的多变量多项式方程的有效解决方案中考虑了Weil下降法。该技术涉及将扩大场上的多元多项式系统转换为子形式中的新的多变量多项式系统，在求解多项式系统之前与子形式中的变量添加了明显的关系。在此技术中，计算的复杂性尚未完全研究。这项研究首先证明了从Weil下降方法获得的多项式系统不是半规则的。此外，可以使用规则性指数估算多项式系统的规律性顺序，该指数是上限的，最初的小数阶是下限。这项研究检查了多项式系统的最初衰减，这些系统主要从Weil衰减方法获得，并揭示了如何估计它们。该论文已提交给国内会议CSS2020，并提交给国际会议CECC2021。 3。我们与东京大学的Yin Changze进行了联合研究，以建造一种新的加密方法，并提出了一种新的签名方法，即简单矩阵。这种签名方法是通过加密方法ABC和签名方法UOV提出的。为了弥补这两种方法的缺点，我们提出了一种新的签名方法简单矩阵。这种签名方法可抵抗所有现有攻击，并且公共密钥长度比UOV较短。结果已发布到国际IWSEC 2021国际会议上。