Method for designing encoding algorithms based on AND/OR trees

Shablya, Yuriy; Polyuga, Vadim

doi:10.47974/JDMSC-2195

Open Access Research Article

Method for designing encoding algorithms based on AND/OR trees

^*Yuriy ShablyaCorresponding authorsyv@fb.tusur.ruLaboratory of Algorithms and Technologies for Discrete Structures Research Tomsk State University of Control Systems and RadioelectronicsTomsk, 634050, RussiaView full profile → , Vadim Polyugavadimiuspolyuga@gmail.comLaboratory of Algorithms and Technologies for Discrete Structures Research Tomsk State University of Control Systems and RadioelectronicsTomsk, 634050, RussiaView full profile →

* Corresponding author · click or hover a name for details

pp. 1219–1238Vol. 29Issue 3March 2026DOI: 10.47974/JDMSC-2195 Crossmark XML

Received:: 09 Apr 2024
Published Online:: 28 Jul 2025
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2195
Pages:: 1219–1238

Abstract

Information security is an important task in the digital age, and one of the ways to protect data is to use cryptographic methods. This paper discusses the problem of creating new combinatorial generation algorithms that can later be used as a mathematical basis for solving specific problems in the field of cryptography. For example, as a result of applying a ranking algorithm to a text over some alphabet, it will be encoded with the appropriate rank value. If some of the information that was used in this encoding process is declared as a secret, then the reverse decoding will become a difficult task. According to this idea, we proposed a method for designing encoding and decoding functions by using combinatorial generation algorithms that is based on applying AND/OR tree structures. Several examples of implementing the steps of the proposed method are also presented.

Keywords

Combinatorial set Combinatorial generation algorithm AND/OR tree Ranking Unranking Encoding Decoding

Subject Classifications

68P2505C05

References

[1] S. Bacchelli, E. Barcucci, E. Grazzini, and E. Pergola, “Exhaustive generation of combinatorial objects by ECO,” Acta Informatica, vol. 40, pp. 585–602 (2004), doi: 10.1007/s00236-004-0139-x.
[2] M. Bellare, T. Ristenpart, P. Rogaway, and T. Stegers, “Format-preserving encryption,” in Lecture Notes in Computer Science, vol. 5867, pp. 295–312 (2009), doi: 10.1007/978-3-642-05445-7_19.
[3] F. Benhamouda, C. Chevalier, A. Thillard, and D. Vergnaud, “Easing Coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness,” in Lecture Notes in Computer Science, vol. 9615, pp. 36–66 (2016), doi: 10.1007/978-3-662-49387-8_3.
[4] D. P. Bhatt, L. Raja, and S. Sharma, “Light-weighted cryptographic algorithms for energy efficient applications,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 3, pp. 643–650 (2020), doi: 10.1080/09720529.2020.1729510.
[5] P. Flajolet, P. Zimmerman, and B. Cutsem, “A calculus for the random generation of combinatorial structures,” Theoretical Computer Science, vol. 132, pp. 1–35 (1994), doi: 10.1016/0304-3975(94)90226-7.
[6] O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools. Cambridge, U.K.: Cambridge Univ. Press (2008).
[7] X. Han, G. Han, H. Cai, and L. Yin, “Locally repairable codes with multiple repair sets based on packings of block size 4,” Cryptography and Communications (2023), doi: 10.1007/s12095-023-00681-z.
[8] E. Hartung, H. Hoang, T. Mutze, and A. Williams, “Combinatorial generation via permutation languages. I. Fundamentals,” Transactions of the American Mathematical Society, vol. 375, pp. 2255–2291 (2022), doi: 10.1090/tran/8199.
[9] L. Kampel, P. Kitsos, and D. E. Simos, “Locating hardware Trojans using combinatorial testing for cryptographic circuits,” IEEE Access, vol. 10, pp. 18787–18806 (2022), doi: 10.1109/ACCESS.2022.3151378.
[10] S. Kant, V. Sharma, N. Verma, and B. K. Dass, “Identification scheme for romanized Indian languages from their plain and ciphered bit stream,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 13, no. 3, pp. 329–345 (2010), doi: 10.1080/09720529.2010.10698298.
[11] P. Kitsos, D. E. Simos, J. Torres-Jimenez, and A. G. Voyiatzis, “Exciting FPGA cryptographic Trojans using combinatorial testing,” in Proc. IEEE 26th Int. Symp. Software Reliability Engineering (ISSRE), pp. 69–76 (2015), doi: 10.1109/ISSRE.2015.7381800.
[12] D. E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Boston, MA, USA: Addison-Wesley Professional (2011).
[13] D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search. Boca Raton, FL, USA: CRC Press (1999).
[14] A. Melman, O. Evsutin, and Y. Shablya, “On the efficiency of combinatorial generation for adaptive image steganography,” in Proc. 2021 Int. Conf. Engineering and Telecommunication (EnT) (2021), doi: 10.1109/EnT50460.2021.9681730.
[15] S. Miracle and S. Yilek, “Targeted invertible pseudorandom functions and deterministic format-transforming encryption,” in Lecture Notes in Computer Science, vol. 13871, pp. 622–642 (2023), doi: 10.1007/978-3-031-30872-7_24.
[16] M. Mumtaz and L. Ping, “Forty years of attacks on the RSA cryptosystem: A brief survey,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 22, no. 1, pp. 9–29 (2019), doi: 10.1080/09720529.2018.1564201.
[17] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, https://oeis.org.
[18] F. Ruskey, Combinatorial Generation (2003), https://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf.
[19] M. Saracevic, S. Adamovic, and E. Bisevac, “Application of Catalan numbers and the lattice path combinatorial problem in cryptography,” Acta Polytechnica Hungarica, vol. 15, pp. 91–110 (2018), doi: 10.12700/aph.15.7.2018.7.5.
[20] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, Wiley (1996).
[21] Y. Shablya, D. Kruchinin, and V. Kruchinin, “Method for developing combinatorial generation algorithms based on AND/OR trees and its application,” Mathematics, vol. 8, 962 (2020), doi: 10.3390/math8060962.
[22] Y. Shablya, A. Merinov, and D. Kruchinin, “Combinatorial generation algorithms for directed lattice paths,” Mathematics, vol. 12, 1207 (2024), doi: 10.3390/math12081207.
[23] K. Sugimoto, T. Nakai, Y. Watanabe, and M. Iwamoto, “The two sheriffs problem: Cryptographic formalization and generalization,” Lecture Notes in Computer Science, vol. 14461, pp. 512–523 (2023), doi: 10.1007/978-3-031-49611-0_37.
[24] Y. Wei, L. Bi, K. Wang, and X. Lu, “An improved BKW algorithm for solving LWE with small secrets,” Lecture Notes in Computer Science, vol. 14411, pp. 578–595 (2023), doi: 10.1007/978-3-031-49187-0_29.
[25] Z. Zhiyong, Modern Cryptography: Volume 1, A Classical Introduction to Informational and Mathematical Principle, Springer Nature (2022), doi: 10.1007/978-981-19-0920-7.

Views: 76Downloads: 11Citations: 0