불 함수

3. 표현

• 진리표: 모든 가능한 인수의 값에 대한 값을 명시적으로 나열한다.
• 마르캉드 다이어그램: 2차원 그리드에 배열된 진리표 값 (카르노 맵에 사용)
• 이진 결정 다이어그램: 이진 트리의 맨 아래에 진리표 값을 나열한다.
• 벤 다이어그램: 평면의 영역을 색칠하여 진리표 값을 묘사한다.

• 부정 정규형: 인수와 보수의 AND 및 OR의 임의의 혼합
• 선언적 정규형: 인수와 보수의 AND의 OR
• 결합적 정규형: 인수와 보수의 OR의 AND
• 정규형: 함수를 고유하게 식별하는 표준화된 공식:
• 대수적 정규형 또는 제갈킨 다항식: 인수(보수 허용 안 함)의 AND의 XOR
• ''전체''(표준) 선언적 정규형: 각 인수 또는 보수(민텀)를 포함하는 AND의 OR
• ''전체''(표준) 결합적 정규형: 각 인수 또는 보수(맥스텀)를 포함하는 OR의 AND
• 블레이크 정규형: 함수의 모든 소수 함의자의 OR

• 명제 방향 비순환 그래프
• 디지털 회로 논리 게이트 다이어그램, 불 대수 회로
• AND-인버터 그래프: AND와 NOT만 사용

4. 분석

불 함수는 다음과 같은 속성들을 가질 수 있다.^[6]

• 상수: 인수에 관계없이 항상 참 또는 항상 거짓이다.
• 단조: 모든 인수 값의 조합에 대해 인수를 거짓에서 참으로 변경하면 출력만 거짓에서 참으로 바뀔 수 있으며 참에서 거짓으로 바뀔 수는 없다. 특정 변수에 대한 변경에 대해 단조이면 해당 함수는 해당 변수에 대해 단항이라고 한다.
• 선형: 각 변수에 대해 해당 변수의 값을 반전하면 진리값에 항상 차이가 있거나 전혀 차이가 없다. ( 패리티 함수 ).
• 대칭: 값은 인수의 순서에 의존하지 않는다.
• 1회 읽기: 논리곱, 논리합, 부정으로 각 변수의 단일 인스턴스로 표현할 수 있다.
• 균형: 진리표에 0과 1의 수가 동일하게 포함된 경우. 함수의 해밍 가중치는 진리표에서 1의 개수이다.
• 벤트: 미분값이 모두 균형을 이룬다(자기 상관 스펙트럼이 0).
• ''m''차 상관 무관: 최대 ''m''개의 인수 중 모든 (선형) 조합과 출력이 상관관계가 없는 경우.
• 회피: 함수의 평가에 항상 모든 인수의 값이 필요한 경우
• 불 함수는 (합성으로) 임의의 불 함수를 생성하는 데 사용할 수 있는 경우 ''셰퍼 함수''이다.( 기능적 완전성 참조)
• 함수의 ''대수 차수''는 대수적 정규 형식에서 가장 높은 차수의 단항식의 차수이다.

5. 효율적 표현

복잡한 불 함수를 효율적으로 표현하기 위한 방법들은 다음과 같다:^[1]

• 진리표: 모든 가능한 인수의 값에 대한 값을 명시적으로 나열한다.
• 마르캉드 다이어그램: 2차원 그리드에 배열된 진리표 값 (카르노 맵에 사용)
• 이진 결정 다이어그램: 이진 트리의 맨 아래에 진리표 값을 나열
• 벤 다이어그램: 평면의 영역을 색칠하여 진리표 값을 묘사한다.

• 부정 정규형: 인수와 보수의 AND 및 OR의 임의의 혼합
• 선언적 정규형: 인수와 보수의 AND의 OR
• 결합적 정규형: 인수와 보수의 OR의 AND
• 정규형: 함수를 고유하게 식별하는 표준화된 공식:
• 대수적 정규형 또는 제갈킨 다항식: 인수(보수 허용 안 함)의 AND의 XOR
• ''전체''(표준) 선언적 정규형: 각 인수 또는 보수(민텀)를 포함하는 AND의 OR
• ''전체''(표준) 결합적 정규형: 각 인수 또는 보수(맥스텀)를 포함하는 OR의 AND
• 블레이크 정규형: 함수의 모든 소수 함의자의 OR

