Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to
Russian

All Issues >> Contents: Volume 07, Issue No 4 (2009)

Binary decision diagrams in logical equations and problems of discrete functions inversion
Aleksei Evgenyevich Khmelnov, Aleksei Sergeyevich Ignatyev, Aleksandr Anatolyevich Semenov

Institute of System Dynamics and Control Theory SB RAS

UDC code: 519.7

Abstract
The paper addresses software implementation of one approach to the problems of discrete functions inversion. Such an approach is based on the technique representing boolean functions in the form of binary decision diagrams (BDD). We propose new methods of memory usage optimization when working with BDD. The described technology is tested on some cryptanalysis problems.

Key Words
cryptanalysis, discrete functions, logical equations, binary decision diagrams

How to cite:
Khmelnov A. E., Ignatyev A. S., Semenov A. A. Binary decision diagrams in logical equations and problems of discrete functions inversion // Vestnik NSU Series: Information Technologies. - 2009. - Volume 07, Issue No 4. - P. 36-52. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

References
1. Lee C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal. 1959. Vol. 38. P. 985–999.
2. Akers S. B. Binary Decision Diagrams // IEEE Transactions on Computers. 1978. Vol. 27. № 6. P. 509–516.
3. Bryant R. E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Transactions on Computers. 1986. Vol. 35. № 8. P. 677–691.
4. Klark E. M., Gramberg O., Peled D. Verifikatciya modelei programm: Model Checking. M.: MTcNMO, 2002. 416 s.
5. Ubar R. Test Generation for Digital Circuits Using Alternative Graphs (in Russian) // Proc. Tallinn Technical University. 1976. № 409. P. 75–81.
6. Yablonsky S. V. Vvedeniye v diskretnuyu matematiku. M.: Nauka, 1986. 384 s.
7. Semenov A. A., Bespalov D. V. Tekhnologii resheniya mnogomernykh zadach logicheskogo poiska // Vestn. Tomsk. gos. un-ta. 2005. Prilozheniye. № 14. S. 61–73.
8. Meinel Ch., Theobald T. Algorithms and Data Structures in VLSI-Design: OBDDFoundations and Applications. Berlin: Springer-Verlag, 1998. 267 p.
9. Katlend N. Vychislimost. Vvedeniye v teoriyu rekursivnykh funktcy. M.: Mir, 1983.
256 s.
10. Geri M., Dzhonson D. Vychislitelnyye mashiny i trudnoreshayemyye zadachi. M.: Mir, 1982. 416 s.
11. Cook S. A. The Complexity of Theorem-Proving Procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing, ACM. Ohio, 1971. P. 151–159. [Perevod: Kuk S. A. Slozhnost protcedur vyvoda teorem. Kibernetichesky sbornik. Novaya seriya. Vyp. 12. M.: Mir, 1975. S. 5–15]
12. Karp R. M., Lipton R. J. Some Connections between Nonuniform and Uniform Complexity Classes // Proc. of the 12th ACM Symposium on Theory of Computing. 1980. P. 302–309.
13. Fortune S. J. A Sweepline Algorithm for Voronoi Diagrams // Algorithmica. 1987. № 2. P. 153–174.
14. Ignatyev A. S., Semenov A. A., Khmelnov A. E. Resheniye sistem logicheskikh uravneny s ispolzovaniyem BDD // Vestn. Tomsk. gos. un-ta. 2006. Prilozheniye. № 17. S. 25–29.
15. Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. 657 p.
16. Semenov A. A. Logiko-evristichesky podkhod v kriptoanalize generatorov dvoichnykh posledovatelnostei // Tr. mezhdunar. nauch. konf. PAVT’07. Chelyabinsk: Izd-vo YuUrGU, 2007. T. 1. S. 170–180.
17. Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V. Osnovy kriptografii. M.: Gelios ARV, 2002. 480 s.
18. Shiple T. R., Hojati R., Sangiovanni-Vincentelli A. L., Brayton R. K. Heuristic Minimization of BDDs, Using Don’t Cares // University of California, Berkeley. Technical Report No. UCB/ERL M93/58. 1993.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 07, Issue No 4 (2009).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 07, Issue No 4 (2009).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2009
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle


|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Old Site in Russian|

inftech@vestnik.nsu.ru
© 2006-2017, Novosibirsk State University.