Design and Cryptanalysis of MPC/FHE-friendly Symmetric-key Primitives

MPC/FHE 友好的对称密钥原语的设计和密码分析

基本信息

批准号：
22K21282
负责人：
リュウフカン
金额：
$ 1.83万
依托单位：
University of Hyogo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2022
资助国家：
日本
起止时间：
2022-08-31 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K21282/
关键词：
プライバシー保護 MPC FHE 共通鍵暗号代数攻撃代数度評価技術有限体

项目摘要

令和4年度にマルチパーチ計算（MPC）向けの共通鍵暗号LowMCの安全性に関する研究に大きな進歩を遂げた。LowMCの安全性をより深く理解するために、部分非線形層という新しい構造に対して新しい解析技術を開発しなければならない。この問題に対して、代数中間一致攻撃という新しい解析技術を提案した。前の代数技術と比べ、この技術はより良い時間と空間のトレードオフをもたらすことができて、LowMCの多くの重要なパラメーターの安全性マージンが更に少なくなり、特にあるパラメーターを初めて破ることもできた。この成果はトップ国際会議ASIACRYPT2022で発表した。多くのFHE向けの共通鍵暗号は大きい有限体で定義された。しかし、このような有限体に対する専用の解析技術が僅かであるため、設計者は未知の脆弱性を見落とす可能性が高くなる。大きい有限体での完全準同型暗号(FHE)向けの共通鍵暗号Chaghriに対して、汎用かつ高速な代数度評価技術「coefficient grouping」を開発し、Chaghriを実際の計算量で破ることをはじめて示した。具体的には、Chaghriの代数度が指数関数的増加ではなく線形関数的増加であることを明らかにした。前の代数度評価技術と比べ、「coefficient grouping」は線形時間でよりタイトな代数度の上界を計算することができる一方、汎用な暗号構造にも応用できる。この結果はトップ国際会議EUROCRYPT2023で発表した。

2020财年，我们在多栖息计算（MPC）的公共密钥密码LowMC安全性研究方面取得了重大进展。为了更好地了解 LowMC 的安全性，必须为称为部分非线性层的新结构开发新的分析技术。为了解决这个问题，我们提出了一种新的分析技术，称为代数中间匹配攻击。与之前的代数技术相比，该技术可以提供更好的时间和空间权衡，LowMC的许多重要参数的安全裕度甚至更小，特别是当某些参数可以第一次被违反时。该成果在国际顶级会议ASIACRYPT2022上公布。 FHE 的许多通用密钥密码系统都是在大型有限域上定义的。然而，由于针对此类有限体只有少数专门的分析技术，设计人员更有可能忽视未知的漏洞。我们为公共密钥密码系统 Chaghri 开发了一种通用的高速代数度评估技术，称为“系数分组”，用于大型有限域中的全同态加密（FHE），并首次证明了 Chaghri 可以被破解实际计算复杂度。具体来说，我们揭示了 Chaghri 的代数度呈线性而非指数增长。与以前的代数度评估技术相比，“系数分组”可以在线性时间内计算更严格的代数度上限，同时也适用于通用密码结构。结果在国际顶级会议EUROCRYPT2023上公布。

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Santanu Sarkar/Indian Institute of Technology Madras(インド)

Santanu Sarkar/印度马德拉斯理工学院（印度）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Willi Meier/FHNW(スイス)

威利·梅尔/FHNW（瑞士）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP

DOI：
10.1007/978-3-031-30634-1_7
发表时间：
2023
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
0
作者：
Fukang Liu;Gaoli Wang;Santanu Sarkar;Ravi Anand;W. Meier;Yingxin Li;Takanori Isobe
通讯作者：
Fukang Liu;Gaoli Wang;Santanu Sarkar;Ravi Anand;W. Meier;Yingxin Li;Takanori Isobe

Gaoli Wang/East China Normal University(中国)

王高丽/华东师范大学（中国）