• 명제 방향 비순환 그래프
• 디지털 회로 논리 게이트 다이어그램, 불 대수 회로
• AND-인버터 그래프: AND와 NOT만 사용

• 이진 결정 다이어그램 (BDD)
• 부정 표준형
• 명제 방향 비순환 그래프 (PDAG)

여기서 $a\_0,\; a\_1,\; \backslash ldots,\; a\_\{1,2,\backslash ldots,n\}\; \backslash in\; \backslash \{0,1\backslash \}^*$이다.^[1]

따라서 열 $a\_0,a\_1,\backslash ldots,a\_\{1,2,\backslash ldots,n\}$의 값의 열도 부울 함수를 유일하게 나타낸다. 부울 함수의 대수적 차수는 하나의 (AND) 항에 나타나는 $x\_i$의 개수로 나타낸다. 즉, $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_3$의 차수는 1(선형)이고, $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_1x\_2x\_3$의 차수는 3(입방)이다.^[1]

6. 간소화

불 함수를 간소화하는 방법은 다음과 같다.

• 컷 앤 트라이 법: 불 대수의 정의를 이용하여 효율적인 표현으로 변형한다.
• 벤 다이어그램: 벤 다이어그램을 이용하여 시각적으로 알기 쉬운 표현으로 한다. 이는 인간의 직관에 의한 것으로, "변환하는 방법"이라고 할 수는 없다.
• 카르노 맵: 카르노 맵을 이용하여 효율적인 표현으로 변형한다.
• 콰인-맥클러스키 방법: 콰인-맥클러스키 방법을 이용하여 효율적인 표현으로 변형한다. 계산기로 간소화하는 데 적합하다.

7. 파생 함수

불 함수는 불의 전개 정리를 사용하여 긍정적이고 부정적인 ''섀넌'' ''코팩터''(섀넌 전개)로 분해될 수 있으며, 이는 인수를 (0 또는 1로) 고정하여 얻은 (k-1)항 함수이다. 입력 집합(선형 부분 공간)에 선형 제약을 가하여 얻은 일반적인 (k-항) 함수를 ''부분 함수''라고 한다.^[7]

함수의 ''불 미분''은 선택한 입력 변수에 함수의 출력이 민감할 때 참이 되는 (k-1)항 함수이다. 이는 두 개의 해당 코팩터의 XOR이다. 미분과 코팩터는 리드-뮬러 전개에 사용된다. 이 개념은 x와 x + dx에서의 함수의 차이(XOR)로 얻은 dx 방향의 k-항 미분으로 일반화될 수 있다.^[7]

불 함수의 ''뫼비우스 변환''(또는 ''불-뫼비우스 변환'')은 모노미얼 지수 벡터의 함수로, 해당 다항식(대수적 정규형)의 계수 집합이다. 이는 자기 역변환이다. 이는 고속 푸리에 변환과 유사한 버터플라이 알고리즘("''고속 뫼비우스 변환''")을 사용하여 효율적으로 계산할 수 있다.^[8] ''일치'' 불 함수는 뫼비우스 변환과 같으며, 즉 진리표(민텀) 값이 대수적(모노미얼) 계수와 같다.^[9] k개의 인수를 갖는 일치 함수는 2^2(k−1)개가 있다.^[10]

8. 암호학적 분석

불 함수는 암호학, 특히 대칭키 암호 설계에서 중요한 역할을 한다.

불 함수의 ''월시 변환''은 선형 함수(월시 함수)로의 분해 계수를 제공하는 k-진 정수 값 함수이며, 이는 푸리에 변환에 의한 실수 값 함수의 조화 분해와 유사하다. 그 제곱은 ''전력 스펙트럼'' 또는 ''월시 스펙트럼''이다. 단일 비트 벡터의 월시 계수는 해당 비트와 불 함수의 출력 간의 상관 관계를 측정하는 척도이다. 최대 (절대값) 월시 계수는 함수의 ''선형성''이라고 한다.^[7] 모든 월시 계수가 0인 비트의 최대 개수(차수) (즉, 하위 함수가 균형을 이룸)는 ''복원력''이라고 하며, 해당 차수에 대해 함수는 상관 면역이라고 한다.^[7] 월시 계수는 선형 암호 분석에서 핵심적인 역할을 한다.

