214
D. M. Miller and M. Soeken
emphasize again that the algorithm can be used to determine the linear, affine or
spectral equivalence of two functions for arbitrary n.
The approaches discussed in this chapter are searches dependent on the number
of variables and the actual spectral coefficient values. Spectra where a large number
of coefficients have equal magnitude values appear to lead to the longest searches.
We are looking at techniques to prune the searches and will undertake a formal
analysis of the computational complexity once those techniques are incorporated.
Acknowledgements The authors gratefully acknowledge the constructive comments from the
referees of an earlier paper presented at IWSBP2018 which led to improvements in the presentation
of this work.
References
1. Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to
cryptology. J. Cryptol. 26(2), 280–312 (2013)
2. Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to
cryptology. In: International Symposium on Experimental Algorithms, pp. 178–189 (2010)
3. Edwards, C.R.: The application of the Rademacher-Walsh transform to Boolean function
classification and threshold logic synthesis. IEEE Trans. Comput. 24(1), 48–62 (1975)
4. Fuller, J.E.: Analysis of affine equivalent Boolean functions for cryptography. Ph.D. Thesis,
Queensland University of Technology (2003)
5. Harrison, M.A.: Introduction to Switching and Automata Theory. McGraw Hill, New York
(1963)
6. Harrison, M.A.: On the classification of Boolean functions by the general linear and affine
group. SIAM J. 12, 284–299 (1964)
7. Hurst, S.L.: The Logical Processing of Digital Signals. Arnold, London (1978)
8. Hurst, S.L., Miller, D.M., Muzio, J.C.: Spectral Techniques in Digital Logic. Academic,
London (1985)
9. Karpovsky, M.G.: Finite Orthogonal Series in the Design of Digital Devices. Wiley, New York
(1976)
10. Lechner, R.J.: Harmonic analysis of switching functions. In: Mukhopadhyay, A. (ed.) Recent
Developments in Switching Theory. Academic, London (1971)
11. Lv, J., Kalla, P., Enescu, F.: Verification of composite Galois field multipliers over GF((2 m ) n )
using computer algebra techniques. In: International High Level Design Validation and Test
Workshop, pp. 136–143 (2011)
12. Maiorana, J.A.: A classification of the cosets of the Reed-Muller code r(1, 6). Math. Comput.
57(195), 403–414 (1991)
13. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge
University Press, Cambridge (2000)
14. Rademacher, H.: Einige sitze uber reihen von allgemeinen orthogonal-funktionen. Math. Ann.
87, 112–138 (1922)
15. Sasao, T., Matsuura, K., Iguchi, Y.: A method to identify affine equivalence classes of logic
functions. In: Proc. SASIMI, pp. 266–271 (2018)
16. Soeken, M., Abdessaied, N., De Micheli, G.: Enumeration of reversible functions and its
application to circuit complexity. In: International Conference on Reversible Computation.
pp. 255–270 (2016)
D. M. Miller and M. Soeken
emphasize again that the algorithm can be used to determine the linear, affine or
spectral equivalence of two functions for arbitrary n.
The approaches discussed in this chapter are searches dependent on the number
of variables and the actual spectral coefficient values. Spectra where a large number
of coefficients have equal magnitude values appear to lead to the longest searches.
We are looking at techniques to prune the searches and will undertake a formal
analysis of the computational complexity once those techniques are incorporated.
Acknowledgements The authors gratefully acknowledge the constructive comments from the
referees of an earlier paper presented at IWSBP2018 which led to improvements in the presentation
of this work.
References
1. Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to
cryptology. J. Cryptol. 26(2), 280–312 (2013)
2. Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to
cryptology. In: International Symposium on Experimental Algorithms, pp. 178–189 (2010)
3. Edwards, C.R.: The application of the Rademacher-Walsh transform to Boolean function
classification and threshold logic synthesis. IEEE Trans. Comput. 24(1), 48–62 (1975)
4. Fuller, J.E.: Analysis of affine equivalent Boolean functions for cryptography. Ph.D. Thesis,
Queensland University of Technology (2003)
5. Harrison, M.A.: Introduction to Switching and Automata Theory. McGraw Hill, New York
(1963)
6. Harrison, M.A.: On the classification of Boolean functions by the general linear and affine
group. SIAM J. 12, 284–299 (1964)
7. Hurst, S.L.: The Logical Processing of Digital Signals. Arnold, London (1978)
8. Hurst, S.L., Miller, D.M., Muzio, J.C.: Spectral Techniques in Digital Logic. Academic,
London (1985)
9. Karpovsky, M.G.: Finite Orthogonal Series in the Design of Digital Devices. Wiley, New York
(1976)
10. Lechner, R.J.: Harmonic analysis of switching functions. In: Mukhopadhyay, A. (ed.) Recent
Developments in Switching Theory. Academic, London (1971)
11. Lv, J., Kalla, P., Enescu, F.: Verification of composite Galois field multipliers over GF((2 m ) n )
using computer algebra techniques. In: International High Level Design Validation and Test
Workshop, pp. 136–143 (2011)
12. Maiorana, J.A.: A classification of the cosets of the Reed-Muller code r(1, 6). Math. Comput.
57(195), 403–414 (1991)
13. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge
University Press, Cambridge (2000)
14. Rademacher, H.: Einige sitze uber reihen von allgemeinen orthogonal-funktionen. Math. Ann.
87, 112–138 (1922)
15. Sasao, T., Matsuura, K., Iguchi, Y.: A method to identify affine equivalence classes of logic
functions. In: Proc. SASIMI, pp. 266–271 (2018)
16. Soeken, M., Abdessaied, N., De Micheli, G.: Enumeration of reversible functions and its
application to circuit complexity. In: International Conference on Reversible Computation.
pp. 255–270 (2016)