Luận án Các hệ mật dựa trên vành đa thức chẵn

BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
--------------------------------------- 
CAO MINH THẮNG 
CÁC HỆ MẬT DỰA TRÊN 
VÀNH ĐA THỨC CHẴN 
LUẬN ÁN TIẾN SỸ KỸ THUẬT 
Hà Nội - 2017 
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
--------------------------------------- 
CAO MINH THẮNG 
CÁC HỆ MẬT DỰA TRÊN 
VÀNH ĐA THỨC CHẴN 
CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ 
MÃ SỐ: 62.52.02.03 
LUẬN ÁN TIẾN SỸ KỸ THUẬT 
NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS.NGUYỄN BÌNH 
Hà Nội – 2017 
i 
LỜI CAM ĐOAN 
Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện. Các số liệu và 
kết quả trình bày trong luận án là trung thực và chưa được công bố bởi bất kỳ tác giả 
nào hay ở bất kỳ công trình nào khác. 
 Hà Nội, tháng 8 năm 2017 
 Tác giả luận án 
 Cao Minh Thắng 
ii 
LỜI CẢM ƠN 
 Tôi xin bày tỏ sự biết ơn sâu sắc tới GS.TS. Nguyễn Bình, người thầy đã định 
hướng và hướng dẫn tôi thực hiện thành công đề tài nghiên cứu. 
 Tôi xin chân thành cảm ơn Ban giám đốc, Khoa Quốc tế và Đào tạo sau đại 
học - Học viện Công nghệ Bưu chính Viễn thông cũng như Ban lãnh đạo và các đồng 
nghiệp tại Viện công nghệ Thông tin và Truyền thông CDIT, nơi tôi đang công tác, 
đã tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận án. 
 Tôi xin chân thành cảm ơn GS.TSKH Nguyễn Ngọc San và PGS.TS.Lê Bá 
Long đã có những góp ý giúp tôi hoàn chỉnh cách trình bày và các chứng minh toán 
học trong luận án. 
 Tôi cũng xin chân thành cảm ơn các đồng nghiệp thuộc Viện Khoa học Công 
nghệ mật mã - Ban Cơ yếu Chính phủ đã có nhiều ý kiến trao đổi có giá trị trong các 
buổi hội thảo giúp tôi hoàn thiện các công trình nghiên cứu trong luận án. 
 Cuối cùng tôi xin gửi lời cảm ơn tới mẹ, vợ và gia đình đã động viên và chia 
sẻ các khó khăn với tôi trong suốt quá trình thực hiện và hoàn thành luận án. 
 Hà nội, tháng 8 năm 2017 
 Tác giả luận án 
 Cao Minh Thắng 
