🏴󠁧󠁢󠁳󠁣󠁴󠁿 👧🏽 🚣 Kecelakaan tidak acak: siapa keluarga dari fungsi pseudo-random (PRFs) 🛃 ♎️ 👜

Pada tahun 1984, Goldreich, Goldwasser, dan Micali meresmikan konsep fungsi pseudo-random dan mengusulkan implementasi PRF berdasarkan generator pseudo-random penggandaan panjang (PRG). Sejak itu, fungsi pseudo-random telah terbukti menjadi abstraksi yang sangat penting yang telah menemukan aplikasi di berbagai bidang, seperti otentikasi pesan dan pembuktian teorema. Dalam artikel ini saya akan membahas:

Apa itu fungsi acak (RF)
Apa itu fungsi pseudo-random (PRF)
Siapa keluargamu ini?
PRF vs. PRG
Apa hubungannya block cipher dengan itu?

Keserampangan

Dari namanya sudah jelas bahwa fungsi pseudo-random adalah sesuatu yang "terlihat" seperti fungsi acak. Nah, apa fungsi acak dalam kasus kita? Untuk memulainya, kami akan membatasi ruang lingkup pertimbangan kami ke fungsi yang menampilkan string nol dan satu dengan panjang string nol dan satu dengan panjang yang sama , yaitu

$\ underbrace {1110 ... 0010} _ {n} \ rightarrow \ underbrace {0100 ... 0011} _ {n} \ Leftrightarrow \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n$

Secara umum, hal ini dapat dihindari dan kita dapat mempertimbangkan pemetaan string dari satu panjang ke string dengan panjang lain, tetapi dalam hal ini kita harus memperhatikan perbedaan dalam dimensi. Selanjutnya, kami memperkenalkan himpunan semua fungsi yang melakukan pemetaan $\ {0,1 \} ^ n \ sisi kanan \ {0,1 \} ^ n$ dan menunjukkannya $\ text {Func} _n$ .

Pertimbangkan kardinalitas himpunan ini. Jelas sekali $| {\ teks {Func} _n} | = 2 ^ {n2 ^ n}$ .

$\ text {Total panjang string berbeda} n \ spasi - \ spasi 2 ^ n.$ $\ text {Untuk menyimpan} 2 ^ n \ text {baris yang Anda butuhkan} n2 ^ n \ text {bits.}$ $\ text {Ini} n2 ^ {n} \ text {bit dan akan menyetel pemetaan yang diinginkan} 2 ^ n \ text {baris.}$ $\ text {Dan akan ada total pemetaan seperti itu} 2 ^ {n2 ^ n}.$

. – $\ text {Func} _n$ . , 2 ^ n - 2 ^ n . ,