Обратимые вычисления

обзор проблемы и новые результаты (отказоустойчивость и криптография)

Аннотация

В работе рассмотрены основные положения обратимости как новой парадигмы развития вычислительной техники. Первые разделы носят обзорный характер. Показана неизбежность т. н. "теплового проклятия" при сохранении традиционной парадигмы создания средств ВТ. Изложены основы обратимой логики, рассмотрены основные обратимые логические элементы и модели обратимых вычислений, в т. ч. обратимые клеточные автоматы. Кратко рассмотрены обратимые языки программирования. Во второй части затронуты основные вопросы логического синтеза схем из обратимых элементов и физическая реализация обратимой схемотехники. Кратко описана проблематика синтеза отказоустойчивых схем в парадигме обратимой схемотехники. Предлагается техника синтеза сбоеустойчивых обратимых элементов в хэмминговом пространстве и описываются некоторые такие схемы. Далее рассматривается проблематика применения схем из обратимых логических элементов в криптографии. Описывается предлагаемая общая схема создания обратимых схем с "уборкой мусора", предназначенных для криптографических применений.

Сведения об авторах

Sergey Isaevich Gurov, Московский государственный университет имени М. В. Ломоносова

старший научный сотрудник, доцент кафедры математических методов прогнозирования, факультет вычислительной математики и кибернетики, кандидат физико-математических наук, доцент

Aleksey Evgenievich Zhukov, Московский государственный технический университет имени Н. Э. Баумана (национальный исследовательский университет)

доцент кафедры ИУ8 "Информационная безопасность", факультет информатики и систем управления, кандидат физико-математических наук, доцент

Dmitry Vladimirovich Zakablukov, ООО "Алгоритмы и данные"

программист, кандидат физико-математических наук

Georgy Vladimirovich Kormakov, Московский государственный университет имени М. В. Ломоносова

студент, факультет вычислительной математики и кибернетики

Литература