iii 
MỤC LỤC 
LỜI CAM ĐOAN ....................................................................................................... i 
LỜI CẢM ƠN ............................................................................................................ ii 
MỤC LỤC ................................................................................................................. iii 
DANH MỤC CÁC TỪ VIẾT TẮT .......................................................................... ix 
DANH MỤC CÁC KÝ HIỆU.................................................................................. xii 
DANH MỤC CÁC BẢNG ...................................................................................... xiv 
DANH MỤC CÁC HÌNH VẼ................................................................................... xv 
MỞ ĐẦU ..................................................................................................................... 1 
CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ VÀ CÁC HỆ MẬT DỰA TRÊN 
VÀNH ĐA THỨC .................................................................................................... 10 
1.1 MỞ ĐẦU CHƯƠNG ................................................................................... 10 
1.2 TỔNG QUAN VỀ MẬT MÃ ...................................................................... 10 
1.2.1 Mật mã khóa bí mật .............................................................................. 10 
1.2.2 Mật mã khóa công khai ......................................................................... 12 
1.2.3 Mật mã lai ghép .................................................................................... 14 
1.2.4 Độ an toàn của một hệ mật ................................................................... 15 
1.2.5 Thí nghiệm đánh giá độ an toàn không thể phân biệt ........................... 18 
1.2.6 Phương pháp đánh giá độ an toàn ngữ nghĩa của các hệ mật ............... 20 
1.2.7 Một số tham số khác được sử dụng để đánh giá các hệ mật ................. 22 
1.3 CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC ........................................ 23 
1.3.1 Các hệ mật khoá bí mật dựa trên vành đa thức ..................................... 23 
1.3.2 Các hệ mật khoá công khai dựa trên vành đa thức ............................... 24 
iv 
1.3.3 Các hệ mật lai ghép dựa trên vành đa thức ........................................... 26 
1.4 TIỀM NĂNG ỨNG DỤNG CỦA VÀNH ĐA THỨC CHẴN TRONG MẬT 
MÃ VÀ CÁC VẤN ĐỀ MỞ ................................................................................. 26 
1.4.1 Các vấn đề chung với các hệ mật dựa trên vành đa thức chẵn ............. 26 
1.4.2 Các tiềm năng ứng dụng của vành đa thức chẵn trong mật mã ............ 27 
1.5 KẾT LUẬN CHƯƠNG ............................................................................... 28 
CHƯƠNG 2. VÀNH ĐA THỨC CHẴN ............................................................. 30 
2.1 MỞ ĐẦU CHƯƠNG ................................................................................... 30 
2.2 TỔNG QUAN VỀ VÀNH ĐA THỨC ........................................................ 30 
2.2.1 Các định nghĩa và ký hiệu..................................................................... 30 
2.2.2 Lũy đẳng trong vành đa thức nR .......................................................... 32 
2.2.3 Các phần tử khả nghịch trong nR ......................................................... 34 
2.2.4 Đa thức bù và nghịch đảo mở rộng trong các vành nR với n lẻ .......... 36 
2.3 VÀNH ĐA THỨC CHẴN, CÁC THẶNG DƯ BẬC HAI VÀ CÁC PHẦN 
TỬ LIÊN HỢP ...................................................................................................... 37 
2.3.1 Các định nghĩa ...................................................................................... 38 
2.3.2 Tính chất của các thặng dư bậc hai ....................................................... 38 
2.3.3 Tính chất của các CE của lũy đẳng 
1
1e trên vành đa thức chẵn ....... 41 
2.4 VÀNH ĐA THỨC CHẴN TUYỆT ĐỐI 
2k
R ............................................. 41 
2.4.1 Tập các phần tử khả nghịch trong 
2k
R .................................................. 41 
2.4.2 Thuật toán tính phần tử nghịch đảo trong 
2k
R ...................................... 44 
2.5 VÀNH ĐA THỨC CHỈ CÓ HAI LỚP KỀ CYCLIC 2CR ......................... 45 
2.5.1 Các định nghĩa ...................................................................................... 45 
v 
2.5.2 Tập các phần tử khả nghịch trên vành 2CR .......................................... 45 
2.5.3 So sánh vành 2CR với vành 2kR ........................................................... 46 
2.6 KẾT LUẬN CHƯƠNG ............................................................................... 47 
CHƯƠNG 3. CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC CHẴN .............. 48 
3.1 MỞ ĐẦU CHƯƠNG ................................................................................... 48 
3.2 HỆ MẬT KHÓA BÍ MẬT RISKE .............................................................. 48 
3.2.1 Giới thiệu .............................................................................................. 48 
3.2.2 Cấu trúc đại số nền tảng của RISKE .................................................... 49 
3.2.3 Thủ tục tạo khóa ................................................................................... 50 
3.2.4 Thủ tục mã hóa ..................................................................................... 50 
3.2.5 Thủ tục giải mã ..................................................................................... 51 
3.2.6 Ví dụ minh họa ..................................................................................... 51 
3.2.7 Phân tích độ an toàn lý thuyết của RISKE ........................................... 52 
3.2.8 Phân tích hiệu năng lý thuyết của RISKE ............................................ 55 
3.2.9 Lựa chọn tham số .................................................................................. 55 
3.2.10 So sánh RISKE với OTP ................................................................... 56 
3.2.11 Kết luận về hệ mật RISKE ................................................................ 57 
3.3 HỆ MẬT LAI GHÉP QRHE ....................................................................... 57 
3.3.1 Giới thiệu .............................................................................................. 57 
3.3.2 Sơ đồ hệ mật lai ghép QRHE ................................................................ 58 
3.3.3 Cấu trúc đại số nền tảng của QRHE ..................................................... 59 
3.3.4 Thủ tục tạo khóa ................................................................................... 60 
3.3.5 Thủ tục mã hóa ..................................................................................... 60 
3.3.6 Thủ tục giải mã ..................................................................................... 60 
vi 
3.3.7 Ví dụ minh họa ..................................................................................... 61 
3.3.8 Phân tích độ an toàn lý thuyết của QRHE ............................................ 62 
3.3.9 Phân tích hiệu năng lý thuyết của QRHE ............................................. 63 
3.3.10 Lựa chọn tham số .............................................................................. 63 
3.3.11 Kết luận về QRHE ............................................................................. 64 
3.4 HỆ MẬT KHÓA CÔNG KHAI IPKE ........................................................ 64 
3.4.1 Giới thiệu .............................................................................................. 64 
3.4.2 Hàm cửa sập dựa trên các phần tử khả nghịch trong 
2k
R ..................... 65 
3.4.3 Không gian các cửa sập trong 
2k
R ........................................................ 66 
3.4.4 Cấu trúc đại số nền tảng của IPKE ....................................................... 67 
3.4.5 Thủ tục tạo khóa ................................................................................... 68 
3.4.6 Thủ tục mã hóa ..................................................................................... 68 
3.4.7 Thủ tục giải mã ..................................................................................... 68 
3.4.8 Chứng minh thủ tục giải mã ................................................................. 69 
3.4.9 Ví dụ minh họa ..................................................................................... 69 
3.4.10 Phân tích độ an toàn lý thuyết của IPKE ........................................... 72 
3.4.11 Phân tích hiệu năng lý thuyết của IPKE ............................................ 74 
3.4.12 Lựa chọn tham số .............................................................................. 75 
3.4.13 Kết luận về IPKE ............................................................................... 76 
3.5 KẾT LUẬN CHƯƠNG ............................................................................... 76 
CHƯƠNG 4. CÁC HỆ MẬT MỞ RỘNG DỰA TRÊN VÀNH ĐA THỨC CHẴN 
KẾT HỢP VỚI CÁC VÀNH ĐA THỨC KHÁC ..................................................... 78 
4.1 MỞ ĐẦU CHƯƠNG ................................................................................... 78 
4.2 HỆ MẬT KHÓA CÔNG KHAI DTRU ...................................................... 79 
vii 
4.2.1 Giới thiệu .............................................................................................. 79 
4.2.2 Hệ mật NTRU ....................................................................................... 79 
4.2.3 Ý tưởng về hệ mật DTRU ..................................................................... 84 
4.2.4 Hệ mật DTRU ....................................................................................... 84 
4.3 HỆ MẬT KHÓA BÍ MẬT E-RISKE .......................................................... 95 
4.3.1 Giới thiệu .............................................................................................. 95 
4.3.2 Cấu trúc đại số nền tảng của E-RISKE ................................................. 96 
4.3.3 Thủ tục tạo khóa ................................................................................... 96 
4.3.4 Thủ tục mã hóa ..................................................................................... 97 
4.3.5 Thủ tục giải mã ..................................................................................... 97 
4.3.6 Ví dụ minh họa ..................................................................................... 98 
4.3.7 Phân tích độ an toàn lý thuyết của E-RISKE ........................................ 99 
4.3.8 Phân tích hiệu năng lý thuyết của E-RISKE ....................................... 102 
4.3.9 Lựa chọn tham số ................................................................................ 102 
4.3.10 Kết luận về E-RISKE ...................................................................... 102 
4.4 HỆ MẬT LAI GHÉP HpNE ...................................................................... 103 
4.4.1 Giới thiệu ............................................................................................ 103 
4.4.2 Hệ mật pNE ........................................................................................ 103 
4.4.3 Hệ mật lai ghép HpNE ........................................................................ 105 
4.4.4 Kết luận về HpNE ............................................................................... 109 
4.5 KẾT LUẬN CHƯƠNG ............................................................................. 110 
KẾT LUẬN ............................................................................................................. 111 
DANH MỤC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ .................................... 114 
TÀI LIỆU THAM KHẢO ....................................................................................... 116 
viii 
PHỤ LỤC 1: TẬP CÁC PHẦN TỬ 
2
, 10000
C
n N n ................................ 126 
ix 
DANH MỤC CÁC TỪ VIẾT TẮT 
AES Advanced Encryption 
Standard 
Chuẩn mã hóa tiên tiến 
CE Conjugate Element Phần tử liên hợp (thực chất là các 
căn bậc hai của một thặng dư bậc 
hai trong vành đa thức chẵn) 
COA Ciphertext Only Attack Tấn công chỉ bằng bản mã 
CCA Chosen Ciphertext Attack Tấn công bằng bản mã chọn trước 
CBC Cipher Block Chaining Chế độ mật mã khối dạng móc 
xích 
CPA Chosen Plaintext Attack Tấn công bằng bản rõ chọn trước 
DES Data Encryption Standard Chuẩn mã hóa dữ liệu 
DHP Diffie – Hellman Problem Bài toán khó Diffie – Hellman 
DLP Discrete Logarithm Problem Bài toán logarit rời rạc 
DSS Digital Signature Standard Chuẩn chữ ký số 
DTRU Dual Truncated public-key 
cryptosystem 
Hệ mật khóa công khai DTRU dựa 
trên hai vành đa thức hệ số nhị 
phân bậc hữu hạn 
EAV Eavesdropping Attack Tấn công kiểu nghe lén 
ECB Electronic Codebook Chế độ hoạt động sổ điện tử mật 
mã khối 
E-RISKE Extende ... ologies 2007, Malaysia, ISBN: 983-43160-0-3. 
15. Nguyen Binh, Tran Duc Su, Pham Viet Trung (2001), “Decomposition of 
polynomial ring according to the classes of conjugate elements”, AIC-26, 
Hanoi, Vietnam. 
118 
16. Nguyen Binh (2002), “Crypto-system based on cyclic geometric progressions 
over polynomial ring” (Part I). REV’02. 
17. Nguyen Binh, Le Dinh Thich (2002), “The orders of polynomials and 
algorithms for defining order of polynomial over polynomial Ring”, VICA-5, 
Hanoi, Vietnam. 
18. Nguyen Binh, Dang Hoai Bac (2004), “Cyclic codes over extended rings of 
polynomial rings with two cyclotomic cosets”, REV-04, Hanoi, Vietnam. 
19. Cabarcas D., Weiden P., Buchmann J. (2014), “On the Efficiency of Provably 
Secure NTRU”, Post-Quantum Cryptography Volume 8772 of the 
series Lecture Notes in Computer Science, pp 22-39. Springer. 
20. Cai Jin-Yi, Cusick Thomas W (1999), “A Lattice-Based Public-Key 
Cryptosystem”, Lecture Notes in Computer Science Volume 1556, 1999, pp 
219-233. 
21. Chandrasekaran, J. et al. (2011), "A Chaos Based Approach for Improving 
Non Linearity in the S-Box Design of Symmetric Key Cryptosystems". In 
Meghanathan, N. et al. Advances in Networks and Communications: First 
International Conference on Computer Science and Information Technology, 
CCSIT 2011, Bangalore, India, January 2-4, 2011. Proceedings, Part 2. 
Springer. p. 516. ISBN 978-3-642-17877-1. 
22. Chenal M., Tang Q. (2015), “Key Recovery Attacks Against NTRU-Based 
Somewhat Homomorphic Encryption Schemes”. Information Security Volume 
9290 of the series Lecture Notes in Computer Science, pp. 397-418, Springer. 
23. Chor B., Rivest R. L. (1988), “A knapsack-type public key cryptosystem based 
on arithmetic in finite fields”, IEEE Trans. Inform. Theory 34, 901–909. 
24. Cocks, Clifford (20 November 1973). "A Note on 'Non-Secret Encryption'" 
(PDF). CESG Research Report. 
119 
25. Coglianese M., Goi B.M. (2005), “MaTRU: A New NTRU-Based 
Cryptosystem”. Lecture Notes in Computer Science Volume 3797, 2005, pp 
232-243. 
26. Coppersmith D., Shamir A. (1997), Lattice attacks on NTRU. In: Fumy, W. 
(ed.) EUROCRYPT 1997, LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg. 
27. Cramer R. and Shoup V. (1998), "A practical public key cryptosystem 
provably secure against adaptive chosen ciphertext attack." in proceedings of 
CRYPTO 1998, LNCS 1462, p. 13ff. 
28. Cramer, Ronald; Shoup, Victor (2004). "Design and Analysis of Practical 
Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext 
Attack" (PDF). SIAM Journal on Computing 33 (1): 167–226. 
29. W. Diffie, M.E. Hellman, “New directions in cryptography”, IEEE Trans on 
Information Theory Volume: 22, Issue: 6, (1976), 644-654. 
30. Data Encryption Standard (DES) (1977), Federal Information Processing 
Standard (FIPS) Publication 46. 
31. Dolev D., Dwork C., and Naor M. (2000), “Non-Malleable Cryptography”, 
SIAM Journal on Computing, 30(2):391–437. 
32. ElGamal T. (1985), "A Public-Key Cryptosystem and a Signature Scheme 
Based on Discrete Logarithms", IEEE Transactions on Information Theory, 
31 (4): 469–472. 
33. Feistel H. (1973), “Cryptography and Computer Privacy". Scientific 
American, 228(5), May 1973, pp 15–23. 
34. Fujisaki E., Okamoto T., Pointcheval D., and Stern J. (2001) “RSA-OAEP is 
secure under the RSA assumption”. In J. Kilian, ed., Advances in Cryptology 
-- CRYPTO 2001, vol. 2139 of Lecture Notes in Computer Science, 
SpringerVerlag. 
120 
35. "FIPS PUB 197: The official Advanced Encryption Standard" (PDF). 
Computer Security Resource Center. 
36. Gaborit, P., Ohler, J., Sole, P. (2002),: “CTRU, a Polynomial Analogue of 
NTRU”, INRIA. Rapport de recherche, N.4621, (ISSN 0249-6399). 
37. Gentry C. (2001), “Key recovery and message attacks on NTRU-composite.” 
In Proceeding of Eurocrypt ’01, LNCS, vol. 2045, Springer-Verlag, pp.182-
194, 2001. 
38. Gentry C., Peikert C., and Vaikuntanathan V. (2008), “Trapdoors for hard 
lattices and new cryptographic constructions,” in Proceedings of the 40th 
annual ACM symposium on Theory of computing, Victoria, British Columbia, 
Canada: ACM, pp. 197-206. 
39. Goldreich O., Goldwasser S., and Halevi S. (1997), “Public-key cryptosystems 
from lattice reduction problems”. In CRYPTO ’97: Proceedings of the 17th 
Annual International Cryptology Conference on Advances in Cryptology, 
pages 112–131, London, UK, Springer-Verlag. 
40. Goldwasser S. and Micali S. (1982), “Probabilistic encryption & how to play 
mental poker keeping secret all partial information”, Annual ACM Symposium 
on Theory of Computing. 
41. Goldwasser S. and Micali S. (1984), "Probabilistic encryption", Journal of 
Computer and System Sciences 28 (2): 270–29. 
42. Han D., Hong J., Han J. W. and Kwon D. (2003), “Key recovery attacks on 
NTRU without ciphertext validation routine”. In Proceeding of ACISP ’03, 
LNCS, vol. 2727, Springer-Verlag, pp.274-284. 
43. Hoffstein J., Pipher J., Silverman J.H. (1996), “NTRU: A new high speed 
public key”. Preprint, presented at the rump session of Crypto 1996. 
44. Hoffstein J., Pipher J., Silverman J.H. (1998), “NTRU: A ring-based public 
key cryptosystem”, Lecture Notes in Computer Science, Volume 1423, pp 
267-288, Springer Verlag. 
121 
45. Hoffstein J., Pipher J., Silverman J.H. (2008), An Introduction to 
Mathematical Crytography. Springer. ISBN: 978-0-387-77993-5. 
46. Hoffstein J. and Silverman J.H. (2000), “Optimizations for NTRU”. In Public-
key Cryptography and Computational Number Theory, DeGruyter. 
47. Hoffstein J. and Silverman J.H. (2003), “Random small hamming weight 
products with applications to cryptography”. Discrete Applied Mathematics, 
vol. 130, Issue 1 - special issue on the 2000 com2MaC workshop on 
cryptography, pp. 37 - 49, 2003. 
48. Hofheinz, Dennis; Kiltz, Eike (2007). "Secure Hybrid Encryption from 
Weakened Key Encapsulation" (PDF). Advances in Cryptology -- CRYPTO 
2007. Springer. pp. 553–571. 
49. Howgrave-Graham N., Silverman J.H., Whyte W., “NTRU Cryptosystems 
Technical Report #004, Version 2: A Meet-In-The-Middle Attack on an 
NTRU Private Key”. 
50. IBM (1997), "A brief history of the data encryption standard". ACM 
Press/Addison-Wesley Publishing Co. New York, NY, USA. pp. 275–280. 
51. IEEE (2000), “Standard Specification for Public-Key Cryptographic 
Techniques Based on Hard Problems over Lattices”, Standard P1363.1. 
52. Jaulmes E. and Joux A. (2000), “A Chosen Ciphertext Attack on NTRU”, In 
Proceeding of CRYPTO ’00, LNCS, vol. 1880, Springer-Verlag, pp. 20-35. 
53. Jarvis K., Nevins M. (2013), “ETRU: NTRU over the Eisenstein integers”, 
Designs, Codes and Cryptography Volume 74, Issue 1, Page 219-242. 
Springer. 
54. Katz J., Lindell Y. (2007), “Introduction to Modern Cryptography: Principles 
and Protocols”, Chapman & Hall/CRC Cryptography and Network Security 
Series. 
122 
55. Koblitz, N. (1987). "Elliptic curve cryptosystems". Mathematics of 
Computation 48 (177): 203–209. 
56. Lenstra A.K., Lenstra H.W., Lovász L. (1982), “Factoring polynomials with 
polynomial coefficients”, Math. Annalen 261, 515-534. 
57. Lai X., Massey J. L. (1991), “A proposal for a new block encryption standard”, 
Advances in Cryptology EUROCRYPT'90, Aarhus, Denemark, LNCS 473, p. 
389-404, Springer. 
58. R. Lidl and H. Niederreiter (1983), Finite Fields, Addison-Wesley, Reading, 
Mass. 
59. Hill L. S. (1929), “Cryptography in an Algebraic Alphabet”, The American 
Mathematical Monthly Vol.36, June–July 1929, pp. 306–312. 
60. Lyubashevsky V., Peikert C., Regev O. (2010), “On ideal lattices and learning 
with errors over rings”. In: Gilbert H. (ed.) Advances in Cryptology 
(EUROCRYPT 2010). Lecture Notes in Computer Science, vol. 6110, pp. 1–
23. Springer, Berlin (2010). 
61. Malekian, Zakerolhosseini E. (2010), “OTRU: A non-associative and high 
speed public key cryptosystem”. A.Computer Architecture and Digital 
Systems (CADS), 2010 15th CSI International Symposium on, Tehran, pp 83 – 
90, ISBN: 978-1-4244-6267-4. 
62. Matsumoto T. and IMAI H.(1988), “Public Quadratic Polynomial-tuples for 
efficient signature-verification and message-encryption”, EUROCRYPT’88, 
Springer Verlag, pp. 419–453. 
63. McEliece R. J., "A public-key cryptosystem based on algebraic coding 
theory." DSN Progress Report, pp. 114-116, 1978. 
64. Menezes A. J, Van Oorchot P. C. (1996), Handbook of Applied Cryptography, 
CRC Press. 
123 
65. Merkle R. and Hellman M. (1978), "Hiding information and signatures in 
trapdoor knapsacks", IEEE Trans. Inform. Theory, vol. IT-24, no. 5, pp.525 
-530. 
66. Miller, V. (1985), "Use of elliptic curves in cryptography", CRYPTO. Lecture 
Notes in Computer Science 85: 417–426. 
67. Moon, Todd K. (2005), Error Correction Coding. Wiley-Interscience, a John 
Wiley & Sons, Inc., Publication. 
68. Naccache D. and Stern J. (1998), "Proceedings of the 5th ACM Conference 
on Computer and Communications Security". CCS '98. ACM. pp. 59–66. 
69. Network Working Group of the IETF, January 2006, RFC 4251, The Secure 
Shell (SSH) Protocol Architecture. 
70. Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "A new public-key 
cryptosystem as secure as factoring". Advances in Cryptology — 
EUROCRYPT'98. Lecture Notes in Computer Science 1403. Springer. pp. 
308–318. 
71. Pan Y., Deng Y., Jiang Y., Tu Z. (2011), “A New Lattice-Based Public-Key 
Cryptosystem Mixed with a Knapsack”. Lecture Notes in Computer Science 
Volume 7092, pp 126-137. 
72. Pan Y., Deng Y. (2012), “A General NTRU-Like Framework for Constructing 
Lattice-Based Public-Key Cryptosystems”. Lecture Notes in Computer 
Science Volume 7115, pp 109-120. 
73. Patarin J. (1996), “Hidden Fields Equations (HFE) and Isomorphisms of 
Polynomials (IP): two new families of Asymmetric Algorithms”; 
Eurocrypt’96, Springer Verlag, pp. 33–48. 
74. Patsakis C., Kotzanikolaou P., Bouroche M. (2015), “Private Proximity 
Testing on Steroids: An NTRU-based Protocol”, Security and Trust 
Management Volume 9331 of the series Lecture Notes in Computer Science 
pp 172-184. Springer, 2015. 
124 
75. Peikert C. and Waters B. (2008), “Lossy trapdoor functions and their 
applications,” in Proceedings of the 40th annual ACM symposium on Theory 
of computing (Victoria, British Columbia, Canada: ACM, 2008), 187-19. 
76. Peikert C. (2009), “Public-key cryptosystems from the worst-case shortest 
vector problem: extended abstract,” in Proceedings of the 41st annual ACM 
symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333-
342. 
77. Perlner, R.A., Cooper, D.A. (2009), “Quantum resistant public key 
cryptography: a survey”. In: Proc. of IDtrust, pp. 85–93. ACM, New York. 
78. Rabin, Michael (1979), “Digitalized Signatures and Public-Key Functions as 
Intractable as Factorization”, MIT Laboratory for Computer Science. 
79. Regev O., “On lattices, learning with errors, random linear codes, and 
cryptography”, in Proceedings of the thirty-seventh annual ACM symposium 
on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93. 
80. Rivest R.L., Shamir A., Adleman L. (1978), “A method for obtaining digital 
signatures and public key cryptosystems”, Communications of the ACM 21, 
120-126. 
81. Shamir, Adi (1984), "A polynomial-time algorithm for breaking the basic 
Merkle - Hellman cryptosystem". Information Theory, IEEE Transactions on 
30 (5): 699–704. 
82. Shannon C.E., Communication theory of secrecy systems, Bell System Tech. 
J. 28 (1949), 5not56-715. 
83. Wayner, Peter (24 December 1997), "British Document Outlines Early 
Encryption Discovery". New York Times. 
84. "RFC 2440 - Open PGP Message Format". Internet Engineering Task Force. 
November 1998. 
85. Singh, Simon (1999), The Code Book, Doubleday. pp. 279–292. 
125 
86. Shoup V. (2001), “A proposal for an ISO standard for public key encryption 
(version 2.1)”. Available on  
87. Shoup V. (2004), “ISO 18033-2: An emerging standard for public-key 
encryption”,  December 2004. Final Committee 
Draft. 
88. Stehle, D., Steinfeld, R. (2011), “Making NTRU as secure as worst-case 
problems over ideal lattices”, In: Paterson, K.G.(ed.) EUROCRYPT 2011. 
LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg. 
89. Stinson, D., R. (2006). Cryptography. Theory and Practice (Third ed.). 
Chapman & Hall/CRC. ISBN 1584885084. 
90. Nitin Vats (2008), “Algebraic cryptanalysis of CTRU”, COCOON 2008, 
LNCS 5092, pp. 235244, 2008. Springer-Verlag Berlin Heidelberg. 
126 
PHỤ LỤC 1: TẬP CÁC PHẦN TỬ 
2
, 10000
C
n N n 
{ 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 
211 227 269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 
547 557 563 587 613 619 653 659 661 677 701 709 757 773 787 797 821 827 829 
853 859 877 883 907 941 947 1019 1061 1091 1109 1117 1123 1171 1187 1213 1229 
1237 1259 1277 1283 1291 1301 1307 1373 1381 1427 1451 1453 1483 1493 1499 
1523 1531 1549 1571 1619 1621 1637 1667 1669 1693 1733 1741 1747 1787 1861 
1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029 2053 2069 2083 
2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357 2371 
2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 
2699 2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 
3011 3019 3037 3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 
3467 3469 3491 3499 3517 3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 
3677 3691 3701 3709 3733 3779 3797 3803 3851 3853 3877 3907 3917 3923 3931 
3947 3989 4003 4013 4019 4021 4091 4093 4099 4133 4139 4157 4219 4229 4243 
4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483 4493 4507 4517 4547 
4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987 5003 5011 
5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443 
5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 
5779 5813 5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 
6173 6197 6203 6211 6229 6269 6277 6299 6317 6323 6373 6379 6389 6397 6469 
6491 6547 6619 6637 6653 6659 6691 6701 6709 6733 6763 6779 6781 6803 6827 
6829 6869 6883 6899 6907 6917 6947 6949 6971 7013 7019 7027 7043 7069 7109 
7187 7211 7219 7229 7237 7243 7253 7283 7307 7331 7349 7411 7451 7459 7477 
7499 7507 7517 7523 7541 7547 7549 7573 7589 7603 7621 7643 7669 7691 7717 
7757 7789 7829 7853 7877 7883 7901 7907 7933 7949 8053 8069 8093 8117 8123 
8147 8171 8179 8219 8221 8237 8243 8269 8291 8293 8363 8387 8429 8443 8467 
8539 8563 8573 8597 8627 8669 8677 8693 8699 8731 8741 8747 8803 8819 8821 
8837 8861 8867 8923 8933 8963 8971 9011 9029 9059 9173 9181 9203 9221 9227 
9283 9293 9323 9341 9349 9371 9397 9419 9421 9437 9467 9491 9533 9539 9547 
9587 9613 9619 9629 9643 9661 9677 9733 9749 9803 9851 9859 9883 9901 9907 
9923 9941 9949 }