Điểm:3

kích thước của mã Goppa

lá cờ in

Đối với các hệ thống mật mã McEliece/Niederreiter, một lựa chọn mã hiệu quả có vẻ an toàn là mã Goppa nhị phân bất khả quy, được xác định bởi một hàm bất khả quy. $g(x)\trong GF(2^m)[x]$ bằng cấp $t$ và một vectơ hỗ trợ $L=(\alpha_0,\ldots,\alpha_{n-1})$ với sự khác biệt $\alpha_i\trong GF(2^m)$.

Bản thân mã này là $GF(2)$-vectơ có giá trị trong hạt nhân của ma trận kiểm tra chẵn lẻ $$ H=\trái( \begin{array}{cccc} g(\alpha_0)^{-1}&g(\alpha_1)^{-1}&\ldots&g(\alpha_{n-1})^{-1}\ g(\alpha_0)^{-1}\alpha_0&g(\alpha_1)^{-1}\alpha_1&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}\ \vdots&\vdots&\ldots&\vdots\ g(\alpha_0)^{-1}\alpha_0^{t-1}&g(\alpha_1)^{-1}\alpha_1^{t-1}&\ldots&g(\alpha_{n-1})^{ -1}\alpha_{n-1}^{t-1}\ \end{mảng}\phải). $$ Lưu ý rằng $H$ là hạng đầy đủ. Để tạo ma trận kiểm tra chẵn lẻ $H'$ trên $GF(2)$, người ta có thể thay thế các mục của $H$ với các vectơ cột trong $GF(2)$ (sử dụng một số cơ sở cho phần mở rộng $GF(2^m)/GF(2)$).

Hầu như tất cả các nguồn tôi tham khảo đều liệt kê mã kết quả là $[n,k]=[n, n-mt]$, nhưng cấu trúc chung (ví dụ mã thay thế) cho $k=n-mt$ như một chặn dưới cho kích thước $k$ của mã không gian con kết quả.

Câu hỏi của tôi là:

  1. Xếp hạng kết quả thường xuyên như thế nào $k=n-mt$? Trong thiết lập AG, tôi đoán đây là thứ nguyên Riemann-Roch nên có lẽ một nhà hình học đại số có thể trả lời.
  2. Có vấn đề gì nếu chúng ta có các hàng dư thừa trong kiểm tra chẵn lẻ $H'$? Điều này có ảnh hưởng đến việc triển khai hệ thống mật mã không?

Tôi đoán điều này được giải quyết trong trình tạo khóa từ https://eprint.iacr.org/2017/595.pdf (phần 5.2), nếu chỉ trả về lỗi và khởi động lại quá trình tạo khóa khi không đạt được rref; họ đưa ra xác suất thành công là 29% dựa trên mật độ $GL_{mt}(GF(2))$ Trong $Mat_{mt\times mt}(GF(2))$, tức là mật độ tiệm cận là $$ \prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0,288\ldots. $$


Suy nghĩ thứ hai liên quan đến 1), tôi đoán đó là câu hỏi nhiều hơn về thời điểm hạt nhân của bản đồ tuyến tính được xác định trên một trường con (ví dụ: hạt nhân của $x-\sqrt{2}y$ có kích thước một trên $\mathbb{Q}(\sqrt{2})$ nhưng thứ nguyên bằng không khi bị giới hạn ở $\mathbb{Q}$).

Daniel S avatar
lá cờ ru
https://eprint.iacr.org/2017/595.pdf có thể cải thiện tỷ lệ thành công của họ bằng cách cho phép quy trình hệ thống hóa của họ hoán đổi các cột nếu cần. Vì họ đang kiểm tra các ma trận trong đó các cột $mt$ đầu tiên có thứ hạng hàng đầy đủ, điều này thực sự hiếm hơn so với ma trận đầy đủ có thứ hạng hàng đầy đủ.
Điểm:2
lá cờ ru
  1. Từ quan điểm heuristic (đối với các tham số quan tâm đến mật mã), điều đó khá khó xảy ra. nhị phân $n\times(n-r)$ ma trận với các mục nhập ngẫu nhiên có ít hơn $2^{-n+r}$ cơ hội bị thiếu thứ hạng. Có thể có một câu trả lời hình học chính xác hơn.

  2. Mã này có thể được tính toán bằng cách sử dụng các phép biến đổi hàng để đặt $H'$ ở dạng hệ thống $(I|A)$ và sau đó lấy mã Goppa nhị phân là $(I|A^t)$. Nếu $H'$ bị thiếu thứ hạng thì việc triển khai sẽ cần phải có một phương tiện để phát hiện rằng hình thức hệ thống đầy đủ chưa đạt được và loại bỏ các hàng còn lại của $H'$. Nếu hạng của $H'$$r$ thì ma trận tạo mã Goppa nhị phân của chúng ta sẽ là $n\times(n-r)$ có thể lớn hơn bộ nhớ được phân bổ (và thêm vào các vấn đề về băng thông vốn đã nhức nhối). Bây giờ một số hàng của ma trận trình tạo sẽ phải được bỏ đi. Chúng tôi muốn tránh các cột dư thừa để giữ cho bộ thông tin khó giải mã, vì vậy chúng tôi có thể muốn hủy hệ thống hóa ma trận trình tạo một cách ngẫu nhiên trước khi xóa các hàng, hoán vị các cột và hệ thống hóa lại. Sau đó, có một vấn đề thú vị là các hàng bị cắt xén của các hàng đã bị xóa có thể được trình bày cho bộ giải mã của chúng tôi và được tách thành công thành thứ gì đó không nằm trong khoảng của ma trận trình tạo của chúng tôi, nhưng bộ giải mã của chúng tôi có thể sẽ sử dụng ma trận được hệ thống lại của chúng tôi để ánh xạ nó vào khoảng của ma trận trình tạo. ma trận máy phát điện. Việc triển khai dường như chưa sẵn sàng cho việc này và có thể thể hiện hành vi không thể đoán trước. Tất cả trong tất cả, có lẽ sẽ tốt hơn nếu chọn một cái mới $g(X)$ và bắt đầu lại.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.