AIM: Symmetric Primitive for Shorter Signatures with Stronger Security

AIM: Symmetric Primitive for Shorter Signatures with Stronger Security
CCS 2023

笔记

后续的研究方向

摘要

基于头部MPC（MPCitH）范式的后量子签名方案最近引起了人们的极大关注，因为它们的安全性仅取决于底层原语的单向性，为后量子密码学中的硬度假设提供了多样性。最近的MPCitH友好密码是使用在大域上操作的简单代数S盒来设计的，以提高所得签名方案的性能。由于其代数结构简单，因此应全面研究其对抗代数攻击的安全性。

在本文中，我们改进了二进制扩展域上基于幂映射的S盒的代数密码分析，以及基于这种S盒的密码原语。特别是，对于F2上的Groübner基攻击，我们通过实验证明，从底层S盒获得的布尔二次方程的确切数量对于正确估计理论复杂性至关重要基于规则性的程度。同样，当从S盒中找到并使用所有可能的二次方程时，XL攻击可能会更快。这种精细的密码分析导致基于代数S盒的密码原语的更精确的代数分析。

考虑到精细的代数密码分析，我们提出了一种新的单向函数，称为AIM，作为一种MPCitH友好的对称原语，具有很高的代数攻击抵抗力。从代数攻击、统计攻击、量子攻击和一般攻击等方面全面分析了AIM的安全性。AIM与BN++证明系统相结合，产生了一种新的签名方案，称为AIMer。我们的实现表明，AIMer在签名大小和签名时间方面优于现有的基于对称基元的签名方案。

引言

近年来，随着对量子计算机的大量研究，量子计算机带来的安全威胁正在迅速成为现实。密码学在量子计算环境中被认为是特别危险的，因为最广泛使用的公钥方案的安全性依赖于因子分解或离散对数的硬度，而这是用量子计算机在多项式时间内解决的[89]。这鼓励密码社区研究对量子攻击具有弹性的后量子密码方案。NIST发起了一场后量子密码术（PQC）标准化竞赛，最近宣布了其选定的算法：CRYSTAL Kyber[87]作为公钥加密方案，CRYSTAL Dilithium[79]、Falcon[83]和SPHINCS+[55]作为数字签名方案。

基于头部的签名中的MPC。Ishai等人[56]提出的头部MPC（MPCitH）是一种从多方计算（MPC）协议构建零知识证明（ZKP）系统的范例。它的实用性通过ZKBoo方案得到了证明，这是Giacomelli等人提出的第一个有效的基于MPCitH的证明方案。[48]。MPCitH范式的主要应用之一是构建如下的后量子签名。给定一个单向函数𝑓和一个输入输出对(𝑥, 𝑦)使得𝑓(𝑥) = 𝑦,可以构造具有密钥的数字签名方案𝑥,公钥𝑦,和秘密的知识的非交互式零知识证明（NIZKPoK）𝑥作为签名。

基于MPCitH的签名方案的主要优点是，它们的安全性仅取决于密钥生成中使用的单向函数的安全性，这使得它们与安全性基于某些数学问题的硬度假设的方案相比更可靠，这些数学问题在安全性降低方面存在潜在差距。例如，多元签名方案Rainbow[34]最近通过利用其硬度假设和实际安全性之间的差距而被打破[19]。此外，基于同源性的密钥交换算法SIKE[60]揭示了其弱点，因为其安全假设不成立[23]。在这种情况下，基于MPCitH的签名方案吸引了人们的极大关注，因为它们为潜在的硬度假设提供了多样性。NIST最近呼吁增加数字签名方案[82]，也表达了对非基于结构化格的签名方案的主要兴趣。

Picnic[24]是第一个也是最著名的基于MPCitH范式的签名方案；它结合了MPC友好的分组密码LowMC[3]和称为ZKB++的MPCitH证明系统，ZKB++是ZKBoo的优化变体。Katz等人[62]通过预处理进一步提高ZKB++的效率，提出了一种新的证明系统KKW，并相应地更新了Picnic。Picnic的更新版本是唯一一个晋级NIST PQC第三轮比赛的基于ZKP的方案。

