Model Simetris untuk Syndrome Decoding

Model polinomial baru berbasis polinomial simetris elementer untuk Masalah Syndrome Decoding biner eksak, dengan batas kompleksitas yang lebih baik dan varian yang adaptif terhadap instansi.

Elisa Gorla; Simone Trebiani· 2026· DOI 10.48550/arXiv.2609.14052

Masalah inti

Masalah Syndrome Decoding (SDP) adalah masalah fundamental dalam teori pengkodean dan kriptografi, khususnya dalam konteks kriptografi berbasis kode. Varian eksak dari SDP meminta pencarian vektor dengan bobot Hamming tertentu yang memenuhi sistem linear atas lapangan hingga. Makalah ini berfokus pada kasus biner dan memperkenalkan model polinomial baru untuk SDP eksak berdasarkan polinomial simetris elementer. Penulis bertujuan menyediakan model yang menghasilkan kompleksitas komputasi lebih rendah untuk menyelesaikan sistem polinomial terkait dibandingkan pendekatan sebelumnya. Makalah ini memperkirakan kompleksitas dengan membatasi derajat regularitas dan derajat penyelesaian dari ideal yang dibangkitkan oleh polinomial model tersebut. Selanjutnya, mereka mengusulkan varian yang kompleksitasnya bergantung pada instansi SDP tertentu, sehingga menghasilkan kompleksitas bahkan lebih rendah. Terakhir, mereka membahas cara menerapkan pendekatan ini pada varian SDP lainnya.

Penulis menetapkan batas pada derajat regularitas dan derajat penyelesaian untuk ideal yang terkait dengan model baru ini. Mereka menunjukkan bahwa batas-batas ini lebih rendah daripada batas untuk model polinomial sebelumnya untuk SDP biner eksak. Secara spesifik, estimasi kompleksitas untuk model baru ini lebih rendah daripada model berbasis pemodelan Support Minors atau model yang menggunakan transformasi Walsh-Hadamard. Batas eksaknya bergantung pada parameter seperti n, r, dan w, tetapi perilaku asimtotiknya menunjukkan perbaikan. Untuk varian yang adaptif terhadap instansi, kompleksitasnya bahkan lebih rendah dan bergantung pada instansi tertentu, yang berpotensi memungkinkan penyelesaian lebih efisien dalam praktik. Makalah ini memberikan estimasi kompleksitas teoretis tetapi tidak menyertakan hasil eksperimen; namun, analisis teoretis menunjukkan bahwa model baru ini lebih unggul daripada model yang ada dalam hal derajat regularitas dan derajat penyelesaian.

Masalah Syndrome Decoding (SDP) adalah masalah fundamental dalam teori pengkodean dan kriptografi, khususnya dalam konteks kriptografi berbasis kode. Varian eksak dari SDP meminta pencarian vektor dengan bobot Hamming tertentu yang memenuhi sistem linear atas lapangan hingga. Makalah ini berfokus pada kasus biner dan memperkenalkan model polinomial baru untuk SDP eksak berdasarkan polinomial simetris elementer. Penulis bertujuan menyediakan model yang menghasilkan kompleksitas komputasi lebih rendah untuk menyelesaikan sistem polinomial terkait dibandingkan pendekatan sebelumnya. Makalah ini memperkirakan kompleksitas dengan membatasi derajat regularitas dan derajat penyelesaian dari ideal yang dibangkitkan oleh polinomial model tersebut. Selanjutnya, mereka mengusulkan varian yang kompleksitasnya bergantung pada instansi SDP tertentu, sehingga menghasilkan kompleksitas bahkan lebih rendah. Terakhir, mereka membahas cara menerapkan pendekatan ini pada varian SDP lainnya.

Penulis membangun sistem polinomial yang solusinya bersesuaian dengan solusi SDP biner eksak. Model ini berbasis polinomial simetris elementer. Misalkan H \in F_{2}^{r \times n} adalah matriks pemeriksa paritas dan s \in F_{2}^{r} adalah sindrom. SDP eksak meminta e \in F_{2}^{n} dengan He = s dan wt (e) = w . Model baru ini memperkenalkan variabel yang merepresentasikan polinomial simetris elementer dari vektor galat. Secara spesifik, untuk i = 1, \dots, w, misalkan σ_{i} menyatakan polinomial simetris elementer ke- i yang dievaluasi pada support e . Model ini terdiri atas:

Model baru ini memanfaatkan struktur polinomial simetris elementer untuk menciptakan sistem polinomial dengan derajat regularitas lebih rendah. Hal ini dicapai dengan memperkenalkan variabel yang menangkap sifat simetris dari vektor galat, sehingga mengurangi jumlah persamaan berderajat tinggi. Varian yang adaptif terhadap instansi lebih lanjut menyesuaikan model dengan instansi SDP tertentu, berpotensi dengan memasukkan informasi tambahan tentang sindrom atau matriks pemeriksa paritas. Penulis membahas bagaimana pendekatan ini dapat diperluas ke varian SDP lainnya, seperti kasus ketika bobot tidak tetap atau lapangannya bukan biner. Estimasi kompleksitas didasarkan pada asumsi bahwa sistem polinomial diselesaikan menggunakan algoritma basis Gröbner, dan batas pada derajat penyelesaian secara langsung diterjemahkan menjadi kompleksitas algoritma tersebut. Makalah ini menyimpulkan bahwa model baru ini menawarkan peningkatan signifikan dibandingkan model polinomial sebelumnya untuk SDP biner eksak, dan varian yang adaptif terhadap instansi sangat menjanjikan untuk aplikasi praktis. Pekerjaan selanjutnya mencakup validasi eksperimen dan optimasi lebih lanjut.

Praktisi dan peneliti ilmu komputer

Membuka konten member…