Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
Constraints and Evaluations on Signature Transmission Interval for Aggregate Signatures with Interactive Tracing Functionality
Membuka akses
Kekangan dan Penilaian pada Selang Penghantaran Tandatangan untuk Tandatangan Agregat dengan Fungsi Pengesanan Interaktif

Ryu ISHII, Kyosuke YAMASHITA, Zihao SONG, Yusuke SAKAI, Tadanori TERUYA, Takahiro MATSUDA, Goichiro HANAOKA, Kanta MATSUURA, Tsutomu MATSUMOTO

  • pandangan teks lengkap

    549

  • Petikan Ini
  • Free PDF (2.9MB)

Ringkasan:

Tandatangan agregat toleran kesalahan (FT-AS) ialah jenis tandatangan agregat khas yang dilengkapi dengan fungsi untuk mengesan penandatangan yang menghasilkan tandatangan tidak sah sekiranya tandatangan agregat dikesan sebagai tidak sah. Dalam skim FT-AS sedia ada (yang fungsi pengesanannya memerlukan berbilang pusingan), pengesah perlu menghantar maklum balas kepada pengagregat untuk mengesan penandatangan yang tidak sah dengan cekap. Walau bagaimanapun, dalam amalan, jika maklum balas ini tidak dijawab kepada agregator dengan cara yang cukup pantas dan tepat pada masanya, proses pengesanan akan gagal. Oleh itu, adalah penting untuk menganggarkan sama ada maklum balas ini boleh dijawab dan diterima tepat pada masanya pada sistem sebenar. Dalam kerja ini, kami mengukur jumlah masa pemprosesan yang diperlukan untuk maklum balas dengan melaksanakan skim FT-AS sedia ada, dan menilai sama ada skim itu berfungsi tanpa masalah dalam sistem sebenar. Keputusan percubaan kami menunjukkan bahawa masa yang diperlukan untuk maklum balas ialah 605.3 ms untuk tetapan parameter biasa, yang menunjukkan bahawa jika masa maklum balas yang boleh diterima adalah lebih besar daripada beberapa ratus ms, skema FT-AS sedia ada akan berfungsi dengan berkesan dalam sistem sedemikian. Walau bagaimanapun, terdapat situasi di mana masa maklum balas sedemikian tidak boleh diterima, yang mana skim FT-AS sedia ada tidak boleh digunakan. Oleh itu, kami seterusnya mencadangkan skim FT-AS novel yang tidak memerlukan sebarang maklum balas. Kami juga melaksanakan skim baharu kami dan menunjukkan bahawa maklum balas dalam skim ini dihapuskan sepenuhnya tetapi saiz tandatangan agregatnya (menjejaskan kos komunikasi daripada pengagregat kepada pengesah) adalah 144.9 kali lebih besar daripada skim FT-AS sedia ada ( dengan maklum balas) untuk tetapan parameter biasa, dan dengan itu mempunyai pertukaran antara masa menunggu maklum balas dan kos komunikasi daripada pengesah kepada pengagregat dengan skim FT-AS sedia ada.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.4 pp.619-633
Tarikh penerbitan
2024/04/01
Diumumkan
2023/10/10
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2023SSP0002
Jenis Manuskrip
Special Section PAPER (Special Section on Information and Communication Technologies for Safe and Secure Life)
kategori

1. Pengenalan

Skim tandatangan agregat [2]-[5] ialah skema tandatangan di mana beberapa tandatangan boleh diagregatkan menjadi satu tandatangan agregat. Skim tandatangan agregat berpotensi membolehkan kami mengurangkan dengan ketara kos komunikasi dalam sistem maklumat di mana sejumlah besar data bertandatangan dihantar. Sebagai contoh, skim tandatangan agregat boleh digunakan untuk pemantauan hidup peranti di kilang. Katakan terdapat beribu-ribu peranti yang menghantar tandatangan mereka sendiri sebagai laporan kelangsungan hidup. Terima kasih kepada skim tandatangan agregat, beribu-ribu laporan boleh diagregatkan menjadi satu tandatangan agregat. Oleh itu, kilang boleh menghantar keseluruhan laporan kepada pusat pemantauan dengan menghantar tandatangan agregat, yang akan mengurangkan penggunaan lebar jalur secara drastik.

Di sini, bagaimanapun, masalah yang berpotensi ialah, jika tandatangan tidak sah terkandung dalam tandatangan agregat, maka keseluruhan laporan akan ditolak. Dalam kertas ini, kami memanggil penandatangan yang menjana tandatangan tidak sah penyangak penandatangan. Penandatangan penyangak boleh dilihat sebagai model penandatangan yang menjana tandatangan tidak sah secara berkemungkinan (disebabkan, contohnya, kegagalan peranti), atau penandatangan yang dirosakkan oleh pihak yang berniat jahat1. Pada pandangan pertama, nampaknya remeh untuk mengesan tandatangan tidak sah jika pengagregat mengesahkan tandatangan individu sebelum pengagregatan. Walau bagaimanapun, dalam amalan, agregator diandaikan sebagai peranti yang agak kecil pada laluan komunikasi, seperti peranti IoT, yang mempunyai saiz memori yang kecil dan sukar untuk mengesahkan banyak tandatangan dengan cukup pantas. Oleh itu, kami menganggap agregator ialah peranti kecil yang murah yang boleh mengagregat dengan pantas tetapi tidak dapat mengesahkan tandatangan individu dengan cukup pantas sebelum mengagregat atau menyimpan kesemuanya.

Untuk menyelesaikan masalah ini, Hartung et al. [6] cadangan Tandatangan Agregat Toleransi Kesalahan (pendek kata FT-AS) yang dilengkapi dengan fungsi untuk mengenal pasti penandatangan penyangak. Dalam skim FT-AS, pengagregat menyimpan sementara semua tandatangan yang belum diagregatkan dalam ingatannya, dan apabila tandatangan agregat yang tidak sah dikesan, ia mengenal pasti penandatangan penyangak dengan menggunakan kaedah gabungan seperti keluarga tanpa perlindungan [7 ]-[9], atau ujian kumpulan [10], [11]. Ambil perhatian bahawa skim ini lebih cekap daripada skim remeh kerana kaedah gabungan memerlukan pengiraan yang ringan dan lebih sedikit masa pengesahan daripada kaedah remeh. Masalah yang berpotensi dalam skim ini ialah pengagregat diperlukan untuk mempunyai memori yang agak besar yang boleh menyimpan semua tandatangan individu (bukan teragregat). Memandangkan pengagregat diandaikan sebagai peranti yang tidak berkuasa, tidak semestinya memori yang cukup besar itu tersedia untuk pengagregat. Oleh itu, berikutan [6], terdapat beberapa percubaan untuk mengurangkan saiz memori yang diperlukan untuk agregator dalam konteks FT-AS. Terutamanya, [12] menyiasat pendekatan untuk mengurangkan saiz ingatan agregator dengan memperkenalkan pengesanan berbilang pusingan [13]. Jenis khas FT-AS ini dipanggil tandatangan agregat dengan fungsi pengesanan interaktif (ASIT) dalam [12]. Seperti yang dinyatakan di atas, satu kemungkinan aplikasi FT-AS ialah pemantauan hidup peranti tepi di kilang, di mana setiap peranti tepi secara berkala menghantar tandatangan dan proses pengesanan untuk penandatangan penyangak dijalankan dengan menggunakan berbilang tandatangan agregat pada setiap tempoh masa. Dalam senario sedemikian, berbeza dengan tetapan pusingan tunggal, skema FT-AS dalam tetapan berbilang pusingan tidak mengenal pasti penandatangan penyangak dalam satu pelaksanaan fungsi pengesanan. Biasanya, ia berfungsi seperti berikut: Sebaik sahaja pengagregat menerima tandatangan individu, ia mengagregatkannya dengan mengikut beberapa cara yang telah ditetapkan (ditentukan oleh kaedah gabungan asas seperti Pengesanan Pengkhianat Dinamik (DTT) [14]), dan kemudian menghantar tandatangan agregat ke pengesah. Pengesah, apabila menerima tandatangan agregat, mengesahkannya untuk menentukan cara pengagregatan seterusnya (dengan menjalankan kaedah gabungan), dan menghantarnya kepada agregator sebagai maklum balas. Apabila pengagregat menerima tandatangan individu dalam tempoh masa seterusnya, ia mengagregatkannya berdasarkan cara yang ditentukan oleh maklum balas. Proses ini diulang sehingga semua penandatangan penyangak dikenal pasti.

Seperti yang dinyatakan di atas, dalam skim FT-AS berbilang pusingan sedia ada, pengesah menghantar maklum balas kepada pengagregat untuk mengesan penandatangan penyangak dengan cekap. Oleh itu, dalam sistem sebenar, maklum balas ini mesti dihantar dengan cara yang cukup pantas dan tepat pada masanya kepada agregator supaya agregator boleh meneruskan ke langkah seterusnya prosedur pengesanan dalam masa. Oleh itu, adalah penting untuk menyiasat sama ada maklum balas ini boleh dihantar dan diterima dengan pantas pada sistem sebenar, dan mungkin perlu untuk mempertimbangkan skim alternatif jika masa menunggu maklum balas tidak boleh diterima.

1.1 Sumbangan Kami

Untuk pengetahuan terbaik kami, skim FT-AS berbilang pusingan yang paling berkesan adalah yang dicadangkan oleh Ishii et al. [12]. (Dalam perkara berikut, kami merujuk skim ini sebagai AS-FT-2, mengikut penerangan dalam [12].) Sumbangan pertama kerja kami ialah kami mengukur jumlah masa pemprosesan yang diperlukan untuk maklum balas dengan melaksanakan AS-FT- 2. Untuk merealisasikan persekitaran dalam ruang siber yang sehampir mungkin dengan sistem sebenar, kami melaksanakan skim ini dalam persekitaran simulasi yang dibina pada Amazon Web Services (AWS). Kami mengukur prestasi algoritma dan mengetahui bahawa masa menunggu maklum balas adalah \(605.3\) ms secara purata dalam tetapan dengan bilangan penandatangan \(N=3000\) termasuk \(d=5\) penandatangan penyangak (yang mana kami mempunyai contoh kilang yang disebutkan di atas dalam fikiran). Masa menunggu maklum balas adalah berkadar asimptotik dengan \(N\). Ini menunjukkan bahawa dalam aplikasi yang masa maklum balas yang boleh diterima adalah jauh lebih besar daripada beberapa ratus ms, skema FT-AS sedia ada boleh digunakan tanpa masalah. Walau bagaimanapun, skim ini tidak boleh digunakan jika aplikasi memerlukan masa maklum balas yang lebih cepat. Sebagai contoh, keperluan purata untuk selang penghantaran dianggap sebagai \(5\) saat hingga satu jam [15], manakala dalam beberapa sistem komunikasi masa nyata, selang penghantaran data untuk sistem pengangkutan pintar koperasi dianggap sebagai \(200\) ms [16]. Skim sedia ada tidak akan sesuai untuk kes kedua.

Sumbangan kedua kami ialah kami mencadangkan varian baharu skim ASIT [12] yang tidak memerlukan maklum balas, dengan menjangkakan permohonan di mana masa menunggu maklum balas adalah lebih pendek supaya skim sedia ada tidak boleh digunakan. Idea di sebalik skim cadangan kami ialah kami membenarkan pengagregat memutuskan cara menjana tandatangan agregat terlebih dahulu. Lebih khusus lagi, skim kami menggunakan Sequential Traitor Tracing (STT) [17] sebagai fungsi pengesanan, bukannya DTT yang digunakan dalam skim ASIT sedia ada (lihat Bahagian 3 untuk butiran teknikal). Kami juga melaksanakan skim baharu kami, dan membandingkan prestasi dengan AS-FT-2. Percubaan mendedahkan bahawa skim baharu berjalan lebih pantas daripada skim sedia ada, tetapi memerlukan lebih banyak kos komunikasi (iaitu, lebar jalur untuk menghantar tandatangan agregat). Lihat Mazhab. 5 untuk perbincangan.

1.2 Implikasi Keputusan Kami: Skim yang Sesuai untuk Aplikasi Individu

Dalam subseksyen ini, kami membincangkan implikasi keputusan kami. Khususnya, kami menyediakan skim FT-AS berbilang pusingan khusus yang disyorkan untuk beberapa aplikasi. Kami menggambarkan ini dalam Rajah 1. Ambil perhatian bahawa ini ialah senarai skim disyorkan yang kelihatan paling sesuai, dan skim lain juga boleh digunakan untuk aplikasi yang sama. Di samping itu, apabila agregator adalah mencukupi berkuasa dari segi pengiraan atau saiz memori, kita boleh menggunakan kaedah remeh iaitu pengagregat mengesahkan semua tandatangan individu sebelum pengagregatan atau menyimpan semua tandatangan individu untuk mengesan tandatangan yang tidak sah. Jika agregator cukup kuat maka kita boleh menggunakan kaedah remeh ini. Oleh itu, kami hanya mempertimbangkan kes di mana pengagregat berkuasa sedemikian tidak tersedia.

Rajah 1  Peta skema yang paling sesuai dalam skema FT-AS berbilang pusingan sedia ada untuk rangkaian yang pengagregat mempunyai ingatan kecil dan kuasa pengiraan yang rendah.

Keputusan kami menunjukkan bahawa untuk aplikasi yang mempunyai kadar komunikasi tinggi (lebih daripada kira-kira 1 Mbps) tetapi kami perlu menghantar mesej baharu dalam masa nyata dengan selang kurang daripada 1 saat (rantau kiri-atas Rajah 1), skim cadangan kami (dibentangkan dalam Bahagian 4) adalah disyorkan. Aplikasi sedemikian termasuk, sebagai contoh, pemantauan lalu lintas.

Bagi aplikasi di mana kadar penghantaran adalah rendah (kira-kira 128 kbps) tetapi ia memadai untuk menghantar maklumat terkini pada selang masa yang agak panjang dalam beberapa saat atau lebih (rantau kanan-bawah Rajah 1), skema dalam [12]. ] dan [18] disyorkan2. Aplikasi sedemikian termasuk rangkaian sensor.

Untuk aplikasi di mana kadar komunikasi tinggi tersedia dan di mana ia mencukupi untuk menghantar mesej baharu pada selang masa yang agak panjang dalam beberapa saat atau lebih (rantau kanan atas Rajah 1), pelbagai skim FT-AS secara semula jadi boleh digunakan. Walau bagaimanapun, antara skim tersebut, kami mengesyorkan [12] dan [18] sebagai skim yang paling sesuai kerana saiz penghantaran datanya yang sangat kecil. Sudah tentu, AS-SW-1 (dibentangkan dalam Bahagian 4) juga boleh digunakan, tetapi memandangkan saiz data komunikasi AS-SW-1 jauh lebih besar daripada [12] dan [18], tidak ada merit tertentu. kecuali dapat menerima selang waktu yang singkat.

Untuk aplikasi di mana hanya kadar penghantaran rendah tersedia dan mesej terkini mesti dihantar dalam masa nyata pada selang masa kurang daripada 1 saat (rantau kiri-bawah Rajah 1), pada masa ini tiada skim yang disyorkan. Dalam keadaan sedemikian, jika perlu menggunakan skim FT-AS, satu-satunya cara ialah menggunakan kaedah remeh menggunakan berkuasa agregator seperti yang diterangkan di atas.

Ambil perhatian bahawa skim yang dicadangkan kami bukanlah yang terbaik untuk tetapan rangkaian yang dikekang masa sedemikian. Dakwaan kami ialah hanya skim kami yang boleh digunakan untuk beberapa rangkaian di mana skim sedia ada tidak diandaikan.

1.3 Kerja Berkaitan

Boneh et al. [2] mencadangkan skim tandatangan agregat pertama (bersama-sama dengan konsepnya sendiri), yang selamat dalam model oracle rawak dan berdasarkan tandatangan BLS [19] dalam kumpulan dengan peta bilinear yang boleh dikira dengan cekap. Hohenberger et al. [20] memberikan skema tandatangan agregat menggunakan peta berbilang linear dalam model standard. Skim ini boleh mengagregatkan tandatangan individu dan juga tandatangan yang telah diagregatkan dalam sebarang susunan.

Hartung et al. [6] mencadangkan skim tandatangan agregat toleran kesalahan. Dalam skim mereka, keluarga tanpa perlindungan [7]-[9], yang merupakan skim gabungan, digunakan untuk menentukan set tandatangan individu untuk diagregatkan. Beberapa karya [13], [18], [21] mencadangkan tandatangan agregat yang cekap dengan fungsi pengesanan berdasarkan ujian kumpulan [10], [11]. Skim ini terbukti selamat terhadap penyerang statik.

Terdapat jenis skim tandatangan agregat yang lain. Satu ialah tandatangan agregat berurutan, yang pertama kali dicadangkan oleh Lysyanskaya et al. [3] dan ditunjukkan selamat dalam model oracle rawak. Sejak itu, beberapa skema telah dicadangkan dalam model oracle rawak [3], [22], [23] dan dalam model standard [24], [25]. Jenis lain ialah tandatangan agregat dengan pengagregatan disegerakkan, yang pertama kali dicadangkan oleh Gentry dan Ramzan [4] (dalam tetapan berasaskan identiti) dan terbukti selamat dalam model oracle rawak. Sekali lagi, sejak itu, beberapa pembinaan telah dicadangkan dalam model oracle rawak [4], [5] dan dalam model standard [5].

1.4 Organisasi Kertas

Dalam Mazhab. 2, kami memperkenalkan tatatanda dan mengingat semula takrif ASIT. Dalam Mazhab. 3, kami menyemak skim ASIT AS-FT-2 oleh Ishii et al. [12], perhatikan masa menunggu maklum balas skim ini, dan berikan perbincangan mengenainya. Dalam Mazhab. 4, kami mencadangkan skim ASIT baharu, dipanggil AS-SW-1, yang tidak memerlukan maklum balas, berdasarkan STT. Dalam Mazhab. 5, kami menunjukkan keputusan eksperimen untuk skema yang dicadangkan dan membincangkan AS-FT-2 dan AS-SW-1 yang mana lebih sesuai untuk beberapa sistem rangkaian. Akhirnya, Sekt. 6 menyimpulkan kerja ini.

2. Pendahuluan

2.1 Notasi

Kami membiarkan \([n]\mathop{\mathrm{:=}}\{1,\ldots, n\}\). Kami menandakan rentetan kosong dengan \(\epsilon\), set kosong oleh \(\emptyset\), ruang mesej (skema tandatangan) oleh \(\mathop{\mathrm{\mathcal{M}}}\), polinomial tidak ditentukan oleh \(\mathsf{poly}(\cdot)\), fungsi boleh diabaikan yang tidak ditentukan oleh \(\mathop{\mathrm{\mathrm{negl}}}(\cdot)\), dan parameter keselamatan oleh \(\lambda\). PPT bermaksud masa polinomial probalistik. Kami berkata demikian \(P\) ialah partition bagi set \(U(\subseteq [n])\) jika ia memenuhi syarat berikut: \(P=(S_1, \ldots, S_p)\), \(p\in [|U|]\), \(S_1, \ldots, S_p \in 2^{U}\setminus \{\emptyset\}\), \(\bigcup_{i \in [p]} S_i = U\), dan \(S_i \cap S_j = \emptyset\) untuk semua \(i \neq j\) \((i, j \in [p])\).

2.2 Tandatangan Agregat

Di sini, kami mengingati tandatangan agregat biasa dan definisi keselamatannya. Dalam kertas ini, untuk memudahkan, kami berurusan dengan tandatangan agregat yang mengagregatkan hanya satu mesej dan pasangan tandatangan di bawah satu kunci pengesahan3.

Skim tandatangan agregat terdiri daripada lima algoritma PPT (KeyGen, Sign, Verify, Agg, AggVerify).

  • \((\mathop{\mathrm{\mathsf{pk}}}, \mathop{\mathrm{\mathsf{sk}}}) \leftarrow\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda)\): KeyGen ialah algoritma penjanaan kunci yang diperlukan \(1^\lambda\) sebagai input dan output sepasang \((\mathop{\mathrm{\mathsf{pk}}}, \mathop{\mathrm{\mathsf{sk}}})\) kunci awam dan rahsia.
  • \(\sigma \leftarrow\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}, m)\): Tanda ialah algoritma tandatangan yang mengambil kunci rahsia \(\mathop{\mathrm{\mathsf{sk}}}\) dan mesej \(m\in\mathop{\mathrm{\mathcal{M}}}\) sebagai input, dan mengeluarkan tandatangan \(\sigma\).
  • \(1 / 0 \leftarrow\mathop{\mathrm{\mathsf{Verify}}}(\mathop{\mathrm{\mathsf{pk}}}, m, \sigma)\): Sahkan ialah algoritma pengesahan (untuk tandatangan individu) yang mengambil kunci awam \(\mathop{\mathrm{\mathsf{pk}}}\), mesej \(m\), dan tandatangan \(\sigma\) sebagai input, dan output sama ada \(1\) \((\mathrm{valid})\) or \(0\) \((\mathrm{invalid})\).
  • \(\tau \leftarrow\mathop{\mathrm{\mathsf{Agg}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i, \sigma_i)\}_i)\): Agg ialah algoritma pengagregatan yang mengambil sebagai tuple input bagi kunci awam, mesej dan tandatangan, \(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i, \sigma_i)\}_i\). Ia kemudian mengeluarkan tandatangan agregat \(\tau\).
  • \(1 / 0 \leftarrow\mathop{\mathrm{\mathsf{AggVerify}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i,\tau)\): AggVerify ialah algoritma pengesahan (untuk tandatangan agregat) yang mengambil sebagai pasangan input kunci awam dan mesej \(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i\), dan tandatangan agregat \(\tau\). Ia kemudian mengeluarkan sama ada \(1\) \((\mathrm{valid})\) or \(0\) \((\mathrm{invalid})\).

2.1 Definisi (Ketepatan): Skim tandatangan agregat \(\Sigma_{\mathrm{AS}} = (\mathop{\mathrm{\mathsf{KeyGen}}}, \mathop{\mathrm{\mathsf{Sign}}}, \mathop{\mathrm{\mathsf{Verify}}}, \mathop{\mathrm{\mathsf{Agg}}}, \mathop{\mathrm{\mathsf{AggVerify}}})\) memenuhi ketepatan jika ada \(\lambda \in \mathbb{N}\), ada \(n = \mathsf{poly}(\lambda)\), dan mana-mana \(m_1, \ldots, m_n\in \mathop{\mathrm{\mathcal{M}}}\), ia memegang bahawa

\[\begin{aligned} &\Pr \left[\begin{array}{c} \, \\ 1 \leftarrow\mathop{\mathrm{\mathsf{AggVerify}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_{i\in [n]},\tau) \\ \, \\ \end{array} \middle| \right. \\ & \left. \begin{array}{l} \forall i \in [n], \, (\mathop{\mathrm{\mathsf{pk}}}_i, \mathop{\mathrm{\mathsf{sk}}}_i) \leftarrow\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda),\\ {\rm and} \, \sigma_i \leftarrow\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_i, m_i);\\ \tau \leftarrow\mathop{\mathrm{\mathsf{Agg}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i, \sigma_i)\}_{i\in [n]})\\ \end{array} \right] = 1. \end{aligned}\]

Untuk pemalsuan aganist keselamatan, kami menganggap keselamatan EUF-CMA (Existential UnForgeability against Chosen Message Attacks) dalam model di mana semua pasangan kunci dijana secara jujur ​​(model kunci jujur). Takrifan menangkap situasi di mana musuh, termasuk pengagregat, tidak boleh memalsukan pasangan tandatangan mesej yang sah dan baharu walaupun mereka memperoleh tandatangan sah dari penandatangan yang jujur.

Kami mentakrifkan keselamatan menggunakan percubaan di mana semua penandatangan dan pengagregat kecuali penandatangan pertama dianggap sebagai musuh, dan lawan menang jika ia berjaya memalsukan tandatangan agregat yang sah yang mengandungi penandatangan pertama. Pemerolehan tandatangan sah pihak lawan diwakili sebagai akses oracle.

2.2 Definisi (Keselamatan EUF-CMA): Skim tandatangan agregat \(\Sigma_{\mathrm{AS}} = (\mathop{\mathrm{\mathsf{KeyGen}}}, \mathop{\mathrm{\mathsf{Sign}}}, \mathop{\mathrm{\mathsf{Verify}}}, \mathop{\mathrm{\mathsf{Agg}}}, \mathop{\mathrm{\mathsf{AggVerify}}})\) memenuhi keselamatan EUF-CMA jika ada \(\lambda \in \mathbb{N}\), ada \(n = \mathsf{poly}(\lambda)\) dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), ia memegang bahawa \(\Pr\left[\mathop{\mathrm{\mathsf{ExpAS}}}_{\Sigma_{\mathrm{AS}}, \mathop{\mathrm{\mathcal{A}}}}^{EUF\text{-}CMA}(\lambda,n)=1\right] = \mathop{\mathrm{\mathrm{negl}}}(\lambda)\) di mana \(\mathop{\mathrm{\mathsf{ExpAS}}}_{\Sigma_{\mathrm{AS}}, \mathop{\mathrm{\mathcal{A}}}}^{EUF\text{-}CMA}(\lambda,n)\) ialah eksperimen berikut:

\[\begin{aligned} \begin{aligned} \begin{array}{@{}l@{}} \mathop{\mathrm{\mathsf{ExpAS}}}_{\Sigma_{\mathrm{AS}}, \mathop{\mathrm{\mathcal{A}}}}^{EUF\text{-}CMA}(\lambda,n)\\ \hline \forall i \in [n], \, (\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i)\leftarrow\Sigma_{\mathrm{AS}}.\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda); \\ Q \mathop{\mathrm{:=}}\emptyset;\\ (\{m_i\}_{i\in S}, \tau, S) \leftarrow \\ \ \ \mathop{\mathrm{\mathcal{A}}}^{\Sigma_{\mathrm{AS}}.\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_1, \cdot)}(\mathop{\mathrm{\mathsf{pk}}}_1, \{(\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i)\}_{i\in[n]\setminus \{1\}}) : \\ {\rm Output} \, 1 \, {\rm if} \, S \subseteq [n], \, 1 \in S, \, m_1 \notin Q \, {\rm and} \\ \Sigma_{\mathrm{AS}}.\mathop{\mathrm{\mathsf{AggVerify}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_{i \in S}, \tau)=1,\\ {\rm else \, output} \, 0 \end{array} \end{aligned} \end{aligned}\]

