Обратимые вычисления
обзор проблемы и новые результаты (отказоустойчивость и криптография)
Аннотация
В работе рассмотрены основные положения обратимости как новой парадигмы развития вычислительной техники. Первые разделы носят обзорный характер. Показана неизбежность т. н. "теплового проклятия" при сохранении традиционной парадигмы создания средств ВТ. Изложены основы обратимой логики, рассмотрены основные обратимые логические элементы и модели обратимых вычислений, в т. ч. обратимые клеточные автоматы. Кратко рассмотрены обратимые языки программирования. Во второй части затронуты основные вопросы логического синтеза схем из обратимых элементов и физическая реализация обратимой схемотехники. Кратко описана проблематика синтеза отказоустойчивых схем в парадигме обратимой схемотехники. Предлагается техника синтеза сбоеустойчивых обратимых элементов в хэмминговом пространстве и описываются некоторые такие схемы. Далее рассматривается проблематика применения схем из обратимых логических элементов в криптографии. Описывается предлагаемая общая схема создания обратимых схем с "уборкой мусора", предназначенных для криптографических применений.
Литература
[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.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
