Một giải pháp nâng cao hiệu quả giải mã của các hệ mật đa trị và nhập nhằng MAS

Nội dung text: Một giải pháp nâng cao hiệu quả giải mã của các hệ mật đa trị và nhập nhằng MAS

1. Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00176 MỘT GIẢI PHÁP NÂNG CAO HIỆU QUẢ GIẢI MÃ CỦA CÁC HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG MAS Long Thị Lệ, Nguyễn Đình Hân Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội le.lt@sis.hust.edu.vn, han.nguyendinh@hust.edu.vn TÓM TẮT: Hệ mật đa trị và nhập nhằng MAS (multi-valued and ambiguous cryptosystem) được thiết kế nhằm bảo vệ an toàn dữ liệu của các mạng cảm biến đám mây. Vì vậy, MAS thích hợp và có thể hoạt động hiệu quả trên các máy chủ dữ liệu đám mây, các thiết bị di động cũng như các thiết bị cảm biến nhỏ. Tuy nhiên, do đặc tính đa trị của MAS, giải mã dữ liệu thường cần nhiều thời gian hơn so với mã hóa dữ liệu. Trong bài báo này, chúng tôi thiết lập những kết quả mới cho phép phát triển một thuật toán giải mã hiệu quả cho các hệ mật MAS. Nhờ đó, thời gian giải mã dữ liệu trong các hệ mật này được giảm xuống mức tối thiểu. Từ khóa: Bảo mật, mật mã, hệ mật đa trị và nhập nhằng, MAS, đồ thị. I. GIỚI THIỆU Mục tiêu cơ bản của mật mã học là tạo ra các hệ mật cho phép truyền tin bí mật trong môi trường không an toàn. Do không có hệ mật nào tồn tại được lâu dài trước sự tấn công nên nhu cầu phát triển những hệ mật mới phục vụ các lĩnh vực của đời sống mang tính thời sự cấp thiết, là hướng đi phù hợp với xu hướng phát triển và nhu cầu của xã hội. Năm 2014, nhóm tác giả Nguyễn Đình Hân, Longzhe Han, Đào Minh Tuấn, Hoh Peter In và Minho Jo [1] đã đề xuất một phương pháp mới cho phép xây dựng các hệ mật đa trị và nhập nhằng (Multi-valued and ambiguous cryptosystem - MAS). Đặc tính đa trị của phép mã hóa cùng với thuộc tính nhập nhằng của ngôn ngữ biểu diễn (không là mã như trong các hệ mật thông thường) đã giúp các hệ mật MAS nâng cao đáng kể hiệu quả bảo vệ an toàn dữ liệu. Tuy nhiên, đặc tính đa trị cũng gây ra một trở ngại cho quá trình giải mã. Cụ thể là, giải mã cần phân biệt và lựa chọn đúng bản rõ trong số nhiều bản rõ nhận được từ một bản mã. Vì vậy, quá trình giải mã dữ liệu thường cần nhiều thời gian hơn so với quá trình mã hóa dữ liệu. Trong bài báo này, chúng tôi đề xuất một giải pháp nâng cao hiệu quả giải mã của các hệ mật MAS. Từ đó, giúp giảm thiểu thời gian giải mã dữ liệu trong các hệ mật này. Để cải thiện hiệu quả giải mã, chúng tôi sử dụng một đồ thị đầy đủ đặc biệt để biểu diễn ngôn ngữ của hệ mật MAS. Khi thực hiện giải mã, các bản rõ của cùng một bản mã sẽ được biểu diễn tương ứng với các đường đi trên đồ thị. Chúng tôi chứng minh một kết quả mới khẳng định bản rõ tương ứng với đường đi ngắn nhất trên đồ thị là kết quả của phép giải mã. Tính hiệu quả của thuật toán tìm đường đi ngắn nhất trên đồ thị đã được biết đến rộng rãi. Vì vậy, giải pháp của chúng tôi có thể làm giảm đáng kể thời gian giải mã dữ liệu. Trước khi trình bày chi tiết giải pháp, sau đây chúng tôi nhắc lại một số định nghĩa liên quan về đồng cấu đa trị, quy tắc mã hóa đa trị; điều kiện cần và đủ để một đồng cấu đa trị trở thành một quy tắc mã hóa đa trị hoặc một quy tắc mã hóa đa trị hạn chế; các kĩ thuật giúp tăng tính bảo mật với thuộc tính nhập nhằng của ngôn ngữ. Hệ mật đa trị và nhập nhằng cùng với thủ tục mã hóa, giải mã sẽ được trình bày ở Phần 2. Đóng góp chính của bài báo gồm phương pháp và các kết quả mới sẽ được trình bày cụ thể trong Phần 3. Trước hết, ta nhắc lại một số khái niệm cơ sở liên quan đến ngôn ngữ hình thức (chi tiết tham khảo [1]). Cho A là bảng chữ cái. Như thường lệ, A* là vị nhóm tự do của các từ trên A. Từ rỗng được kí hiệu là và A+ = A*-{ }. ≤n * Độ dài của từ w = a1a2 an với ai A là |w| = n, | | = 0. A = w A : |w| ≤ n}. * * Một phân tích của từ w A trên X A là w = u1u2 un, trong đó ui X , i = 1, 2, , n và n ≥ 1. Mỗi tập con của A* được gọi là một ngôn ngữ. Một ngôn ngữ X A* được gọi là mã nếu mỗi từ w A* có nhiều nhất một phân tích trên X. Kí hiệu X* là vị nhóm con tự do được sinh bởi X và X* = X+ { }. Kiến thức chung về các hệ mật được tham khảo từ [2]. Chi tiết các vấn đề liên quan đến ngôn ngữ không nhập nhằng được tham khảo từ [3]. Định nghĩa 1.1. Một hệ mật là bộ năm thành phần ( ) thỏa mãn các điều kiện sau: 1. là tập hữu hạn các từ/văn bản gốc (từ rõ/từ hiện/bản rõ). 2. là tập hữu hạn các từ/văn bản mã (bản mã). 3. là tập hữu hạn các khóa. 4. Với mỗi , có một phép mã hóa và một phép giải mã tương ứng . Mỗi và là các ánh xạ sao cho ( ( )) với mọi . Định nghĩa 1.2. Xét ngôn ngữ X A+ và số tự nhiên k . Khi đó:
2. Long Thị Lệ, Nguyễn Đình Hân 255 (i) Tập được gọi là -không nhập nhằng nếu thỏa mãn điều kiện sau: với mọi k m 1 và với mọi x1, x2, , xk, y1, y2, , ym X nếu x1x2 xk = y1 y2 ym thì k = m và xi = yi với i = 1, 2, , k. Ngược lại, X không thỏa mãn điều kiện trên thì X được gọi là k-nhập nhằng. (ii) Nếu tồn tại số k lớn nhất sao cho X là k-không nhập nhằng, thì k được gọi là độ không nhập nhằng của X. Ngược lại, X được gọi là có độ không nhập nhằng ∞. II. HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG A. Tiếp cận và phương pháp thiết lập Trong phần này, ta sẽ nhắc lại các khái niệm, phương pháp để thiết kế một hệ mật có tính chất đa trị và nhập nhằng. Ta cần những khái niệm về phép đồng cấu đa trị được sử dụng để thiết lập quy tắc mã hóa đa trị. Định nghĩa 2.1. Cho A, B là các bảng chữ cái có hữu hạn phần tử. ∗ ∗ ∗ (i) Một đồng cấu đa trị là một hàm đơn ánh f: A → B tương ứng mỗi chữ cái a A với một tập con Xa B và có f(a1 an) = f(a1) f(an), ai A (ii) Một đồng cấu đa trị f được gọi là một quy tắc mã hóa đa trị nếu: w, w′ A∗, w ≠ w′ ta có f(w) ∩ f(w′) = (iii) Một đồng cấu đa trị f được gọi là một quy tắc mã hóa đa trị hạn chế nếu tồn tại một số nguyên k > 0 và với mọi w, w’ A k, w w’ ta có: f(w) f(w’) = . Nhận xét 2.1. Thủ tục mã hóa nhận được từ quy tắc mã hóa đa trị liên kết một bản rõ trong A∗ với một số bản mã trong B∗ (và ngược lại). Tuy nhiên vì f là đơn ánh nên đảm bảo rằng mỗi bản mã được giải mã một cách duy nhất để thu được bản rõ ban đầu. Các kết quả lý thuyết sau đây cung cấp điều kiện cần và đủ để đồng cấu đa trị f trở thành một quy tắc mã hóa đa trị hoặc một quy tắc mã hóa đa trị hạn chế. Mệnh đề 2.1. Cho A, B là bảng chữ cái có hữu hạn phần tử. Giả sử một đồng cấu đa trị f: A∗ → B∗ tương ứng ∗ mỗi chữ cái a A với một tập con Xa B và cho một số nguyên k > 0. Khi đó, với mọi f(a1), , f(ap), f(b1), , f(bq) ∗ B với ai, bj A, i = 1, , p , j = 1, , q ta có: (i) f là một quy tắc mã hóa đa trị khi và chỉ khi: f(a1) f(ap) f(b1) f(bq) suy ra p = q và f(ai) = f(bi) với i = 1, , p. (ii) f là một quy tắc mã hóa đa trị hạn chế khi và chỉ khi: f(a1) f(ap) f(b1) f(bq) với p, q k suy ra p = q và f(ai) = f(bi) với i = 1, , p. Để tăng tính bảo mật với thuộc tính nhập nhằng, ta sử dụng các kĩ thuật được mô tả trong các hệ quả sau đây: Hệ quả 2.1. Cho A = {a1, a2, , an} và số nguyên dương k. Xét ngôn ngữ X có độ không nhập nhằng là k, nghĩa là X có thể được phân hoạch thành n tập con X1, X2, , Xn, Xi Xj = , i j, X1 X2 Xn = X. ∗ ∗ Giả sử rằng một đồng cấu đa trị g: A → X tương ứng mỗi chữ cái a A với một tập con Xi và g(ww’) = g(w)g(w’), w, w’ A k. Khi đó g là một quy tắc mã hóa đa trị hạn chế. Nhận xét 2.2. Hệ quả 2.1 cung cấp một điều kiện đủ để xây dựng hệ mật đa trị và nhập nhằng. Khi xem xét một hệ mật thuộc loại này, ta để ý rằng tính đa trị của nó được xác định bởi g và tính nhập nhằng được xác định bởi X. Chú ý rằng thủ tục mã hóa sử dụng g có thể mã hóa bất kì từ nào trong A*. Tuy nhiên, đối với mỗi bản mã, thủ tục giải mã chỉ cho kết quả duy nhất trong trường hợp bản rõ tương ứng có độ dài nhỏ hơn hoặc bằng k. Điều này là do thuộc tính nhập nhằng của X (nghĩa là bất kì từ nào có độ dài lớn hơn k đều có thể có nhiều hơn một cách phân tích trên X). Do đó g và X được coi là khóa bí mật trong các hệ mật như trên. Ví dụ 2.1. Cho A = {u1, u2, u3, u4, u5} và xét X = {c, ca1, a1b1, b1a2, a2b2, b2a3, a3b3, b3} có độ nhập nhằng k = 3. Khi đó, một trong các phân hoạch của X là X1 = {c, a1, b1}, X2 = {ca1}, X3 = {b1a2, a2b2}, X4 = {b3}, X5 = {b2a3, a3b3} và g được định nghĩa là: g(ui) Xi , i = 1, 2, 3, 4, 5. Giả sử bản rõ ban đầu là w = u2u3u5u4. Vì nó có độ dài là 4 > k nên ta chia thành hai từ w1 = u2u3u5 và w2 = u4 để đảm bảo rằng độ dài của chúng nhỏ hơn hoặc bằng k.
3. 256 MỘT GIẢI PHÁP NÂNG CAO HIỆU QUẢ GIẢI MÃ CỦA CÁC HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG MAS Với g được định nghĩa như trên, bản mã có thể là ca1b1a2b2a3 và b3, hoặc ca1a2b2b2a3 và b3, hoặc ca1b1a2a3b3 và b3, hoặc ca1a2b2a3b3 và b3. Giải mã bản mã ca1b1a2b2a3 ta thu được ba từ ca1 X2, b1a2 X3, b2a3 X5. Do đó ta thu được bản rõ là w1 = u2u3u5. Từ u4 được giải mã thành từ b3.Từ đó ta thu được bản rõ ban đầu là w. Các bản mã khác có thể được giải mã theo cách tương tự và tất cả đều cho ra bản rõ ban đầu là w. Sự nhập nhằng có thể xảy ra khi ta giải mã từ có độ dài lớn hơn k. Ví dụ, trong trường hợp chúng ta mã hóa bản rõ w = u2u3u5u4. Cho g định nghĩa ở trên, một bản mã có thể là ca1b1a2b2a3b3. Sau đó, giải mã cho ra hai kết quả: (c)(a1b1)(a2b2)(a3b3) với c X1, a1b1 X2, a2b2 X3, a3b3 X5, hoặc (ca1)(b1a2)(b2a3)(b3) với ca1 X2, b1a2 X3, b2a3 X5, b3 X4. Giải mã cho ra hai bản rõ tương ứng là u1u1u3u5 và u2u3u5u4. B. Mô tả hệ mật đa trị và nhập nhằng Các phương pháp và kĩ thuật được giới thiệu trong phần trước cho phép ta thiết lập các hệ mật đa trị và nhập nhằng để bảo mật dữ liệu (chi tiết tham khảo [1]). Cho A = {u1, u2, u3, u4, , un} là bảng chữ cái hữu hạn. Xét ngôn ngữ X có độ không nhập nhằng là k, k > 0 sao cho X có thể được phân hoạch thành n tập con: X1, X2, , Xn, Xi Xj = , i j, X1 X2 Xn = X. Ta kí hiệu XP là tập các phân hoạch có thể có của X. Do đó, theo Nhận xét 2.2. ta có thể định nghĩa hệ mật này như sau: Lược đồ 2.1. Hệ mật đa trị và nhập nhằng. k * Cho = A , = X . bao gồm tất cả các hàm đơn ánh đa trị g: A → XP = {X1, X2, , Xn}. Với mỗi g , ta định nghĩa: eg(x) = w g(x), và định nghĩa dg(w) = {y |w g(y)}. Chú ý 2.1. Với bất kì w X*, nếu w g(x) thì w được xem là một bản mã của x. Do đó số lượng bản mã của bất kì bản rõ nào có thể rất lớn. Tuy nhiên, cách xây dựng ngôn ngữ X với độ nhập nhằng k với k đủ lớn tùy thuộc vào nhu cầu sử dụng thực tiễn. Theo Nhận xét 2.2, cùng với g, ngôn ngữ X phải được giữ bí mật. Hơn nữa, dù k được sử dụng để giải mã, độ trễ giải mã cần được xem xét vì nó ảnh hưởng đến hiệu suất của hệ mật. Cho m là một số nguyên dương cố định và cho Sh là chuỗi bit bí mật có độ dài m. Xét ngôn ngữ không nhập * nhằng X {0, 1} có độ không nhập nhằng là k thỏa mãn điều kiện: x1, x2, , xk X, ta có |x1| + |x2| + + |xk| m. Với X và A được định nghĩa như trên, ta có thể định nghĩa eg và dg như trong Lược đồ 2.1. Bây giờ ta có thể mô tả chi tiết một hệ mật MAS ứng với A, X, g đã cho. Để tránh nhầm lẫn, ta sẽ gọi nó là lược đồ hay sơ đồ ứng dụng bảo mật dữ liệu. Lược đồ này bao gồm một thủ tục mã hóa ENCODE và một thủ tục giải mã DECODE được trình bày dưới đây. C. Thủ tục mã hóa ENCODE * Thủ tục ENCODE dưới đây cho phép mã hóa từ u A , u = u1u2 un, ui A với n thành từ mã w với kích thước cố định. Sơ đồ khối biểu diễn thủ tục ENCODE được trình bày trong Hình 1. Trong thủ tục, ta sử dụng vòng lặp để quét từ u từ trái qua phải. Sau đó mỗi khối m-bit của bản mã có thể được tạo ra bằng cách sử dụng vòng lặp lồng nhau. Thêm vào đó, điều kiện (count k) và (|wj| < m) đảm bảo rằng độ dài của từ được sử dụng để tạo ra khối wj là nhỏ hơn hoặc bằng k và wj có độ dài không quá m-bit. Tùy thuộc vào tình huống mã hóa, PAD(wj) được gọi để độn thêm bit nhằm đạt được khối m-bit. Tiếp theo, phép XOR ( ) hai chuỗi bit được sử dụng để tạo mặt nạ cho khối m-bit cấu thành đầu ra.
4. Long Thị Lệ, Nguyễn Đình Hân 257 u = u1u2 un; i = 1, j = 1 i ≤ n w = w’1w’2 w’j-1 j = j + 1 count = 1 S S count ≤ k |wj| ≤ m and |wj| ≤ m Đ PAD(w ) Đ j PAD(wj) Đ S j == 1 |wjeg(ui)| ≤ m S w’j = wj ⊕ Sh Đ w’ = w ⊕ w wj = wjeg(ui); j j-1 j count = count + 1; i = i + 1 Hình 1. Thủ tục ENCODE D. Thủ tục giải mã DECODE Thủ tục DECODE dưới đây cho phép giải mã từ w của q khối m-bit thành bản rõ u A*. Sơ đồ khối các bước chi tiết của thủ tục DECODE được trình bày trong Hình 2. Trong thủ tục DECODE, đầu tiên khóa bí mật m-bit Sh được sử dụng để loại bỏ mặt nạ của các khối đầu vào, sau đó giải mã từng khối riêng biệt. Thủ tục EXTRACT(wj, tmp) trích xuất các từ trong X từ wj, sau đó lưu trữ chúng trong mảng tmp. Tiếp theo, bản rõ tương ứng được giải mã từ tmp bằng cách sử dụng hàm dg. w = w’1w’2 w’q; i = 1, j = 1 Đ u = u1u2 ui-1 j ≤ q j = j + 1 S S wj = wj-1 ⊕ w’j j == 1 Đ wj = w’j ⊕ Sh EXTRACT(wj,tmp) S count ≤ len(tmp) count = 1 Đ count = count + 1; i = i + 1 Hình 2. Thủ tục DECODE Nhận xét 2.3. Rõ ràng là g, X và Sh tạo thành một khóa bí mật. Do đó, sơ đồ ứng dụng trình bày ở trên tạo thành một hệ mật khóa đối xứng.
5. 258 MỘT GIẢI PHÁP NÂNG CAO HIỆU QUẢ GIẢI MÃ CỦA CÁC HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG MAS III. GIẢI MÃ TRONG HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG Ở phần này, trước hết ta sẽ nhắc lại một số định nghĩa liên quan đến đồ thị và đồ thị biểu diễn ngôn ngữ (được tham khảo từ [5]). Theo qui ước, đồ thị được kí hiệu là G = (V, E) trong đó V ∅ là tập các đỉnh và E là tập các cạnh. Trong đồ thị có hướng mỗi cạnh là một cặp có thứ tự (u, v) E xuất phát từ u và kết thúc ở v, với u, v V. Cạnh kết nối một đỉnh với chính nó, kí hiệu (u, u) được gọi là khuyên. Đồ thị chứa khuyên được gọi là đa đồ thị. Đường đi độ dài n từ u đến v, trong đó n là số nguyên dương, trên đồ thị có hướng G là một dãy các đỉnh x0, x1, , xn . Trong đó, u = x0, v = xn, (xi, xi +1) E, i = 0, 1, 2, , n. Kí hiệu đường đi p là p = (x0, x1, , xn) và kí hiệu độ dài đường đi là |p| = n. Tiếp theo, ta sẽ biểu diễn các từ mã bằng đồ thị. Xét ngôn ngữ X có độ không nhập nhằng là k, k > 0. Ta sẽ sử dụng một đa đồ thị có hướng G = (V, E) để biểu diễn các từ của X. Trong đó, mỗi đỉnh trong tập đỉnh V biểu diễn một từ trong X. Các cạnh thuộc E biểu diễn phép kết nối (concatenation) của các từ trong X. Từ cách xây dựng đồ thị, dễ thấy mỗi đường đi trên G biểu diễn một từ nào đó trên X+; đường đi có độ dài n biểu diễn một từ nào đó thuộc Xn+1. Theo thủ tục DECODE, bản mã được giải mã theo từng khối m-bit. Do đó, ta sẽ biểu diễn mỗi từ w X≤k tương ứng với một khối m-bit (sau khi đã loại bỏ bit dư thừa) bằng đồ thị được định nghĩa như trên. Tiếp theo, ta xây dựng các đường đi có thể có biểu diễn từ wj để giải mã. Đường đi ngắn nhất trong các đường đi trên là đường đi cần tìm và nó biểu diễn cách phân tích từ wj. Mệnh đề 3.1. Có nhiều nhất một đường đi biểu diễn từ w X≤ k nằm trong mỗi khối m-bit trên đồ thị G = (V, E) và độ dài của đường đi đó nhỏ hơn k. Từ chú ý 2.1 và từ cách xây dựng đồ thị biểu diễn từ mã, ta sẽ chứng minh Mệnh đề 3.1. Chứng minh. Phản chứng, giả sử tồn tại hai đường đi khác nhau p và q biểu diễn từ w và |p| = m k Nếu |p| ≥ k, vì p là đường đi ngắn nhất nên có |δ| ≥ k. Nghĩa là wj = x1x2 xn X , suy ra δ không phải là đường đi tương ứng với từ mã cần tìm, mâu thuẫn giả thiết. >k Nếu |p| < k ≤ |δ| = n thì suy ra wj = x1x2 xn X , mâu thuẫn giả thiết. Nếu |p| ≤ |δ| < k, theo Mệnh đề 3.1 thì m = |p| = |δ| = n và xi = yi, i = 1, 2, , n. Điều này mâu thuẫn với giả thiết phản chứng. Do đó giả thiết phản chứng là sai. Mệnh đề được chứng minh. Ví dụ 3.1. Cho X = {c, ca1, ca1a3b1, a1b1, b1a2, a2b2, b2a3, a3}, biểu diễn các phân tích có thể có của từ mã w = ca1b1a2b2a3b3. Có hai phân tích có thể có là p1 = (c)(a1b1)(a2b2)(a3) (tương ứng với đường nét đứt trong đồ thị) và p2 = (ca1)(b1a2)(b2a3) (tương ứng với đường nét liền).
6. Long Thị Lệ, Nguyễn Đình Hân 259 Phân tích cần tìm là p2 = (ca1)(b1a2)(b2a3) ứng với đường đi ngắn nhất. c a1b1 a2b2 ca1 b1a2 ca1a3b1 b2a3 a3 Hình 3. Đồ thị biểu diễn ngôn ngữ X IV. KẾT LUẬN Trong bài báo, chúng tôi đề xuất khái niệm đồ thị biểu diễn ngôn ngữ, phát biểu và chứng minh các kết quả cho phép sử dụng đồ thị trong thuật toán giải mã của hệ mật đa trị và nhập nhằng MAS. Định lý 3.1 đã khẳng định việc giải mã có thể được thực hiện chính xác và hiệu quả. Từ đó, ta luôn có thể xây dựng được một thuật toán giải mã hữu hiệu cho các hệ mật MAS dựa trên các kết quả đã thiết lập. TÀI LIỆU THAM KHẢO [1] Nguyen Dinh Han, Longzhe Han, Dao Minh Tuan, Hoh Peter In, Minho Jo, “A Scheme for Data Confidentiality in Cloud-assisted Wireless Body Area Networks”, Information Sciences, Vol. 284, pp. 157-166, 2014. [2] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata, Cambridge University Press, Cambridge, UK, 2010. [3] D.R. Stinson and M. Paterson, Cryptography: Theory and Practice, CRC Press, Inc., Florida, 2018. [4] Nguyen Dinh Han, Ho Ngoc Vinh, Phan Trung Huy, “An extension of codes by unambiguity of languages”, In Proceeding of the Eighth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IEEE Computer Society, pp. 490-493, 2012. [5] K. H. Rosen, Discrete Mathematics and Its Applications, Seven Edition ed., McGraw-Hill, NewYork, 2012. A NEW METHOD TO ENHANCE THE PERFORMANCE OF MULTI-VALUED AND AMBIGUOUS CRYPTOSYSTEMS Long Thi Le, Nguyen Dinh Han ABSTRACT: In this paper, we establish new results that allow us to develop effective decoding algorithms for multi-valued and ambiguous cryptosystems. We demonstrate that, with the application of a special graph, decoding algorithms can improve the performance of those multi-valued and ambiguous cryptosystems.