Pengemasan Subgrup untuk Transciphering PASTA Terbatch

Tradeoff biaya-noise yang bergantung pada pengemasan dalam transciphering homomorfik

Mugurel Barcau; Vicenţiu Paşol; George C. Ţurcaş· 2026· DOI 10.48550/arXiv.2609.12624

Masalah inti

Transciphering memungkinkan server mengonversi rekaman terenkripsi simetris menjadi ciphertext homomorfik tanpa mengetahui rekaman maupun kunci simetrisnya. Untuk cipher PASTA, konversi ini memerlukan peta linear padat yang biaya implementasinya bergantung pada bagaimana kata-kata rekaman disusun di dalam ciphertext. Penulis mengajukan pertanyaan sederhana namun konsekuensial: dapatkah penataan ulang batch tetap mengurangi biaya konversinya? Jawabannya ya, dan mekanismenya adalah perubahan tata letak pengemasan. Alih-alih menyimpan kata-kata setiap rekaman dalam blok kontigu, mereka menyisipkan rekaman sehingga pergeseran kata siklik mempertahankan posisi setiap rekaman. Posisi-posisi tersebut membentuk koset dari subgrup siklik, sehingga dinamakan *subgroup packing*. Makalah ini mencirikan perpindahan yang diperlukan untuk evaluasi langsung sebagai jumlah translasi bertopeng dan menghubungkan jumlahnya—255 untuk tata letak kontigu dan 128 untuk tata letak subgrup—dengan invarian transversal-difference sebelumnya. Karya ini diposisikan dalam taksonomi yang lebih luas mencakup Architecture, Cybersecurity, Network, dan Cryptography, serta menyasar biaya praktis konversi PASTA-3 terba

Inovasi

Di dua belas korpus berpasangan di bawah enam kunci homomorfik, semua 24 konversi langsung dan subgrup serta semua 48 kueri berikutnya mengembalikan nilai yang diharapkan dan nol yang diperlukan. Rasio berpasangan median biaya server langsung terhadap subgrup adalah 1,60, termasuk pembangkitan publik baru, konversi, dan dua kueri. Dengan kata lain, tata letak subgrup mengurangi biaya server sekitar 37,5% relatif terhadap tata letak kontigu pada run berpasangan median. Pengurangan ini konsisten di seluruh korpus dan kunci berpasangan, dan dikaitkan dengan pemangkasan separuh perpindahan yang diperlukan: 255 untuk tata letak kontigu versus 128 untuk tata letak subgrup. Penulis juga melaporkan bahwa pengurangan tersebut disertai kapasitas noise yang tersisa lebih sedikit, sehingga menetapkan tradeoff biaya-noise yang bergantung pada pengemasan. Hasilnya dirangkum dalam alur berikut:

Transciphering memungkinkan server mengonversi rekaman terenkripsi simetris menjadi ciphertext homomorfik tanpa mengetahui rekaman maupun kunci simetrisnya. Untuk cipher PASTA, konversi ini memerlukan peta linear padat yang biaya implementasinya bergantung pada bagaimana kata-kata rekaman disusun di dalam ciphertext. Penulis mengajukan pertanyaan sederhana namun konsekuensial: dapatkah penataan ulang batch tetap mengurangi biaya konversinya? Jawabannya ya, dan mekanismenya adalah perubahan tata letak pengemasan. Alih-alih menyimpan kata-kata setiap rekaman dalam blok kontigu, mereka menyisipkan rekaman sehingga pergeseran kata siklik mempertahankan posisi setiap rekaman. Posisi-posisi tersebut membentuk koset dari subgrup siklik, sehingga dinamakan *subgroup packing*. Makalah ini mencirikan perpindahan yang diperlukan untuk evaluasi langsung sebagai jumlah translasi bertopeng dan menghubungkan jumlahnya—255 untuk tata letak kontigu dan 128 untuk tata letak subgrup—dengan invarian transversal-difference sebelumnya. Karya ini diposisikan dalam taksonomi yang lebih luas mencakup Architecture, Cybersecurity, Network, dan Cryptography, serta menyasar biaya praktis konversi PASTA-3 terbatch yang diikuti kueri subset-sum publik.

Penulis mengimplementasikan tiga jadwal terbatch yang setara untuk konversi PASTA-3 lengkap dan kueri subset-sum publik berikutnya di HElib. Desain eksperimennya berpasangan: dua belas korpus dievaluasi di bawah enam kunci homomorfik, menghasilkan 24 konversi langsung dan subgrup serta 48 kueri berikutnya. Tata letak langsung menyimpan kata-kata setiap rekaman secara kontigu, sedangkan tata letak subgrup menyisipkan rekaman sehingga pergeseran siklik bekerja di dalam koset subgrup siklik. Secara formal, jika batch memiliki B rekaman dan setiap rekaman memiliki W kata, tata letak kontigu menempatkan rekaman r pada posisi {r W, r W + 1, \dots, r W + W - 1}, sedangkan tata letak subgrup menempatkannya pada koset g H dari subgrup siklik H \leq Z_{N} . Konversi dinyatakan sebagai jumlah translasi bertopeng, dan jumlah perpindahan yang diperlukan dicirikan sebagai 255 untuk tata letak kontigu dan 128 untuk tata letak subgrup. Jumlah ini terkait dengan invarian transversal-difference sebelumnya, yang menjelaskan mengapa tata letak subgrup memangkas separuh jumlah translasi. Implementasi menggunakan HElib dan mengukur biaya server termasuk pembangkitan publik baru, konversi, dan dua kueri. Evaluasi memeriksa bahwa semua konversi dan kueri mengembalikan nilai yang diharapkan dan nol yang diperlukan, serta melaporkan rasio berpasangan median biaya server langsung terhadap subgrup.

Mengapa penting

Kontribusi utama makalah ini adalah identifikasi dan kuantifikasi tradeoff biaya-noise yang bergantung pada pengemasan. Dengan menyisipkan rekaman sehingga pergeseran kata siklik mempertahankan posisi setiap rekaman, tata letak subgrup mengurangi jumlah translasi bertopeng dari 255 menjadi 128. Pengurangan ini bukan sekadar trik implementasi; hal ini didasari oleh invarian transversal-difference yang mencirikan perpindahan yang diperlukan. Rasio berpasangan median 1,60 menunjukkan penghematan biaya server yang substansial, tetapi penulis berhati-hati untuk mencatat bahwa pengurangan tersebut disertai kapasitas noise yang tersisa lebih sedikit. Tradeoff ini penting untuk penerapan praktis: server yang perlu melakukan banyak kueri atau sirkuit lebih dalam mungkin lebih memilih tata letak kontigu karena ruang noise-nya, sementara server yang mengoptimalkan throughput pada kueri dangkal mungkin lebih memilih tata letak subgrup. Hasilnya divalidasi di dua belas korpus berpasangan dan enam kunci homomorfik, dengan semua konversi dan kueri mengembalikan nilai yang diharapkan dan nol yang diperlukan. Karya ini dengan demikian memberikan dasar yang jelas dan reproducible untuk memilih tata letak pengemasan dalam transciphering PASTA terbatch, dan membuka pertanyaan apakah pengemasan berbasis subgrup serupa dapat dirancang untuk cipher lain atau skema homomorfik yang berbeda. Kandidat taksonomi—Architecture, Cybersecurity, Network, dan Cryptography—mencerminkan relevansi karya ini bagi infrastruktur komputasi aman dan desain protokol kriptografi.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…