多输出正交布尔函数的构在及其计数.docVIP

有限域上的多输出正交函数* 丁金扣1 黄铮1 温巧燕1 杨义先2 北京邮电大学理学院 北京100876) （2．北京邮电大学信息工程学院，北京 100876） 摘要：把多输出正交函数的概念推广到了有限域上，给出了一种在有限域上递归地构造平衡函数的方法，从而得到构造多输出正交函数的方法。当p=2时，就是多输出正交布尔函数。进一步给出了用这种方法所构造的多输出正交函数的个数。 关键词：正交函数，平衡函数，计数，多输出函数。 中图分类号：O157.4 TN918.1 流密码和分组密码是实现私钥密码体制的两种基本方式。对于流密码，最常用的密钥流生成器是非线性滤波生成器和非线性组合生成器，它们的安全性能与所选用的滤波函数和组合函数有非常密切的关系，而滤波函数和组合函数都是布尔函数，因此要提高生成器的安全性能，必须采用有良好密码学性质的滤波函数和组合函数，从而构造具有良好密码学性质的布尔函数显得尤为重要。分组密码由于其固有的特点而成为标准化进程的首选体制，而分组密码的核心部分就是S盒的安全设计，它要采用具有多个良好密码学性质的多输出布尔函数。为了提高系统的安全性，所使用的多输出函数也必须满足一定的性质，如平衡性、高非线性性、正交性、相关免疫性等，并且已有不少结果。 近年来，人们开始了一般有限域和单位环上多输出函数的研究，但由于难度比较大，进展缓慢，取得的成果也很有限。本文利用p元完全正则树，给出了一种构造多输出正交函数的递归方法，推广了[4]的结果。对于任意给定的有限域上的平衡函数，通过对做集合划分，使得所构造的函数都是平衡函数，且它们的任意线性组合也都是平衡函数，从而相应的多输出函数是正交的。进一步我们讨论了用这种方法所构造的多输出函数的计数问题。 1.定义和引理 设是到的映射，即 其中，。因每个都是的函数，可记，称 为由到的多输出函数，简称多输出函数。 定义1：设是一多输出函数。若对任意的，集合中恰好有个元素，则称是正交的（或称是无偏的）。显然，时，就是元平衡函数。 引理1[3]：设是一多输出函数，则是正交的充分必要条件是：对任意的，，恒有=是平衡函数。亦即由的任意线性组合构成的函数都是平衡函数。 下面根据这一结论，递归构造到上的多输出正交布尔函数。 2．正交函数的递归构造 设是定义在上的任一平衡函数，记，。由于是平衡函数，显然。把每个集合等分，并记等分后的小集合为，，即有。这种等分过程可用图1的完全正则树表示。 下面我们根据来构造新的平衡函数。 取为集合中所有第2个下标为k的集合的并，即，则有 ，。 图1 用元完全正则树表示的等分过程 定义 上的函数如下： ① 的取值与的第二个下标相同，即当的值为时的第二个下标也是。由平衡函数的定义知，我们如此定义的函数是上的平衡函数。 定理1：已知是定义在上的任一平衡函数，由①式给出，则 是到上的正交函数。 证明：由引理1，只要证明对每一个，，函数=是平衡函数即可。 当为0或为0时，=或=。由于，都是平衡函数，故也是平衡函数，所以是平衡函数。 当，时，记= （a）当时，考虑在每个集合上的取值情况。固定，由前述定义知， ， 对每一个给定的，有。有代数学知识知，当取遍中的每一个元素时，也分别取遍中的每一个元素。又考虑到中有个元素，所以集合中有个元素。 (b)当时，取遍，有 综合以上情况，我们证明了=是平衡函数。 下面考虑到上的多输出正交函数的构造。 对上文的作一次等分后，得到个集合。设对做次等分后的集合记为，则应有 。 定义 , , 分别取 。其中表示的全排列。易知是上的平衡函数。 定理2：设，是上的任一平衡函数， 是按上述方法构造的平衡函数，则多输出函数是由到的正交函数。 证明：用归纳法证明。当时，由定理１知：是正交函数。 设是正交函数，即对，有　 是平衡的。取　，现在证明是平衡的 记　　　　＝= 　　　　 由构造法知是平衡函数，又根据归纳假设，也是平衡函数，所以由代数学知识我们可以得到，对任意，是平衡函数。由的任意性知，是平衡函数。即是由到的正交函数。 3．多输出正交布尔函数的计数 定理3：设是上的任一平衡函数，是由上述方法定义的平衡函数，则由到 上的多输出正交函数共有个。 证明：根据递归构造方法，首先把等分成个集合：，则每个都含有个元素，共有种不同的分法。考虑把做等分，等分后的集合含有个元素，共有 种不同的分法。因为集合有个，所以我们可构造出个。以此类推，的个数为，……，的个数为：。所以由构成的多输出正交布尔函数共有个。 根据定理3可有结论：到 上的多输出正交函数共有