布尔函数代数度的概率估计

2024-05-07 11:27 浏览:103

摘要

代数度是密码学中布尔函数的一个重要参数。当含有大量变量的函数没有以代数范式显式给出时，通常无法计算其次数，因此需要对其进行估计。我们提出了一个概率检验来判断布尔函数f的代数次是否低于某一值k。如果次确实低于k，则f总是通过检验，否则f将以概率\(\textrm{dt}_k(f)\)不通过每次检验。这与仿射等价于f的多项式的k次单项式的平均数目密切相关。只有当不通过测试的概率\(\textrm{dt}_k(f)\)不太小时，测试才具有良好的准确性。我们开始研究\(\textrm{dt}_k(f)\)，通过证明在特定情况下，当f的度实际上等于k时，概率将在(0.288788,0.5)区间内，因此少量的测试运行将足以以非常高的概率给出正确答案。使用Hou、Langevin和Leander列出的代表，计算8个变量中所有多项式的精确值\(\textrm{dt}_k(f)\)。

1 介绍和动机

代数度是密码学中布尔函数的一个重要参数。包含n个变量的布尔函数f可以唯一地表示为代数范式(ANF)，即作为包含n个变量的多项式除以(二元域)，每个变量的次数最多为1。该多项式的次数称为f的代数次数。可以表示(或近似)为低次函数的密码容易受到攻击，例如高阶微分攻击。

当f的ANF没有明确给出(例如f是一个函数的组合，或者作为一个“黑盒”给出)并且依赖于大量变量时，精确地计算它的度可能是不可行的。相反，我们的目标是使用概率测试来估计程度。

在f的ANF中，特定k次单项的系数可以通过将k个向量在正则基中生成的向量空间上的值相加来计算。这种方法有时被称为莫比乌斯变换，在密码学和编码理论中有许多应用;在密码分析中，它被用来检测和利用给定程度的单项式数量的非随机性特征(见[3,5,10,12])。

我们可以用莫比乌斯变换来估计一个函数的阶数，方法如下:选择一个k阶的单项式，计算它在f中的系数，然后检验它是否为零。如果不是，那么我们知道。如果我们运行这个测试几个单项度k和所有的计算系数为零,然后,我们得出这样的结论:f可能程度严格小于k。找到一个单项的可能性程度的k(并正确地总结)在一个运行的测试的比例等于单项度k的非零系数f。因此,这种方法的缺点是如果f学位至少k,但只有极少数的单项度k,那么人们可能会错误地将f分类为度数小于k，如下例所示:

示例1

该函数在9个变量中只有3个可能的3次单项式。假设我们运行基于两栖变换的测试，以搜索3次单项式。测试的每次运行都有只检测到一项的概率。例如，在运行测试9次之后，我们仍然有相当高的概率，测试尚未检测到3次单项，因此我们可能会错误地得出结论。只有在测试运行82次后，错误结论的概率才会降低到0.05。

在本文中，我们概括了这一思想。我们提出的测试方法背后的直觉是，即使函数f具有非常少量的k阶单项，在对f进行随机仿射可逆变量变化(f的程度对这种变量变化不变)之后，k阶单项的数量可能很高，因此更容易从概率上检测到它们的存在。目标是测试应该对所有功能执行得相当好。

我们将把我们提议的测试称为测试，并对其进行如下定义。选择并检查f在仿射空间上的值的和是否为零。同样，给定一个函数f，我们多次运行测试。如果它通过了所有这些测试我们就得出结论，否则我们就得出结论。次数小于k的函数f总是通过这个测试(没有假阴性)。k次或更高次的函数有时会失败，有时会通过测试，这取决于所选择的向量。我们用测试失败的概率表示，取所有值。这个概率决定了在t检验后错误得出结论的概率，而事实上(假阳性)。理想情况下，不应该很低。非常小的值意味着我们需要运行测试非常多的次数来获得合理的准确性。

