Tôi không thể tái tạo độ phức tạp bit chính xác từ bài báo đã đề cập [1], các tác giả đã không cung cấp mã nguồn. Tôi đang đăng các công cụ ước tính của mình cho các cuộc tấn công MMT và BJMM đây.
Kết luận rằng thuật toán BJMM kém hơn MMT là không chính xác vì MMT là trường hợp đặc biệt của BJMM. Tóm lại, BJMM là MMT không có đại diện cho loại $1 = 0+0 \bmod 2 $ cho vectơ lỗi. Sự nhầm lẫn xuất phát từ thực tế là các tác giả của [1] xem xét BJMM với độ sâu cố định nhất định của cây tìm kiếm (cụ thể là độ sâu 3 như được thực hiện trong bài báo gốc [2]. Tuy nhiên, điều này có thể không tối ưu đối với một chế độ thưa thớt nhất định, do đó, kết luận sai lầm rằng BJMM kém hơn MMT. Tôi cung cấp thêm chi tiết dưới đây.
Cốt lõi của cả thuật toán MMT và BJMM là ý tưởng về mơ hồ tách vectơ lỗi $e \in \{0,1\}^k$ trọng lượng $p$ như $e = e_1 + e_2$. MMT mất $e_1, e_2 \in \{0,1\}^k$ mỗi trọng lượng $p/2$, do đó cho $\binom{p}{p/2}$ cách để đại diện $0$-tọa độ như $0+1$ hoặc $1+0$ Trong $e$. BJMM lấy $e_1, e_2 \in \{0,1\}^k$ mỗi trọng lượng $p/2 + \varepsilon$, do đó cho $\binom{p}{p/2} \cdot \binom{k-p}{\varepsilon}$ biểu diễn (bội số thứ hai là số lượng biểu diễn của loại $0 = 1+1$).
Nó chỉ ra rằng đối với vấn đề giải mã trong chế độ dày đặc, tức là khi trọng lượng của $e$ là thứ tự $\Theta(n)$, thuật toán BJMM sẽ nhanh hơn khi chúng ta lặp lại quy trình bằng cách biểu diễn $e_1$, $e_2$ một cách mơ hồ. Do đó, người ta kết thúc với cấu trúc cây tìm kiếm của thuật toán, trong đó độ sâu tối ưu của cây là một tham số được tối ưu hóa. Từ [2] đối với chế độ dày đặc, nó xảy ra là 3.
Đối với các tham số McEliece cổ điển, hóa ra việc thực hiện độ sâu-2 là tối ưu. Theo trực giác, lỗi càng thưa thớt thì cây tối ưu sẽ càng nông, bởi vì người ta không thể chia đôi một trọng lượng nhỏ quá nhiều lần.
Cụ thể, tôi có được các chứng khoán bit sau (và độ phức tạp của bộ nhớ) với công cụ ước tính của mình. Đây có thể là đánh giá thấp, như $poly(n)$ các yếu tố bị bỏ qua. Bạn có thể sao chép chúng bằng cách chạy tập lệnh.
-------------------- MMT --------------------
n = 3488 k = 2720 w = 64 {'thời gian chạy': 133.610045757394, 'mem': 61.4108701659799}
n = 4608 k = 3360 w = 96 {'thời gian chạy': 174.170500202444, 'mem': 76.7183814578096}
n = 6960 k = 5413 w = 119 {'thời gian chạy': 244.706198594600, 'mem': 123.451330788046}
n = 8192 k = 6528 w = 128 {'thời gian chạy': 277.268692835670, 'mem': 140.825234863797}
BJMM độ sâu 2 vượt trội hơn một chút so với cả MMT và BJMM độ sâu 3.
----------------BJMM độ sâu 2 ----------------
n = 3488 k = 2720 w = 64 {'thời gian chạy': 127.121142192395,'mem': 65.4912086419963,'eps': 4}
n = 4608 k = 3360 w = 96 {'thời gian chạy': 164.510671206084, 'mem': 88.1961572319148, 'eps': 6}
n = 6960 k = 5413 w = 119 {'thời gian chạy': 231.228308300186, 'mem': 118.193072674123, 'eps': 8}
n = 8192 k = 6528 w = 128 {'thời gian chạy': 262.367185095806,'mem': 134.928413147468, 'eps': 8}
----------------Độ sâu BJMM 3 ----------------
n = 3488 k = 2720 w = 64 {'thời gian chạy': 132.929177320070, 'mem': 30.8744409777593, 'eps': [2, 0]}
n = 4608 k = 3360 w = 96 {'thời gian chạy': 167.443669507488, 'mem': 45.4015594758618, 'eps': [6, 0]}
n = 6960 k = 5413 w = 119 {'thời gian chạy': 236.346159271338, 'mem': 67.5649403829532,'eps': [6, 0]}
n = 8192 k = 6528 w = 128 {'thời gian chạy': 269.431207750362, 'mem': 70.1193015124538, 'eps': [6, 0]}
[1] https://www.mdpi.com/1999-4893/12/10/209/pdf
[2] https://eprint.iacr.org/2012/026.pdf
