计算机学院博士生在计算机系统结构领域顶级期刊发表论文

文:韩孟洁 / 来源:计算机学院 / 2017-01-11 / 点击量:2608

  近日,计算机学院博士生在计算机体系结构领域顶级期刊《IEEE Transactions on Computers》(IEEE-TOC)以长文形式发表题为“Computing Affine Equivalence Classes of Boolean Functions by Group Isomorphism”的研究论文。2014级博士生张艳为论文第一作者,其导师杨国武教授为论文第二作者,电子科技大学大数据研究中心为论文第一通讯单位。这是我校以在校博士生为第一作者在该期刊上发表的首篇论文。

  在数字集成电路与密码学领域,布尔函数仿射等价类的划分问题一直是一个很重要的问题。从理论上讲,该问题可被归约为一个NP难问题,因此从事该问题的研究十分困难;从实际应用出发,该问题的研究推进可以应用到逻辑电路和密码设计中。一方面,由于仿射等价的布尔函数可以共用一个逻辑电路,因此在组合逻辑电路的设计中,如果已经完成了布尔函数的仿射等价类划分,那么只需要对每一个等价类中的代表元设计一个逻辑电路,其他与这个代表元等价的布尔函数都可以通过对该电路的输入进行相应的仿射变换来实现(如图)。通过这种方法可以简化电路的设计,从而提高组合电路设计的效率。

无标题1.gif无标题2.gif

同一个逻辑电路实现两个仿射等价的布尔函数f1、f2 

  另一方面,在密码学领域,由于仿射等价的布尔函数具有许多相似的密码学性质, 如非线性度、差分性质等。密码学界一直致力于寻找和构造具有优良密码学性质的密码函数,通过对布尔函数进行仿射等价分类的研究,可以帮助寻找具有优良性质的密码函数。

  受计算机现有内存限制,之前的方法只能对至多6个变量的布尔函数集合进行仿射等价分类,该论文提出的方法可对更大规模的布尔函数集合进行仿射等价类的划分。文章首次将群同构思想应用到布尔函数的仿射等价分类中,通过建立仿射群到置换群的同构映射,利用置换群作用在集合上的性质,应用GAP完成计算。在计算过程中,不需要存储整个布尔函数空间,因此计算所需的存储空间比整个布尔函数空间小很多,从而在很大程度上提高了可等价分类的布尔函数集合的规模。用文章的方法可对10个变量的布尔函数全集等价分类,使可计算的规模从232(4G)提高到21024(≈26T)。  

  计算机体系结构领域的研究主要关注计算机的设计原理与实现方案,是计算机学科的基石,也是微电子、集成电路与计算机科学的交叉学科,在信息技术领域具有重要地位。《IEEE Transactions on Computers》是电子电气工程师协会计算机分会(IEEE Computer Society)会刊,是计算机体系结构领域顶级期刊。该期刊也被中国计算机学会(CCF)推荐为“计算机体系结构领域A类期刊”。


  论文链接:

  http://ieeexplore.ieee.org/document/7458854/


编辑:罗莎  / 审核:林坤  / 发布者:一戈