Parallel Fast Walsh Transform Algorithm and Its Implementation with CUDA on GPUs

Bikov, Dusan; Bouyukliev, Iliya

doi:10.2478/cait-2018-0018

Abstract

Some of the most important cryptographic characteristics of the Boolean and vector Boolean functions (nonlinearity, autocorrelation, differential uniformity) are connected with the Walsh spectrum. In this paper, we present several algorithms for computing the Walsh spectrum implemented in CUDA for parallel execution on GPU. They are based on the most popular sequential algorithm. The algorithms differ in the complexity of implementations, resources used, optimization strategies and techniques. In the end, we give some experimental results.

References

1. Alvarez-Cubero, J., P. Zufiria. A C++ Class for Analysing Vector Boolean Functions from a Cryptographic Perspective. – In: Proc. of International Conference on Security and Cryptography (SECRYPT’10), 2010, pp. 512-520.10.5220/0002964505120520
Search in Google Scholar Back to article
2. Andrade, J., G. Falcao, V. Silva. Optimized Fast Walsh-Hadamard Transform on GPUs for Non-Binary LDPC Decoding. – Parallel Computing, Vol. 40, 2014, No 9, pp. 449-453.10.1016/j.parco.2014.07.001
Open DOI Search in Google Scholar Back to article
3. Bouyukliev, I., D. Bikov. Applications of the Binary Representation of Integers in Algorithms for Boolean Functions. – In: Proc. of 44th Spring Conference of the Union of Bulgarian Mathematicians, Mathematics and Education in Mathematics, 2015, pp. 161-166.
Search in Google Scholar Back to article
4. Carlet, C. Boolean Functions for Cryptography and Error Correcting Codes. – In: C. Crama and P. Hammer, Eds. Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, 2010, pp. 257-397.10.1017/CBO9780511780448.011
Search in Google Scholar Back to article
5. Copeland, A. D., N. B. Chang, S. Lung. GPU Accelerated Decoding of High Performance Error Correcting Codes. – In: Proc. of 14th Annual Workshop on HPEC, Lexington, Massachusetts, USA, 2010.
Search in Google Scholar Back to article
6. CUDA C Programming Guide. https://docs.nvidia.com/cuda/cuda-c-programming-guide/
Search in Google Scholar Back to article
7. CUDA Homepage. http://www.nvidia.com/object/cudahomenew.html
Search in Google Scholar Back to article
8. Demouth, J. Kepler’s Shuffle: Tips and Tricks. – GPU Technology Conference, 2013. http://on-demand.gputechconf.com/gtc/2013/presentations/S3174-Kepler-Shuffle-Tips-Tricks.pdf
Search in Google Scholar Back to article
9. Good, I. J. The Interaction Algorithm and Practical Fourier Analysis. – Journal of the Royal Statistical Society, Vol. 20, 1958, No 2, pp. 361-372.10.1111/j.2517-6161.1958.tb00300.x
Search in Google Scholar Back to article
10. Joux, A. Algorithmic Cryptanalysis. Chapman & Hall/CRC Cryptography and Network Security Series, 2009.
Search in Google Scholar Back to article
11. Karpovsky, M. G., R. S. Stankovic, J. T. Astola. Spectral Logic and Its Applications for the Design of Digital Devices. Wiley, 2008.10.1002/9780470289228
Search in Google Scholar Back to article
12. Kirk, D. B., We n-me i W. Hw u. Programming Massively Parallel Processors: A Hands-on Approach. Elsevier, 2013.
Search in Google Scholar Back to article
13. Kurzak, J., D. A. Bader, J. Dongarra. Scientific Computing with Multicore and Accelerators. CRC Press, 2010.10.1201/b10376
Search in Google Scholar Back to article
14. Lindholm, E., J. Nickolls, S. Oberman, J. Montrym. NVIDIA Tesla: A Unied Graphics and Computing Architecture. – IEEE Micro, Vol. 28, 2008, Issue 2.10.1109/MM.2008.31
Search in Google Scholar Back to article
15. Lobeiras, J., M. Amor, R. Doallo. BPLG: A Tuned Buttery Processing Library for GPU Architectures. – International Journal of Parallel Programming, Vol. 43, 2015, No 6, pp. 1078-1102.10.1007/s10766-014-0323-8
Search in Google Scholar Back to article
16. Maciol, P., K. Banas. Testing Tesla Architecture for Scientific Computing: The Performance of Matrix-Vector Product. – In: Computer Science and Information Technology, IMCSIT 2008, pp. 285-291.10.1109/IMCSIT.2008.4747253
Search in Google Scholar Back to article
17. MATLAB Platform for Solving Engineering and Scientific Problems. https://www.mathworks.com/products/matlab/
Search in Google Scholar Back to article
18. NVIDIA GeForce GT 740M Specification. http://www.geforce.com/hardware/notebook-gpus/geforce-gt-740m
Search in Google Scholar Back to article
19. NVIDIA GeForce GTX TITAN Specification. http://http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-titan/specifications
Search in Google Scholar Back to article
20. NVIDIA: CUDA cuFFT Library. http://docs.nvidia.com/cuda/cufft/
Search in Google Scholar Back to article
21. Owens, J.D., M. Houston, D. Luebke, S. Green, J. E. Stone, J. C. Phillips. GPU Computing. – Proc. of IEEE, Vol. 96, 2008, No 5, pp. 879-899.10.1109/JPROC.2008.917757
Open DOI Search in Google Scholar Back to article
22. Picek, S., L. Batina, D. Jakobovic, B. Ege, M. Golub. S-Box, SET, Match: A Toolbox for S-Box Analysis. – In: Information Security Theory and Practice. Securing the Internet of Things, Lecture Notes in Computer Science, Vol. 8501, 2014, pp. 140-149.10.1007/978-3-662-43826-8_10
Search in Google Scholar Back to article
23. Sage Mathematics Software. http://www.sagemath.org/
Search in Google Scholar Back to article
24. Shucai, Xiao, Wu-chun Feng. Inter-Block GPU Communication via Fast Barrier Synchronization. – In: IEEE International Symposium on Parallel & Distributed Processing (IPDPS’10), 2010.10.1109/IPDPS.2010.5470477
Search in Google Scholar Back to article

Parallel Fast Walsh Transform Algorithm and Its Implementation with CUDA on GPUs

Abstract

Paradigm

My account