我们开始研究测试失败的可能性。我们考虑f的度数实际上等于k的情况(尽管我们事先不知道度数;如果我们知道它，我们就不需要做任何测试了。我们在定理14和推论16中证明了概率满足上界0.5和下界0.288788…(q-Pochhammer符号at)。这意味着不存在概率非常低的函数，因此少量的测试运行就足以以非常高的概率给出正确答案。例如，对于度数为k的任何多项式f，我们只需要运行9次测试，就可以获得f被错误地分类为度数小于k的概率小于0.05。与例1中所示的情况相比，这是一个显著的改进。

我们使用Hou[6]和Langevin和Leander[8]列出的代表(见第5节)，计算并分析了k度8个变量中所有函数的检验失败概率值。

对于严格高于k次的多项式不通过检验的概率的研究将是今后工作的主题。

概率与其他现有的概念联系如下。对于测试，如果我们限制线性空间而不是仿射空间，我们得到通常的教科书线性测试，通常被称为BLR测试。有几篇论文研究了BLR测试不及格的概率，例如[1]。在[13]中，在立方体/AIDA攻击的背景下，我们提出了一个类似于上述测试的线性测试，但固定了一个维度为k的线性空间，并在其所有维度为m的子空间上运行测试。

我们定理8中显示测试失败的概率,当限制在仿射空间维度的k,等于平均的单项度k / f的仿射等价类中的所有多项式。我们建议这平均密度的单项度作为一个新的参数k(见定义4)的布尔函数。它有点类似,但不同的概念代数厚度在[2]中定义,参见备注6。

2 定义

我们用两个元素的有限域表示，用n维向量空间表示。in和in的加法用表示，以区别于in的加法，并用于in的加法。

任何函数都可以用它的代数范式(ANF)表示，即在每个变量中都有一个最多为1次的多项式给出一个多项式函数:

与。这个多项式的次称为f的代数次，这里我们简单地称它为f的次，用。

f的ANF的系数可以用下面的公式计算(例如，参见[9，第13章，定理1])，有时被称为莫比乌斯变换:

（1）

该公式的等价形式为:设为a的支持，即当且仅当。也就是的系数。用正则基表示，即在位置i为1，在其他位置为0。然后

(2) (3)

其中是由生成的-向量空间。

回想一下k维的子空间的个数等于高斯二项式系数，定义为

考虑一般线性群，由上的可逆矩阵组成。对于任意矩阵和任意矩阵我们用和表示可逆的线性仿射变换分别定义为和。有可逆线性变换和仿射变换。

两个函数被称为仿射等价，记为，如果对于一些可逆仿射变换。回想一下，度是一个仿射不变量，即if then。

在后面的文章中，会出现多项式中只有k次或k次以上的单项是相关的，而任何低次的单项都可以忽略的情况。结合仿射等价，我们也定义等价关系，如果有一个函数h使得和(即g和h重合，如果我们忽略任何小于k次的单项式)。

3.度测试和度密度

我们将定义两个概念:“小于k度”概率检验和函数的“平均度-k单项密度”。然后我们将研究它们之间的关系。

定义2

设为整数，设为函数。给定，我们将调用该测试

度小于k的测试，或测试。将表示f不通过本次测试的概率。换句话说

（4）

备注3

这并不难验证，如果是线性相关的，那么任何函数f都可以通过这个特定的测试。因此，在实践中，当它们线性相关时，不需要运行测试。因此，我们可以使用线性无关的要求来定义测试，也可以不使用线性无关的要求。我们决定，有或没有需求的两种失败概率都是值得关注的。至少有两个原因可以解释为什么在没有线性无关要求的情况下失败的概率是有意义的。首先，案例与通常所说的BLR测试相对应;在定义BLR测试失败的概率时，不要求线性无关(参见示例[1])。其次，正如我们将在命题10(i)中看到的，如果将包含n个变量的函数f视为包含多于n个变量的函数，则值不会改变。相反，如果定义需要线性无关的向量，这个值就会改变。当我们要求它们线性无关时，测试失败的概率等于定义4中的量，见定理8。

定义4

设为整数，设为函数。f的k阶单项密度，记为，定义为f的ANF中k阶单项的个数除以(n个变量中k阶单项的总数)，即如果f的ANF为，t取值于n个变量中所有的单项，则

(5)

表示f的平均度k单项密度，是所有函数g的平均值(算术平均值)，使得，即。

（6）

备注5

式(6)中的两种定义方法确实相等。即，用A表示f的稳定子在可逆仿射变换作用下的基数，即由不同的变换得到的每一个元素。因此相等和的基数。

注6

平均度-k单项密度的概念与[2]中定义的函数f的代数厚度有一些相似之处，但又有所不同。代数厚度定义为所有函数g中单项式的最小个数，使得。这两个概念都关注单项式的数量，但平均度密度关注的是给定度的单项式，而代数厚度关注的是所有度的单项式。此外，虽然这两个概念都考虑f的整个等价类，但平均度密度计算平均值，而代数厚度计算最小值。

平均度k单项密度与测试失败的概率密切相关。在初步引理之后，我们将在下一个定理中给出确切的关系。

引理7

设是一个可逆矩阵。分别用在M中作为列出现的线性无关向量表示。同样，让。那么in的系数等于。

证明

利用式(23)和事实，我们看到的系数b等于

定理8

函数f的平均k度单项密度等于所有向量线性无关的测试失败的概率。换句话说，等于乘以k个向量是线性无关的概率，即。

（7）

证明

我们的目标是把所有k次的单项式都算进去，我们称这个数为。换句话说，使用(5)和(6)是这样的

(8）

然后我们将这个数字与测试失败的向量元组的数量进行比较，我们称这个数字为。使用(4)我们有

（9）

请注意，测试失败的事实意味着它们是线性无关的(见注释3)。

对于每个固定矩阵，我们从引理7中知道，当且仅当单项式出现在某个可逆矩阵M中且列在某些位置时，检验不成立。可逆矩阵M的个数，其中向量以列的顺序出现

(有几种方法可以选择这k列出现的位置，对于每一列，我们都可以增量地选择剩余的列，这样每个新选择的列都不在由以前选择的列生成的向量空间中，以确保最终矩阵是可逆的)。因此，测试失败的每个固定值对应于多项式形式的单项式，因此

将这个关系与式(8)和式(9)结合起来，就得到了期望的结果。注意任意k元组向量线性无关的概率是

由上列引理7和定理8，以及度对可逆仿射变换不变的事实，我们可以推导出:

推论9

设为函数。

(i)
如果那么
(2)
和都是仿射等价的不变量，即隐含和。此外，暗示和。

我们证明了一些有用的性质:

命题10

设和是n个变量的函数。

(i)
如果，那么。
(2)
如果，那么。

证明

式(i)是式(ii)的特例，有和，因此我们只证明式(ii)。

由于两个函数和的变量集是不相交的，它们的值可以看作是独立的事件。函数g不能通过测试当且仅当其中一个函数不能通过测试，所以。

4 测试失败的概率f有学位k

测试的使用方法如下:我们对不同的向量(独立选择，均匀分布)进行多次测试，比如t次。如果f通过了所有的t检验，我们得出结论，我们可能有;如果f不能通过至少一项测试，我们得出结论。

当小于k时，函数f总是通过检验，根据推论9，我们有。换句话说，没有假阴性。然而，当f的真实度至少为k时，就有可能得出错误的结论(假阳性)。发生这种情况的概率是。因此，确定k次或更多次多项式是很重要的。在本文中，我们通过证明结果来开始对案例的研究;此案将是进一步研究的主题。

在本节中，我们假设。注意，对于仿射可逆变换，最大次数in的单项式是相同的，与的值无关，因此与线性可逆变换in的单项式相同。因此，当我们只研究最大次单项式时，看线性变换就足够了，而不是仿射变换，因此，当式(6)变为:

类似地，使用引理7，我们可以看到，如果考虑这些测试，即我们有

（10）

回顾推论9，和在等价即下是不变的，意味着和。在等价条件下考虑k次多项式时，考虑只包含k次多项式即齐次的表示就足够了。在这种情况下，[6]和[8]的分类中广泛使用了以下结构。设f为k次齐次，将其代数范式写成，其中t取值于变量中所有k次单项式。定义(这有时被称为f的补码，但不应与布尔补码混淆，后者是)。

我们证明了一些额外的有用性质:

命题11

设为n个变量的次函数。

(i)
如果，那么。
(2)
如果f次齐次，则和。

证明

(i)考虑线性无关的向量。在这些向量上运行测试需要对仿射空间中的所有向量加上f的值。对于其他所有-元组，结果将是相同的。有选择k元组的方法也有选择-元组的方法。

让我们用维数为0的向量空间的集合来表示测试不通过，用维数为k的仿射空间的集合来表示测试不通过。由式(5)和式(10)的定义可得:

和

因此

我们现在要做的就是证明集合和具有相同的基数。

首先注意，如果一个的-维线性空间不包含任何最后一个分量等于1的元素，那么对于所有元素，因此g通过检验，即。

每个k维仿射空间U可以写成对于某个唯一确定的k维向量空间。我们把维线性空间U定义为

我们可以证明这是k维仿射空间和那些包含最后一个分量为1的元素的线性空间之间的一一对应。对于上面定义的空间U和V，我们有

（11）

因此当且仅当，所以和具有相同的基数。

(ii)在[6,page 110]中证明了等价下的轨道与f下的轨道具有相同的基数，而且，is的轨道也具有相同的基数。因为h和有相同数量的单项式，从定义4中我们得到。然后，我们应用定理8来获得关于的所需结果。

上面的命题10和11允许我们计算一些简单函数f的值:

推论12

我们有

示例13

利用上面的推论12，我们计算出某些函数f的确切值。例如，，。最后，回顾例1，因为我们计算。这意味着在对这个f进行9次测试后，我们只有一个错误决定的概率;将其与原始测试的0.72概率进行比较，如例1所示。

现在我们要证明下面的下界和上界:

定理14

它是度的函数。然后

当且仅当达到下界。

证明

回想一下，由于f的阶数是k，因此考虑与的测试就足够了，见(10)。

用归纳法对k进行证明。我们首先考虑。回想一下，f的归一化汉明权被定义为产生非零输出的输入的比例，即:

当f的次数为1时，测试值为。这个测试失败的概率，总体上等于if，它等于if。由于f的阶为1，即它是一个仿射非常数函数，它的归一化权为。因此，下界和上界相等。注意，任何1次函数都是仿射等价于。

现在考虑一个任意的度数k，并假设这个命题对小于k的度数成立。回想一下，f在一个方向上的离散导数被定义为(通常这种情况被排除在外，但这里我们允许它，很明显，当)。

回想一下(见[7])。一个向量被称为f if([4])的快速点。因为我们允许在这个方向上求导，所以这个向量也是一个快点。文献[11]表明，在n个变量中，k次函数f的快速点(包括)的个数可以从1变化到最多，当且仅当实现快速点。我们用S(f)表示其中的向量不是f的快点，因此我们有

（12）

当达到下界时。

对f的测试

可以重写为

这是测试。无论何时对我们来说都是一个快点，因此会通过测试。什么时候不是快点，用(10)我们有

（13）

同样，当不是一个快速点时，意味着我们可以应用归纳假设

将其与式(13)结合得到

最后用式(12)我们得到了定理表述中的界。请注意，当且仅当和时才能实现下界，它满足当且仅当。

例15

对于有8个变量的函数f，上面的定理14表明，当f有3次时，有;当f是4次时，我们有。

如果我们对不依赖于k或变量数n的下界和上界感兴趣，定理14表明:

推论16

设f是度的函数。然后

下界是q-Pochhammer符号，等于。

表1列出了8个变量中31个3度非零代表的和的值;它们按递增顺序排列。取值范围为0.328125 ~ 0.489626。定理14给出的下界和上界分别为0.328125和0.496101379，见例15;虽然达到了下界，但在这种情况下上界并不紧。除了一个多项式(即由单个多项式组成的多项式)之外，所有多项式都在(0.4,0.5)区间内。我们注意到只有16个不同的值;31个类中的一些确实具有相同的值。

对于8个变量的998个4次多项式，有54个不同的值，取值范围从0.307617到0.480051。定理14给出的下界和上界分别为0.307617和0.4941635，见例15;虽然达到了下界，但在这种情况下上界并不紧。所有多项式在(0.4,0.5)区间内都有，除了两个多项式类，即单项式类，例如和类，其值为0.307617和0.384521，如推论12所期望的那样。

直方图在附录的图1和2中给出。第一个直方图显示，对于相同大小的间隔，在该间隔中多项式的数量。我们注意到绝大多数类的值在0.462808和0.480051之间。第二个直方图显示，对于每个可能的值，具有该特定值的类的数量。这允许我们查看是否可以用来区分等价类(回想一下，这是等价的不变项)。已知f, g，如果，我们知道f和g是不相等的。然而，如果我们不能用这个不变量来决定f和g是否等价。在[6]和[8]的分类中，已经使用了几个不变量的组合来区分(几乎)所有的类。不幸的是，从图2中可以看出，on本身并不特别适合于区分类，因为有许多具有相同值的类。然而，它与其他现有的不变量结合起来可能是有用的。

对于degree，也有31个代表，就像前面提到的31个代表一样。利用第11(ii)号提案，我们可以计算。同样，对于学位有4个代表，它们是由2个代表得到的。最后，对于每个学位7和8只有一个班级，分别有代表和。使用推论12，我们分别得到0.291056和0.289919。

6 结论

我们提出了一个概率测试，称为测试，用于确定布尔函数f的代数次是否低于某值k。这个测试没有假阴性(如果f的次确实低于k，那么f总是通过测试)，但可能有假阳性，即至少k次的多项式通过测试的某些实例。这样的多项式不通过测试的概率，表示，因此决定了测试的准确性。

我们通过证明f的阶实际上是k的情况的结果来研究。我们确定了的下界和上界，下界是紧的。这些界限意味着，这意味着它足以运行测试9次，至少有0.95的概率f不通过至少一个测试实例，因此正确地得出结论。我们还计算了某些类型的多项式在任意数量的变量n中的精确公式，以及计算机计算所有多项式在最多变量n中的精确公式。对严格高于k次的多项式的研究将是今后工作的主题。

下载原文档：https://link.springer.com/content/pdf/10.1007/s12095-023-00660-4.pdf

文章链接：http://m.900614.com/news/show-94876.html

摘要