2.7. Ý tưởng xây dựng các hệ mật mã dựa trên mã sửa sai

Đặt \(\bm{G}\) là ma trận sinh của linear code \([n, k]_q\) \(\mathcal{C}\) có thể sửa \(t\) lỗi.

Nếu code với ma trận sinh \(\bm{G}\) không có các cấu trúc đại số hoặc tổ hợp thì theo định lí trên về độ khó NP của bài toán nhận dạng syndrome decode, bài toán decode linear code \([n, k]_q\) là rất khó.

Khi đó nếu mã hóa thông điệp \(m\) có thể thực hiện qua việc: \(\bm{m} \to \bm{c} = \bm{m} \bm{G} + \bm{e}\), \(\mathrm{wt}(\bm{e}) = t\), \(\bm{e} \in V_n(q)\).

Khi đó, cho trước vector \(\bm{c}\), việc tìm một vector \(\bm{m}\) là bài toán decode trên linear code \([n, k]_q\) với ma trận sinh \(\bm{G}\), không có các cấu trúc đại số hoặc tổ hợp. Suy ra việc phá mã rất khó.

Vấn đề là ở phía bên việc tìm lại \(\bm{m}\) từ \(\bm{c}\) rất khó nên cần một phương án để giải mã lại thông điệp ban đầu.