Visconti Andrea, Schiavo Chiara Valentina, Peralta René
Università degli Studi di Milano, Department of Computer Science, via Comelico 39/41, 20135, Milano, Italy.
National Institute of Standards and Technology, 100 Bureau Dr, Gaithersburg, MD, United States.
Inf Process Lett. 2018;137. doi: 10.1016/j.ipl.2018.04.010.
Minimizing the Boolean circuit implementation of a given cryptographic function is an important issue. A number of papers [1], [2], [3], [4] only consider cancellation-free straight-line programs for producing small circuits over GF(2). Cancellation is allowed by the Boyar-Peralta ( ) heuristic [5, 6]. This yields a valuable tool for practical applications such as building fast software and low-power circuits for cryptographic applications, e.g. AES [5, 7], HMAC-SHA-1 [8], PRESENT [9], GOST [9], and so on. However, the heuristic does not take into account the matrix density. In a dense linear system the rows can be computed by adding or removing a few elements from a "common path" that is "close" to almost all rows. The new heuristic described in this paper will merge the idea of "cancellation" and "common path". An extensive testing activity has been performed. Experimental results of the new and the heuristic were compared. They show that the Boyar-Peralta results are not optimal on dense systems.
将给定密码函数的布尔电路实现最小化是一个重要问题。许多论文[1]、[2]、[3]、[4]仅考虑用于在GF(2)上生成小型电路的无抵消直线程序。Boyar - Peralta启发式算法[5, 6]允许抵消。这为诸如构建用于密码应用（如AES[5, 7]、HMAC - SHA - 1[8]、PRESENT[9]、GOST[9]等）的快速软件和低功耗电路等实际应用产生了一个有价值的工具。然而，该启发式算法没有考虑矩阵密度。在密集线性系统中，行可以通过从几乎所有行“接近”的“公共路径”添加或移除一些元素来计算。本文描述的新启发式算法将融合“抵消”和“公共路径”的思想。已经进行了广泛的测试活动。比较了新启发式算法和该启发式算法的实验结果。结果表明，在密集系统上，Boyar - Peralta的结果并非最优。
