Celah Proksimitas untuk Kode Gabidulin dan Penerapannya

Celah proksimitas metrik rank, batas ketat, dan skema komitmen polinomial metrik rank pertama

Songsong Li; Chaoping Xing; Chen Yuan; Ruiqi Zhu· 2026· DOI 10.48550/arXiv.2609.09838

Masalah inti

Celah proksimitas adalah properti fundamental yang menopang kesahihan interactive oracle proofs of proximity (IOPP) dan skema komitmen polinomial (PCS). Untuk kode linear , celah proksimitas- dengan galat berarti bahwa untuk sembarang garis afin , entah semua titik pada garis tersebut berjarak -dekat ke , atau paling banyak sebagian kecil yang demikian. Meskipun celah proksimitas untuk kode metrik Hamming telah dipahami dengan baik, padanan metrik rank-nya sebagian besar masih belum dieksplorasi. Makalah ini mengatasi celah tersebut dengan mempelajari celah proksimitas untuk kode metrik rank linear dan aplikasi kriptografinya. Penulis meninjau kode atas lapangan perluasan yang dilengkapi metrik rank, di mana jarak antara dua vektor adalah rank selisihnya sebagai matriks atas . Kontribusi utamanya meliputi: (1) celah proksimitas umum untuk sembarang kode metrik rank linear dengan dan galat dengan ; (2) celah yang diperbaiki untuk kode Gabidulin hingga $\de

Makalah ini menyajikan beberapa hasil kunci. Pertama, untuk sembarang kode metrik rank linear [n, k, d] C atas F_{q^{m}}, terdapat celah proksimitas untuk setiap δ \leq (d - 1) / (3 n) dengan galat paling banyak q^{e + 1} / q^{m}, dengan e = ⌊ δ n ⌋ . Kedua, untuk kode Gabidulin, celahnya diperbaiki menjadi δ \leq (d - 1) / (2 n) dengan galat 10 q^{n - 1} / q^{m} . Batas-batas ini masing-masing setara dengan batas untuk kode metrik Hamming linear umum dan kode Reed-Solomon. Ketiga, batas (d - 1) / (2 n) terbukti ketat: terdapat keluarga tak hingga kode Gabidulin laju-konstan dan garis afin di mana sebagian 1 - o (1) titik berjarak d / (2 n) -dekat ke kode, sementara u_{1} setidaknya berjarak 3 d / (4 n) -jauh darinya. Keempat, pada δ = d / (3 n), sebuah contoh kontra menetapkan batas bawah untuk ϵ, yang menunjukkan bahwa galat tidak dapat dibuat sembarang kecil. Terakhir, sebagai penerapan, penulis membangun IOPP untuk kode Gabidulin terinterleaving dengan mengadaptasi IOPP Ligero, dan skema komitmen polinomial terlinearisasi- q dengan mengadaptasi PCS berbasis Ligero. Ini adalah kerangka PCS pertama yang berbasis kode pengoreksi galat metrik rank. Hasil-h

Celah proksimitas adalah properti fundamental yang menopang kesahihan interactive oracle proofs of proximity (IOPP) dan skema komitmen polinomial (PCS). Untuk kode linear C \subseteq F^{n}, celah proksimitas- δ dengan galat ϵ berarti bahwa untuk sembarang garis afin ℓ_{u_{0}, u_{1}} = {u_{0} + α u_{1} : α \in F}, entah semua titik pada garis tersebut berjarak δ -dekat ke C, atau paling banyak sebagian kecil ϵ yang demikian. Meskipun celah proksimitas untuk kode metrik Hamming telah dipahami dengan baik, padanan metrik rank-nya sebagian besar masih belum dieksplorasi. Makalah ini mengatasi celah tersebut dengan mempelajari celah proksimitas untuk kode metrik rank linear dan aplikasi kriptografinya. Penulis meninjau kode atas lapangan perluasan F_{q^{m}} yang dilengkapi metrik rank, di mana jarak antara dua vektor adalah rank selisihnya sebagai matriks atas F_{q} . Kontribusi utamanya meliputi: (1) celah proksimitas umum untuk sembarang kode metrik rank linear dengan δ \leq (d - 1) / (3 n) dan galat q^{e + 1} / q^{m} dengan e = ⌊ δ n ⌋; (2) celah yang diperbaiki untuk kode Gabidulin hingga δ = (d - 1) / (2 n) dengan galat 10 q^{n - 1} / q^{m}; (3) hasil ketat yang menunjukkan batas (d - 1) / (2 n) bersifat optimal; (4) contoh kontra pada δ = d / (3 n) yang menetapkan batas bawah untuk ϵ; dan (5) penerapan pada IOPP dan PCS, termasuk kerangka PCS pertama yang berbasis kode pengoreksi galat metrik rank.