dimana bila \(\mathop{\mathrm{\mathcal{A}}}\) membuat pertanyaan \(m\in \mathop{\mathrm{\mathcal{M}}}\) kepada oracle yang menandatangani \(\Sigma_{\mathrm{AS}}.\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_1, \cdot)\), ia mengira \(\sigma \leftarrow \Sigma_{\mathrm{AS}}.\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_1, m)\), menghantar \(\sigma\) kepada \(\mathop{\mathrm{\mathcal{A}}}\), dan set \(Q\leftarrow Q\cup \{m\}\).

Ambil perhatian bahawa dalam percubaan, indeks pengguna \(1\) digunakan sebagai pengguna cabaran, yang kunci rahsianya tidak diketahui oleh musuh, dan kunci yang tinggal \((\mathop{\mathrm{\mathsf{pk}}}_i, \mathop{\mathrm{\mathsf{sk}}}_i)_{i \in [n] \setminus \{1\}}\) diberikan secara langsung kepada \(\mathop{\mathrm{\mathcal{A}}}\). Oleh itu, oracle menandatangani disediakan hanya untuk indeks \(1\).

2.3 Tandatangan Agregat dengan Fungsi Pengesanan Interaktif

Di sini kita ingat takrif formal untuk skema tandatangan agregat dengan fungsi pengesanan interaktif (ASIT) dalam bentuk yang diberikan dalam [12]. Dalam Takrif 2.3, \(\mathop{\mathrm{\mathsf{Trace}}}\) ialah algoritma untuk mengesan musuh daripada tandatangan agregat yang tidak sah dan menjana partition set penandatangan, dan \(\mathop{\mathrm{\mathsf{PartVerify}}}\) ialah algoritma untuk mengesahkan tandatangan agregat yang mengandungi penandatangan tertentu.

2.3 Definisi (ASIT): Skim ASIT terdiri daripada algoritma PPT \((\mathsf{KeyGen}\), \(\mathsf{Sign}\), \(\mathsf{Agg}\), \(\mathsf{Verify}\), \(\mathsf{PartVerify}\), \(\mathsf{Trace})\) kerja itu seperti berikut.

  • \((\mathop{\mathrm{\mathsf{pk}}}, \mathop{\mathrm{\mathsf{sk}}}) \leftarrow\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda)\): \(\mathsf{KeyGen}\) adalah algoritma penjanaan utama yang mengambil \(1^\lambda\) sebagai input dan output sepasang \((\mathop{\mathrm{\mathsf{pk}}}, \mathop{\mathrm{\mathsf{sk}}})\) kunci awam dan rahsia.
  • \(\sigma \leftarrow\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}, m)\): \(\mathsf{Sign}\) ialah algoritma tandatangan yang mengambil kunci rahsia \(\mathop{\mathrm{\mathsf{sk}}}\) dan mesej \(m\in\mathop{\mathrm{\mathcal{M}}}\) sebagai input, dan mengeluarkan tandatangan \(\sigma\).
  • \(1 / 0 \leftarrow\mathop{\mathrm{\mathsf{Verify}}}(\mathop{\mathrm{\mathsf{pk}}}, m, \sigma)\): \(\mathsf{Verify}\) ialah algoritma pengesahan (untuk tandatangan individu) yang mengambil kunci awam \(\mathop{\mathrm{\mathsf{pk}}}\), mesej \(m\), dan tandatangan \(\sigma\) sebagai input, dan output sama ada \(1\) \((\mathrm{valid})\) or \(0\) \((\mathrm{invalid})\).
  • \(\tau \leftarrow\mathop{\mathrm{\mathsf{Agg}}}(f,\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i, \sigma_i)\}_i)\): \(\mathsf{Agg}\) ialah algoritma penjumlahan yang mengambil maklum balas sebagai input \(f\) daripada pengesah dan tupel kunci awam, mesej dan tandatangan \(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i, \sigma_i)\}_i\) sebagai input. Ia kemudian mengeluarkan tandatangan agregat \(\tau\).
  • \(1 / 0 \leftarrow\mathop{\mathrm{\mathsf{PartVerify}}}(\beta, \{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i, \tau, j)\): \(\mathsf{PartVerify}\) ialah algoritma pengesahan separa yang mengambil sebagai input keadaan dalaman pengesah \(\beta\), pasangan kunci awam dan mesej \(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i\), tandatangan agregat \(\tau\), dan indeks pengguna sasaran \(j\). Ia kemudian mengeluarkan sama ada \(1\) \((\mathrm{valid})\) or \(0\) \((\mathrm{invalid})\).
  • \((\beta', f, V) \leftarrow\mathop{\mathrm{\mathsf{Trace}}}(\beta, \{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i, \tau)\): \(\mathsf{Trace}\) ialah algoritma pengesanan yang mengambil sebagai input keadaan dalaman pengesah \(\beta\), pasangan kunci awam dan mesej \(\{(\mathop{\mathrm{\mathsf{pk}}}_i, m_i)\}_i\), dan tandatangan agregat \(\tau\). Ia kemudian mengeluarkan tupel \((\beta', f, V)\) di mana \(\beta'\) ialah keadaan dalaman pengesah dalam pusingan seterusnya, \(f\) adalah maklum balas, dan \(V\) ialah set pengguna yang dikesan. Ia dikehendaki bahawa maklum balas \(f\) dan set pengguna yang dikesan \(V\) boleh diambil secara unik dari keadaan dalaman \(\beta'\).

Perhatikan bahawa \(\mathop{\mathrm{\mathsf{PartVerify}}}\) bukan sebahagian daripada operasi sebenar pengagregat atau pengesah tetapi diperkenalkan untuk ringkasan keselamatan EUF-CMA ASIT.

Kami juga membentangkan ketepatan \(\mathop{\mathrm{\mathsf{Trace}}}\) and \(\mathop{\mathrm{\mathsf{PartVerify}}}\) sebagai keperluan fungsi algoritma ASIT. Ketepatan daripada \(\mathop{\mathrm{\mathsf{Trace}}}\) mewakili bahawa mana-mana penandatangan tidak dikesan oleh \(\mathop{\mathrm{\mathsf{Trace}}}\) algoritma dalam mana-mana pusingan jika semua pengguna mengikuti algoritma ASIT.

2.4 Definisi (Ketepatan daripada \(\mathop{\mathrm{\mathsf{Trace}}}\)): Biarlah \(\Sigma_{\mathrm{ASIT}}\) menjadi skim ASIT. Algoritma \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Trace}}}\) memenuhi ketepatan jika ada \(\lambda \in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), ada \(t\in \mathbb{N}\), dan mana-mana \(m_1, \ldots, m_n \in \mathcal{M}\), ia memegang bahawa \(\Pr[V_t=\emptyset] = 1\) di mana \(V_t\) ialah nilai dalam eksperimen \(\mathop{\mathrm{\mathsf{ExpASIT}}}^{\mathrm{Trace}}_{\Sigma_{\mathrm{ASIT}}}(\lambda, n, \{m_i\}_{i \in [n]})\) diterangkan dalam Rajah 2 (kiri).

Rajah 2  Percubaan yang digunakan untuk mentakrifkan ketepatan skim ASIT.

Ketepatan daripada \(\mathop{\mathrm{\mathsf{PartVerify}}}\) mewakili bahawa jika semua pengguna mengikuti algoritma ASIT, \(\mathop{\mathrm{\mathsf{PartVerify}}}\) algoritma boleh menunjukkan ketepatan tandatangan agregat termasuk pengguna tertentu.

2.5 Definisi (Ketepatan daripada \(\mathop{\mathrm{\mathsf{PartVerify}}}\)): Biarlah \(\Sigma_{\mathrm{ASIT}}\) menjadi skim ASIT. Algoritma \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{PartVerify}}}\) memenuhi ketepatan jika ada \(\lambda\in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), sebarang bentuk keadaan dalaman yang mungkin \(\beta\), ada \(j \in [n]\), dan mana-mana \(m_1, \ldots, m_n \in \mathcal{M}\), ia memegang bahawa \(\Pr[v=1] = 1\) di mana \(v\) adalah keluaran eksperimen \(\mathop{\mathrm{\mathsf{ExpASIT}}}^{\mathrm{PartVrf}}_{\Sigma_{\mathrm{ASIT}}}(\lambda, n, \beta, j, \{m_i\}_{i \in [n]})\) diterangkan dalam Rajah 2 (kanan).

2.3.1 Keselamatan EUF-CMA

Kami menarik balik keselamatan EUF-CMA untuk ASIT [12]. Keselamatan EUF-CMA untuk ASIT juga ditakrifkan serta keselamatan EUF-CMA untuk tandatangan agregat standard yang kami bentangkan dalam Sekt. 2.2. Keselamatan EUF-CMA untuk ASIT menangkap situasi di mana musuh, termasuk agregator, tidak boleh memalsukan pasangan tandatangan mesej yang sah dan baharu walaupun mereka memperoleh tandatangan sah dari penandatangan yang jujur. Dalam eksperimen Takrif 2.6, \(O_S\) ialah oracle tandatangan, dan \(O_V\) ialah oracle pengesahan, yang mengesahkan sama ada tandatangan yang dijana oleh musuh yang tidak dikesan adalah tandatangan sah yang mengandungi penandatangan pertama, iaitu, sama ada pemalsuan tandatangan berjaya. Jika berjaya, lawan menang, dan permainan berhenti; jika tidak, algoritma pengesanan dilaksanakan.

Definisi 2.6: Skim ASIT \(\Sigma_{\mathrm{ASIT}}\) memenuhi keselamatan EUF-CMA jika ada \(\lambda \in \mathbb{N}\), ada \(n = \mathsf{poly}(\lambda)\), dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), ia memegang bahawa \(\Pr[\mathop{\mathrm{\mathsf{ExpASIT}}}_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}^{\mathrm{EUF\text{-}CMA}}(\lambda,n)=1]=\mathop{\mathrm{\mathrm{negl}}}(\lambda)\) di mana \(\mathop{\mathrm{\mathsf{ExpASIT}}}_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}^{\mathrm{EUF\text{-}CMA}}\) ialah eksperimen berikut.

\[\begin{aligned} \begin{aligned} \begin{array}{@{}l@{}} \mathop{\mathrm{\mathsf{ExpASIT}}}^{\mathrm{EUF\text{-}CMA}}_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda, n) \\ \hline \forall i \in [n], (\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i) \leftarrow\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda);\\ t\mathop{\mathrm{:=}}1; Q \mathop{\mathrm{:=}}\emptyset; W_1 \mathop{\mathrm{:=}}\emptyset;\\ {\rm run} \, \mathop{\mathrm{\mathcal{A}}}^{O_S(\cdot), O_V(\cdot)}(\mathop{\mathrm{\mathsf{pk}}}_1, \{(\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i)\}_{i\in[n]\setminus \{1\}}) : \\ {\rm Output} \, 0 \, {\rm when} \, \mathop{\mathrm{\mathcal{A}}}\, {\rm halts} \end{array} \end{aligned} \end{aligned}\]

di mana \(\mathop{\mathrm{\mathcal{A}}}\) boleh berhenti pada titik sewenang-wenangnya, \(\mathop{\mathrm{\mathcal{A}}}\) dibenarkan membuat sewenang-wenangnya (polinomial) banyak pertanyaan kepada oracle yang menandatangani \(O_S\) dan oracle pengesahan \(O_V\), yang berfungsi seperti berikut:

  • \(O_S\): Diberi pertanyaan \(m\in \mathop{\mathrm{\mathcal{M}}}\) dari \(\mathop{\mathrm{\mathcal{A}}}\), \(O_S\) berjalan \(\sigma\leftarrow \Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_1,m)\), kembali \(\sigma\) kepada \(\mathop{\mathrm{\mathcal{A}}}\), dan kemas kini \(Q \leftarrow Q \cup \{m\}\).
  • \(O_V\): Diberi pasangan indeks dan mesej \(\{(i, m_{i, t})\}_{i\in I_t}\) dan tandatangan agregat \(\tau\) dari \(\mathop{\mathrm{\mathcal{A}}}\), \(O_V\) output \(1\) (menunjukkan bahawa \(\mathop{\mathrm{\mathcal{A}}}\) menang) dan menamatkan percubaan jika ia memegangnya \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{PartVerify}}}(\beta_t, \{(\mathop{\mathrm{\mathsf{pk}}}_i, m_{i, t})\}_{i\in I_t},\tau_t, 1)=1\), \(1\notin W_t\), dan \(m_{1,t}\notin Q\). Jika tidak, \(O_V\) dilaksanakan \((\beta_{t+1}, f_t, V_t)\) \(\leftarrow \Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Trace}}}(\beta_t, \{(\mathop{\mathrm{\mathsf{pk}}}_i, m_{i,t})\}_{i\in I_t}, \tau_t)\), kembali \((f_t, V_t)\) kepada \(\mathop{\mathrm{\mathcal{A}}}\), dan kemas kini \(W_t = W_t \cup V_t\) and \(t\leftarrow t+1\).

