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