대수적 정규 형식 (Algebraic Normal Form, ANF)

대수적 정규 형식(ANF)은 부울 함수를 변수들의 곱(AND, 단항식)을 배타적 논리합(XOR)으로 더한 형태로 나타내는 표준 표기법입니다. 2원소 체 GF(2) 위의 다항식으로 보는 것이며, 이 다항식을 지갈킨 다항식(Zhegalkin polynomial)이라고도 부릅니다.

변수가 n개인 부울 함수는 모두 다음과 같은 모양으로 단 한 가지 방식으로 쓸 수 있습니다.

f(x₁, …, x_n) = a₀ ⊕ a₁x₁ ⊕ a₂x₂ ⊕ … ⊕ a₁₂x₁x₂ ⊕ … ⊕ a_12…nx₁x₂…x_n

여기서 계수 a는 0 또는 1이고, 곱은 AND, 덧셈은 XOR입니다. GF(2)에서는 x·x = x이므로 각 변수는 한 단항식 안에 한 번만 나타납니다.

예시

• x OR y = x ⊕ y ⊕ xy
• NOT x = 1 ⊕ x
• x AND y = xy (이미 ANF입니다)

OR처럼 겉보기에는 다른 연산도 ANF로 바꾸면 XOR과 AND만으로 표현됩니다.

표준형이라는 성질

ANF는 표준형(canonical form)입니다. 논리적으로 동등한 두 공식은 같은 ANF로 변환되므로, 자동 정리 증명에서 두 공식이 동등한지 쉽게 확인할 수 있습니다. 다른 정규형과 달리 변수 이름 목록의 목록으로 간단히 표현할 수 있습니다.

1. 외부 목록: 전체 부울 표현식을 나타냅니다(각 항은 XOR로 결합됩니다).
2. 내부 목록: 각 내부 목록은 표현식의 항(단항식) 하나를 나타내며, 그 항에 들어가는 변수(AND로 결합)만 나열합니다. 상수항 1은 빈 목록으로 나타냅니다.

예를 들어 x ⊕ y ⊕ xy는 [[x], [y], [x, y]]로 적을 수 있습니다. 이런 구조 덕분에 소프트웨어에서 부울 표현식을 효율적으로 저장하고 비교할 수 있습니다.

암호학에서의 역할

• 대수적 차수: ANF에서 가장 많은 변수를 곱한 단항식의 변수 개수를 그 함수의 대수적 차수(algebraic degree)라고 합니다. 블록 암호의 S-box를 이루는 부울 함수는 차수가 충분히 높아야 고차 차분 공격 같은 공격에 강합니다. 예를 들어 AES S-box의 구성 함수는 차수가 7입니다.
• 대수적 공격: 암호를 연립 다항식으로 표현해 푸는 대수적 공격은 ANF 형태의 방정식을 다룹니다. 차수가 낮거나 항이 적으면 이런 공격이 쉬워질 수 있습니다.
• 동등성 검사와 검증: 두 회로나 구현이 같은 부울 함수를 계산하는지 ANF를 비교해 확인할 수 있습니다.

한계

• CNF(Conjunctive Normal Form)나 DNF(Disjunctive Normal Form)보다 덜 직관적일 수 있습니다.
• 원래 공식에 따라 ANF로 변환하면 항의 개수가 크게 늘어날 수 있어(최대 2ⁿ개) 계산 비용이 많이 들 수 있습니다.