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 [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 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.
Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2) / A. Visconti, C.V. Schiavo, R. Peralta. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 137(2018 Sep), pp. 1-5.
Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2)
A. Visconti
;C.V. Schiavo;
2018
Abstract
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 [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 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.File | Dimensione | Formato | |
---|---|---|---|
58_AV_Riassunto_INF_PROC_LETT_Rev 1b_after_WERB_process.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
270.87 kB
Formato
Adobe PDF
|
270.87 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S0020019018300905-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
416.83 kB
Formato
Adobe PDF
|
416.83 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.