[1] Landauer R. Irreversibility and Heat Generation in the Computing Proces. IBM Journal of Research and Development. 1961; 5(3):183-191. (In Eng.) DOI: 10.1147/rd.53.0183
[2] Bérut A., Arakelyan A., Petrosyan A. et al. Experimental verification of Landauer’s principle linking information and thermodynamics. Nature. 2012; 483:187-189. (In Eng.) DOI: 10.1038/nature10872
[3] DeBenedictis E.P. Will Moore's Law Be Sufficient? In: SC '04: Proceedings of the 2004 ACM/IEEE Conference on Supercomputing. Pittsburgh, PA, USA, 2004, pp. 45-45. (In Eng.) DOI: 10.1109/SC.2004.68
[4] Bennett C.H. Logical Reversibility of Computation. IBM Journal of Research and Development. 1973; 17(6):525-532. (In Eng.) DOI: 10.1147/rd.176.0525
[5] Saeedi M., Markov I.L. Synthesis and Optimization of Reversible Circuits – A Survey. ACM Computing Surveys (CSUR). 2013; 45(2):21. (In Eng.) DOI: 10.1145/2431211.2431220
[6] Merkle R.C. Reversible electronic logic using switches. Nanotechnology. 1993; 4(1):21 40. (In Eng.) DOI: 10.1088/0957-4484/4/1/002
[7] Zakablukov D.V. Synthesis methods for reversible circuits from NOT, CNOT, and 2-CNOT functional elements: dis. ... Ph.D. (Phys.-Math.). Moscow, 2018. (In Russ.)
[8] Toffoli T. Computation and construction universality of reversible cellular automata. Journal of Computer and System Sciences. 1977; 15(2):213-231. (In Eng.) DOI: 10.1016/S0022-0000(77)80007-X
[9] Feynman R.P. Quantum Mechanical Computers. Optics News. 1985; 11(2):11-20. (In Eng.) DOI: 10.1364/ON.11.2.000011
[10] Zhirnov V.V., Cavin R.K., Hutchby J.A., Bourianoff G. Limits to Binary Logic Switch Scaling - A Gedanken Model. Proceedings of the IEEE. 2003; 91(11):1934-1939. (In Eng.) DOI: 10.1109/JPROC.2003.818324
[11] Foster J.N. Bidirectional Programming Languages.Technical Report MS-CIS-10-08. Department of Computer & Information Science University of Pennsylvania. March 13, 2010. (In Eng.)
[12] Yokoyama T., Glück R. A reversible programming language and its invertible self-interpreter. In:Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation (PEPM ’07). Association for Computing Machinery, New York, NY, USA, 2007, pp. 144-153. (In Eng.) DOI: 10.1145/1244381.1244404
[13] Yokoyama T. Reversible Computation and Reversible Programming Languages. Electronic Notes in Theoretical Computer Science. 2010; 253(6):71-81. (In Eng.) DOI: 10.1016/j.entcs.2010.02.007
[14] Fredkin E.F., Toffoli T. Conservative logic. International Journal of Theoretical Physics. 1982; 21(3-4):219-253. (In Eng.) DOI: 10.1007/BF01857727
[15] Perumalla K.S. Introduction to Reversible Computing. CRC Press, 2014. (In Eng.)
[16] Nepejvoda N.N. Algebras as an alternative to numerical parallelism. In: NSCF-2012, First National Supercomputing Forum. Russia, Pereslavl-Zalessky, Program Systems Institute of RAS, November 29-30, 2012.
[17] Nepejvoda N.N. From Numerical Modeling to Algebraic. In: The parallel calculations and the tasks of the control. The works of the International Conference PACO-2012. Moscow, vol. 1, 2012, pp. 93-103. Available at: https://elibrary.ru/item.asp?id=22032867 (accessed 16.07.2019). (In Russ., abstract in Eng.)
[18] Toffoli T. Reversible computing. In: de Bakker J., van Leeuwen J. (eds). Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 1980; 85:632-644. (In Eng.) DOI: 10.1007/3-540-10003-2_104
[19] Shende V.V., Prasad A.K., Markov I.L., Hayes, J.P. Synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2003; 22(6):710-722. (In Eng.) DOI: 10.1109/TCAD.2003.811448
[20] Maslov D. The role of reversibility in computer technology of the future. Computerra. 2004; 14. Available at: http://www.kinnet.ru/cterra/538/33163.html (accessed 16.07.2019). (In Russ.)
[21] Wille R., Große D., Teuber L., Dueck G.W., Drechsler R. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In: 38th International Symposium on Multiple Valued Logic (ismvl 2008). Dallas, TX, 2008, pp. 220-225. (In Eng.) DOI: 10.1109/ISMVL.2008.43
[22] Maslov D., Dueck G.W., Scott N. Reversible logic synthesis benchmarks page. Technical report, 2003. Available at: http://www.cs.unb.ca/profs/gdueck/quantum (accessed 16.07.2019). (In Eng.)
[23] Jain A. Fault Tolerant Synthesis of Reversible Circuits. arXiv: 1310.5231, 2013. (In Eng.)
[24] Bruce J.W., Thornton M.A., Shivakumaraiah L., Kokate P.S., Li X. Efficient adder circuits based on a conservative reversible logic gate. In: Proceedings IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002. Pittsburgh, PA, USA, 2002, pp. 83-88. (In Eng.) DOI: 10.1109/ISVLSI.2002.1016879
[25] Bobkov S.G. Vysokoproizvoditelnye vychislitelnye systemy [High-Performance Computer Systems]. Moscow, NIISI RAN Publ., 2014. (In Russ.)
[26] Коrmakov G. V., Gurov S.I. Failure-proof reversible circuits and a method for their synthesis in Hamming space. in: Applied Mathematics and Informatics. Proceedings of the Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University. Moscow, MAKS Press, 2018, no. 57, pp. 21-35. (In Russ.)
[27] Thapliyal H., Zwolinski M. Reversible Logic to Cryptographic Hardware: A New Paradigm. In: 2006 49th IEEE International Midwest Symposium on Circuits and Systems. San Juan, 2006, pp. 342-346. (In Eng.) DOI: 10.1109/MWSCAS.2006.382067
[28] Noor Muhammed Nayeem, Lafifa Jamal, Hafiz Md. Hasan Babu. Efficient Reversible Montgomery Multiplier and Its Application to Hardware Cryptography. Journal of Computer Science. 2009; 5(1):49-56. (In Eng.) DOI: 10.3844/jcssp.2009.49.56
[29] Banerjee A., Pathak A. An analysis of reversible multiplier circuits. arXiv: 0907.3357v1 [quant-ph] 20 Jul 2009. (In Eng.)
[30] Zhukov A., Zakablukov D., Zasorina Yu., Chikin A. Computationally Asymmetric transformations And Reversible Logic Circuits. Voprosy kiberbezopasnosti. 2015; 2(10):49-55. Available at: https://elibrary.ru/item.asp?id=23293952 (accessed 16.07.2019). (In Russ., abstract in Eng.)
[31] Chau H.F., Lo H.-K. One-way Functions in Reversible Computations. Cryptologia. 1997; 21(2): 139-148. (In Eng.) DOI: 10.1080/0161-1197918858
[32] Zhukov A. Circuits from reversible logic elements: One approach to the study of unidirectionality. In: Proceeding of The Third International Conference on Information Systems and Technologies (IST'2006). Minsk, 2006, p. 85. (In Russ.)
[33] Zhukov A. One approach to the study of unidirectionality. Information Security. 2018; 1:40-43. Available at: http://lib.itsec.ru/articles2/crypto/odin-podhod-k-izucheniyu-odnonapravlennosti (accessed 16.07.2019). (In Russ.)
Опубликована
2019-09-30
Как цитировать
GUROV, Sergey Isaevich et al. Обратимые вычисления. Современные информационные технологии и ИТ-образование, [S.l.], v. 15, n. 3, p. 541-552, sep. 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/594>. Дата доступа: 10 dec. 2022 doi: https://doi.org/10.25559/SITITO.15.201903.541-552.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук