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).
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:
- 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\).
- 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})\).
- 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})\).
- 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)\).
- 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.
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++.
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.
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.
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.
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*{◻}\)