부울 함수에서 순열을 만드는 데 대한 몇 가지 질문
순열로 사용되는 부울 함수의 여러 예를 보았습니다.
예를 들어 Keccak Chi : 2.3.1 함수 :
...에서 https://keccak.team/figures.html
또는 공식 : for $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ 모듈로 5로 계산 된 인덱스 포함
첫 번째 질문은 이것이 순열 인 이유 (또는 증거)가 무엇입니까?
두 번째, 관련된 것 : 속성은 무엇입니까? 부울 함수는 순열 결과를 충족해야합니까?
그리고 이제 그러한 순열의 역에 관해서.
그러한 구조의 역을 찾는 일반적인 방법 / 알고리즘이 있습니까?
또한 역의 복잡도 (변수 수, 대수 정도 등)의 주요 원인은 무엇입니까?
그리고 그러한 방법이 더 큰 입력에 적용된다면 $i=\{0..127\}$, 함수에 입력 변수가 적은 경우 (예 : Chi의 경우 3) 또는 많은 (예 : 128) 입력 변수가있는 경우 역을 계산하기가 더 어렵습니까?
모든 답변 / 포인터에 감사드립니다.
답변
일반적인 대수 문제는 다면적이며 매우 복잡 할 수 있습니다. 일부는 벡터 공간에 의존하고 일부는 확장 필드 속성에 의존합니다.
주석에서 언급했듯이 속성을 확인하는 것이 더 간단 할 수 있습니다.
관련 질문에 답변했습니다. 다중 출력 비트 균형 부울 함수의 예
거기에 언급 된 Nyberg의 기사는
K. Nyberg, 암호화를위한 차동 균일 매핑 , 1993 및
K Nyberg, Perfect nonlinear S-boxes , 1992 년
둘 다 Google 학자에서 쉽게 찾을 수 있습니다.
편집 : 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})$ 결과적으로 bitflip이 모호하지 않습니다.
만약 $(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.$
따라서 고유 한 역 매핑이 존재합니다.
비고 : 일반적으로 순열과 "기본 종속"비트 벡터 순열의 "기초 독립"확장 필드 공식 사이를 이동하는 것은 간단하지 않습니다. 나는이 순열에 대한 즉각적인 기초 독립 확장 필드 공식을 보지 못하며, Lagrange 보간에 의해 얻은 이러한 공식은 (예를 들어) 질문에 대한 의견에서 지적했듯이 매우 복잡하고 수준이 높을 수 있습니다.
그만큼 $\chi$기능은 Joan Daemen Ph.D에서 정의하고 분석합니다. 명제
- 선형 및 차등 암호화를 기반으로 한 암호 및 해시 함수 설계 전략, 1995
6 장 : SIT (Shift-Invariant Transformations)는 이론이 언급되는 곳입니다. 나는 그것을 엿볼 것이다 (많은 정의와 결과).
유용하게 만드는 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. Richardson) If a transformation$\phi$ 유한하게 $\nu$ 가역적이면 그 역 $\phi^{−1}$ 유한 한 시프트 불변 변환 $\nu$.
어디 $\nu$이웃을 정의합니다 . 6.3 로컬지도를 참조하십시오 . 이 정리는 역의 구성을 명시 적으로 제공하지 않습니다.
섹션 6.6 유한 한 비선형 변환 $\nu$ 액션이 시작되는 곳입니다.
여기에서 지역지도는 보완 경관 (CL)이라고하는 패턴 집합으로 지정됩니다. 이웃이 이러한 패턴 중 하나를 취하면 구성 요소의 가치가 보완됩니다. 풍경은 기호로 구성된 패턴입니다.$1, 0$, 및 $\textbf{-}$ 원점을 기준으로 배치 된 "관심 없음"을 표시하며 $∗$. 이 컨텍스트에서 모두 0 상태는 다음과 같이 표시됩니다.$0^*$ 그리고 올원 상태 $1^*$.
역 $\chi$더 깊은 이론이 필요한 지역 및 글로벌 가역성 섹션에서 설명합니다. 원하는 경우 배우기 좋은 읽기.
그래서 제가 코멘트에서 말했듯이 원하는 속성을보기 위해 가능한 모든 순열을 찾거나 Daemen이 한 것처럼 이론을 볼 수 있습니다. 그들은 몇 년 후 스폰지 구조에서이 이론을 사용했습니다.$\chi$ SHA-3의 유일한 비선형 부분입니다.
내 첫 번째 질문이 kodlu와 kelalaka의 답변에서 자세히 답변되었으므로 게시 후 두 번째 질문에서 수집 한 결과를 공유하고 싶었습니다.
속성은 무엇입니까? 부울 함수는 순열 결과를 충족해야합니까?
많은 추가 자료를 읽으면서 이것이 잘 알려진 (그러나 널리 알려진 것은 아님) 재산 인 것 같다는 것을 발견했습니다. 예를 들어 암호화를위한 벡터 부울 함수 2.3.1 장에서 명제 2로 언급되고 입증되었습니다 .
(n, m)-함수는 구성 요소 함수가 균형을 이루는 경우에만 균형을 이룹니다. 즉, 0이 아닌 모든 v ∈에 대해 균형을 이룹니다. $F^2_m$, 부울 함수 v · F가 균형을 이룹니다.
2.3 장의 추가 사실 :
균형 잡힌 (n, n) 함수는 $F^2_n$
따라서 (n, n)-함수는 위의 정의에 따라 균형이 잡힌 경우에만 순열입니다.
즉, 모든 구성 요소 기능과 구성 요소 기능의 가능한 조합이 균형을 이루어야합니다. 한 번에 모든 기능이 균형을 이루어야합니다.
그건 그렇고,이 속성은 덜 분명하게도 선형 및 차동 암호화에 기반한 Cipher and Hash Function Design Strategies, 1995 Theorem 5.1 에서 언급됩니다.
이것은 또한 더 큰 기능 (예 : 64 비트 폭 (n = 64))에 대한 일반적인 경우에 대해이 속성을 확인하는 것은 2 ^ 64-1 개의 다른 조합 (각각 2 ^ 64 개의 가능한 입력에 대해)에 대한 균형을 확인해야하기 때문에 실현 가능하지 않음을 의미합니다. . 따라서 몇 가지 트릭이나 단축키가 필요할 수 있습니다.