Kriptografi Berbasis Kisi
- Diperkenalkan oleh
- Miklós Ajtai
- Tahun
- 1996
- Jenis
- public-key cryptosystem based on lattice hardness
- Keluarga
- Post-quantum cryptography
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Kriptografi berbasis kisi adalah kelas sistem kriptografi yang keamanannya berasal dari kesulitan komputasi masalah kisi, khususnya masalah vektor terpendek (SVP) dan pembelajaran dengan kesalahan (LWE).
Pertama kali diusulkan oleh Miklós Ajtai pada tahun 1996, pendekatan berbasis kisi telah mendapatkan perhatian sebagai kandidat utama untuk kriptografi pasca-kuantum. Berbeda dengan RSA dan ECC, yang rentan terhadap komputer kuantum, masalah kisi diyakini tetap sulit bahkan terhadap algoritma kuantum.
Intuisi di balik metode
Kisi adalah subgrup diskrit dari ruang Euclidean yang dibentuk oleh kombinasi linear bilangan bulat dari vektor basis. Kriptografi berbasis kisi mengeksploitasi kesenjangan antara dua masalah: menemukan vektor pendek dalam kisi secara komputasi sulit, tetapi dengan informasi tambahan (basis rahasia), vektor pendek dapat ditemukan dengan cepat. Kriptografi kunci publik dibangun dengan mempublikasikan basis yang sulit dan menjaga basis yang mudah tetap rahasia. Penambahan derau acak kecil (paradigma pembelajaran dengan kesalahan) semakin memperkuat keamanan dengan membuat masalah menyerupai sistem linear yang bising yang sulit dipecahkan.
Sejarah
Karya dasar Ajtai tahun 1996 menghubungkan kesulitan kisi dengan kriptografi. Kerangka kerja pembelajaran dengan kesalahan (LWE) Regev pada tahun 2005 memberikan dasar yang praktis dan serbaguna untuk kriptografi kisi. Bidang ini dipercepat setelah lembaga akademik dan pemerintah mengenali ancaman komputasi kuantum terhadap infrastruktur kriptografi saat ini. Pada tahun 2022, NIST menstandarkan algoritma kriptografi pasca-kuantum, memilih skema berbasis kisi (CRYSTALS-Kyber untuk enkripsi, CRYSTALS-Dilithium untuk tanda tangan) sebagai rekomendasi utama.
Kapan digunakan
Kriptografi berbasis kisi sangat penting untuk sistem yang dirancang agar tetap aman terhadap komputer kuantum di masa depan. Ini direkomendasikan untuk kerahasiaan jangka panjang data sensitif, komunikasi pemerintah dan militer, serta infrastruktur yang harus tetap aman selama beberapa dekade. Seiring algoritma pasca-kuantum yang terstandarisasi matang (NIST baru-baru ini menstandarkan ML-KEM dan ML-DSA), metode kisi menjadi arus utama dalam sistem kriptografi modern.
Batasan dan pertimbangan
- Ukuran kunci dan sandi yang lebih besar dibandingkan dengan RSA atau ECC tradisional, meningkatkan beban penyimpanan dan transmisi
- Lebih baru dan kurang banyak diterapkan dibandingkan RSA atau ECC, sehingga pengalaman penerapan di dunia nyata terbatas
- Beberapa skema berbasis kisi memiliki pilihan parameter halus yang secara signifikan memengaruhi keamanan; parameter yang salah bisa berakibat fatal
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Diyakini tahan terhadap serangan komputer kuantum, termasuk algoritma Shor
- Dasar matematika yang kuat berdasarkan masalah kisi yang telah dipelajari dengan baik
- Mendukung enkripsi dan tanda tangan digital dalam kerangka kerja yang sama
- Implementasi praktis tersedia dengan biaya komputasi yang wajar untuk perangkat keras modern
Penerapan
- Keamanan transportasi pasca-kuantum untuk melindungi komunikasi dari dekripsi kuantum di masa depan
- Enkripsi arsip jangka panjang untuk dokumen dan data yang harus tetap rahasia selama beberapa dekade
- Sistem komunikasi pemerintah dan militer yang tangguh terhadap ancaman kuantum
- Sistem blockchain dan mata uang kripto yang dirancang untuk keamanan tahan kuantum
- Sistem IoT dan tertanam di mana ketahanan kuantum adalah persyaratan desain
- Sistem kriptografi hibrida yang menggabungkan algoritma kisi dan tradisional selama periode transisi kriptografi
Cara kerjanya
Cara kerjanya
Pilih dimensi kisi n, modulus q, dan distribusi kesalahan. Hasilkan basis pendek rahasia dan turunkan basis publik darinya menggunakan transformasi kisi.
Kunci publik diturunkan dari basis kisi yang sulit; kunci tersebut tidak memberikan informasi tentang basis rahasia dari perspektif komputasi.
Untuk mengenkripsi, tambahkan teks biasa ke kombinasi linear yang bising dari vektor basis publik, menciptakan titik kisi ditambah derau.
Menggunakan basis pendek rahasia, reduksi titik kisi yang bising dan ekstrak teks biasa.
Kesalahan umum
- Memilih parameter kisi (dimensi, modulus, distribusi kesalahan) tidak sepele; menggunakan parameter standar yang disetujui NIST sangat direkomendasikan
- Serangan saluran samping (waktu, analisis daya) pada operasi kisi memerlukan implementasi yang cermat; algoritma waktu konstan sangat penting
- Mencampur algoritma berbasis kisi dan klasik secara keliru dapat menciptakan sistem hibrida dengan kelemahan yang tidak terduga
Pertanyaan yang sering diajukan
Apa itu masalah pembelajaran dengan kesalahan (LWE)?
LWE adalah masalah komputasi di mana seseorang diberikan persamaan linear yang bising di atas medan hingga. Diberikan persamaan berbentuk a·x + e (mod q) di mana a acak, x rahasia, dan e adalah derau kecil, memulihkan x tanpa mengetahui e secara komputasi sulit.
Mengapa kunci berbasis kisi lebih besar dari kunci RSA?
Basis kisi dan matriks yang mengkodekannya mengandung lebih banyak informasi daripada satu bilangan komposit. Mengkodekan basis kisi secara kriptografis membutuhkan lebih banyak bit, meskipun skema terbaru telah mengoptimalkan representasi.
Apakah masalah kisi tahan kuantum?
Tidak ada algoritma kuantum yang diketahui lebih cepat daripada algoritma klasik untuk masalah kisi seperti SVP atau LWE, meskipun ini tetap menjadi area penelitian aktif. Kesulitan kisi dikonjekturkan akan bertahan dari komputer kuantum.
Apa rekomendasi NIST tentang kriptografi kisi?
NIST menstandarkan ML-KEM (Mekanisme Enkapsulasi Kunci Berbasis Modul-Kisi) untuk enkripsi dan ML-DSA (Algoritma Tanda Tangan Digital Berbasis Modul-Kisi) untuk tanda tangan sebagai algoritma pasca-kuantum utama dalam FIPS 203 dan FIPS 204.
Bisakah saya menggunakan kriptografi kisi hari ini?
Ya. Banyak pustaka kriptografi modern sekarang mendukung algoritma kisi yang terstandarisasi NIST. Organisasi yang menangani data sensitif dengan periode retensi yang lama harus mulai merencanakan migrasi.
Metode terkait
Sumber
Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.
Buka referensi publikasiDisalin.Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.
Buka referensi publikasiDisalin.