LowMC是一种相对较新的设计，它可以在MPC环境中有效地计算，其中与XOR相比，AND运算非常昂贵。LowMC受到了各种攻击，部分原因是LowMC挑战1，其中一些攻击有效[10，11，38，39，72，75，76，84]，LowMC参数也进行了相应的修改。由于针对LowMC的安全问题，有人试图从标准AES分组密码的单向性构建基于MPCitH的签名方案。2这样，从AES的单一评估中恢复密钥的难度降低到了基于签名方案的安全性。BBQ[31]和Banque[15]是基于AES的签名方案，其中BBQ采用KKW证明系统，Banquet通过为中间状态注入份额来改进BBQ。

为了在宴会证明系统中充分利用大域上的有效乘法，Dobraunig等人提出了MPCitH友好密码LS-AES和Rain。它们是基于大域上的逆S盒的置换置换密码[40]。这种设计策略提高了基于MPCitH的签名方案的效率，同时由于其代数结构简单，应通过对任何可能的代数攻击进行综合分析来仔细确定轮数。Kales和Zaverucha[61]提出了许多优化技术来进一步提高Baum和Nof证明系统的效率[14]，他们的变体被称为BN++。当Rain与BN++相结合时，据我们所知，在相同的签名/验证时间水平下（与现有的基于MPCitH的签名相比），得到的签名方案具有最短的签名大小。

最近，在MPCitH范式中考虑了许多计算问题，如综合症解码问题[45]、子集和问题[46]、多元二次问题和格问题[18，20]。还研究了交替模量的PRF[37]。这些方案中的大多数都是基于众所周知的安全假设，而它们的性能通常不具有竞争力，因此我们认为它们与我们的基于对称基元的方案相当正交。

贡献

本文的主要贡献有两个方面。首先，我们改进了二进制扩展域上基于幂映射的S盒的代数密码分析，以及基于这种S盒的密码原语。特别是，我们关注Groübner基和XL（扩展线性化）攻击，因为它们允许人们仅从单向函数的单个求值来求解方程组，这是在基于MPCitH的签名方案中使用的情况。以前关于大域上对称基元的大多数工作仅在大域上分析了它们对Groübner基攻击的安全性[1，4，40，49]。Dobraunig等人考虑了对F2的分析[40]，但只处理高次方程。我们使用中间变量将Groübner基攻击应用于F2上的低阶方程组。当谈到F2上的Groübner基攻击时，我们通过实验证明，从底层S盒获得的布尔二次方程的确切数量对于基于正则度正确估计理论复杂度至关重要。同样，当从S盒中找到并使用所有可能的二次方程时，XL攻击可能会更快。这些结果导致了基于代数S盒的密码原语的更精确的代数分析。

其次，根据基于精细代数密码分析的设计原理，我们提出了一种新的单向函数，称为AIM3，作为一种MPCitH友好的对称原语，具有很高的代数攻击抵抗力。AIM使用基于幂映射的梅森S盒，幂映射具有形式2的指数𝑒 −1.与典型的逆S盒相比，Mersenne S盒对代数攻击具有更高的抵抗力。从代数攻击、统计攻击、量子攻击和一般攻击等方面全面分析了AIM的安全性。AIM与BN++证明系统相结合，BN++证明是最先进的MPCitH证明系统之一，适用于大型领域，产生了一种新的签名方案，称为AIMer。AIM函数旨在充分利用BN++证明系统的各种优化技术，在不显著牺牲签名和验证时间的情况下减少整体签名大小。

我们实现了AIMer签名方案，并将其基准与同一机器上现有的后量子签名进行了比较。我们的实施可在https://anonymous.4open.science/r/AMER-CCS23，结果总结在第6节中。与基于BN++证明系统和3轮（分别为4轮）Rain相结合的签名方案相比，AIMer在128位安全级别下，签名大小缩短了8.21%（分别为21.15%），签名性能提高了1.22%（分别为13.41%）𝑁被设置为16。