线性反馈移位寄存器的邻接图

活动时间： 01月18日09时00分       

地            点  ： 公教楼E-405教室

讲座内容：

De Bruijn 序列是指周期为 2^n 并且一个周期中包含了所有 n 长比特串的序列. 这种序列具有很多良好的性质, 被广泛应用在通信和密码学中. 构造 De Bruijn 序列目前仍然是比较困难的问题. 传统的构造方法是并圈法---考察某个移位寄存器, 将移位寄存器中的所有圈合并成一个极大圈, 从而得到 De Bruijn 序列. 并圈法的一个关键步骤是寻找圈之间的共轭状态. 对于一般的移位寄存器, 考察共轭状态的分布很困难, 因此并圈法大多应用于线性移位寄存器. 共轭状态在圈中的分布情况称为移位寄存器的邻接图. 在很早的时候 (1960s), 人们就开始研究线性移位寄存器的邻接图, 一些特殊的移位寄存器的邻接图先后被确定了下来. 最近几年, 人们考察了更多类型的线性移位寄存器, 计算了它们的邻接图并构造 De Bruijn 序列. 然而, 还缺少求解线性移位寄存器邻接图的一般理论，而且, 已有的结果中, 所使用的工具各有不同, 这给进一步研究带来了困难. 我们希望看到一些更深层次的规律, 进而建立起求解邻接图的一般性理论, 这将给并圈法在线性移位寄存器的应用打下基础. 我们的工作正是围绕于此. 通过观察我们发现, 线移位寄存器的邻接图与某条特殊序列的直和分解有着密切的关系. 利用这种关系, 可以可将求解邻接图的问题转化为求解子空间上相关图的问题. 我们的结果涵盖了目前的已知结果, 并且将它们推广到了一般的情形. 线性移位寄存器邻接图理论还有一些遗留问题, 我们将在报告中与各位讨论.

主讲人介绍：

林东岱，中国科学院信息工程研究所研究员、博士生导师，信息安全国家重点实验室主任，中国密码学会常务理事及中国保密协会理事。主要从事密码学、安全协议、网络与系统安全、分布式密码计算等方面的研究工作，在《IEEE Transaction on Information Theory》，《Discrete Applied Mathematics》，《IEE Proceedings communications》，《Science in China》、EUROCRYPT欧洲密码学年会和ASIACRYPT亚洲密码学年会等国内外学术刊物和学术会议上发表学术论文200余篇，出版著作10余部。先后参加或承担八五攀登计划项目并任专家委员会委员、九五攀登预选项目，国家重大基础研究规划（973）、国家高科技发展计划（863）、国家自然科学基金等项目。目前参加承担的项目有国家自然科学基金“代数动力系统及其序列密码相关问题研究”、中国科学院先导专项子课题“海云信息安全体系研究”等。

发布时间：2018-01-16 17:13:33