Reversible Computing
Review of the Problem and New Results (Fault Tolerance and Cryptography)
Abstract
The paper considers the main provisions of reversibility as a new paradigm for the development of computer technology. The first sections are of an overview nature. The inevitability of the so-called "heat curse" while maintaining the traditional paradigm of creating means of computer engineering. The fundamentals of reversible logic are presented, the main reversible logic elements and models of reversible computations, including reversible cellular automata, are considered. Reversible programming languages are briefly reviewed. The second part addresses the basic issues of the logical synthesis of circuits from reversible elements and the physical implementation of reversible circuitry. The synthesis of fault-tolerant circuits in the paradigm of reversible circuitry is briefly described. A technique for synthesizing fault-tolerant reversible elements in a hamming space is proposed and some such schemes are described. Next, the problems of using circuits of reversible logic elements in cryptography are considered. The proposed general scheme for creating reversible schemes with "garbage collection" intended for cryptographic applications is described.
References
[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.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
