Lattice-based Cryptography

Brief Overview of Quantum Computing

Quantum Computing adalah teknologi yang menggunakan prinsip fisika kuantum untuk melakukan komputasi. Dengan memanfaatkan qubit sebagai unit penyimpanan dan pengolahan informasi, bukan bit klasik, quantum computing memungkinkan parallelisme yang signifikan melalui superposition dan entanglement. Hal ini membawa potensi untuk menyelesaikan masalah yang sulit dalam waktu polynomial dibanding komputer klasik. Meskipun masih dalam tahap pengembangan, quantum computing membawa risiko bagi kriptografi klasik karena algoritma seperti Shor dapat mengompromikan banyak sistem enkripsi yang umum digunakan saat ini

Key Principles

• Superposition: Sebuah qubit dapat berada dalam beberapa keadaan secara bersamaan, memungkinkan komputer kuantum untuk mengeksplorasi banyak solusi sekaligus. Kemampuan ini secara signifikan meningkatkan kecepatan dan efisiensi komputasi untuk jenis masalah tertentu.
• Entanglement: Qubit dapat terentang, yang berarti keadaan satu qubit terkait langsung dengan keadaan qubit lainnya, terlepas dari jarak yang memisahkan mereka. Properti ini memungkinkan korelasi kompleks dan pemrosesan informasi yang lebih cepat.

Importance of Lattice-Based Digital Signature 

Lattice based digital signature memiliki peran penting untuk autentikasi, memastikan integritas dari suatu dokumen/transaksi, dan lainnya yang didasarkan oleh Lattice based cryptography. Lattice based digital signature dianggap lebih dapat diandalkan dibanding kriptografi biasa karena fondasi mereka yang dapat menyelesaikan masalah lattice yang sangat kompleks seperti shortest vector problem (SVP) dan closest vector problem (CVP). Permasalahan ini tidak mudah untuk diselesaikan bahkan untuk komputer quantum jadinya lebih aman dari serangan.

Simplified Overview of Lattice Based Cryptography

Post-quantum cryptography adalah sebuah bidang dalam kriptografi yang dibuat untuk mengantisipasi, menjaga, dan memperkuat enkripsi di masa post-quantum computing. Salah satu algoritma kriptografi yang paling dipelajari untuk mengantisipasi masa tersebut adalah Lattice based cryptography.

Sumber: Lattice-based cryptography: The tricky math of dots

Lattice-based cryptography bekerja dengan memanfaatkan sejumlah vektor atau “basis”. Vektor-vektor ini kemudian dapat dikombinasi untuk menunjuk ke sebuah titik dari satu titik pusat dalam sebuah bidang.

Sumber: Lattice-based cryptography: The tricky math of dots

Dengan cukup kombinasi vektor, algoritma ini akan membentuk sebuah pola yang menyerupai kisi-kisi atau lattice. Namun uniknya, algoritma lattice-based dapat membentuk 2 pola lattice yang serupa dengan 2 basis yang berbeda. Misalnya seperti pada gambar diatas, Basis pertama menggunakan dua vektor (1,0) dan (0,1). Sedangkan basis kedua menggunakan vektor (2,1) dan (7,3). Namun, keduanya dapat menghasilkan pola lattice yang serupa.

Melalui algoritma ini, terdapat satu persoalan yang cukup sulit untuk diselesaikan, yaitu Shortest Vector Problem atau bisa disingkat SVP. Singkatnya, SVP adalah kombinasi vektor yang menunjuk sebuah titik yang terdekat dengan titik pusat.  Algoritma yang menggunakan 2 vektor (2 dimensi) mungkin masih bisa dibilang relatif mudah untuk diselesaikan oleh komputer. Namun algoritma lattice-based  dapat dikembangkan dengan menambah jumlah vektor (dimensi) yang digunakan. Persoalan ini akan terus menjadi jauh lebih sulit dengan semakin banyaknya vektor yang digunakan. 

Keamanan Terhadap Serangan Kuantum

Salah satu keunggulan utama dari kriptografi berbasis kisi adalah kemampuannya untuk bertahan terhadap serangan yang dilakukan oleh komputer kuantum. Ini terutama disebabkan oleh dua masalah matematis yang mendasari, yaitu Shortest Vector Problem (SVP) dan Closest Vector Problem (CVP).

• Shortest Vector Problem (SVP): SVP adalah masalah yang melibatkan pencarian vektor terpendek dalam sebuah kisi. Meskipun ada algoritma yang dapat menyelesaikan masalah ini dalam waktu polinomial untuk dimensi rendah, kompleksitasnya meningkat secara eksponensial seiring dengan bertambahnya dimensi. Ini menjadikan SVP sangat sulit untuk diselesaikan bahkan oleh komputer kuantum, yang memiliki kemampuan komputasi yang jauh lebih tinggi dibandingkan dengan komputer klasik.
• Closest Vector Problem (CVP): CVP berkaitan dengan menemukan vektor dalam kisi yang paling dekat dengan titik tertentu. Seperti SVP, CVP juga dikenal sebagai masalah yang sulit dan tidak ada algoritma efisien yang diketahui untuk menyelesaikannya, bahkan dengan teknologi kuantum.

Future Application of Lattice-based Algorithm (ML-DSA)

Untuk mengantisipasi masa quantum computing, National Institute of Standards and Technology (NIST) telah menetapkan beberapa algoritma yang diharapkan dapat menjadi standar kriptografi baru. Salah satu algoritma tersebut adalah Module-Lattice-Based Digital Signature Algorithm atau ML-DSA. Sesuai namanya, algoritma ini dibentuk berdasarkan kriptografi lattice-based dan dipercayai sebagai algoritma yang sangat aman dan fleksibel, sehingga dapat diterapkan dalam berbagai interaksi digital seperti memastikan integritas data melalui digital signature, mengamankan komunikasi perangkat IOT, serta mengamankan data-data sensitif terutama dalam bidang kesehatan, keuangan, hingga pemerintahan.

Source:

https://aws.amazon.com/what-is/quantum-computing/?nc1=h_ls

https://www.ibm.com/topics/quantum-computing

https://www.mdpi.com/1999-5903/15/3/94

https://www.sectigo.com/resource-library/what-is-lattice-based-cryptography