Kriptografi Berdasar Multivariat: Skema Tanda Tangan Digital Hidden Product of Polynomial Composition (HPPC)

Saifullah Ali, Prof. Dr.rer.nat. Indah Emilia Wijayanti, S.Si., M.Si. ; Uha Isnaini, S.Si., M.Sc., Ph.D.

2024 | Tesis | S2 Matematika

Skema tanda tangan digital Hidden Product of Polynomial Composition (HPPC) merupakan salah satu partisipan pada kompetisi post-quantum cryptography yang diselenggarakan oleh NIST sejak tahun 2023 dengan fokus pada pencarian skema tanda tangan digital yang pendek, efisien dan aman. Skema tanda tangan digital yang diusulkan pada kompetisi ini perlu ditinjau oleh publik terhadap teori ataupun praktik. Pada penelitian ini, dilakukan tinjauan teori terhadap teori-teori aljabar yang mendasari skema HPPC dengan kajian pustaka dan pemaparan mendetail skema HPPC. Skema HPPC merupakan skema yang didasari oleh pintu jebakan HFE dengan memanfaatkan repreresentasi matriks sehingga kunci public berupa matriks di berukuran n × n^2 atas Fq . Skema HPPC memberikan cara konstruksi pemetaan pusat HFE menggunakan dua polinomial dilinearisasi dengan menghitung produk dari komposisi polinomial. Pada penelitian ini, skema HPPC juga diaplikasikan untuk enkripsi.

Skema HPPC memanfaatkan permasalahan multivariat kuadrat untuk keamanannya. Walaupun demikian, penggunaan representasi matriks dan pembentukan pemetaan pusat pada HPPC memberikan kemudahan dalam menghitung pintu jebakan HFE. Skema tanda tangan digital HPPC merupakan skema dengan teori aljabar yang kuat dan bervariasi tetapi mudah dihitung. Namun, skema HPPC tidak direkomendasikan untuk skema enkripsi karena tidak ada jaminan ketunggalan akar suatu polinomial univariat.

The Hidden Product of Polynomial Composition (HPPC) digital signature scheme is one of the participants in the post-quantum cryptography competition organized by NIST since 2023 to find digital signature that short, efficient, and secure. The digital signature schemes are proposed in the competition must be reviewed by the public in theory and application. In this research, we conduct a theoretical review of the algebraic theories underlying the HPPC Scheme with a literature review and a detailed study of the HPPC scheme. The HPPC scheme is based on the HFE trapdoor by utilizing a matrix representation of size n x n^2 over Fq. The HPPC scheme provides a way of constructing the HFE center map using two linearized polynomials by computing its product and composition. In this research, we also applied the HPPC scheme for encryption

The HPPC Scheme is based on a quadratic multivariate problem. However, the use of the matrix representation and the way of constructing a center map makes the HFE trapdoor calculate easily. The HPPC scheme has a strong and varied algebraic theory but keeps it easy to compute. However, the application of the HPPC scheme for encryption is not recommended because the uniqueness of the root for a univariate polynomial is not guaranteed.

Kata Kunci : Ring polinomial Multivariat, Skema tanda tangan digital, Hidden Field Equation (HFE)