Ambil perhatian bahawa indeks pengguna \(1\) dianggap sebagai pengguna cabaran, dan musuh diberikan kunci rahsia untuk pengguna yang tinggal dengan indeks \(2\) kepada \(n\), dan oleh itu oracle menandatangani hanya diperlukan untuk indeks pengguna \(1\). Perhatikan juga bahawa percubaan boleh mengeluarkan \(1\) hanya jika \(\mathop{\mathrm{\mathcal{A}}}\) membuat \(O_V\)-pertanyaan yang mengandungi tandatangan palsu berkenaan dengan indeks pengguna 1 (dinilai menggunakan algoritma \(\mathop{\mathrm{\mathsf{PartVerify}}}\)).

2.3.2  \(R\)-Pengenalpastian dan Ketepatan

Kami ingat \(R\)-pengenalpastian dan ketepatan skim ASIT \(\Sigma_{\mathrm{ASIT}}\). \(R\)-pengenalpastian menjamin bahawa pengesah boleh mengenal pasti semua penandatangan penyangak dalam \(R\) pusingan pelaksanaan prosedur pengesanan. Musuh yang berpotensi dalam tanggapan keselamatan ini ialah sekumpulan pengguna \(C \subseteq [n]\) yang mungkin menjana tandatangan tidak sah. Sebaliknya, ketepatan menjamin bahawa tiada penandatangan yang jujur ​​akan dikesan. Ambil perhatian bahawa pengagregat dan pengesah berkelakuan jujur. Tanggapan keselamatan ini ditakrifkan berdasarkan eksperimen berikut \(\mathop{\mathrm{\mathsf{ExpASIT}}}_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda,n)\) di mana musuh bernegara \(\mathop{\mathrm{\mathcal{A}}}\) dilaksanakan:

\[\begin{aligned} \begin{aligned} \begin{array}{@{}l@{}} \mathop{\mathrm{\mathsf{ExpASIT}}}_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda, n) \\ \hline \forall i \in [n], (\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i) \leftarrow\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{KeyGen}}}(1^\lambda);\\ C \leftarrow\mathop{\mathrm{\mathcal{A}}}(\{(\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i)\}_{i\in[n]}); \\ t\mathop{\mathrm{:=}}1; r\mathop{\mathrm{:=}}0; W_1\mathop{\mathrm{:=}}\emptyset; \beta_1\mathop{\mathrm{:=}}\epsilon; f_0\mathop{\mathrm{:=}}\epsilon; I_1 \mathop{\mathrm{:=}}[n]; J_1 \mathop{\mathrm{:=}}C;\\ {\rm run} \, \mathop{\mathrm{\mathcal{A}}}^{O_T(\cdot)}(\{(\mathop{\mathrm{\mathsf{pk}}}_i,\mathop{\mathrm{\mathsf{sk}}}_i)\}_{i\in[n]}) : \\ {\rm Output} \, (W := \bigcup_{t' = 1}^t V_{t'}, C, r) \, {\rm when} \, \mathop{\mathrm{\mathcal{A}}}\, {\rm halts} \end{array} \end{aligned} \end{aligned}\]

di mana \(\mathop{\mathrm{\mathcal{A}}}\) boleh berhenti pada titik sewenang-wenangnya, dan \(\mathop{\mathrm{\mathcal{A}}}\) dibenarkan membuat secara sewenang-wenangnya (polinomial) banyak pertanyaan kepada oracle pengesanan \(O_T\). Biarkan \(W_t := \bigcup_{t' =1}^t V_t\), \(I_t := [n] \backslash W_t\), dan \(J_t := C \setminus W_t\). Diberi pertanyaan \((\{m_{i,t}\}_{i \in I_t},\{(m_{j,t},\sigma_{j,t})\}_{j\in J_t})\) dari \(\mathop{\mathrm{\mathcal{A}}}\), \(O_T\) beroperasi seperti berikut:

  1. Jika ada \(j\in J_t\) seperti itu \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Verify}}}(\mathop{\mathrm{\mathsf{pk}}}_j,m_{j,t}\), \(\sigma_{j,t})\) \(=0\), kemudian tetapkan \(r\leftarrow r+1\).
  2. Untuk setiap \(i\in I_t\), pengiraan \(\sigma_{i,t} \leftarrow \Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Sign}}}(\mathop{\mathrm{\mathsf{sk}}}_{i},m_{i,t})\).
  3. Kirakan\(\tau_t \leftarrow \Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Agg}}}(f_{t-1},\{(\mathop{\mathrm{\mathsf{pk}}}_i,m_{i,t},\sigma_{i,t})\}_{i\in I_t\cup J_t})\).
  4. Kirakan\((\beta_{t+1}, f_t, V_t)\) \(\leftarrow \Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Trace}}}(\beta_t, \{(\mathop{\mathrm{\mathsf{pk}}}_i, m_{i,t})\}_{i\in I_t\cup J_t}, \tau_t)\).
  5. Pulangkan \((f_t, V_t)\) kepada \(\mathop{\mathrm{\mathcal{A}}}\) dan tetapkan \(t \leftarrow t+1\).

Kami mentakrifkan \(R\)-pengenalpastian dan ketepatan ASIT seperti berikut.

2.7 Definisi (\(R\)-Kebolehcaman): Skim ASIT \(\Sigma_{\mathrm{ASIT}}\) memuaskan \(R\)-boleh dikenal pasti jika ada \(\lambda \in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), kita ada

\[\begin{aligned} \Pr&[(C\not\subseteq W) \, | \, (W, C, r) \\ &\leftarrow\mathop{\mathrm{\mathsf{ExpASIT}}}\nolimits_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda, n) \land (r \geq R)] = \mathop{\mathrm{\mathrm{negl}}}(\lambda). \end{aligned}\]

2.8 Definisi (Ketepatan): Skim ASIT \(\Sigma_{\mathrm{ASIT}}\) memenuhi ketepatan jika kedua-duanya \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{Trace}}}\) and \(\Sigma_{\mathrm{ASIT}}.\mathop{\mathrm{\mathsf{PartVerify}}}\) memenuhi ketepatan, dan untuk mana-mana \(\lambda \in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), kita ada