불 함수의 ''자기 상관''은 입력의 특정 변경 집합과 함수 출력 간의 상관 관계를 제공하는 k-진 정수 값 함수이다. 주어진 비트 벡터의 경우 해당 방향의 도함수의 해밍 가중치와 관련이 있다. 최대 자기 상관 계수(절대값)는 ''절대 지표''라고 한다.^[6][7] 특정 비트 수에 대해 모든 자기 상관 계수가 0인 경우 (즉, 도함수가 균형을 이룸) 함수는 해당 차수에 대해 ''전파 기준''을 만족한다고 하며, 모두 0인 경우 함수는 벤트 함수이다.^[11] 자기 상관 계수는 차분 암호 분석에서 핵심적인 역할을 한다.

불 함수의 월시 계수와 자기 상관 계수는 비너-킨친 정리와 동등한 관계를 가지며, 이는 자기 상관과 전력 스펙트럼이 월시 변환 쌍임을 나타낸다.^[7]

이러한 개념은 출력 비트(''좌표'')를 개별적으로 고려하거나, 더 자세하게는 출력 비트의 모든 선형 함수의 집합, 즉 해당 ''구성 요소''를 살펴봄으로써 ''벡터'' 불 함수로 자연스럽게 확장될 수 있다.^[12] 구성 요소의 월시 변환 집합은 '''선형 근사표''' (LAT)^[13][14] 또는 ''상관 행렬''로 알려져 있으며,^[15][16] 입력 및 출력 비트의 다양한 선형 조합 간의 상관 관계를 설명한다. 구성 요소의 자기 상관 계수 집합은 ''자기 상관표''이며,^[14] 구성 요소의 월시 변환을 통해 입력 및 출력 비트의 차이 간의 상관 관계를 나열하는 더 널리 사용되는 ''차분 분포표'' (DDT)^[13][14]와 관련이 있다(참고: S-box).

9. 실수 다항식 형태

모든 불 함수 $f(x):\; \backslash \{0,1\backslash \}^n\; \backslash rightarrow\; \backslash \{0,1\backslash \}$는 $\backslash mathbb\{R\}^n$의 다중선형 다항식으로 고유하게 확장(보간)될 수 있으며, 이는 진리표 값에 라그랑주 다항식의 지표 다항식을 곱하여 합산하여 구성된다.

:$$f^*(x)\; =\; \backslash sum\_\{a\; \backslash in\; \{\backslash \{0,1\backslash \}\}^n\}\; f(a)\; \backslash prod\_\{i:a\_i=1\}\; x\_i\; \backslash prod\_\{i:a\_i=0\}\; (1-x\_i)$$

예를 들어, 이진 XOR 함수 $x\; \backslash oplus\; y$의 확장은 다음과 같다.

:$$0(1-x)(1-y)\; +\; 1x(1-y)\; +\; 1(1-x)y\; +\; 0xy$$

이것은 다음과 같다.

:$$x\; +\; y\; -2xy$$

다른 예로는 부정($1-x$), AND($xy$) 및 OR($x\; +\; y\; -\; xy$)가 있다. 모든 피연산자가 독립적일 때(변수를 공유하지 않음) 함수의 다항식 형태는 불리언 수식에서 연산자의 다항식을 반복적으로 적용하여 찾을 수 있다. 계수를 모듈러 산술로 계산하면 대수적 정규형(제갈킨 다항식)을 얻는다.

다항식의 계수에 대한 직접적인 표현은 적절한 미분을 통해 파생될 수 있다.

:

f^*(01) & = & (\partial_1f^*)(00) & = & -f(00) + f(01) \\

f^*(10) & = & (\partial_2f^*)(00) & = & -f(00) + f(10) \\

f^*(11) & = & (\partial_1\partial_2f^*)(00) & = & f(00) -f(01)-f(10)+f(11) \\

\end{array}

이는 비트 벡터의 뫼비우스 변환으로 일반화된다.

:$$f^*(m)\; =\; \backslash sum\_\{a\; \backslash subseteq\; m\}\; (-1)^$$