TARU PUBLICATIONS
Journal of Discrete Mathematical Sciences and Cryptography cover

Journal of Discrete Mathematical Sciences and Cryptography

(Since 1998)
Open Access ·Peer-reviewed·ISSN (Online): 2169-0065·ISSN (Print): 0972-0529

CiteScore 2025: 2.7 (Q1)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research in all areas of Discrete Mathematical Sciences, Cryptography, Combinatorics, Elliptic Curves and Information Security.

Issues up to 2022 co-published with and available at:Taylor & Francis Online
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Discrete Mathematical Sciences and Cryptography
Open Access Research Article

Analysis of the empirical complexity of Advanced Encryption Standards - 128 statistically

, * , ,

* Corresponding author · click or hover a name for details

pp. 1887–1903Vol. 27Issue 6September 2024DOI: 10.47974/JDMSC-1854 Crossmark XML
Received:
12 Nov 2019
Published Online:
16 Sep 2024
Article type:
Research Article
Language:
EN
Article no.:
JDMSC-1854
Pages:
1887–1903

Abstract

Algorithm analysis stands as a cornerstone in the field of theoretical computer science, captivating researchers with its focus on dissecting and understanding the operational complexity of various algorithms. This intricate process is pivotal for acquiring deeper insights into the practical performance of algorithms, beyond what is discernible from theoretical analysis alone. A relatively novel and increasingly relevant approach in this realm is the concept of empirical complexity. This method diverges from traditional theoretical analysis by placing emphasis on the practical execution of an algorithm across a spectrum of varying and escalating input sizes. Such a hands-on approach is instrumental in predicting the complexity of the algorithm in real-world scenarios. The empirical data thus obtained undergoes rigorous statistical analysis, enabling a more nuanced and concrete understanding of the algorithm’s behavior and performance. This approach not only enriches our comprehension of algorithms but also plays a crucial role in optimizing and refining their application in practical computing environments. • Background: In the realm of digital security, cryptographic algorithms are indispensable for protecting applications and safeguarding sensitive information, be it of national significance or personal confidentiality. The efficiency of these algorithms in contemporary, high-velocity computational environments is paramount. Such algorithms typically incorporate intricate mathematical operations. This study delves into the computational intricacies of AES-128, a predominant cryptographic algorithm, scrutinizing its computational complexity.  • Method: This study applies a thorough empirical complexity framework to establish the asymptotic limits of AES-128 accurately. It then conducts a detailed regression analysis with closed boundaries to measure AES-128’s empirical complexity with precision. • Result: The investigation reveals that the empirical complexity of AES-128 adheres to an Oemp (n) notation, where ‘n’ represents the size of the input data.  • Conclusion: The research establishes that AES-128’s time complexity for both encryption and decryption processes aligns with O(n), a finding supported through both empirical evidence and theoretical analysis. Furthermore, a statistical model has been crafted to accurately forecast the execution time based on any specified input size for AES-128’s encryption and decryption activities. This advancement aids in predicting performance outcomes prior to the actual encoding process.

Keywords

Statistical analysisEmpirical complexityCryptographyAES-128Algorithmic analysis

Subject Classifications

94A6094A6262M1011T71

References

[1] Goldsmith, S. F., Aiken, A. S., & Wilkerson, D. S. Measuring empirical computational complexity. In Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering (pp. 395-404) (2007, September).
[2] D.E. Knuth, “Fundamental Algorithms, Volume 1”, Addison-Wisley, (1973).
[3] S. Chakraborty, P.P. Choudhury, “A Statistical Analysis of an Algorithm’s Complexity,” Applied Mathematics Letters 13, Elsevier, pp-121-126 (2000).
[4] S. Chakraborty, K.K. Sundararajan, “A Simple Empirical Formula for Categorizing Computing Operation”, Applied Mathematics and Computation 187”, Elsevier, pp-326-340 (2007).
[5] S.K. Sourabh, S. Chakraborty, “Empirical O(n2) Complexity is Convincingly Gettable with Two Dense Matrix in nXn Matrix Multiplication”, InterStat (2006).
[6] S.C. Gupta, V.K. Kapoor, “Fundamental of Mathematical statistics”, Sultan Chand & Sons
[7] L. Wasserman, “All of Statistics: A Concise course in Statistical Inference”, Springer, Oct. (2004).
[8] G. James, D. Witten, T. Hastie, R. Tibshirani, “An Introduction to Statistical Learning with application in R”, Springer, September (2017).
[9] D. Wackerly, W. Mendenhall, R.L. Scheaffer, “Mathematical Statistics with Application”, Thomson Brooks/Cole, 7th edition (2008).
[10] S. Chakraborty, S. K. Sourabh, “A Computer Experiment Oriented Approach to Algorithmic Complexity”, LAP LAMBERT Academic, (2010).
[11] “Announcing the ADVANCED ENCRYPTION STANDARD (AES)” Federal Information Processing Standards Publication 197. United States National Institute of Standards and Technology (NIST). November 26, 2001. Retrieved October 2, (2012).
[12] Daemen, Joan; Rijmen, Vincent (March 9, 2003). “AES Proposal: Rijndael”. 
[13] Marcelo Vaz Netto and Sahudy Montenegro González. 2022. SSLC: A Search Algorithm Based on Linear Collisions and Poisson Probability Distribution. ACM J. Exp. Algorithmics 27, Article 1.4, 15 pages (December 2022). https://doi.org/10.1145/3497876.
[14] Bossaerts, P., Yadav, N., & Murawski, C. Uncertainty and computational complexity. Philosophical Transactions of the Royal Society B, 374(1766), 20180138 (2019).
[15] Athanasopoulos, D., & McEwen, M. Multi-objective empirical computational complexity of single-tenant service instances deployed at the Edge. Journal of Systems and Software, 111665 (2023).
[16] Bossaerts, P., & Murawski, C. Computational complexity and human decision-making. Trends in Cognitive Sciences, 21(12), 917-929 (2017).
[17] Anowar, F., Sadaoui, S., & Selim, B. Conceptual and empirical comparison of dimensionality reduction algorithms (pca, kpca, lda, mds, svd, lle, isomap, le, ica, t-sne). Computer Science Review, 40, 100378 (2021).
[18] Alizadeh, R., Allen, J. K., & Mistree, F. Managing computational complexity using surrogate models: a critical review. Research in Engineering Design, 31, 275-298 (2020).
[19] Prashant Pranav, Sandip Dutta and Soubhik Chakraborty, “Empirical and Statistical Comparison of Intermediate Steps of AES – 128 and RSA in Terms of Time Consumption”, Soft Computing Springer,  Volume – 25, pp. 13127 – 13145, August (2021). 
[20] Sacks, J., Welch, W. J., Mitchell, T. J., & Wynn, H. P. Design and analysis of computer experiments. Statistical science, 4(4), 409-423 (1989).

Views: 144Downloads: 6Citations: 0