zbMATH — the first resource for mathematics

Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2). (English) Zbl 06889951
Summary: 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 (BP) heuristic . This yields a valuable tool for practical applications such as building fast software and low-power circuits for cryptographic applications, e.g. AES , HMAC-SHA-1 [8], PRESENT [9], GOST [9], and so on. However, the BP 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 BP heuristic were compared. They show that the Boyar-Peralta results are not optimal on dense systems.

68Q Theory of computing
Full Text: DOI
[1] Paar, C., Optimized arithmetic for Reed-Solomon encoders, (Proceedings of 1997 IEEE International Symposium on Information Theory, (1997)), 250
[2] Satoh, A.; Morioka, S.; Takano, K.; Munetoh, S., A compact rijndael hardware architecture with S-box optimization, (Advances in Cryptology, Lecture Notes in Computer Science, vol. 2248, (2001), Springer), 239-254 · Zbl 1067.94563
[3] Paar, C., Some remarks on efficient inversion in finite fields, (Proceedings of 1995 IEEE International Symposium on Information Theory, (1995)), 58
[4] Canright, D., A very compact S-box for AES, (Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, vol. 3659, (2005), Springer), 441-455 · Zbl 1319.94054
[5] Boyar, J.; Peralta, R., A new combinational logic minimization technique with applications to cryptology, (Experimental Algorithms, Lecture Notes in Computer Science, vol. 6049, (2010), Springer Berlin Heidelberg), 178-189
[6] Boyar, J.; Matthews, P.; Peralta, R., Logic minimization techniques with applications to cryptology, J. Cryptol., 26, 280-312, (2013) · Zbl 1279.94056
[7] Boyar, J.; Find, M. G.; Peralta, R., Small low-depth circuits for cryptographic applications, Cryptogr. Commun., (2018)
[8] Visconti, A.; Gorla, F., Exploiting an HMAC-SHA-1 optimization to speed up PBKDF2, (2018), Cryptology ePrint Archive, Report 2018/097
[9] Courtois, N.; Hulme, D.; Mourouzis, T., Solving circuit optimisation problems in cryptography and cryptanalysis, (2011), Cryptology ePrint Archive, Report 2011/475
[10] CMT, Circuit minimization team
[11] De Piccoli, A.; Visconti, A.; Rizzo, O. G., Polynomial multiplication over binary finite fields: new upper bounds, (2018), Cryptology ePrint Archive, Report 2018/091
[12] Bernstein, D. J., High-speed cryptography in characteristic 2, (2009)
[13] Lupanov, O., On rectifier and switching-and-rectifier schemes, Dokl. Akad. 30 Nauk SSSR, 111, 1171-1174, (1965) · Zbl 0072.43204
[14] Boyar, J.; Find, M. G., Cancellation-free circuits in unbounded and bounded depth, Theor. Comput. Sci., 590, 17-26, (2015) · Zbl 1328.94110
[15] Visconti, A.; Schiavo, C.; Peralta, R., Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2), (2017), Cryptology ePrint Archive, Report 2017/194
[16] Visconti, A., A benchmark set · Zbl 0043.42406
[17] Fuhs, C.; Schneider-Kamp, P., Synthesizing shortest linear straight-line programs over GF(2) using SAT, (Theory and Applications of Satisfiability Testing - SAT 2010, Lecture Notes in Computer Science, vol. 6175, (2010), Springer Berlin Heidelberg), 71-84 · Zbl 1306.68156
[18] Fuhs, C.; Schneider-Kamp, P., Optimizing the AES S-box using SAT, (8th International Workshop on the Implementation of Logics IWIL 2010, EPiC Series in Computing, vol. 2, (2012), EasyChair), 64-70
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.