Penulis menggunakan kombinasi teknik aljabar dan kombinatorial untuk menganalisis celah proksimitas pada kode metrik rank. Untuk batas umum, mereka memanfaatkan struktur kode metrik rank linear dan sifat-sifat garis afin dalam ruang metrik rank. Pembuktian untuk kode Gabidulin memanfaatkan struktur aljabar spesifiknya sebagai polinomial terlinearisasi- q . Untuk menetapkan ketatnya batas, mereka membangun keluarga tak hingga kode Gabidulin laju-konstan dan garis afin di mana sebagian 1 - o (1) titik berjarak d / (2 n) -dekat ke kode, sementara u_{1} setidaknya berjarak 3 d / (4 n) -jauh darinya. Konstruksi ini memakai parameter yang dipilih secara cermat dan argumen probabilistik. Contoh kontra pada δ = d / (3 n) diturunkan dengan menganalisis distribusi rank dari kombinasi linear kata kode dan vektor galat. Untuk penerapannya, penulis mengadaptasi IOPP Ligero untuk kode Reed-Solomon terinterleaving ke konteks metrik rank, khususnya untuk kode Gabidulin terinterleaving. Mereka kemudian memodifikasi PCS berbasis Ligero untuk polinomial biasa guna memperoleh skema komitmen polinomial terlinearisasi- q . Analisis keamanan PCS bergantung pada hasil celah proksimitas. Metodologinya rigor, menggabungkan pembuktian teoretis dengan konstruksi eksplisit dan adaptasi algoritmik.

Hasil-hasil ini menunjukkan bahwa kode metrik rank, khususnya kode Gabidulin, memiliki celah proksimitas yang sebanding dengan padanan metrik Hamming-nya. Hasil ketat menyoroti keterbatasan fundamental: batas (d - 1) / (2 n) tidak dapat diperbaiki untuk kode Gabidulin. Contoh kontra pada d / (3 n) lebih lanjut menegaskan trade-off yang halus antara parameter celah dan probabilitas galat. Penerapan pada IOPP dan PCS sangat patut dicatat. IOPP untuk kode Gabidulin terinterleaving memperluas kerangka Ligero ke metrik rank, memungkinkan pengujian proksimitas yang efisien untuk kode-kode tersebut. Skema komitmen polinomial terlinearisasi- q adalah yang pertama dari jenisnya, membuka jalan baru bagi protokol kriptografi berbasis kode metrik rank. Konstruksi ini dapat menghasilkan sistem yang lebih efisien dan aman dalam skenario di mana kode metrik rank menawarkan keunggulan, seperti pada network coding dan penyimpanan terdistribusi. Penulis juga membahas potensi perbaikan dan masalah terbuka, seperti menutup celah antara batas umum dan batas spesifik Gabidulin, serta mengeksplorasi keluarga kode metrik rank lainnya. Secara keseluruhan, karya ini secara signifikan memajukan pemahaman tentang celah proksimitas dalam metrik rank dan menyediakan penerapan kriptografi yang praktis.

Praktisi dan peneliti ilmu komputer

Membuka konten member…