Amankan MAC saat musuh memiliki oracle verifikasi

Sebuah kode otentikasi pesan (MAC) didefinisikan oleh tiga algoritma yang efisien , yang memenuhi berikut (definisi diambil dari bagian 4.3 dari Katz -Lindell book ):$(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$

• Pada input , algoritma menghasilkan kunci .$1^n$$\mathsf{Gen}$$k \ge n$
• Pada input dihasilkan oleh , dan beberapa pesan , algoritma menghasilkan tag . Kami menulis .$k$$\mathsf{Gen}$$m \in \{0,1\}^*$$\mathsf{MAC}$$t$$t \gets \mathsf{MAC}_k(m)$
• Pada input tiga , algoritma menghasilkan bit tunggal . Kami menulis b ← V e r i f k ( m , t ) .$(k,m,t)$$\mathsf{Verif}$$b$$b \gets \mathsf{Verif}_k(m,t)$

Diperlukan bahwa untuk semua $k$ keluaran oleh $\mathsf{Gen}$ dan semua $m \in \{0,1\}^*$ , kami memiliki $\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$ .

Persyaratan keamanan didefinisikan melalui percobaan berikut, antara penantang dan musuh $A$ :

1. $k \gets \mathsf{Gen}(1^n)$ .
2. $(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$ .
3. Biarkan $Q$ menunjukkan himpunan semua pertanyaan yang diminta $A$ ke oracle-nya.
4. Output percobaan didefinisikan menjadi 1 jika dan hanya jika:
   • $\mathsf{Verif}_k(m, t) = 1$, dan
   • $m \notin Q$ .

MAC dianggap aman jika probabilitas bahwa hasil percobaan 1 diabaikan dalam $n$ .

Eksperimen di atas menyerupai eksperimen "plaintext terpilih" terhadap skema enkripsi simetris, di mana musuh dapat memperoleh ciphertext yang sesuai dengan pesan pilihannya. Dalam serangan yang lebih kuat, yang disebut serangan "ciphertext yang dipilih", musuh juga diizinkan mengakses oracle dekripsi.

Jadi, pertanyaan saya adalah:

Apa yang terjadi jika kita mengizinkan musuh MAC juga mengakses oracle verifikasi? Dengan kata lain, bagaimana jika jalur 2 percobaan diganti dengan yang berikut:

.$(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$

Perhatikan bahwa dalam percobaan baru, hanya mencakup kueri A yang diminta dari oracle M A C k .$Q$$A$$\mathsf{MAC}_k$

Jika ada kode otentikasi pesan aman sesuai dengan salah satu definisi,
maka ada sistem yang definisi buku mengklasifikasikan sebagai
kode otentikasi pesan aman dan definisi Anda diklasifikasikan sebagai tidak aman.

Membiarkan $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.02 in}\rangle\:$ amankan menurut definisi mana pun. $\;\;$Karena definisi buku
lebih lemah dari definisi Anda, maka definisi tersebut secara khusus aman menurut definisi buku.
Memperbaiki beberapa efisien-komputasi dan efisien-invertable coding dari
pasangan memerintahkan, misalnya, concatenating efisien-komputasi dan
efisien-dibalik representasi prefix bebas dari masuknya kiri ke entri yang tepat.
Biarkan Bekerja dengan memasangkan output MAC k dengan string kosong. Biarkan Verif $\operatorname{MAC}_k\hspace{-0.09 in}'$$\operatorname{MAC}_k$
Terima jika dan hanya jika [[ Verif k akan menerima pesan dan entri kiri tag] dan [entri kanan input adalah awalan k ]].$\operatorname{Verif}_k\hspace{-0.09 in}'$$\operatorname{Verif}_k$
$k$$\;\;$ $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ jelas efisien dan memenuhi persyaratan. $\;\;\;$Karena [memasangkan tag dengan string kosong untuk]
dan [mengambil entri kiri dari output], musuh yang layak menyerang
definisi buku tentang keamanan$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$tidak dapat memiliki probabilitas yang tidak dapat diabaikan
untuk melanggar definisi keamanan buku ini$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.03 in}\rangle\:$, $\:$
definisi buku juga mengklasifikasikan$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$sebagai kode otentikasi pesan aman.
Namun, setelah musuh mendapatkan setiap valid pasangan pesan-tag untuk ,$k$$\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\operatorname{length}(k)\hspace{-0.04 in}+\hspace{-0.05 in}1)\:$
pertanyaan adaptif ke Cukup untuk belajar$\operatorname{Verif}_k\hspace{-0.09 in}'$$k\hspace{.01 in}$, yang akan memungkinkan pemalsuan pada pesan apa pun.
Jadi definisi Anda mengklasifikasikan$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ tidak aman. $\;\;\;$ QED