\[\begin{aligned} \Pr&[([n]\backslash C)\cap W \neq \emptyset \, | \, (W, C, r) \\ &\leftarrow\mathop{\mathrm{\mathsf{ExpASIT}}}\nolimits_{\Sigma_{\mathrm{ASIT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda, n)] = \mathop{\mathrm{\mathrm{negl}}}(\lambda). \end{aligned}\]

3. Masa Menunggu Maklum Balas di ASIT

Bahagian ini membentangkan sumbangan pertama kami. Ingat bahawa, seperti yang dibincangkan dalam Sekt. 1, masa menunggu maklum balas bagi skim FT-AS berbilang pusingan boleh menjadi kritikal jika kita menggunakannya dalam amalan. Oleh itu, di sini kami menilai masa menunggu maklum balas bagi instantiasi konkrit ASIT. Lebih khusus lagi, kami menilai instantiasi ASIT dalam [12], yang dibina daripada skema tandatangan agregat biasa dan DTT. Dalam Mazhab. 3.1, kami memperkenalkan instantiasi konkrit FT-2 DTT yang dicadangkan oleh Fiat dan Tassa [14], dan skim ASIT yang dicadangkan oleh Ishii et al. [12] yang berdasarkan skim tandatangan agregat dan FT-2. Kami menyemak definisi rasmi DTT yang diformalkan oleh Ishii et al. [12] dalam Lampiran A. Dalam Sek. 3.2, kami menilai masa menunggu maklum balas skim ASIT. Kami menyatakan bahawa ini adalah hasil percubaan pertama untuk skim ASIT, kerana [12] hanya mencadangkan skim tersebut.

3.1 Instalasi Sedia Ada DTT dan ASIT

DTT ialah kaedah untuk mengesan cetak rompak dalam perkhidmatan pengedaran kandungan, yang berfungsi seperti berikut: Pengguna dibahagikan kepada beberapa subkumpulan, dan untuk setiap subkumpulan kandungan dengan tera air yang unik diedarkan. Setelah cetak rompak ditemui, pengedar kandungan menyemak tera air, membahagikan subkumpulan yang sepadan kepada subkumpulan yang lebih kecil dan mengulangi prosedur ini sehingga ia mengesan cetak rompak. Kami merujuk kepada selang antara pelaksanaan pengesanan sebagai 1 keliling. Fiat dan Tassa [14] mencadangkan dua DTT, dan kami ingat salah satu daripadanya.

Rajah 3 menggambarkan instantiasi DTT yang dicadangkan dalam [14], dinamakan FT-2. FT-2 ialah kaedah untuk mengesan pengkhianat dalam satu set pengguna yang serupa dengan carian binari. Pada mulanya, semua pengguna dimasukkan ke dalam set \(I\) (mewakili tidak bersalah), yang dibahagikan kepada \(L_j\) and \(R_j\) apabila cetak rompak dikesan. Kemudian dalam pusingan seterusnya, apabila cetak rompak ditemui dari \(L_j\) (Atau \(R_j\)), \(L_j\) (Atau \(R_j\)) terbahagi kepada dua. Proses ini diulang sehingga musuh diasingkan. Adalah diketahui bahawa FT-2 mengesan semua pengkhianat \(d(\log_2 N + 1)\) pusingan, di mana bilangan penandatangan adalah \(N\) dan bilangan pengkhianat adalah \(d\).

Rajah 3  Penerangan mengenai DTT (FT-2) oleh Fiat dan Tassa [14] dan subrutin \(\mathsf{Halve}\) digunakan dalam skema.

Kami ingat skim ASIT yang dicadangkan oleh Ishii et al. [12]. Idea di sebalik fungsi pengesanan skim ini adalah untuk menganggap penandatangan penyangak sebagai lanun, dan menjalankan FT-2 untuk mengesan mereka. Rajah 4 menggambarkan skema ASIT \(\Sigma_{\mathrm{ASIT}}\) berdasarkan skim tandatangan agregat \(\Sigma_{\mathrm{AS}}\) dan DTT FT-2 \(\Sigma_{\mathrm{DTT}}\). Kami memanggil instantiasi ini sebagai AS-FT-2. Untuk AS-FT-2, pengagregat mengagregat semua tandatangan individu menjadi tandatangan agregat pada pusingan pertama. Pengesah mengesahkannya, dan jika ia tidak sah, itu \(\mathop{\mathrm{\mathsf{Trace}}}\) algoritma FT-2 dijalankan untuk menghasilkan partition seterusnya. Pembahagian ini dihantar sebagai maklum balas kepada pengagregat. Dalam pusingan seterusnya, pengagregatan dilakukan secara bahagian demi bahagian mengikut pembahagian dalam maklum balas. Khususnya, bagi setiap subset individu dibahagikan dengan partition, hanya tandatangan dalam subset yang sama diagregatkan (iaitu, bilangan tandatangan agregat yang dijana oleh agregator adalah sebanyak bilangan subset). Kemudian pengesah mengesahkan tandatangan dan jika ia mendapati yang tidak sah, ia menjalankan \(\mathop{\mathrm{\mathsf{Trace}}}\) algoritma. Proses ini diulang sehingga semua penandatangan yang tidak sah dikesan.

Rajah 4  Instalasi itu \(\Sigma_{\mathrm{ASIT}}\) daripada skim ASIT berdasarkan skim tandatangan agregat \(\Sigma_{\mathrm{AS}}\) dan FT-2 \(\Sigma_{\mathrm{DTT}}\) oleh [12]. \({}^{(\dagger)}\) Perintah ini keluar Untuk dan bergerak ke baris seterusnya.

3.2 Penilaian Masa Menunggu Maklum Balas AS-FT-2

Kami menilai masa menunggu maklum balas AS-FT-2, menerangkan eksperimen pelaksanaan AS-FT-2 secara terperinci dan membentangkan hasilnya. Kami juga membincangkan sama ada masa menunggu maklum balas memenuhi keperluan untuk beberapa aplikasi.

3.2.1 Persekitaran Eksperimen

Kami menggunakan simulator yang dilaksanakan menggunakan Amazon Web Service (AWS) yang ditunjukkan dalam [26]. Untuk peranti, kami menggunakan empat contoh Amazon EC2, yang merupakan peranti maya yang disediakan oleh AWS. Jenis tika EC2 adalah semua t3.micro (pemproses Boleh Skala Intel Xeon 3.1 GHz, prestasi garis dasar setiap CPU maya: 10%, CPU maya: 2, memori: 1 GiB, lebar jalur maksimum: 5 Gbps, jalur lebar garis dasar: 87 Mbps). Empat kejadian ini diuruskan oleh Amazon Elastic Kubernetes Service (EKS) seperti yang ditunjukkan dalam Rajah 5 dan setiap daripadanya mempunyai imej bekas, yang terdiri daripada alpine Linux 3.15 (terkini) sebagai OS dan g++ 10.3.1 sebagai versi C++.

Rajah 5  Konfigurasi peranti dalam kelompok. Nod yang sah dihantar \(N-d\) tandatangan yang sah dan nod penandatangan penyangak menghantar \(d\) tandatangan tidak sah dalam setiap pusingan, di mana \(N\) ialah bilangan semua penandatangan dan \(d\) ialah bilangan penandatangan penyangak.

3.2.2 Tetapan Eksperimen

Kami menangkap situasi di mana beberapa penandatangan penyangak tetap di kalangan ramai penandatangan sentiasa menghantar tandatangan tidak sah. Jumlah \(N\) daripada semua penandatangan dan nombor \(d\) penandatangan penyangak adalah \(N=1000\), \(3000\), dan \(d=5, 10, 40\), masing-masing. Tetapan parameter ini adalah berdasarkan [27], yang berkaitan dengan mengenal pasti nod penderia yang gagal dihantar dalam rangkaian penderia. Ia menganggap tetapan rangkaian serupa dengan kami di mana sejumlah besar (\(1000\)-\(3000\)) nod sensor menghantar data dan beberapa nod yang rosak disertakan. Setiap penandatangan jujur/penyangak menghantar sepasang a \(128\)-Mesej bait dan tandatangan kepada pengagregat. Untuk skim tandatangan agregat asas, kami melaksanakan skim tandatangan agregat BGLS [2] dengan menggunakan perpustakaan kriptografi berpasangan mcl [28] dan BN254 [29] untuk lengkung eliptik. Eksperimen dijalankan \(10\) kali dan purata diambil.

3.2.3 Keputusan Eksperimen

Jadual 1 menunjukkan keputusan simulasi AS-FT-2 di bawah keadaan eksperimen yang diterangkan di atas. Perhatikan bahawa masa pelaksanaan pengesanan menduduki nisbah besar masa menunggu maklum balas, yang semakin meningkat apabila \(N\) menjadi besar. Ini kerana pengesah memerlukan \(N+1\) operasi berpasangan dan operasi berpasangan mengambil masa yang lebih lama daripada operasi kumpulan lain dalam instantiasi kami4. Kami melihat bahawa masa pelaksanaan pengesanan menjadi kurang seperti \(d\) bertambah. Dalam percubaan ini, setiap penandatangan penyangak sentiasa menghantar tandatangan yang tidak sah, jadi sekurang-kurangnya satu daripada pemisahan daripada dua termasuk penandatangan penyangak dan tandatangan yang tidak sah boleh ditemui dalam dua kali pengesahan. Selain itu, apabila \(d\) adalah besar, bilangan partition set dalam pengesanan juga besar dan bilangan tandatangan dalam setiap set menjadi kecil, maka bilangan operasi berpasangan yang dilaksanakan untuk mencari tandatangan agregat yang tidak sah menjadi kecil5.

Jadual 1  Keputusan simulasi AS-FT-2. Trace ialah purata masa pelaksanaan algoritma pengesanan, dan Maklum Balas ialah masa purata dari masa pengagregat menjana tandatangan agregat hingga masa pengesah mengembalikan maklum balas. Saiz maklum balas setiap pusingan apabila \(N=1000\), \(3000\) adalah \(3.9\) kilobait dan \(11.9\) kilobait masing-masing.

Untuk lajur Maklum Balas, menjadi jelas bahawa apabila \((N,d)=(1000,5)\), \((3000,5)\), pengagregat perlu menunggu secara purata \(233.3\) Cik, \(605.3\) ms, masing-masing, dan setiap penandatangan perlu mempunyai selang penghantaran lebih lama daripada ini. Perbezaan masa lajur Trace and Maklum Balas adalah disebabkan oleh kelewatan komunikasi kepada agregator sebagai tambahan kepada masa pengesanan.

3.2.4 Masa Menunggu Maklum Balas Yang Boleh Diterima

Kami mempertimbangkan sama ada masa menunggu maklum balas AS-FT-2 boleh diterima atau tidak untuk keperluan selang penghantaran data bagi sistem komunikasi masa yang kurang terhad atau masa nyata. Kami juga mempertimbangkan sama ada AS-FT-2 boleh digunakan atau tidak dalam sistem rangkaian ini.

Dalam sistem komunikasi yang kurang terhad masa seperti rangkaian penderia pemantauan, menurut [15], untuk mengurangkan penggunaan kuasa dan meningkatkan jangka hayat nod, keperluan purata untuk selang penghantaran dianggap sebagai \(5\) saat hingga satu jam. Daripada keperluan ini dan Jadual 1, masa menunggu maklum balas AS-FT-2 adalah cukup singkat apabila AS-FT-2 digunakan dalam rangkaian ini. Oleh itu, AS-FT-2 boleh digunakan dalam memantau rangkaian sensor dan rangkaian industri.

Sebaliknya, dalam beberapa sistem komunikasi masa nyata, menurut [16], untuk menjamin keselamatan lalu lintas di bawah kekangan lebar jalur, selang penghantaran data untuk sistem pengangkutan pintar koperasi dianggap sebagai \(200\) ms, iaitu untuk mengoptimumkan kecekapan keseluruhan sistem dalam ciri penunjuk keselamatan. Daripada keperluan ini dan Jadual 1, masa menunggu maklum balas AS-FT-2 adalah terlalu lama. Oleh itu, AS-FT-2 ialah tidak terpakai untuk sistem komunikasi masa nyata tersebut.

4. Skim ASIT tanpa Maklum Balas

Dalam bahagian ini, kami mencadangkan skim ASIT baharu yang tidak memerlukan maklum balas, dengan menjangkakan permohonan di mana masa menunggu maklum balas adalah singkat supaya skim ASIT AS-FT-2 tidak boleh digunakan. Idea di sebalik skim yang dicadangkan ialah kami membenarkan pengagregat memutuskan cara membuat tandatangan agregat (iaitu, partition) terlebih dahulu, berbeza dengan pembinaan AS-FT-2, di mana pengesah (algoritma pengesanan) memutuskannya secara adaptif semasa pelaksanaan. Begitu juga dengan AS-FT-2, kami membina skim ASIT baharu berdasarkan skema tandatangan agregat dan algoritma pengesanan cetak rompak, tetapi dalam skema kami, kami menggunakan Pengesanan Pengkhianat Berurutan (STT) [17]. STT menentukan penetapan tera air terlebih dahulu dan ciri ini membolehkan kami mengalih keluar maklum balas daripada skim ASIT.

Kami mula-mula menyemak konsep STT, dan kemudian instantiasi konkrit STT, dinamakan \(c\)-SW-1 [17]. Kemudian kami menyediakan pembinaan ASIT baharu kami yang dinamakan AS-SW-1 berdasarkan skim tandatangan agregat dan \(c\)-SW-1. Seperti yang dijelaskan sebelum ini, [12] mencadangkan pembinaan generik ASIT berdasarkan skim tandatangan agregat dan DTT. Skim ASIT kami AS-SW-1 dibina hanya dengan menggantikan FT-2 yang digunakan dalam AS-FT-2 dengan \(c\)-SW-1. Oleh itu, untuk membuktikan AS-SW-1 memenuhi keperluan skim ASIT, adalah memadai untuk membuktikan bahawa \(c\)-SW-1 ialah DTT.

4.1 Pengesanan Pengkhianat Berurutan

Seperti yang telah disebutkan, STT ialah varian daripada algoritma pengesanan cetak rompak yang menentukan penetapan tera air terlebih dahulu. Tugasan sebenarnya ditentukan oleh matriks peruntukan \(M\), yang penyertaannya ditentukan oleh keluarga majlis \(\Phi\). Lajur daripada \(M\) sepadan dengan peruntukan tera air bagi setiap pengedaran. Selang masa antara setiap pengedaran dipanggil segmen. Dalam subseksyen ini, kami memperkenalkan matriks peruntukan dan keluarga fungsi bersama beberapa lema dan pelaksanaan keluarga fungsi. Kemudian, kami menyediakan pelaksanaan STT.

Mari \(W\mathop{\mathrm{:=}}[q]\) menjadi set tera air, dan \(b\) \((\leq q)\) and \(l\) menjadi integer. Kami biarkan \(\Phi=\{\phi_{i,j}:1\leq i\leq b, 1\leq j\leq l\}\), Di mana \(\phi_{i,j}:W\rightarrow W\) ialah keluarga fungsi yang memenuhi syarat berikut:

Keadaan 1: Untuk semua \(x \in W\), sebarang tetap \(j\) dan sepasang indeks pertama \((i_1, i_2)\) di mana \(i_1 \neq i_2\), ia memegang bahawa \(\phi_{i_1j}(x) \neq \phi_{i_2j}(x)\).

Keadaan 2: Bagi apa apa \((i_1,i_2)\) and \((j_1,j_2)\) di mana \(j_1\neq j_2\), dan mana-mana \(x_1,x_2\in W\) seperti itu \(x_1\neq x_2\), Jika \(\phi_{i_1,j_1}(x_1)=\phi_{i_2,j_1}(x_2)\) kemudian \(\phi_{i_1,j_2}(x_1)\neq \phi_{i_2,j_2 }(x_2)\).

Sekarang, kami menerangkan matriks peruntukan \(M\). Biarkan \(\Phi\) menjadi keluarga fungsi yang memenuhi syarat di atas. biarlah \(M_0\) and \(\phi_{i,j}(M_0)\) (\(i\in [b]\), \(j\in [l]\)) menjadi yang berikut \(q\times 1\) matriks:

\[M_0=\begin{pmatrix} 1\\2\\\vdots\\q \end{pmatrix}, \phi_{i,j}(M_0)=\begin{pmatrix} \phi_{i,j}(1)\\\phi_{i,j}(2)\\\vdots\\\phi_{i,j}(q)\end{pmatrix}.\]

Kemudian, matriks peruntukan \(M\) diterangkan seperti berikut:

\[M= \begin{pmatrix} M_0 & \phi_{1,1}(M_0) & \phi_{1,2}(M_0) & \cdots & \phi_{1,l}(M_0) \\ M_0 & \phi_{2,1}(M_0) & \phi_{2,2}(M_0) & \cdots & \phi_{2,l}(M_0) \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ M_0 & \phi_{b,1}(M_0) & \phi_{b,2}(M_0) & \cdots & \phi_{b,l}(M_0) \end{pmatrix}.\]

Perhatikan bahawa \(M\) mempunyai \(b\) baris blok dan setiap blok terdiri daripada \(q\) barisan. The \(i\)-baris ke- \(M\) mewakili tera air yang diberikan kepada pengguna \(i\) mengikut urutan (oleh itu, secara tersirat diandaikan bahawa bilangan pengguna adalah \(bq\)), Dan \(j\)Lajur -th mewakili penetapan tera air untuk setiap pengguna di segmen \(j\). Biarkan \((r,k)\) menandakan \(k\)-baris ke- \(r\)-blok ke.

Di sini kami menerangkan caranya \(M\) digunakan untuk mengesan cetak rompak dalam perkhidmatan pengedaran kandungan. Pengedar kandungan mengedarkan tera air sesuatu kandungan \(M(i, j)\) kepada pengguna \(i\) pada segmen tersebut \(j\), dengan memantau cetak rompak. Untuk memudahkan perbincangan, kami menganggap bahawa pengedar mengesan betul-betul satu cetak rompak dalam setiap segmen. biarlah \(F_j=(f_1,\ldots,f_j)\) menjadi urutan indeks tera air pada kandungan yang dikesan oleh pengedar daripada segmen \(1\) kepada segmen \(j\). Tambahan pula, biarkan

\[\begin{aligned} &\rho(F_j, i, s) = \left\{ \begin{array}{ll} 1 & (\mathrm{if} f_s = M(i, j))\\ 0 & (\mathrm{otherwise}) \end{array} \right., \\ &\rho(F_j, i) = \sum_{s=1}^{j} \rho(F_j, i, s). \end{aligned}\]

Jika ada pengguna \(i\) seperti itu \(\rho(F_j, i) \geq t\) untuk ambang \(t\), kemudian pengedar salam \(i\) sebagai lanun dan menghapuskannya. Mengenai ambang, Safavi-Naini dan Wang [17] menunjukkan lemma berikut.

Lema 4.1 ([17]): Biarlah \(C\) menjadi kumpulan lanun di mana \(|C| = c\), dan \(F_j=(f_1,\ldots,f_j)\) menjadi urutan indeks tera air pada kandungan yang dikesan oleh pengedar daripada segmen \(1\) kepada segmen \(j\). Jika ada pengguna \(i\) seperti itu \(\rho(F_j, i) \geq c+1\), Maka \(i \in C\).

Mengenai berapa banyak segmen yang diperlukan untuk mengesan semua lanun, mereka juga menunjukkan lemma berikut.

Lema 4.2 ([17]): Biarlah \(C\) menjadi kumpulan lanun di mana \(|C| = c\). Semua lanun boleh dikesan dengan paling banyak \(c^2 + c\) segmen.

Lemma 4.2 memberitahu kita hubungan antara bilangan segmen dan bilangan lanun.

Akibat 4.1 ([17]): Biarlah \(M\) menjadi satu \(n \times (l+1)\) matriks peruntukan. STT yang menggunakan matriks ini boleh mengesan paling banyak

\[\begin{equation*} c = \left\lfloor\frac{-1+\sqrt{5+4l}}{2} \right\rfloor \tag{1} \end{equation*}\]

lanun.

4.1.1 Pelaksanaan \(\Phi\)

Safavi-Naini dan Wang [17] mencadangkan pelaksanaan berikut \(\Phi\) daripada keluarga fungsi.

Teorem 4.1 ([17]): Biarlah \(p\) menjadi nombor perdana. biarlah \(\Phi=\{\phi_{i,j}:i,j\in[(p-1)/2]\}\) \((\phi_{i,j}:Z^*_p \rightarrow Z^*_p)\) menjadi keluarga fungsi yang ditakrifkan oleh \(\phi_{i,j}(x)=(i+j)x \mod{p}\). Kemudian, \(\Phi\) memenuhi Syarat 1 dan Syarat 2.

4.1.2 Pemerhatian

Semasa kita menggunakan \(\Phi\) dalam Teorem 4.1 dalam STT, matriks peruntukan haruslah \(n \times l\) matriks di mana \(n=(p-1)^2/2\) and \(l=(p-1)/2\). Juga, bilangan maksimum lanun yang boleh dikesan ialah \(c= \lfloor\frac{-1+\sqrt{2p+3}}{2} \rfloor\). Diberikan \(n\) and \(c\), syarat untuk \(p\) dinyatakan sebagai \(p\geq \max(1+\sqrt{2n}, 2c^2+2c-1)\) dari \((p-1)^2/2\geq n\) and \(c^2+c\leq (p-1)/2+1\) (perhatikan bahawa ketidaksamaan kedua adalah disebabkan oleh Lemma 4.2).

4.1.3 Instalasi STT

Di sini kami menyediakan instantiasi STT berdasarkan keluarga fungsi dalam Teorem 4.1. biarlah \(n \mathop{\mathrm{:=}}bq\) menjadi bilangan penandatangan, \(C \subseteq [n]\) menjadi satu set lanun di mana \(|C| = c \leq n\), dan \(W \mathop{\mathrm{:=}}[q]\) menjadi satu set tera air yang diandaikan akan diberikan kepada pengedar terlebih dahulu. biarlah \(Q_{j,x}\) menjadi set pengguna yang mempunyai tera air \(x \in W\) ditetapkan pada segmen \(j\), iaitu, \(Q_{j,x} = \{i\in [n] : M[i,j]=x\}\).

Rajah 6 menggambarkan pembinaan \(c\)-SW-1 STT yang menggunakan keluarga fungsi \(\Phi\) dalam Teorem 4.1. Ambil perhatian bahawa dalam subrutin GenMatrix, perdana \(p\) dipilih berdasarkan pemerhatian di atas. Kami menunjukkan lemma berikut.

Rajah 6  Pembinaannya \(c\)-SW-1 STT. GenMatrix ialah subrutin yang digunakan untuk menjana matriks peruntukan \(M\) berdasarkan keluarga fungsi \(\Phi\) dalam Teorem 4.1.

Lemma 4.3: Algoritma \(c\)-SW-1 ialah DTT.

Bukti 4.3 dibentangkan dalam Lampiran B.

4.2 Pembinaan Skim ASIT tanpa Maklum Balas

Kami menunjukkan skim ASIT yang tidak memerlukan maklum balas berdasarkan tandatangan agregat dan STT \(c\)-SW-1 (selepas ini dirujuk sebagai AS-SW-1). Rajah 7 menggambarkan AS-SW-1, di mana \(c\) memenuhi Persamaan. (1). Kami menganggap tanpa kehilangan umum bahawa bilangan pengguna \(n\) dan bilangan penandatangan penyangak \(c\) diberikan kepada algoritma. AS-SW-1 berprestasi serupa dengan AS-FT-2 dalam pengagregatan itu dilakukan secara sebahagian demi bahagian mengikut partition, tetapi tidak seperti AS-FT-2, AS-SW-1 mengelakkan komunikasi maklum balas antara pengagregat dan seorang pengesah. Khususnya, pengagregat dan pengesah kedua-duanya melaksanakan \(c\)-SW-1 untuk berkongsi bagaimana set penandatangan dibahagikan dalam setiap pusingan, dan partition \(P\) dipegang oleh pengagregat dan pengesah disimpan dalam keadaan dalaman \(\alpha\) and \(\beta\), Masing-masing.

Rajah 7  Skim ASIT yang dicadangkan AS-SW-1. \({}^{(\dagger)}\) Perintah ini keluar Untuk dan bergerak ke baris seterusnya.

Perhatikan bahawa kedua-duanya \(\mathop{\mathrm{\mathsf{Agg}}}\) and \(\mathop{\mathrm{\mathsf{Trace}}}\) menjalankan \(c\)-SW-1\(.\mathop{\mathrm{\mathsf{Initialize}}}\) apabila mereka dimulakan. Kerana \(c\)-SW-1, termasuk subrutin \(\mathsf{GenMatrix}\), adalah deterministik, algoritma ini berkongsi partition yang sama \(P\) (atau matriks peruntukan yang sama). Perhatikan bahawa output \(f\) by \(\mathop{\mathrm{\mathsf{Trace}}}\) ialah rentetan kosong (maklum balas ini diletakkan hanya untuk mengikuti sintaks ASIT, dan dengan itu \(\mathop{\mathrm{\mathsf{Agg}}}\) tidak menerima ini \(f\) dalam pelaksanaan sebenar). Selain itu, apabila pengesah mengenal pasti penandatangan penyangak, ia menghantar set penyerang yang dikesan \(V\) kepada agregator.

4.2.1 Keselamatan

Perhatikan bahawa AS-SW-1 dibina dengan hanya menggantikan DTT FT-2 yang digunakan dalam AS-FT-2 dengan \(c\)-SW-1. Tambahan pula, seperti yang ditunjukkan dalam Lemma 4.3, \(c\)-SW-1 ialah DTT. Oleh itu, AS-SW-1 mengikuti pembinaan generik ASIT yang dicadangkan oleh Ishii et al. [12], yang membayangkan lema berikut.

Lemma 4.4: Andaikan skim tandatangan agregat asas \(\Sigma_{\mathrm{AS}}\) adalah EUF-CMA selamat, dan asas DTT ialah \(c\)-SW-1. Kemudian, AS-SW-1 ialah skim ASIT yang memenuhi keselamatan EUF-CMA, \((c^2 + c)\)-pengenalpastian, dan ketepatan.

5. Perbandingan AS-SW-1 dengan AS-FT-2

Dalam bahagian ini, kami secara teori dan eksperimen menilai kecekapan AS-SW-1 berbanding AS-FT-2. Kemudian, kita bincangkan yang mana antara dua skim itu lebih sesuai dalam beberapa situasi.

5.1 Penilaian Teori

Kami secara teorinya menilai skim remeh (iaitu, tiada pengagregatan), skim sedia ada AS-FT-2 dan skim cadangan kami AS-SW-1 berkenaan dengan kecekapan fungsi pengesanan dan jalur lebar komunikasi AS-FT-2 dan AS-SW-1. Untuk membandingkan metrik ini, kami menilai bilangan maksimum pusingan yang diperlukan untuk mengesan semua penandatangan penyangak, bilangan maksimum tandatangan yang dihantar oleh pengagregat setiap pusingan dan jumlah bilangan tandatangan sehingga semua penandatangan penyangak dikesan.

Kami mula-mula membandingkan kaedah remeh dan skim lain. Daripada Jadual 2, Trivial memerlukan bilangan pusingan pengesanan yang paling sedikit, manakala \(\mathrm{TotalSig}\) adalah linear kepada \(N\). Apabila \(d(2N-d+1)/2<3d(d+1)\), iaitu, \(N<4d+2\) or \(d(2N-d+1)/2<(d^2+d)(p-1)\), iaitu, \(N<(d+1)(p-1)+(d-1)/2\), Trivial ialah skim terbaik dari segi pengesanan dan lebar jalur, jika tidak, ia memerlukan kos komunikasi yang besar dalam keseluruhan pengesanan.

Jadual 2  Penilaian teori. Trivial bermaksud skema remeh. \(N\) and \(d\) ialah nombor semua penandatangan dan penandatangan penyangak, masing-masing, dan \(p\) ialah nombor perdana yang memuaskan \(p > \max (2d^2+2d, \lceil \frac{\sqrt{2N}}{2} \rceil)\). \(R_{\max}\) ialah bilangan maksimum pusingan yang diperlukan untuk mengesan semua penandatangan penyangak. \(\mathrm{Sig}_{\max}\) ialah bilangan maksimum tandatangan yang dihantar oleh pengagregat setiap pusingan. \(\mathrm{TotalSig}\) ialah jumlah bilangan tandatangan untuk mengesan semua penandatangan penyangak yang bersekongkol apabila ada pusingan untuk dihantar \(\mathrm{Sig}_{\max}\) tandatangan.

Seterusnya, kami membandingkan AS-FT-2 dan AS-SW-1. Untuk bilangan pusingan \(R_{\max}\), Apabila \(d<\log_2 N\), AS-SW-1 memerlukan lebih sedikit pusingan daripada AS-FT-2, sebaliknya AS-FT-2 memerlukan lebih sedikit pusingan daripada AS-SW-1. Untuk \(\mathrm{Sig}_{\max}\), Apabila \(2(d^2+d)< \frac{\sqrt{2N}}{2}\) and \(\frac{\sqrt{2N}}{2}-1 < 2d+1\), iaitu, \(8(d^2+d)^2<N<8(d+1)^2\), bilangan maksimum tandatangan yang dihantar oleh pengagregat setiap pusingan AS-SW-1 adalah kurang daripada AS-FT-2, jika tidak AS-FT-2 menghantar kurang tandatangan daripada AS-SW-1. Oleh itu, AS-SW-1 mengesan dengan lebih cekap apabila bilangan penandatangan penyangak agak jauh lebih kecil berbanding bilangan semua penandatangan tetapi memerlukan lebih lebar jalur daripada AS-FT-2.

5.2 Penilaian Pelaksanaan

Berdasarkan penilaian teori, kami secara konkrit menetapkan bilangan semua penandatangan dan penandatangan penyangak, dan melaksanakan skim kami, dan menilai AS-FT-2 atau AS-SW-1 yang mana lebih berkesan berdasarkan eksperimen. Butiran persekitaran eksperimen adalah sama seperti dalam Sekt. 3.

5.2.1 Tetapan Simulasi

Dalam tetapan percubaan, kami menangkap situasi di mana sebilangan kecil penyerang tetap sentiasa menghantar tandatangan tidak sah untuk menunjukkan kecekapan pengesanan dan penggunaan lebar jalur AS-SW-1 dengan membandingkan dengan AS-FT-2. Seperti dalam Mazhab. 3, nombor \(N\) daripada semua penandatangan dan nombor \(d\) penandatangan penyangak adalah \(N=1000\), \(3000\), dan \(d=5, 10, 40\), masing-masing. Eksperimen dilakukan 10 kali dan purata diambil.

5.2.2 Keputusan Simulasi

Jadual 3 menunjukkan keputusan kami. Dalam jadual ini, perdana \(p\) adalah yang terkecil yang memenuhi syarat dalam Jadual 2 untuk AS-SW-1. Bahagian yang paling penting ialah lajur bukan FB, yang menunjukkan keperluan maklum balas. Kami mengesahkan bahawa AS-SW-1, yang tidak memerlukan maklum balas, sememangnya berfungsi dengan baik. Untuk kecekapan pengesanan, jumlah masa pengesanan adalah hampir berkadar dengan \(d^2\) and \(N/p\) untuk AS-SW-1 apabila \(p<N\), manakala AS-FT-2 hampir berkadar dengan \(d\log N\). Keputusan ini konsisten dengan penilaian teori yang ditunjukkan dalam Jadual 2. Daripada Jadual 3, jumlah masa pengesanan AS-SW-1 adalah kurang daripada AS-FT-2 apabila \(200d<N\), jika tidak AS-FT-2 adalah kurang. Sebaliknya, untuk penggunaan lebar jalur, daripada Jadual 2, lajur Sig adalah hampir berkadar dengan \(d^2\) untuk AS-SW-1 apabila \(p<N\) dan sebaliknya ia adalah sama seperti penghantaran tandatangan individu, manakala AS-FT-2 adalah hampir berkadar dengan \(d\). Khususnya, AS-SW-1 memerlukan \(144.9\) kali lebih banyak tandatangan untuk mengesan penandatangan penyangak daripada AS-FT-2 apabila \((N,d)=(3000,40)\). Perhatikan bahawa keputusan ini menunjukkan bahawa AS-SW-1 memerlukan lebih banyak penggunaan lebar jalur daripada AS-FT-2.

Jadual 3  Hasil simulasi untuk AS-FT-2 dan AS-SW-1. bukan FB bermaksud tiada maklum balas (“\(\checkmark\)” bermakna ia tidak memerlukan maklum balas, dan “-” bermakna ia memerlukan), Bulat ialah jumlah pusingan untuk mengesan semua penyerang, Masa ialah jumlah masa dari permulaan pusingan pertama hingga selesai pengesanan, dan Sig ialah saiz purata tandatangan yang dihantar setiap pusingan.

5.2.3 Skim Sesuai untuk Permohonan

Kami menganggap AS-FT-2 dan AS-SW-1 yang mana lebih sesuai untuk sesetengah aplikasi, yang kurang terhad masa atau sistem komunikasi masa nyata. Dalam sistem komunikasi yang kurang terhad masa, contohnya, dalam rangkaian penderia pemantauan [15], protokol jalur lebar rendah, seperti LoRa, yang mempunyai kelajuan \(37.5\) kbps [30] digunakan. Di samping itu, sistem boleh mempunyai banyak peranti penyangak, katakan, daripada \(40\) kepada \(300\) peranti penyangak daripada \(1000\) peranti [27]. Daripada keputusan di atas, AS-FT-2 adalah lebih cekap daripada AS-SW-1 dari segi lebar jalur dan masa untuk mengesan semua penandatangan penyangak apabila \(d\) adalah besar. Walaupun agregator AS-FT-2 perlu menunggu maklum balas, seperti yang dinyatakan dalam Sekt. 3, masa menunggu tidak terlalu lama untuk aplikasi ini, dan lebar jalur adalah mencukupi untuk AS-FT-2. Oleh itu, AS-FT-2 lebih sesuai untuk sistem komunikasi yang kurang terhad masa untuk memanfaatkan kecekapan lebar jalur dan masa pengesanan yang singkat apabila \(d\) adalah besar. Dalam sesetengah sistem komunikasi masa nyata, cth, sistem pengangkutan pintar koperasi, beberapa protokol komunikasi jalur lebar tinggi, seperti LTE (\(23.6\) Mbps), digunakan. Di samping itu, untuk mengoptimumkan kecekapan keseluruhan sistem dalam ciri penunjuk keselamatan, banyak peranti menghantar data dalam selang masa yang singkat, iaitu kira-kira \(200\) ms [16]. Oleh itu, AS-FT-2 tidak boleh digunakan kerana masa menunggu maklum balas. Sebaliknya, keputusan di atas menunjukkan bahawa AS-SW-1 adalah lebih cekap dari segi masa untuk mengesan semua penandatangan penyangak apabila \(d\) adalah kecil (\(d \leq 10\)) kerana tiada ciri maklum balasnya. Namun, apabila \(d\) adalah besar, AS-SW-1 memerlukan lebih banyak masa pengesanan dan lebar jalur yang besar. Oleh itu, AS-SW-1 lebih sesuai untuk sistem komunikasi masa nyata untuk memanfaatkan ciri tiada maklum balas, penggunaan lebar jalur yang boleh diterima dan masa pengesanan yang singkat apabila \(d\) adalah kecil.

6. Kesimpulan

Dalam makalah ini, untuk mengkaji sama ada skim FT-AS sedia ada mampu menghantar maklum balas dengan cukup pantas pada sistem sebenar, kami menilai masa menunggu maklum balas pelaksanaan AS-FT-2 skim ASIT yang dicadangkan dalam [12]. Keputusan eksperimen pelaksanaan menunjukkan bahawa jika masa maklum balas yang boleh diterima sistem adalah jauh lebih besar daripada beberapa ratus ms, contohnya, sistem sensor industri [31], AS-FT-2 boleh digunakan tanpa masalah. Sebaliknya, mungkin terdapat beberapa aplikasi di mana masa maklum balas yang cukup besar tidak boleh diterima, contohnya, sistem pengangkutan pintar koperasi [16]. Untuk menjangkakan permohonan sedemikian, kami juga mencadangkan skim ASIT AS-SW-1 yang tidak memerlukan maklum balas. Skim yang dicadangkan menghapuskan maklum balas dengan menggunakan STT yang dicadangkan oleh Safavi-Naini et al. [17] dalam pembinaan generik ASIT Ishii et al. [12]. Daripada keputusan pelaksanaan kami, kami mendapati bahawa walaupun maklum balas dihapuskan sepenuhnya dalam skim kami, kos komunikasinya jauh lebih besar, contohnya \(144.9\) kali lebih besar apabila \((N,d) = (3000,40)\). Oleh itu, AS-SW-1 lebih sesuai untuk aplikasi yang mempunyai kekangan masa yang tinggi dan lebar jalur yang tinggi tersedia, manakala untuk aplikasi yang mempunyai kekangan lebar jalur tetapi masa tidak, AS-FT-2 lebih sesuai.

Kami meninggalkannya sebagai kerja masa depan untuk membina sistem konkrit yang menggunakan skim ASIT. Ke arah matlamat ini, pertama sekali kita perlu mempertimbangkan persekitaran pelaksanaan seperti topologi rangkaian dan format mesej untuk skema ASIT.

Rujukan

[1] R. Ishii, K. Yamashita, Z. Song, Y. Sakai, T. Teruya, G. Hanaoka, K. Matsuura, and T. Matsumoto, “Constraints and evaluations on signature transmission interval for aggregate signatures with interactive tracing functionality,” ESORICS 2022 Workshop on ADIoT, pp.51-71, 2022.
CrossRef

[2] D. Boneh, C. Gentry, B. Lynn, and H. Shacham, “Aggregate and verifiably encrypted signatures from bilinear maps,” EUROCRYPT 2003, pp.416-432, 2003.
CrossRef

[3] A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham, “Sequential aggregate signatures from trapdoor permutations,” EUROCRYPT 2004, pp.74-90, 2004.
CrossRef

[4] C. Gentry and Z. Ramzan, “Identity-based aggregate signatures,” PKC 2006, Lecture Notes in Computer Science, vol.3958, pp.257-273, Springer, 2006.
CrossRef

[5] J.H. Ahn, M. Green, and S. Hohenberger, “Synchronized aggregate signatures: New definitions, constructions and applications,” CCS 2010, pp.473-484, ACM, 2010.
CrossRef

[6] G. Hartung, B. Kaidel, A. Koch, J. Koch, and A. Rupp, “Fault-tolerant aggregate signatures,” PKC 2016, pp.331-356, 2016.
CrossRef

[7] W.H. Kautz and R.C. Singleton, “Nonrandom binary superimposed codes,” IEEE Trans. Inf. Theory, vol.10, no.4, pp.363-377, 1964.
CrossRef

[8] R. Kumar, S. Rajagopalan, and A. Sahai, “Coding constructions for blacklisting problems without computational assumptions,” CRYPTO'99, pp.609-623, 1999.
CrossRef

[9] G.M. Zaverucha and D.R. Stinson, “Group testing and batch verification,” ICITS 2009, pp.140-157, 2009.
CrossRef

[10] D. Du, F.K. Hwang, and F. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2000.
CrossRef

[11] D. Eppstein, M.T. Goodrich, and D.S. Hirschberg, “Improved combinatorial group testing algorithms for real-world problem sizes,” SIAM J. Comput., vol.36, no.5, pp.1360-1375, 2007.
CrossRef

[12] R. Ishii, K. Yamashita, Y. Sakai, T. Matsuda, T. Teruya, G. Hanaoka, K. Matsuura, and T. Matsumoto, “Aggregate signature with traceability of devices dynamically generating invalid signatures,” ACNS 2021 Satellite Workshop on SCI, pp.378-396, 2021.
CrossRef

[13] J. Shikata, T. Matsumoto, and ECSEC, “Digital signature system and digital signature method,” 2021. JP, 2021-077961, A, 2021-5-20 (In Japanese).

[14] A. Fiat and T. Tassa, “Dynamic traitor tracing,” CRYPTO'99, pp.354-371, 1999.
CrossRef

[15] S. Suryavansh, A. Benna, C. Guest, and S. Chaterji, “A data-driven approach to increasing the lifetime of iot sensor nodes,” Sci. Rep., vol.11, no.1, pp.1-12, 2021.
CrossRef

[16] S. Tak and S. Choi, “Safety monitoring system of CAVs considering the trade-off between sampling interval and data reliability,” Sensors, vol.22, no.10, 3611, 2022.
CrossRef

[17] R. Safavi-Naini and Y. Wang, “Sequential traitor tracing,” IEEE Trans. Inf. Theory, vol.49, no.5, pp.1319-1326, 2003.
CrossRef

[18] S. Sato, J. Shikata, and T. Matsumoto, “Aggregate signature with detecting functionality from group testing,” IACR Cryptol. ePrint Arch., vol.2020, p.1219, 2020.
URL

[19] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” ASIACRYPT 2001, pp.514-532, 2001.
CrossRef

[20] S. Hohenberger, A. Sahai, and B. Waters, “Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures,” CRYPTO 2013, LNCS, vol.8042, pp.494-512, Springer, 2013.
CrossRef

[21] S. Sato and J. Shikata, “Interactive aggregate message authentication equipped with detecting functionality from adaptive group testing,” IACR Cryptol. ePrint Arch., vol.2020, p.1218, 2020.
URL

[22] G. Neven, “Efficient sequential aggregate signed data,” EUROCRYPT 2008, N.P. Smart, ed., LNCS, vol.4965, pp.52-69, Springer, 2008.
CrossRef

[23] M. Gerbush, A.B. Lewko, A. O'Neill, and B. Waters, “Dual form signatures: An approach for proving security from static assumptions,” ASIACRYPT 2012, pp.25-42, 2012.
CrossRef

[24] S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters, “Sequential aggregate signatures and multisignatures without random oracles,” EUROCRYPT 2006, pp.465-485, 2006.
CrossRef

[25] K. Lee, D.H. Lee, and M. Yung, “Sequential aggregate signatures with short public keys without random oracles,” Theor. Comput. Sci., vol.579, pp.100-125, 2015.
CrossRef

[26] Z. Song, R. Anzai, J. Sakamoto, N. Yoshida, and T. Matsumoto, “Proposal and prototype implementation of a cloud-based simulator for traceable aggregate signature protocol,” SCIS 2022, 2022 (in Japanese).

[27] M. Pandey, S. Dhanoriya, and A. Bhagat, “Fast and efficient data acquisition in radiation affected large wsn by predicting transfaulty nodes,” International Conference on Next Generation Computing Technologies, pp.246-262, Springer, 2017.
CrossRef

[28] S. Mitsunari, “mcl - a portable and fast pairing-based cryptography library,” https://github.com/herumi/mcl, 2016.
URL

[29] P.S.L.M. Barreto and M. Naehrig, “Pairing-friendly elliptic curves of prime order,” SAC 2005, LNCS, vol.3897, pp.319-331, Springer, 2005.
CrossRef

[30] A. Lavric and V. Popa, “Performance evaluation of lorawan communication scalability in large-scale wireless sensor networks,” Wireless Communications and Mobile Computing, vol.2018, 2018.
CrossRef

[31] M.P.R.S. Kiran and P. Rajalakshmi, “Performance analysis of CSMA/CA and PCA for time critical industrial iot applications,” IEEE Trans. Ind. Inform., vol.14, no.5, pp.2281-2293, 2018.
CrossRef

Lampiran A: Definisi DTT

Ingat bahawa DTT ialah kaedah untuk mengesan cetak rompak dalam perkhidmatan pengedaran kandungan digital. Dua keperluan keselamatan ditakrifkan untuk DTT. Satu adalah \(R\)-pengenalan, yang bermaksud bahawa pengedar boleh mengenal pasti semua pengkhianat dalam \(R\) pusingan pelaksanaan prosedur pengesanan. Yang lain ialah kesempurnaan, yang bermaksud bahawa pengedar tidak mengesan pengguna yang sah. Dalam DTT, diandaikan bahawa sekurang-kurangnya seorang pengkhianat mengedarkan semula dalam setiap segmen. Mula-mula kita ingat sintaks DTT, kemudian ingat keperluan keselamatan.

Definisi Lampiran A.1 (Dynamic Traitor Tracing): Pengesanan pengkhianat dinamik (DTT) terdiri daripada dua algoritma PPT \((\mathop{\mathrm{\mathsf{Initialize}}},\mathop{\mathrm{\mathsf{Trace}}})\) yang berfungsi seperti berikut:

  • \((\alpha, P)\leftarrow\mathop{\mathrm{\mathsf{Initialize}}}(1^\lambda,1^n)\): Algoritma Initialize mengambil \(1^\lambda\), \(1^n\) sebagai input dan output sepasang \((\alpha, P)\) keadaan dalaman dan sekatan set pengguna.
  • \((\alpha', P', V)\leftarrow\mathop{\mathrm{\mathsf{Trace}}}(\alpha,i)\): Algoritma Trace mengambil sebagai input keadaan dalaman \(\alpha\) dan indeks \(i\), dan mengeluarkan tuple keadaan dalaman pusingan seterusnya, partition set pengguna dan set pengguna yang dikesan, dengan indeks input ialah indeks tera air yang diberikan kepada kandungan yang diedarkan semula daripada pengkhianat.

Sintaks ini menangkap senario berikut. Pada mulanya, pengedar melaksanakan \(\mathop{\mathrm{\mathsf{Initialize}}}\) untuk mencipta keadaan dalaman awal dan partition awal. Ambil perhatian bahawa partition ialah subset set pengguna dan pengguna yang berada dalam partition yang sama menerima kandungan dengan tera air yang sama. Sebaik sahaja pengedar mengesan cetak rompak, ia menyemak tera air \(i\) kandungan yang diedarkan semula dan dijalankan \(\mathop{\mathrm{\mathsf{Trace}}}\) on \(i\) untuk membuat partition baru. Pengedar mengulangi ini sehingga ia mengesan pengagihan semula kandungan yang tera airnya sepadan dengan partition yang mengandungi hanya satu pengguna. Kemudian, pengedar menganggap pengguna sebagai lanun, dan menghapuskannya. Kami mengira selang antara pelaksanaan \(\mathop{\mathrm{\mathsf{Trace}}}\) sebagai 1 keliling.

A.1 Keperluan Keselamatan

Di sini, kami ingat keperluan keselamatan DTT. Dalam model keselamatan, musuh mengisytiharkan satu set \(C\) (di mana \(|C| \le d\)) lanun pada mulanya. Tambahan pula, kami menganggap bahawa lanun menyiarkan semula kandungan yang diterimanya. Dalam erti kata lain, kami tidak menganggap kes di mana lanun mencuri dengar kandungan pengguna lain dan menyiarkannya semula. Ini adalah sekatan yang dimasukkan secara tersirat [14].

Seperti yang dinyatakan sebelum ini, dua tanggapan keselamatan dipertimbangkan untuk DTT: \(R\)-boleh dikenal pasti, yang memastikan pengedar boleh mengenal pasti semua lanun dalam \(R\) (atau kurang) pusingan, dan kesempurnaan, yang memastikan pengedar tidak mengesan pengguna yang sah sebagai lanun. Ini ditakrifkan menggunakan eksperimen berikut \(\mathop{\mathrm{\mathsf{ExpDTT}}}_{\Sigma_{\mathrm{DTT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda,n)\) di mana musuh bernegara \(\mathop{\mathrm{\mathcal{A}}}\) dilaksanakan.

\begin{align*}&\ \ \ \ \mathop{\mathrm{\mathsf{ExpDTT}}}\nolimits_{\Sigma_{\mathrm{DTT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda, n)\\ &\begin{aligned} \begin{aligned} \hline \begin{array}{l} (\alpha_1,P_1)\leftarrow\Sigma_{\mathrm{DTT}}.\mathop{\mathrm{\mathsf{Initialize}}}(1^\lambda,1^n); \\ C \leftarrow \mathop{\mathrm{\mathcal{A}}}(\alpha_1,P_1); t:=1; W \mathop{\mathrm{:=}}\emptyset; {\rm run} \, \mathop{\mathrm{\mathcal{A}}}^{O_T(\cdot)}(\alpha_1,P_1) \, : \\ {\rm Output} (W, C) \end{array} \end{aligned} \end{aligned} \end{align*}

di mana \(\mathop{\mathrm{\mathcal{A}}}\) boleh menyesuaikan diri membuat berbilang pertanyaan \(i_t\) kepada oracle pengesanan \(O_T\). Walau bagaimanapun, \(\mathop{\mathrm{\mathcal{A}}}\)'s \(t\)-th \(O_T\) pertanyaan \(i_t\) mesti puas hati \(i _t \in [|P_t|]\) and \(S_{i_t,t} \cap C \neq \emptyset\), Di mana \(\alpha_t\) ialah keadaan dalaman dan \(P_t=(S_{1,t}, \ldots, S_{p_t, t})\) (untuk beberapa nombor asli \(p_t\)) menandakan partition selepas \(\mathop{\mathrm{\mathcal{A}}}\)'s \((t-1)\)-th \(O_T\) pertanyaan dijawab. Memandangkan \(t\)-th \(O_T\) pertanyaan \(i_t\) dari \(\mathop{\mathrm{\mathcal{A}}}\), \(O_T\) berjalan \((\alpha_{t+1},P_{t+1},V_t) \leftarrow\Sigma_{\mathrm{DTT}}.\mathop{\mathrm{\mathsf{Trace}}}(\alpha_t, i_t)\), dan kembali \((\alpha_{t+1}, P_{t+1}, V_t)\) kepada \(\mathop{\mathrm{\mathcal{A}}}\). Kemudian, \(O_T\) update \(W \leftarrow W \cup V_t\) and \(t \leftarrow t+1\). Kami menyatakan bahawa \(W\) dalam output eksperimen ialah pada titik \(\mathop{\mathrm{\mathcal{A}}}\) terhenti.

Definisi Lampiran A.2 (\(R\)-Kebolehcaman): A DTT \(\Sigma_{\mathrm{DTT}}\) memuaskan \(R\)-boleh dikenal pasti jika ada \(\lambda \in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), ia memegang bahawa

\[ \begin{aligned} \Pr&\left[ C \nsubseteq W \, \middle| \, (W, C) \right. \\ &\left. \leftarrow \mathop{\mathrm{\mathsf{ExpDTT}}}\nolimits_{\Sigma_{\mathrm{DTT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda,n) \land t \geq R \right] = \mathop{\mathrm{\mathrm{negl}}}(\lambda). \end{aligned}\]

di mana \(t\) ialah nilai kaunter apabila \(\mathop{\mathrm{\mathcal{A}}}\) berhenti.

Definisi Lampiran A.3 (Kelengkapan): A DTT \(\Sigma_{\mathrm{DTT}}\) memenuhi kesempurnaan jika ada \(\lambda \in \mathbb{N}\), ada \(n=\mathsf{poly}(\lambda)\), dan mana-mana musuh PPT \(\mathop{\mathrm{\mathcal{A}}}\), ia memegang bahawa

\[ \begin{aligned} \Pr &\left[([n]\setminus C) \cap W \neq \emptyset \, \middle| \, (W, C) \right. \\ & \left. \leftarrow \mathop{\mathrm{\mathsf{ExpDTT}}}\nolimits_{\Sigma_{\mathrm{DTT}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda,n) \right] = \mathop{\mathrm{\mathrm{negl}}}(\lambda). \end{aligned}\]

Lampiran B: Bukti Lemma 4.3

Mari \(\Sigma_{\mathrm{cSW1}}\) menjadi algoritma yang diterangkan dalam Rajah 6. Perhatikan bahawa \(\Sigma_{\mathrm{cSW1}}\) memenuhi sintaks DTT. Oleh itu, ia kekal untuk menunjukkan kesempurnaan dan \(R\)-pengenalpastian, yang boleh diperolehi secara remeh daripada Lemma 4.1 dan Lemma 4.2.

Lampiran B.1 Tuntutan: Algoritma \(\Sigma_{\mathrm{cSW1}}\) memenuhi kesempurnaan DTT.

Bukti. Mari \((W, C)\) menjadi output eksperimen \(\mathop{\mathrm{\mathsf{ExpDTT}}}_{\Sigma_{\mathrm{cSW1}}, \mathop{\mathrm{\mathcal{A}}}}(\lambda,n)\) di mana \(|C| = c\) and \(\mathop{\mathrm{\mathcal{A}}}\) adalah musuh PPT, dan biarkan \(u \in W\) (ingat tu \(W\) ialah set pengguna yang dikesan sebagai lanun). Perhatikan itu \(u \in W\) jika dan hanya jika \(c+1\) skor6 Bahawa \(u\) milik dikesan sebagai partition yang mengandungi cetak rompak. Disebabkan oleh Lemma 4.1, \(u \in W\) membayangkan bahawa \(u \in C\), yang menyimpulkan tuntutan itu.\(\tag*{◻}\)

Lampiran B.2 Tuntutan: Katakan cetak rompak berlaku setiap pusingan. Kemudian, algoritma \(\Sigma_{\mathrm{cSW1}}\) memuaskan \((c^2 + c)\)-pengenalpastian di mana \(c\) ialah bilangan lanun.

Bukti. Oleh kerana cetak rompak berlaku setiap pusingan, prosedur pengesanan STT asas diteruskan setiap pusingan. Oleh itu, Lemma 4.2 menyimpulkan tuntutan itu.\(\tag*{◻}\)

Nota kaki

1. Dalam makalah ini, kami memberi tumpuan terutamanya kepada penandatangan yang kemungkinan besar menjana tandatangan tidak sah. Namun, kita boleh menganggap mereka dirosakkan oleh pihak yang berniat jahat.
2. AS-FT-2 [12] dan Pembinaan I dalam [18] pada dasarnya mempunyai prosedur pengesanan yang sama, pemisahan binari.
3. Secara umum, tandatangan agregat boleh mengagregatkan berbilang tandatangan walaupun ia dijana di bawah kunci yang sama.
4. Ia mengambil \(0.679\) mikrosaat setiap operasi kumpulan dan \(286\) mikrosaat setiap operasi berpasangan dalam tetapan kami.
5. Dalam algoritma pengesanan AS-FT-2, apabila pengesah menemui tandatangan agregat yang tidak sah, ia mengeluarkan maklum balas dan tandatangan yang lain tidak disahkan.
6. Oleh kerana kami kini mempertimbangkan DTT, kami mentafsir tera air sebagai sekatan.

Pengarang

Ryu ISHII
  The University of Tokyo,National Institute of Advanced Industrial Science and Technology (AIST)

received the BE degree from Keio University and the ME degree from the University of Tokyo, in 2019 and 2021, respectively. Currently, he is a Ph.D. student at the University of Tokyo and a research assistant at the National Institute of Advanced Industrial Science and Technology (AIST), Japan.

Kyosuke YAMASHITA
  National Institute of Advanced Industrial Science and Technology (AIST),Osaka University

received the BE, ME and Ph.D. degrees from Kyoto University, in 2013, 2015 and 2021, respectively. Currently, he is an assistant professor at Osaka University, Japan. He received SCIS Paper Prize from IEICE in 2019.

Zihao SONG
  Yokohama National University

received the BE degree from Okayama University and the ME degree from the Yokohama National University, in 2020 and 2022, respectively.

Yusuke SAKAI
  National Institute of Advanced Industrial Science and Technology (AIST)

received his B.E., M.E., and Ph.D. degrees from the University of Electro-Communications, Tokyo, Japan, in 2009, 2011, and 2014, respectively. From 2012 to 2014, and from 2014 to 2017, he was a research fellow of Japan Society for the Promotion of Science (JSPS). In 2017, he joined the National Institute of Advanced Industrial Science and Technology (AIST), Japan. He is presently engaged in research on cryptography. He received SCIS Paper Prize from IEICE in 2011 and the Best Student Award in IWSEC 2010.

Tadanori TERUYA
  National Institute of Advanced Industrial Science and Technology (AIST)

received the ME degree and the Ph.D. degree in engineering from the University of Tsukuba, Japan, in 2009 and 2012, respectively. He worked as a postdoctoral researcher in the Faculty of Engineering, Information and Systems, University of Tsukuba, Japan (2012-2013), and in the National Institute of Advanced Industrial Science and Technology (AIST), Japan (2013-2016), and then he worked as a researcher in AIST (2016-2018). He is currently a senior researcher in AIST since 2018. His research interests include cryptography, information security, and privacy-enhancing technologies, in particular, practical aspects of cryptography based on elliptic curves, lattices, and secure computation and their applications.

Takahiro MATSUDA
  National Institute of Advanced Industrial Science and Technology (AIST)

received his bachelors, masters, and Ph.D. degrees in Information and Communication Engineering from the University of Tokyo in 2006, 2008, and 2011, respectively. From 2009 to 2011 and from 2011 to 2013, he had been a Research Fellow of Japan Society for the Promotion of Science (JSPS). From 2011, he has been with the National Institute of Advanced Industrial Science and Technology (AIST), Japan, where he currently works as a Team Leader. His research interests are in the areas of public key cryptography and theory of cryptography.

Goichiro HANAOKA
  National Institute of Advanced Industrial Science and Technology (AIST)

graduated from the Department of Engineering, the University of Tokyo in 1997. He received the Ph.D. degree from the University of Tokyo in 2002. Goichiro joined AIST in 2005. Currently, he is a Prime Senior Researcher, Cyber Physical Security Research Center, AIST. He engages in the R&D for encryption and information security technologies including the efficient design and security evaluation of public key cryptosystems. He has received numerous awards including the DoCoMo Mobile Science Award (2016), Mobile Communication Fund; the Wilkes Award (2007), British Computer Society; Best Paper Award (2008, 2019), The Institute of Electronics, Information and Communication Engineers (IEICE); and Innovative Paper Awards (2012, 2014), Symposium on Cryptography &Information Security (SCIS), IEICE.

Kanta MATSUURA
  The University of Tokyo

received his Ph.D. degree in electronics from the University of Tokyo in 1997. He is currently a Professor of Institute of Industrial Science at the University of Tokyo. His research interests include cryptography, cybersecurity, and security management such as security economics. He was an Associated Editor of IPSJ Journal (2001-2005) and IEICE Transactions on Communications (2005-2008), and won Distinguished-Service Award from the IEICE Communications Society in 2008. He was Editor-in-Chief of Security Management (2008-2012), and is an Editorial-Board member of Design, Codes, and Cryptography (2010-present). He is a fellow of IPSJ, and a senior member of IEEE, ACM, and IEICE. He is President of JSSM (Japan Society of Security Management) (2021-present). He is a member of Science Council of Japan (2017-present).

Tsutomu MATSUMOTO
  National Institute of Advanced Industrial Science and Technology (AIST),Yokohama National University

is a professor of the Faculty of Environment and Information Sciences, Yokohama National University. He also serves as the Director of the Cyber Physical Security Research Center (CPSEC) at the National Institute of Advanced Industrial Science and Technology (AIST). Starting from Cryptography in the early '80s, Prof. Matsumoto has opened up the field of security measuring for logical and physical security mechanisms. He received a Doctor of Engineering degree from the University of Tokyo in 1986. He serves as the chair of the Japanese National Body for ISO/TC68 (Financial Services) and the Cryptography Research and Evaluation Committees (CRYPTREC) and as an associate member of the Science Council of Japan (SCJ). He received the IEICE Achievement Award, the DoCoMo Mobile Science Award, the Culture of Information Security Award, the MEXT Prize for Science and Technology, and the Fuji Sankei Business Eye Award.

Kata kunci