Beberapa pertanyaan tentang permutasi bangunan dari fungsi boolean
Saya telah melihat banyak contoh fungsi boolean digunakan sebagai permutasi.
Misalnya fungsi Keccak Chi: 2.3.1 :
dari https://keccak.team/figures.html
Atau sebagai rumus: untuk $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ dengan indeks yang dihitung modulo 5
Pertanyaan pertama adalah, apa alasan (atau bukti) mengapa ini permutasi?
Yang kedua, terkait: Apa saja propertinya, fungsi boolean harus memenuhi sehingga menghasilkan permutasi?
Dan sekarang tentang kebalikan dari permutasi semacam itu.
Apakah ada metode / algoritma umum untuk menemukan kebalikan dari konstruksi seperti itu?
Juga, apa faktor utama yang berkontribusi untuk kompleksitas invers (jumlah variabel, derajat aljabar, dll.)?
Dan jika metode seperti itu diterapkan pada input yang lebih besar - katakanlah $i=\{0..127\}$, apakah invers lebih sulit untuk dihitung, jika fungsinya hanya memiliki sedikit (seperti 3 untuk Chi) atau banyak, katakanlah 128, variabel masukan?
Setiap jawaban / petunjuk dihargai.
Jawaban
Pertanyaan aljabar umum memiliki banyak segi dan bisa sangat rumit. Beberapa bergantung pada ruang vektor, beberapa pada properti bidang ekstensi.
Seperti yang disebutkan dalam komentar, memeriksa properti bisa lebih sederhana.
Saya menjawab pertanyaan terkait Contoh fungsi Boolean multi output bit balanced
Artikel Nyberg menyebutkan ada
K. Nyberg, Pemetaan seragam yang berbeda untuk kriptografi , 1993 dan
K Nyberg, S-box nonlinier sempurna , 1992
keduanya dapat ditemukan dengan mudah di google scholar.
Sunting : Keccak$\chi$ peta $\{0,1\}^5$ untuk dirinya sendiri.
saya akan gunakan $a_i$ sebagai masukan dan $A_i$ sebagai variabel keluaran seperti pada pertanyaan yang diedit.
Menghitung indeks modulo 5, jika tidak ada $i$ seperti yang $(a_i,a_{i+2})=(0,1)$ kemudian $\chi$memiliki titik tetap untuk masukan itu. Membiarkan$W=\{i: (a_i,a_{i+2})=(0,1)\},$ kemudian pemetaan umum hanya membalik bit-bit yang dimiliki $i.$
Perhatikan bahwa set $J_i,J_j$ dimana $J_i=\{i,i+2\}$ terputus-putus kecuali saat $j=i+2$ atau $i=j+2.$Jadi tidak ada ambiguitas untuk menentukan invers kecuali kita berada dalam kasus khusus ini, sehingga inversnya ada kecuali dalam kasus khusus ini. Tetapi bahkan dalam kasus ini polanya$(a_i,a_{i+2},a_{i+4})$ yang mengakibatkan bitflip tidak ambigu.
Jika $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ kemudian $a_{i+1}$ akan dibalik tetapi tidak $a_{i+3}$. Begitu$A_{i+1}=1\oplus a_{i+1},$ dan $A_{i+3}=a_{i+3}.$
Jika $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ kemudian $a_{i+1}$ akan dibalik tetapi belum tentu $a_{i+3}$, itu akan bergantung pada nilai $a_{i+6}=a_{i+1}$. Tetapi hal itu tidak dipengaruhi oleh argumen sebelumnya sejak saat itu$J_i$ dan $J_j$ terputus-putus jika $i=j+1\pmod 2.$
Jadi ada pemetaan terbalik yang unik.
Catatan : Secara umum, beralih antara formulasi bidang ekstensi "basis independen" dari permutasi vs permutasi vektor bit "bergantung basis" hampir tidak mudah. Saya tidak melihat formulasi lapangan ekstensi independen dasar langsung untuk permutasi ini, dan seperti yang ditunjukkan dalam komentar untuk pertanyaan formulasi tersebut diperoleh (katakanlah) dengan interpolasi Lagrange, bisa sangat rumit dan tingkat tinggi.
Itu $\chi$fungsi didefinisikan dan dianalisis dalam Joan Daemen Ph.D. Tesis
- Strategi Desain Cipher dan Fungsi Hash berdasarkan kriptanalisis linier dan diferensial, 1995
Bab 6: Shift-Invariant Transformations (SIT) adalah tempat teori tersebut disebutkan. Saya akan memberikan sekilas tentang itu (banyak definisi dan hasil).
Properti SIT yang membuatnya berguna;
- Di perangkat keras, transformasi ini dapat diimplementasikan sebagai array yang saling berhubungan dari "prosesor" keluaran 1-bit yang identik.
- Shift-invariance memastikan bahwa beban komputasi terdistribusi secara optimal.
- Dalam perangkat lunak, keteraturannya memungkinkan implementasi yang efisien dengan menggunakan operasi logika bitwise.
- Selain itu, transformasi biner shift-invariant dapat ditentukan dengan satu fungsi Boolean.
SIT sangat terkait dengan automata seluler terbatas yang berfokus pada struktur dan pola jangka panjang dari waktu ke waktu, pekerjaan ini berkonsentrasi pada aspek invertibilitas jangka pendek dan sifat propagasi dan korelasi lokal.
Definisi 6.1: Transformasi$\phi: \mathcal{A} \to \mathcal{A}$adalah shift-invariant if
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ dimana $\mathcal{A}$ adalah semua kemungkinan keadaan.
Kemudian itu mendefinisikan peta lokal di mana gambar hanya bergantung pada beberapa input.
Teorema 6.1 (D. Richardson) Jika terjadi transformasi$\phi$ dengan terbatas $\nu$ bisa dibalik, lalu kebalikannya $\phi^{−1}$ adalah transformasi shift-invariant dengan finite $\nu$.
Dimana $\nu$mendefinisikan lingkungan, lihat 6.3 Peta Lokal . Teorema ini tidak memberikan konstruksi invers secara eksplisit.
Bagian 6.6 Transformasi nonlinier dengan terbatas $\nu$ adalah tempat aksi dimulai.
Di sini peta lokal ditentukan oleh serangkaian pola, yang disebut lanskap pelengkap (CL). Nilai sebuah komponen akan menjadi lengkap jika lingkungannya mengambil salah satu dari pola-pola ini. Lansekap adalah pola yang terdiri dari simbol$1, 0$, dan $\textbf{-}$ menunjukkan "tidak peduli", diposisikan relatif terhadap asal, dilambangkan dengan $∗$. Dalam konteks ini, keadaan semua-nol akan dilambangkan dengan$0^*$ dan status all-one oleh $1^*$.
Kebalikan dari $\chi$dibahas di bagian invertibilitas lokal dan global yang membutuhkan teori yang lebih dalam. Bacaan yang bagus untuk dipelajari jika Anda mau.
Jadi, Seperti yang saya katakan di komentar, seseorang dapat mencari semua kemungkinan permutasi untuk melihat properti yang diinginkan, atau melihat teori seperti yang dilakukan Daemen. Mereka menggunakan teori ini bertahun-tahun kemudian dalam konstruksi Sponge$\chi$ adalah satu-satunya bagian non-linier dari SHA-3.
Karena pertanyaan pertama saya telah terjawab secara detail di jawaban kodlu dan kelalaka, saya ingin membagikan hasil yang saya kumpulkan pada pertanyaan kedua saya sejak memposting:
Apa sajakah properti yang harus dipenuhi oleh fungsi boolean sehingga menghasilkan permutasi?
Selama banyak pembacaan tambahan, saya menemukan, bahwa ini tampaknya merupakan properti yang baik (tetapi tidak banyak diketahui). Misalnya dinyatakan dan dibuktikan dalam Fungsi Boolean Vektor untuk Kriptografi bab 2.3.1 sebagai Proposisi 2:
Sebuah (n, m) -fungsi diseimbangkan jika dan hanya jika fungsi komponennya seimbang, yaitu jika dan hanya jika, untuk setiap bukan nol v $F^2_m$, fungsi Boolean v · F seimbang.
dengan fakta tambahan dari bab 2.3:
balanced (n, n) -functions adalah permutasi aktif $F^2_n$
Jadi, fungsi (n, n) adalah permutasi, jika dan hanya jika seimbang menurut definisi di atas.
Dengan kata lain, setiap fungsi komponen harus seimbang, serta kemungkinan kombinasi fungsi komponen, termasuk. semua fungsi sekaligus, harus seimbang.
Omong-omong, properti ini juga dinyatakan, kurang jelas, dalam Strategi Desain Fungsi Cipher dan Hash berdasarkan kriptanalisis linier dan diferensial, Teorema 5.1 1995
Ini juga berarti, memeriksa properti ini untuk kasus umum untuk fungsi yang lebih besar, misalnya lebar 64bit (n = 64), tidak dapat dilakukan karena memerlukan pemeriksaan keseimbangan untuk 2 ^ 64 - 1 kombinasi yang berbeda (untuk masing-masing 2 ^ 64 kemungkinan input) . Jadi beberapa trik atau jalan pintas kemungkinan akan dibutuhkan.