A Novel Method Based on the Post Correspondance Problem for Designing Cryptosystems
Main Article Content
Abstract
Cryptography is an integral part of computer science. Nowadays, cryptosystems are one of the most important applications of cryptography. In communication area, cryptosystems can be used to establish cryptographic protocols and algorithms for transmitting data securely via an unsafe enviroment such as Internet. Recent advances in cryptoanalysis and computing have exhibited a lot of weeknesses of existing cryptosystems. Therefore, it is most urgent that cryptography establishes new powerful cryptosystems. In this paper, we present a novel method to design cryptosystems as the standard approach to protect data. The obtained cryptosystems contain a trapdoor which can be reduced to an undecidable problem, namely the POST correspondance problem.
Keywords
Cryptography, POST correspondance problem, trapdoor
Article Details
References
[1] A. Salomaa, Nhập môn tin học lý thuyết tính toán và các ôtômat (Bản dịch), NXB Khoa học và Kỹ thuật (1992).
[2] E. L. Post, A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc Vol. 52 (No. 4) (1946) 264-268.
[3] K. Ruohonen, "On some variants of Post's correspondence problem". Acta Informatica (Springer) Vol. 19 (No. 4) (1983) 357-367.
[4] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co. New York, NY, USA (1979).
[5] Y. Gurevich, Average case completeness, J. Comp. Sys. Sci. (Elsevier Science) Vol. 42 (No. 3) (1991) 346-398.
[6] V. Halava, M. Hirvensalo, R. de Wolf, Marked PCP is decidable, Theoretical Computer Science, Vol. 255 (2001) 193-204.
[7] P. Chambart, Ph. Schnoebelen, Post embedding problem is not primitive recursive, with applications to channel systems, Lecture Notes in Computer Science, Vol. 4855 (2007) 265-276.
[8] Hồ Ngọc Vinh, Phan Trung Huy, Đỗ Long Vân. -ngôn ngữ chính quy và mã, Hội thảo khoa học quốc gia lần thứ IV Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR 2009), Hà Nội (2009) 13-22.
[9] H. N. Vinh, P. T. Huy, Codes of Bounded Words, Proceedings of the 3rd International Conference on Computer and Electrical Engineering (ICCEE 2010), Vol. 2 (2010) 89-95.
[10] S. Eilenberg, Automata, languages and machines, Vol. B. Academic Press, New York (1976).
[2] E. L. Post, A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc Vol. 52 (No. 4) (1946) 264-268.
[3] K. Ruohonen, "On some variants of Post's correspondence problem". Acta Informatica (Springer) Vol. 19 (No. 4) (1983) 357-367.
[4] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co. New York, NY, USA (1979).
[5] Y. Gurevich, Average case completeness, J. Comp. Sys. Sci. (Elsevier Science) Vol. 42 (No. 3) (1991) 346-398.
[6] V. Halava, M. Hirvensalo, R. de Wolf, Marked PCP is decidable, Theoretical Computer Science, Vol. 255 (2001) 193-204.
[7] P. Chambart, Ph. Schnoebelen, Post embedding problem is not primitive recursive, with applications to channel systems, Lecture Notes in Computer Science, Vol. 4855 (2007) 265-276.
[8] Hồ Ngọc Vinh, Phan Trung Huy, Đỗ Long Vân. -ngôn ngữ chính quy và mã, Hội thảo khoa học quốc gia lần thứ IV Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR 2009), Hà Nội (2009) 13-22.
[9] H. N. Vinh, P. T. Huy, Codes of Bounded Words, Proceedings of the 3rd International Conference on Computer and Electrical Engineering (ICCEE 2010), Vol. 2 (2010) 89-95.
[10] S. Eilenberg, Automata, languages and machines, Vol. B. Academic Press, New York (1976).