K（≥2）值逻辑函数的扩散性
|
摘要
一些密码体制的设计与分析最终可归于多值逻辑函数的设计与分析。1985年，P.V.Kumar首先将布尔函数的扩散性推广到多值逻辑域上，并着重研究了多值Bent函数。由于扩散性在密码学上，尤其是分组密码上，有重要的应用，所以分别满足SAC(m)、PC(k)、PC(k)/m的函数和完全非线性函数的性质和构造成为密码学研究的重要课题。对多值Bent函数性质和构造的研究已经取得了一定的成果，而对满足SAC(m)、PC(k)、PC(k)/m函数的研究相对较少。
本文对K(≥2)值逻辑函数的扩散性和Bent函数进行了研究，做了下列工作：
一、在第一、二章中系统详细地综述了国内外关于满足扩散准则的K(≥2)值逻辑函数和K(≥2)值Bent函数的主要研究成果。
二、第三章是作者完成的研究成果。
1) 采用谱分析技术，分别定出了p值逻辑函数满足PC(k)、PC(k)/m和EPC(k)/m的充要条件。
2) 分别构造出满足PC(2n)（即Bent函数）、PC(k)的高次多值逻辑函数。
3) 改进了文[58]的结果，重新给出了级联函数满足k次扩散准则的充要条件。
4) 分别定出了2次p值逻辑函数满足PC(k)/m,EPC(k)/m的充要条件。
5) 分别定出了满足SAC(m)、SAC(n-2)、SAC(n-1)的一些函数类。
6) 给出了多输出函数是完全非线性函数的充要条件，并构造出满足(n,m,k)SAC的多输出p值逻辑函数。
The design and analysis of some cryptography systems can
contribute to the design and analysis of the multi-valued logical function
from the point of view of root. P.V.Kumar popularized the propagation
property of Boolean function to the multi-valued logical domain in 1985,
and studied the multi-valued Bent functions emphatically. Because
propagation property has an important application in cryptography,
especially on the block cipher, the study on the property and construction
of the multi-valued Bent function and the multi-valued logical functions
satisfying SAC(m) , PC(k) , and PC(k)/m respectively, becomes an
important subject in the study of cryptography. The design and
construction of multi-valued logical functions have made some
achievements, but there are relatively less studies on the multi-valued
logical functions satisfyingSAC(m),PC(k), and PC(k)/m separately.
The propagation property and Bent functions on the multi-valued
logical domain are studied in this paper, and some work has been done as
follows:
1、Main research results about propagation property and Bent
functions on the multi-valued logical domain both at home and abroad
were surveyed systematically in the first and second chapter.
2、The research results achieved by the author are listed in the
chapter 3, these are as follows:
1) The sufficient and necessary conditions which p -valued logical
functions meet PC(k) , PC(k)/m ,and EPC(k)/m respectively were
proved by the means of spectrum analysis method.
2) The high order multi-valued logical functions satisfying
PC(2n)(i.e. , Bent function) and PC(k) respectively were constructed
3) By improving the result of the reference [80], the sufficient and
necessary condition of joint function meeting k order propagation
criterion was proved again.
4) The sufficient and necessary conditions of quadric multi-valued
logical function satisfying PC(k)/m and EPC(k)/m were given
respectively.
5) Some multi-valued logical functions which meet
SAC(m),SAC(n - 2), and SAC(n -1) respectively were given.
6) Present a sufficient and necessary condition according to which
multi-valued functions are perfect nonlinear functions, and constructed
some multi-valued functions satisfying(n,m,k)SAC .
本文对K(≥2)值逻辑函数的扩散性和Bent函数进行了研究，做了下列工作：
一、在第一、二章中系统详细地综述了国内外关于满足扩散准则的K(≥2)值逻辑函数和K(≥2)值Bent函数的主要研究成果。
二、第三章是作者完成的研究成果。
1) 采用谱分析技术，分别定出了p值逻辑函数满足PC(k)、PC(k)/m和EPC(k)/m的充要条件。
2) 分别构造出满足PC(2n)（即Bent函数）、PC(k)的高次多值逻辑函数。
3) 改进了文[58]的结果，重新给出了级联函数满足k次扩散准则的充要条件。
4) 分别定出了2次p值逻辑函数满足PC(k)/m,EPC(k)/m的充要条件。
5) 分别定出了满足SAC(m)、SAC(n-2)、SAC(n-1)的一些函数类。
6) 给出了多输出函数是完全非线性函数的充要条件，并构造出满足(n,m,k)SAC的多输出p值逻辑函数。
The design and analysis of some cryptography systems can
contribute to the design and analysis of the multi-valued logical function
from the point of view of root. P.V.Kumar popularized the propagation
property of Boolean function to the multi-valued logical domain in 1985,
and studied the multi-valued Bent functions emphatically. Because
propagation property has an important application in cryptography,
especially on the block cipher, the study on the property and construction
of the multi-valued Bent function and the multi-valued logical functions
satisfying SAC(m) , PC(k) , and PC(k)/m respectively, becomes an
important subject in the study of cryptography. The design and
construction of multi-valued logical functions have made some
achievements, but there are relatively less studies on the multi-valued
logical functions satisfyingSAC(m),PC(k), and PC(k)/m separately.
The propagation property and Bent functions on the multi-valued
logical domain are studied in this paper, and some work has been done as
follows:
1、Main research results about propagation property and Bent
functions on the multi-valued logical domain both at home and abroad
were surveyed systematically in the first and second chapter.
2、The research results achieved by the author are listed in the
chapter 3, these are as follows:
1) The sufficient and necessary conditions which p -valued logical
functions meet PC(k) , PC(k)/m ,and EPC(k)/m respectively were
proved by the means of spectrum analysis method.
2) The high order multi-valued logical functions satisfying
PC(2n)(i.e. , Bent function) and PC(k) respectively were constructed
3) By improving the result of the reference [80], the sufficient and
necessary condition of joint function meeting k order propagation
criterion was proved again.
4) The sufficient and necessary conditions of quadric multi-valued
logical function satisfying PC(k)/m and EPC(k)/m were given
respectively.
5) Some multi-valued logical functions which meet
SAC(m),SAC(n - 2), and SAC(n -1) respectively were given.
6) Present a sufficient and necessary condition according to which
multi-valued functions are perfect nonlinear functions, and constructed
some multi-valued functions satisfying(n,m,k)SAC .
引文
1）J·F·Dillon. Elementary Hadamard difference Sets, In the Sixth Southeastern Conference on Combinatorics, Group Theory and Computing, 1975,237~249.
2）O·S·Rothaus. On Functions, J Combin Theory, 20(A)(1976),300~305.
3）R·Lidl. H.Niederreriter, Finite Fields [M],Addison-Wesley Publishing Company，1983.
4）P·V·Kumar. R.A.Scholtz , L.R Welch.,Generalized functions and their properties, J Combin Theory, 40(A)(1985),90~107.
5）A·F·Webster. S·E·Tavarse. On the Design of S-boxes, Advances in Cryptology—Crypto’85, Springer―Verlag, 1986, 523~534.
6）Habong Chung. P·V·Kumar. a New General Construction for Generalized Functions, IEEE Transactions on Information Theory. 35 (1) (1989), 206~209.
7）R·Yakagadda. J·E·Hershey. Analysis and synthesis of Sequences, IEE Proc(pt.E)136(1989),112-123 .
8）C·M·Adams. S·E·Tacares. Generating and counting binary sequence,IEEE Trans on Information Theory ,36(1990),1170~1173.
9）R·Forrè. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition, Advances in Cryptology-Crypto’88, Springer-Verlag,1990,450~468.
10）K·Nyberg. Constructions of functions and difference sets ,Proceeding of Eurocrypt’90,Springer-Verlag,1991,151~160.
11）B·Preneel.etc. Propagation Characteristics of Boolean Functions. Advances in Cryptology, Proc.Eurocrypt’90, Lecture Notes in Computer Sciences 473, Springer-Verlag, 1991,161~173.
12）B·Preneel.etc. Boolean Functions Satisfying Higher Order Propagations Criteria. Advances in Cryptology-Eurocrypt’91, Springer-Verlag, 1991, 141~152.
13）Shinya Matsufuji. Kyoki Imamura,Balance Quadriphase sequences with optimal Periodic Correlation Properties Constructed by Real-Valued Functions, IEEE Transactions On Information Theory,39(1)(1993),305~309.
14）J·Seberry, et al,Highly nonlinear 0-1 balanced functions satisfying strict avalanche criterion,In advances in Cryptology-AUS CRPT’92718,Spinger-Verlag,Lecture Notes in computer Science,1993,145~155 .
15）C·Carlet, Partially- functions, Advances in Cryptology-Crypt’92, Berlin: Springer-Verlag,1993,280~291.
16）B·Preneel. Analysis and design of cryptographic hash functions, Ph.D.Katholieke Universiteit Leuven, U.D.C.621.391.7(1993).
17）T·W·Cusick.Boolean Functions Satisfying a Higher Order Strict Avalanche Criterion. In Advances in Cryptology-Eurocrypt’93, Proceeding. Lecture Notes in Computer Science 765. Springer-Verlag, 1994, 102~117.
18）C·Clart. Two new classes offunctions,in"Proc.EUROCRYPT'93",
Lecture Notes in Computer Science,Springer-Verlag,New York/Berlin,765(1994),386~397.
19）C·Carlet,A characterization of binary functions, J of Combin Theory,76(A)(1996),328~378.
20）Kaoru Kurosawa. Takashi Satoh. Generalization of Higher Order SAC to Vector Output Boolean Functions. Advances in Cryptology-ASIACRYPT’96. Lecture Notes in Computer Science, Springer-Verlag,1163(1996),218~213.
21）K·Kurosawa. T·Satoh, Design of SAC/PC() of Order k Boolean Functions and Three other Cryptographic Criteria, Advances in Cryptology, Eurocrytp’97, Lecture Notes in Computer Science 1233, Springer-Verlag,1997, 434~449.
22）Xiang-dong Hou，Results on Functions，Journal of Combinatorial theory, Series A (80) (1997), 232~ 246.
23）Xiang-dong Hou. q-ary Functions Constructed from Chain Rings .Finite Fields And Their Appliance 4(1998),55~61.
24）C·Carlet. On the propagation criterion of degree and order . In Advances in Cryptology - EUROCRYPT'98, number 1403 in Lecture Notes in Computer Science, Springer-Verlag, 1998,462~474.
25）C·Carlet. On Cryptographic Propagation Criterion for Boolean Functions,Information and Computation, 151(1999), 32~56.
26）杨义先，林须端，胡正名。编码密码学。人民邮电出版社，1992。
27）罗铸楷，胡谋，陈廷槐。多值逻辑的理论及其应用，科学出版社，北京,1992。
28）陈连俊,关于严格雪崩准则的几点注记,密码与信息，44(2)(1993),58~61。
29）廖勇,满足（n-2）阶严格雪崩准则的n元平衡布尔函数特征与计数。密码与信息，64(4)(1993),24~29。
30）J.Seberry X－M·Z Y.Zheng,非线性平衡布尔函数与它们的扩散特性。密码与信息，4(1993)，30~39。
31）张木想，肖国镇,关于函数与其变元非线性组合之间的相关性,科学通报，39（19）(1994),1738~1741。
32）余昭平,广义部分函数的性质和构造[J].密码和信息，1995(2):1~4.
33）冯登国，肖国镇, 满足k次扩散准则的布尔函数的谱特征[J]，电子科学学刊，1996，18（4）：386~390。
34）冯登国，肖国镇, 函数与其变元的相关特性，电子学报，24(11)(1996), 65~67。
35）詹榜华, 广义e-函数, 通信学报,17 (6) (1996), 125~128。
36）冯登国，肖国镇，有限域上的函数的相关免疫性和线性结构的谱特征，通信学报,18(1)(1997),40-45.
37）王隽,李世取, 函数和广义函数的递归构造, 河北大学学报,(27)(1998),12~19。
38）鲍皖苏，素域上部分函数的谱特征,通信保密，(1)(1999),76~79。
39）刘文芬,李世取,满足k次扩散准则的布尔函数的性质和构造,信息工程学院学报，18(2)(1999)，25~28。
40）鲍皖苏,环上部分函数的谱特征, 通信学报，19(7) 1998,7~12。
41）王隽，李世取，刘文芬,广义函数的稳定性及其构造,工程数学学报16(1)(1999),99~104。
42）许成谦, 互补函数族的递归构造,燕山大学学报 23 (2) (1999),126~128。
43）王章雄,一类序列的构造方法，北京大学学报（自然科学版）35（3）（1999），311~316。
44）王章雄，龙科，燕子宗, 函数研究综述,荆州师范学院学报（自然科学版）,22(5)( 1999),18~21 。
45）欧洁,罗铸楷,关于函数的一些研究,湘潭大学自然科学学报,21(1)(1999),7~11。
46）王隽,李世取,m值逻辑函数的谱分解式及广义函数的递归构造,应用数学, 12(1)(1999),115~120。
47）温巧燕,钮心析,杨义先,现代密码学中的布尔函数,科学出版社，2000。
48）冯登国,频谱理论及其在密码学中的应用,科学出版社，2000。
49）吴仕文,余昭平,广义函数的性质研究,通信学报,21(5)( 2000),54~56 .
50）罗铸楷,关于P值函数,通信保密，(4)(2000)82~86。
51）赵亚群,李世取,部分函数的自相关函数特征和谱特征[A].密码学进展－CHINACRYPT2000[C]，北京科学出版社，2000,169~174。
52）赵亚群,李世取,广义部分函数和广义函数的关系,高等应用数学学报Ａ组，16(2)(2000),243~247.
53）赵亚群,李世取,张彦肖,部分函数的几种构造方法,中国科学院研究生院报，18(2)(2001),105~109。
54）胡垒,裴定一,冯登国, 一类函数的构造,中国科学院研究生院学报. 19 (2 )(2002),103~106。
55）赵亚群,冯登国,李世取,部分函数的密码学性质,通信学报，23(5)(2002)，113~118。
56）邱显杰,关于函数的构造的一些研究,湘潭大学自然科学学报,24(1)(2002),16~19。
57）邱显杰，关于函数的研究，常德师范学院学报(自然科学版)，14(1)(2002),16~18。
58）罗铸楷,关于满足k次扩散准则的P值逻辑函数 ,计算机科学，29(9)(2002),40~41
59）何建波，罗铸楷。关于满足k次扩散准则布尔函数的研究(一)。湘潭大学自然科学学报，24(3)(2002),40~43。
60）张习勇,韩文报,曾本胜,一种广义部分函数的构造方法, 信息工程大学学报,4(2)(2003),9~13.
61）罗铸楷，多值逻辑理论及应用研究（论文集），长沙,国防科技大学出版社，2003。
2）O·S·Rothaus. On Functions, J Combin Theory, 20(A)(1976),300~305.
3）R·Lidl. H.Niederreriter, Finite Fields [M],Addison-Wesley Publishing Company，1983.
4）P·V·Kumar. R.A.Scholtz , L.R Welch.,Generalized functions and their properties, J Combin Theory, 40(A)(1985),90~107.
5）A·F·Webster. S·E·Tavarse. On the Design of S-boxes, Advances in Cryptology—Crypto’85, Springer―Verlag, 1986, 523~534.
6）Habong Chung. P·V·Kumar. a New General Construction for Generalized Functions, IEEE Transactions on Information Theory. 35 (1) (1989), 206~209.
7）R·Yakagadda. J·E·Hershey. Analysis and synthesis of Sequences, IEE Proc(pt.E)136(1989),112-123 .
8）C·M·Adams. S·E·Tacares. Generating and counting binary sequence,IEEE Trans on Information Theory ,36(1990),1170~1173.
9）R·Forrè. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition, Advances in Cryptology-Crypto’88, Springer-Verlag,1990,450~468.
10）K·Nyberg. Constructions of functions and difference sets ,Proceeding of Eurocrypt’90,Springer-Verlag,1991,151~160.
11）B·Preneel.etc. Propagation Characteristics of Boolean Functions. Advances in Cryptology, Proc.Eurocrypt’90, Lecture Notes in Computer Sciences 473, Springer-Verlag, 1991,161~173.
12）B·Preneel.etc. Boolean Functions Satisfying Higher Order Propagations Criteria. Advances in Cryptology-Eurocrypt’91, Springer-Verlag, 1991, 141~152.
13）Shinya Matsufuji. Kyoki Imamura,Balance Quadriphase sequences with optimal Periodic Correlation Properties Constructed by Real-Valued Functions, IEEE Transactions On Information Theory,39(1)(1993),305~309.
14）J·Seberry, et al,Highly nonlinear 0-1 balanced functions satisfying strict avalanche criterion,In advances in Cryptology-AUS CRPT’92718,Spinger-Verlag,Lecture Notes in computer Science,1993,145~155 .
15）C·Carlet, Partially- functions, Advances in Cryptology-Crypt’92, Berlin: Springer-Verlag,1993,280~291.
16）B·Preneel. Analysis and design of cryptographic hash functions, Ph.D.Katholieke Universiteit Leuven, U.D.C.621.391.7(1993).
17）T·W·Cusick.Boolean Functions Satisfying a Higher Order Strict Avalanche Criterion. In Advances in Cryptology-Eurocrypt’93, Proceeding. Lecture Notes in Computer Science 765. Springer-Verlag, 1994, 102~117.
18）C·Clart. Two new classes offunctions,in"Proc.EUROCRYPT'93",
Lecture Notes in Computer Science,Springer-Verlag,New York/Berlin,765(1994),386~397.
19）C·Carlet,A characterization of binary functions, J of Combin Theory,76(A)(1996),328~378.
20）Kaoru Kurosawa. Takashi Satoh. Generalization of Higher Order SAC to Vector Output Boolean Functions. Advances in Cryptology-ASIACRYPT’96. Lecture Notes in Computer Science, Springer-Verlag,1163(1996),218~213.
21）K·Kurosawa. T·Satoh, Design of SAC/PC() of Order k Boolean Functions and Three other Cryptographic Criteria, Advances in Cryptology, Eurocrytp’97, Lecture Notes in Computer Science 1233, Springer-Verlag,1997, 434~449.
22）Xiang-dong Hou，Results on Functions，Journal of Combinatorial theory, Series A (80) (1997), 232~ 246.
23）Xiang-dong Hou. q-ary Functions Constructed from Chain Rings .Finite Fields And Their Appliance 4(1998),55~61.
24）C·Carlet. On the propagation criterion of degree and order . In Advances in Cryptology - EUROCRYPT'98, number 1403 in Lecture Notes in Computer Science, Springer-Verlag, 1998,462~474.
25）C·Carlet. On Cryptographic Propagation Criterion for Boolean Functions,Information and Computation, 151(1999), 32~56.
26）杨义先，林须端，胡正名。编码密码学。人民邮电出版社，1992。
27）罗铸楷，胡谋，陈廷槐。多值逻辑的理论及其应用，科学出版社，北京,1992。
28）陈连俊,关于严格雪崩准则的几点注记,密码与信息，44(2)(1993),58~61。
29）廖勇,满足（n-2）阶严格雪崩准则的n元平衡布尔函数特征与计数。密码与信息，64(4)(1993),24~29。
30）J.Seberry X－M·Z Y.Zheng,非线性平衡布尔函数与它们的扩散特性。密码与信息，4(1993)，30~39。
31）张木想，肖国镇,关于函数与其变元非线性组合之间的相关性,科学通报，39（19）(1994),1738~1741。
32）余昭平,广义部分函数的性质和构造[J].密码和信息，1995(2):1~4.
33）冯登国，肖国镇, 满足k次扩散准则的布尔函数的谱特征[J]，电子科学学刊，1996，18（4）：386~390。
34）冯登国，肖国镇, 函数与其变元的相关特性，电子学报，24(11)(1996), 65~67。
35）詹榜华, 广义e-函数, 通信学报,17 (6) (1996), 125~128。
36）冯登国，肖国镇，有限域上的函数的相关免疫性和线性结构的谱特征，通信学报,18(1)(1997),40-45.
37）王隽,李世取, 函数和广义函数的递归构造, 河北大学学报,(27)(1998),12~19。
38）鲍皖苏，素域上部分函数的谱特征,通信保密，(1)(1999),76~79。
39）刘文芬,李世取,满足k次扩散准则的布尔函数的性质和构造,信息工程学院学报，18(2)(1999)，25~28。
40）鲍皖苏,环上部分函数的谱特征, 通信学报，19(7) 1998,7~12。
41）王隽，李世取，刘文芬,广义函数的稳定性及其构造,工程数学学报16(1)(1999),99~104。
42）许成谦, 互补函数族的递归构造,燕山大学学报 23 (2) (1999),126~128。
43）王章雄,一类序列的构造方法，北京大学学报（自然科学版）35（3）（1999），311~316。
44）王章雄，龙科，燕子宗, 函数研究综述,荆州师范学院学报（自然科学版）,22(5)( 1999),18~21 。
45）欧洁,罗铸楷,关于函数的一些研究,湘潭大学自然科学学报,21(1)(1999),7~11。
46）王隽,李世取,m值逻辑函数的谱分解式及广义函数的递归构造,应用数学, 12(1)(1999),115~120。
47）温巧燕,钮心析,杨义先,现代密码学中的布尔函数,科学出版社，2000。
48）冯登国,频谱理论及其在密码学中的应用,科学出版社，2000。
49）吴仕文,余昭平,广义函数的性质研究,通信学报,21(5)( 2000),54~56 .
50）罗铸楷,关于P值函数,通信保密，(4)(2000)82~86。
51）赵亚群,李世取,部分函数的自相关函数特征和谱特征[A].密码学进展－CHINACRYPT2000[C]，北京科学出版社，2000,169~174。
52）赵亚群,李世取,广义部分函数和广义函数的关系,高等应用数学学报Ａ组，16(2)(2000),243~247.
53）赵亚群,李世取,张彦肖,部分函数的几种构造方法,中国科学院研究生院报，18(2)(2001),105~109。
54）胡垒,裴定一,冯登国, 一类函数的构造,中国科学院研究生院学报. 19 (2 )(2002),103~106。
55）赵亚群,冯登国,李世取,部分函数的密码学性质,通信学报，23(5)(2002)，113~118。
56）邱显杰,关于函数的构造的一些研究,湘潭大学自然科学学报,24(1)(2002),16~19。
57）邱显杰，关于函数的研究，常德师范学院学报(自然科学版)，14(1)(2002),16~18。
58）罗铸楷,关于满足k次扩散准则的P值逻辑函数 ,计算机科学，29(9)(2002),40~41
59）何建波，罗铸楷。关于满足k次扩散准则布尔函数的研究(一)。湘潭大学自然科学学报，24(3)(2002),40~43。
60）张习勇,韩文报,曾本胜,一种广义部分函数的构造方法, 信息工程大学学报,4(2)(2003),9~13.
61）罗铸楷，多值逻辑理论及应用研究（论文集），长沙,国防科技大学出版社，2003。