Fast Implementation of the ANF Transform


Бакоев, Валентин (2017) Fast Implementation of the ANF Transform Mini-symposium “Optimal Codes and Related Topics” in the frame of Second International Conference “Mathematics Days in Sofia”, July 10–14, 2017, Sofia, Bulgaria, http://www.math.bas.bg/moiuser/OCRT2017/a3.pdf


  The algebraic normal forms (ANFs) of Boolean functions are used in computing the algebraic degree of S-boxes, which is one of the most important cryptographic criteria. It should be computed by fast algorithms so that more S-boxes are generated and the best of them are selected. Here we continue our previous work for fast computing the ANFs of Boolean functions. We represent and investigate the full version of bitwise implementation of the ANF Transform. The obtained algorithm has a time-complexity $\Theta((9n-2).2^{n-7})$ and $\Theta(2^{n-6})$ space complexity. The experimental results show that it is more than 20 times faster in comparison to the well-known byte-wise ANF Transform.
  Доклад
 algebraic normal form transform, (fast) Mobius transform, Zhegalkin transform, positive polarity Reed-Muller transform, bitwise implementation


Природни науки, математика и информатика
Природни науки, математика и информатика Информатика и компютърни науки

Natural sciences, mathematics and informatics
Natural sciences, mathematics and informatics Informatics and Computer Science

 Издадено
  20211
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/