Xiao-Massey定理: 历史背景、学术影响和原创性

Abstract

1985年, 肖国镇在第23届ISIT国际会议上提出非线性组合函数的"线性统计独立"的概念, 用频谱方法刻画了线性统计独立函数的特征. 线性统计独立与同一时期Siegenthaler提出的"相关免疫"是同一概念. 1988年, 肖国镇和Massey以"A spectral characterization of correlation-immune combining functions"为题把这一结论发表在IEEE Transactions on Information Theory上, 后人称之为"Xiao-Massey定理". Xiao-Massey定理的提出是流密码发展史上的重要事件, 对流密码的设计和分析具有重要指导意义. 本文阐述了Xiao-Massey定理的历史背景、学术影响和原创性. 同时指出, Golomb在1959年定义的"不变量"本质上是刻画了特定群不变关系下所划分的等价类中布尔函数的频谱共同特征, 它和相关免疫是两个不同的概念, 更没有刻画出相关免疫函数的频谱特征.

Alternate abstract:

In 1985, at the 23rd IEEE International Symposium on Information Theory (ISIT), Xiao introduced the notion of "linear statistical independence'', which can be used to describe the notion of "correlation immunity", a concept introduced by Siegenthaler in the same period of time. Xiao characterized all n-variable t-order linearly statistical independent Boolean functions for every t, 1≤t≤n−1, in terms of their Fourier spectrum. In 1988, the result was published in IEEE Transactions on Information Theory entitled "A spectral characterization of correlation-immune combining functions", and later the main result was called Xiao-Massey theorem. The Xiao-Massey theorem was an significant result in the field of stream ciphers, and had profound influence on the analysis and design of many stream ciphers. In this paper, we document the historical context, academic influence and originality of Xiao-Massey theorem. In particular, we point out that the notion of "invariant" proposed by Golomb in 1959 is a spectral characterization of the Boolean functions in a group invariance equivalence class by its nature: it is neither equivalent to the notion of correlation immunity, nor a sufficient spectral characterization of correlation-immune functions.