ブール関数から順列を構築することに関するいくつかの質問
順列として使用されているブール関数の例を複数見てきました。
たとえば、Keccak Chi：2.3.1関数：
から https://keccak.team/figures.html
または式として： $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ 5を法として計算されたインデックスを使用
最初の質問は、これが順列である理由（または証明）は何ですか？
2番目の関連するもの：プロパティは何ですか、ブール関数はそれが順列をもたらすことを満たさなければなりませんか？
そして今、そのような順列の逆について。
そのような構造の逆を見つけるための一般的な方法/アルゴリズムはありますか？
また、逆数の複雑さの主な要因は何ですか（変数の数、代数的次数など）？
そして、そのような方法がより大きな入力に適用される場合-言う $i=\{0..127\}$、関数に入力変数が少数（Chiの3のように）または多数、たとえば128の場合、逆数の計算はより困難ですか？
任意の回答/ポインタをいただければ幸いです。
回答
一般的な代数的質問は多面的であり、非常に複雑になる可能性があります。ベクトル空間に依存するものもあれば、拡大体のプロパティに依存するものもあります。
コメントで述べたように、プロパティのチェックはもっと簡単にできます。
関連する質問に答えましたマルチ出力ビット平衡ブール関数の例
そこに言及されているナイバーグの記事は
K. Nyberg、暗号化のための差別的に均一なマッピング、1993年および
K Nyberg、完全な非線形Sボックス、1992年
どちらもGoogleScholarで簡単に見つけることができます。
編集：keccak$\chi$ マップ $\{0,1\}^5$ それ自体に。
私が使用します $a_i$ 入力としておよび $A_i$ 編集された質問のように出力変数として。
ない場合は、5を法とするインデックスのカウント $i$ そのような $(a_i,a_{i+2})=(0,1)$ その後 $\chi$その入力の固定小数点があります。しましょう$W=\{i: (a_i,a_{i+2})=(0,1)\},$ 次に、一般的なマッピングは、に属するビットを反転するだけです。 $i.$
セットに注意してください $J_i,J_j$ どこ $J_i=\{i,i+2\}$ 次の場合を除いて互いに素である $j=i+2$ または $i=j+2.$したがって、この特別な場合を除いて、逆行列を決定するためのあいまいさはありません。したがって、この特別な場合を除いて、逆行列が存在します。しかし、この場合でもパターン$(a_i,a_{i+2},a_{i+4})$ その結果、ビットフリップが明確になります。
場合 $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ その後 $a_{i+1}$ 反転しますが、反転しません $a_{i+3}$。そう$A_{i+1}=1\oplus a_{i+1},$ そして $A_{i+3}=a_{i+3}.$
場合 $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ その後 $a_{i+1}$ 反転しますが、必ずしもそうとは限りません $a_{i+3}$、それはの値に依存します $a_{i+6}=a_{i+1}$。しかし、そのビットは前の議論の影響を受けません$J_i$ そして $J_j$ 次の場合は互いに素です $i=j+1\pmod 2.$
したがって、一意の逆マッピングが存在します。
備考：一般に、順列の「基底に依存しない」拡大体の定式化と「基底に依存する」ビットベクトル順列の間を行き来するのは簡単ではありません。私はこの順列の即時基底の独立した拡大体の定式化を見ていません、そして質問へのコメントで指摘されているように、ラグランジュ補間によって（例えば）得られたそのような定式化は非常に複雑で高度です。
ザ・ $\chi$関数は、Joan DaemenPh.Dで定義および分析されています。定説
- 線形解読法と差分解読法に基づく暗号解読法とハッシュ関数の設計戦略、1995年
第6章：シフト不変変換（SIT）は、理論が言及されている場所です。それを垣間見ることができます（たくさんの定義と結果）。
それらを有用にするSITの特性。
- ハードウェアでは、これらの変換は、同一の1ビット出力「プロセッサ」の相互接続された配列として実装できます。
- シフト不変性により、計算負荷が最適に分散されます。
- ソフトウェアでは、それらの規則性により、ビット単位の論理演算を採用することで効率的な実装が可能になります。
- さらに、バイナリシフト不変変換は、単一のブール関数で指定できます。
SITは、時間の経過に伴う長期的な構造とパターンに焦点を当てた有限セルオートマトンと非常に関連があり、この作業は、可逆性と局所的な伝播および相関特性の短期的な側面に焦点を当てています。
定義6.1：変換$\phi: \mathcal{A} \to \mathcal{A}$次の場合、シフト不変です
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ どこ $\mathcal{A}$ すべての可能な状態です。
次に、画像が一部の入力のみに依存するローカルマップを定義しました。
定理6.1（D。リチャードソン）変換の場合$\phi$ 有限で $\nu$ は可逆であり、その逆 $\phi^{−1}$ は有限のシフト不変変換です $\nu$。
どこ $\nu$近隣を定義します。6.3ローカルマップを参照してください。この定理は、逆の構造を明示的に提供していません。
セクション6.6有限の非線形変換 $\nu$ アクションが開始される場所です。
ここで、ローカルマップは、補完ランドスケープ（CL）と呼ばれる一連のパターンによって指定されます。コンポーネントの値は、その近隣がこれらのパターンの1つをとる場合に補完されます。風景はシンボルからなるパターンです$1, 0$、および $\textbf{-}$ 原点を基準にして配置された「ドントケア」を意味し、 $∗$。このコンテキストでは、すべてゼロの状態は次のように示されます。$0^*$ とオールワン状態 $1^*$。
の逆 $\chi$より深い理論を必要とするローカルおよびグローバルの可逆性のセクションで話されています。必要に応じて学ぶための良い読み物。
したがって、コメントで述べたように、目的のプロパティを確認するために可能なすべての順列を探すか、Daemenが行ったように理論を調べることができます。彼らはこの理論を数年後のスポンジ構造で使用しました。$\chi$ SHA-3の唯一の非線形部分です。
私の最初の質問はkodluとkelalakaの回答で詳細に回答されているので、投稿してから2番目の質問で収集した結果を共有したいと思いました。
プロパティは何ですか、ブール関数はそれが順列をもたらすことを満たさなければなりませんか？
私が発見した多くの追加の読書の間に、これはよく知られている（しかし広くはない）特性のようです。たとえば、暗号化のためのベクトルブール関数の第2.3.1章で、命題2として述べられ、証明されています。
（n、m）関数は、そのコンポーネント関数が平衡化されている場合にのみ、つまり、すべての非ゼロv∈に対して平衡化されている場合にのみ平衡化されます。 $F^2_m$、ブール関数v・Fはバランスが取れています。
2.3章からの追加の事実：
バランスの取れた（n、n）-関数は上の順列です $F^2_n$
したがって、（n、n）関数は、上記の定義に従ってバランスが取れている場合に限り、順列です。
言い換えると、すべてのコンポーネント機能と、コンポーネント機能の可能な組み合わせのバランスをとる必要があります。すべての機能を一度にバランスさせる必要があります。
ちなみに、この特性は、1995年の定理5.1の線形解読法と差分解読法に基づく暗号解読法とハッシュ関数の設計戦略にも記載されています。
これは、64ビット幅（n = 64）などのより大きな関数の一般的なケースでこのプロパティをチェックすることは、2 ^ 64-1の異なる組み合わせ（それぞれ2 ^ 64の可能な入力）のバランスをチェックする必要があるため、実行できないことも意味します。 。したがって、いくつかのトリックやショートカットが必要になる可能性があります。