Tanda Tangan Prefix Puncturable dengan Kunci Penandatanganan Lebih Kecil dari HIBS

Tanda tangan puncturable, yang diperkenalkan oleh Bellare et al. pada EUROCRYPT 2016, memungkinkan kunci penandatanganan untuk dipunctured (diperbarui) sehingga kehilangan kemampuan menandatangani pesan tertentu sambil tetap mempertahankan kemampuan menandatangani pesan lainnya. Halevi et al. (ASIACRYPT 2017) memperkenalkan tanda tangan prefix puncturable, di mana kunci penandatanganan dapat dipunctured terhadap suatu prefix target sehingga tidak dapat menandatangani pesan yang prefix-nya cocok dengan prefix target.

Beberapa konstruksi generik skema tanda tangan prefix puncturable telah diusulkan, termasuk konstruksi berbasis identity-based signature (IBS) (ESORICS 2022) dan delegated constrained signature (IEEE Trans. Inf. Forensics Secure. 2024). Namun, konstruksi-konstruksi tersebut memiliki kelemahan dalam hal ukuran kunci. Ketika ruang prefix adalah himpunan semua string $l$-bit, konstruksi pertama memerlukan kunci penandatanganan yang terdiri dari $2^l$ kunci penandatanganan IBS. Konstruksi kedua, ketika diinstansiasi dengan skema delegated constrained signature berbasis lattice, menghasilkan kunci penandatanganan terpunctured yang ukurannya tumbuh kuadratik terhadap jumla

Hasil utamanya adalah konstruksi generik tanda tangan prefix puncturable dari HIBS dengan ukuran kunci penandatanganan yang jauh lebih kecil. Secara spesifik, untuk ruang prefix $\{0,1{\}}^l$, ukuran kunci penandatanganan terpunctured dibatasi oleh $O(l{Q}^{\text{Punc}})$, di mana $Q^{\text{Punc}}$ adalah jumlah operasi puncturing.

Hal ini meningkatkan konstruksi sebelumnya:

- Konstruksi berbasis IBS (ESORICS 2022) memerlukan kunci penandatanganan berukuran $2^l$ kunci penandatanganan IBS, yang eksponensial terhadap panjang prefix.
- Konstruksi delegated constrained signature (IEEE Trans. Inf. Forensics Secure. 2024), ketika diinstansiasi dengan skema berbasis lattice, menghasilkan kunci penandatanganan terpunctured yang ukurannya tumbuh kuadratik terhadap $Q^{\text{Punc}}$, yaitu $O((Q^{\text{Punc}}{)}^2)$.

Sebaliknya, konstruksi berbasis HIBS yang diusulkan mencapai pertumbuhan linear baik pada $l$ maupun $Q^{\text{Punc}}$. Ketika diinstansiasi dengan HIBS${}^{\text{GPV}}$, skema ini tetap aman di bawah asumsi lattice standar dan aman pasca-kuantum.

Makalah ini memberikan bukti keamanan formal yang menunjukkan bahwa skema tanda tangan prefix puncturable yang dibangun bersifat exi