论文标题
改进代数攻击，以解决超确定的微型实例
Improvement of algebraic attacks for solving superdetermined MinRank instances
论文作者
论文摘要
微小的（MR）问题是在许多加密应用中引起的计算问题。在动词等。 （PQCrypto 2019），作者引入了一种新的方法来解决缩微问题的超确定实例，从双线kipnis-shamir（KS）建模开始。他们使用线性代数在特定的Macaulay矩阵上使用，仅将初始方程的倍数乘以一个变量，即所谓的“内核”变量。后来，Bardet等。 （Asiacrypt 2020）引入了一个新的支持未成年人建模（SM），该建模（SM）考虑了与内核变量相关的PL {ü} CKER坐标，即KS模型中核基质的最大未成年人。在本文中，我们对（ks）和（SM）模型（对于任何实例）之间的链接提供了完整的代数解释。然后，我们证明可以将超级确定的缩影实例视为SM建模的简单实例。特别是，我们表明，以最小程度的程度（“第一度下降”）进行计算，而最小的变量数量并不总是最好的策略。我们给出了对通用随机实例攻击的复杂性估计。我们将这些结果应用于DAGS Cryptosystem，该结果已提交到NIST标准化过程的第一轮。我们表明，Bardet等人在Barelli和Couvreur（Asiacrypt，2018年）的代数攻击得到了改善。 （CBC 2019），是一个特定的超确定的缩影实例。在这里，这些实例不是通用的，但是我们表明可以分析来自DAGS的特定实例，并提供一种方式，并提供了一种最佳参数（缩短位置的数量）来解决特定实例。
The MinRank (MR) problem is a computational problem that arises in many cryptographic applications. In Verbel et al. (PQCrypto 2019), the authors introduced a new way to solve superdetermined instances of the MinRank problem, starting from the bilinear Kipnis-Shamir (KS) modeling. They use linear algebra on specific Macaulay matrices, considering only multiples of the initial equations by one block of variables, the so called ''kernel'' variables. Later, Bardet et al. (Asiacrypt 2020) introduced a new Support Minors modeling (SM), that consider the Pl{ü}cker coordinates associated to the kernel variables, i.e. the maximal minors of the Kernel matrix in the KS modeling. In this paper, we give a complete algebraic explanation of the link between the (KS) and (SM) modelings (for any instance). We then show that superdetermined MinRank instances can be seen as easy instances of the SM modeling. In particular, we show that performing computation at the smallest possible degree (the ''first degree fall'') and the smallest possible number of variables is not always the best strategy. We give complexity estimates of the attack for generic random instances.We apply those results to the DAGS cryptosystem, that was submitted to the first round of the NIST standardization process. We show that the algebraic attack from Barelli and Couvreur (Asiacrypt 2018), improved in Bardet et al. (CBC 2019), is a particular superdetermined MinRank instance.Here, the instances are not generic, but we show that it is possible to analyse the particular instances from DAGS and provide a way toselect the optimal parameters (number of shortened positions) to solve a particular instance.