Versi unforgeability yang kuat dari kedua definisi itu setara.

(Versi "strong unforgeability" diperoleh dengan mengganti dengan set Q + yang diberikan dalam kalimat saya berikutnya, dan yang diperlukan untuk membuat konstruksi enkripsi-lalu-mac memberikan integritas ciphertext dan menjadi IND-CCA2.)$Q$
$Q^+$

Inisialisasi $\:Q^+\:$ sebagai set kosong, dan taruh $\: \langle m,\hspace{-0.03 in}t\rangle \:$ ke setiap kali MAC k mengeluarkan t pada kueri m . Tentukan query untukmencobajika dan hanya jika mengirimkan ke$\:Q^+$
$\operatorname{MAC}_k$$t$$m$

$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ sepasang yang sudah dimasukkan $\:Q^+\:$.
Tetapkan permintaan untuk mencoba lebih awal jika dan hanya jika ia mencoba dan
tidak datang setelah permintaan mencoba itu$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$diterima.


$B^{\hspace{.02 in}\operatorname{MAC}_k(\cdot)}\hspace{-0.02 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right) \;$berinteraksi dengan sebagai berikut:$A$

Menggunakan kurang dari bit acak, pilih$\hspace{.02 in}j$$\;\; r \: \in \: \left\{\hspace{-0.03 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.02 in}\right\} \;\;$hampir seragam.
"Forward" semua 's$A$$\:\operatorname{MAC}_k(\cdot)\:$ pertanyaan ke $\:\operatorname{MAC}_k(\cdot)\:$dan berikan
output oracle itu (aktual) ke , beri 0 sebagai output pada pertama hingga $A$$0$ mencoba kueri, dan memberikan 1 sebagai output dari$r\hspace{-0.04 in}-\hspace{-0.05 in}1$
$1$$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$pada pertanyaan untuk itu yang tidak mencoba.
Jika$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$membuat -th queri mencoba, lalu menampilkan apa itu queri. Jika$r$
$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$memberikan output, lalu memberikan output yang sama.


Dengan keacakan semuanya diperbaiki, jika$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ membuat persis $\:r\hspace{-0.03 in}-\hspace{-0.04 in}1\:$kueri yang mencoba lebih awal dan berhasil dalam versi eksperimen yang tidak dapat dikalahkan yang kuat, lalu
$B^{\hspace{.02 in}A,\operatorname{MAC}_k(\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right)\:$ berhasil dalam percobaan buku versi unforgeability kuat.

Oleh karena itu adalah pengurangan garis lurus yang konstruktif dari keberhasilan dalam versi ketakberantaraan yang kuat dari percobaan Anda dengan probabilitas setidaknya ϵ dengan cara yang membuat kurang dari q kueri yang mencoba lebih awal, untuk berhasil dalam versi yang tidak dapat dikalahkan yang kuat dari eksperimen buku dengan probabilitas lebih besar dari$B$$\epsilon$
$q$
$\;\; \left(\hspace{-0.03 in}\frac1q\hspace{-0.03 in}-\hspace{-0.03 in}\frac{q}{2\text{^}j}\hspace{-0.04 in}\right)\cdot \epsilon \;\;\;$.
menggunakan kurang dari$B$$\hspace{.02 in}j$
$q$
$\:\operatorname{MAC}_k\:$
$\operatorname{MAC}_k\hspace{-0.02 in}$ini$\:$ menanggapi permintaan itu], dan hanya memiliki kompleksitas tambahan sepele di luar itu.

$\operatorname{Verif}_k$