Boole fonksiyonlarından permütasyon oluşturma hakkında bazı sorular
Bir permütasyon olarak kullanılan birçok boole işlevi örneği gördüm.
Örneğin Keccak Chi: 2.3.1 işlevi:
itibaren https://keccak.team/figures.html
Veya formül olarak: $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ indeksler hesaplanmış modulo 5 ile
İlk soru, bunun neden bir permütasyon olduğunun mantığı (veya kanıtı) nedir?
İkincisi, ilgili olanı: Özellikler nelerdir, boole fonksiyonu bir permütasyonla sonuçlandığından emin olmalıdır?
Ve şimdi böyle bir permütasyonun tersi ile ilgili olarak.
Böyle bir yapının tersini bulmak için herhangi bir genel yöntem / algoritma var mı?
Ayrıca, tersin karmaşıklığına katkıda bulunan başlıca faktörler nelerdir (değişken sayısı, cebirsel derece vb.)?
Ve böyle bir yöntem daha büyük bir girdiye uygulanırsa - diyelim ki $i=\{0..127\}$, is the inverse more difficult to calculate, if the function has only a few (like the 3 for Chi) or many, say 128, input variables?
Any answers/pointers are appreciated.
Yanıtlar
The general algebraic question is multifaceted and can be quite complicated. Some depend on vector space, some on extension field properties.
As mentioned in the comments checking the property can be simpler.
I answered a related question Examples of multi output bit balanced Boolean functions
Nyberg’s articles mentioned there are
K. Nyberg, Differentially uniform mappings for cryptography, 1993 and
K Nyberg, Perfect nonlinear S-boxes, 1992
both easily locatable on google scholar.
Edit: The keccak $\chi$ maps $\{0,1\}^5$ to itself.
I will use $a_i$ as input and $A_i$ düzenlenmiş soruda olduğu gibi çıktı değişkenleri olarak.
Modulo 5 indekslerini sayma, eğer yoksa $i$ öyle ki $(a_i,a_{i+2})=(0,1)$ sonra $\chi$bu girdi için sabit bir noktaya sahiptir. İzin Vermek$W=\{i: (a_i,a_{i+2})=(0,1)\},$ daha sonra genel haritalama sadece ait olan bitleri ters çevirir $i.$
Setlerin $J_i,J_j$ nerede $J_i=\{i,i+2\}$ ne zaman dışında $j=i+2$ veya $i=j+2.$Bu nedenle, bu özel durumda olmadıkça, tersi belirlemek için hiçbir belirsizlik yoktur, bu nedenle bu özel durum dışında tersi vardır. Ancak bu durumda bile desenler$(a_i,a_{i+2},a_{i+4})$ bu, bit çevirmeleriyle net bir şekilde sonuçlanır.
Eğer $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ sonra $a_{i+1}$ çevrilecek ama değil $a_{i+3}$. Yani$A_{i+1}=1\oplus a_{i+1},$ ve $A_{i+3}=a_{i+3}.$
Eğer $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ sonra $a_{i+1}$ çevrilecek ama zorunlu değil $a_{i+3}$, değerine bağlı olacaktır $a_{i+6}=a_{i+1}$. Ancak bu bit, önceki argümandan etkilenmez, çünkü$J_i$ ve $J_j$ ayrıksa $i=j+1\pmod 2.$
Yani benzersiz bir ters eşleme var.
Açıklama : Genel olarak permütasyonların "temelden bağımsız" uzantı alanı formülasyonları ile "tabana bağlı" bit vektör permütasyonları arasında gidip gelmek pek kolay değildir. Bu permütasyon için doğrudan bir temel bağımsız uzantı alanı formülasyonu görmüyorum ve soruya yapılan yorumlarda belirtildiği gibi, Lagrange interpolasyonu ile elde edilen bu tür formülasyonlar (diyelim ki) oldukça karmaşık ve yüksek derecede olabilir.
$\chi$fonksiyon Joan Daemen Ph.D.'de tanımlanmış ve analiz edilmiştir. Tez
- Doğrusal ve diferansiyel kriptanalize dayalı Şifreleme ve Hash Fonksiyonu Tasarım Stratejileri, 1995
Bölüm 6: Kayma-Değişmez Dönüşümler (SIT) teoriden bahsedildiği yerdir. Buna bir göz atacağım (birçok tanım ve sonuç).
SIT'nin onları kullanışlı kılan özellikleri;
- Donanımda, bu dönüşümler birbirine bağlı bir özdeş 1-bit çıktı "işlemciler" dizisi olarak uygulanabilir.
- Kayma değişmezliği, hesaplama yükünün en uygun şekilde dağıtılmasını sağlar.
- Yazılımda, düzenlilikleri bitsel mantıksal işlemleri kullanarak verimli uygulamalara izin verir.
- Dahası, ikili kayma-değişmez dönüşümler tek bir Boole fonksiyonu ile belirtilebilir.
SIT'ler, zaman içinde uzun vadeli yapı ve modele odaklanan sonlu hücresel otomatlarla çok ilgilidir. Bu çalışma, tersinirliğin kısa vadeli yönlerine ve yerel yayılma ve korelasyon özelliklerine odaklanır.
Tanım 6.1: Bir dönüşüm$\phi: \mathcal{A} \to \mathcal{A}$bir öteleme ile değişmez halinde
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ nerede $\mathcal{A}$ tüm olası durumlar.
Daha sonra görüntünün yalnızca bazı girdilere bağlı olduğu yerel haritaları tanımladı.
Teorem 6.1 (D.Richardson) Eğer bir dönüşüm$\phi$ sonlu $\nu$ ters çevrilebilir, sonra tersi $\phi^{−1}$ sonlu bir vardiya-değişmez dönüşümdür $\nu$.
Nerede $\nu$mahalleyi tanımlar, bkz. 6.3 Yerel Haritalar . Bu teorem, açıkça tersinin inşasını sağlamaz.
Bölüm 6.6 Sonlu doğrusal olmayan dönüşümler $\nu$ eylemin başladığı yerdir.
Burada yerel harita, tamamlayıcı manzaralar (CL) adı verilen bir dizi modelle belirlenir. Bir bileşenin değeri, komşuluğu bu modellerden birini alırsa tamamlanır. Manzara, sembollerden oluşan bir kalıptır$1, 0$, ve $\textbf{-}$ "umursamıyorum" anlamına gelen, bir orijine göre konumlandırılmış, $∗$. Bu bağlamda, tamamen sıfır durumu şu şekilde gösterilecektir:$0^*$ ve hepsi bir arada devlet $1^*$.
Tersi $\chi$teoride daha derinlemesine gerektiren yerel ve küresel tersinirlik bölümlerinde konuşulmaktadır. İsterseniz öğrenmek için güzel bir okuma.
Yani, yorumlarda da söylediğim gibi, ya istenen özelliği görmek için tüm olası permütasyonlar aranabilir ya da teoriye Daemen'in yaptığı gibi bakılabilir. Bu teoriyi yıllar sonra Sünger yapımında kullandılar.$\chi$ SHA-3'ün doğrusal olmayan tek parçasıdır.
Kodlu ve kelalaka'nın cevaplarında ilk sorum detaylı olarak cevaplandığı için, yayınladığımdan beri ikinci sorumda topladığım sonuçları paylaşmak istedim:
Özellikler nelerdir, boole işlevi bir permütasyonla sonuçlandığından emin olmalıdır?
Pek çok ek okuma sırasında, bunun iyi bilinen (ancak yaygın olarak değil) bir özellik olduğunu keşfettim. Örneğin , Kriptografi için Vektörel Boolean İşlevleri bölüm 2.3.1'de Önerme 2 olarak belirtilmiş ve kanıtlanmıştır :
Bir (n, m) -fonksiyonu, ancak ve ancak bileşen fonksiyonları dengeli ise, yani sıfır olmayan her v ∈ için ve ancak ve ancak $F^2_m$Boole fonksiyonu v · F dengelidir.
Bölüm 2.3'teki ek gerçekle birlikte:
dengeli (n, n) -fonksiyonlar, $F^2_n$
Öyleyse, bir (n, n) -fonksiyonu, ancak ve ancak yukarıdaki tanıma göre dengelenmişse bir permütasyondur.
Başka bir deyişle, her bileşen işlevi ve ayrıca bileşen işlevlerinin olası herhangi bir kombinasyonu dengelenmelidir. tüm işlevler aynı anda dengelenmelidir.
Bu arada, bu özellik doğrusal ve diferansiyel kriptanalize dayalı Şifreleme ve Karma Fonksiyon Tasarım Stratejileri'nde, 1995 Teorem 5.1'de daha az açık bir şekilde belirtilmiştir.
Bu aynı zamanda, daha büyük işlevler için genel durum için bu özelliğin kontrol edilmesi anlamına gelir, örneğin 64 bit genişlik (n = 64), 2 ^ 64-1 farklı kombinasyon için (her biri 2 ^ 64 olası giriş için) dengeyi kontrol etmeyi gerektireceğinden, uygulanabilir değildir. . Bu nedenle, bazı hileler veya kısayollar gerekli olacaktır.