선형 논리 함수 (Linear Logic Function)

선형 논리 함수(linear Boolean function)는 입력 비트 x₁, …, x_n 가운데 정해진 일부를 XOR, 즉 mod 2 덧셈으로만 결합한 불 함수 f(x) = a₁x₁ ⊕ a₂x₂ ⊕ … ⊕ a_nx_n (a_i는 0 또는 1)입니다. 여기에 상수 1을 XOR한 함수까지 포함하면 아핀 함수라고 합니다. n변수 선형 함수는 2ⁿ개, 아핀 함수는 2ⁿ⁺¹개입니다.

자세히 알아보기

XOR은 mod 2 덧셈, AND는 mod 2 곱셈에 해당합니다. 그런데 AND를 쓰면 x₁x₂ 같은 곱 항이 생겨 함수가 비선형이 됩니다. 실제로 XOR와 AND(그리고 상수)를 함께 쓰면 모든 불 함수를 만들 수 있습니다(대수적 정규형, ANF). 따라서 '선형' 논리 함수는 ANF에 곱 항이 전혀 없는, 대수적 차수가 1 이하인 함수입니다. 일부 문헌(리터의 용어집 등)은 이 용어를 'XOR와 AND로 실현되는 함수'로 설명하지만, 이는 선형성을 정확히 표현하지 못하는 정의입니다.

선형 함수는 f(x ⊕ y) = f(x) ⊕ f(y)를 만족합니다. 그래서 출력 여러 개를 관찰하면 미지수에 대한 GF(2) 위의 연립 일차방정식이 되고, 가우스 소거법으로 바로 풀립니다. 암호의 보안에는 치명적인 성질입니다.

블록체인·암호화폐에서는

• 선형 층과 비선형 층의 분업: AES의 MixColumns·ShiftRows, Keccak의 θ·ρ·π 단계, 비트 순열은 모두 GF(2) 위에서 선형입니다. 이들은 확산을 담당하고, 비선형성은 S-box(AES)나 χ(Keccak)가 맡습니다. 이더리움 주소를 만드는 Keccak-256도 이렇게 구성됩니다.
• LFSR과 CRC: LFSR의 귀환 함수와 CRC 계산은 선형 논리 함수입니다. 빠르지만 그 자체로는 예측 가능해, 암호에 쓰려면 비선형 결합이 필요합니다.
• 선형 암호 분석: 공격자는 암호의 입력·출력·키 비트 사이를 선형 논리 함수로 근사하는 식을 찾습니다. S-box가 모든 선형 함수와 거리가 멀도록(비선형도가 높도록) 설계하는 것이 방어책입니다.
• 영지식 회로: 산술 회로에서 선형 연산(덧셈)은 거의 비용이 없고 곱셈만 제약을 만듭니다.

쉽게 말하면

선형 논리 함수는 '몇몇 스위치의 홀짝만 세는' 함수입니다. 단순해서 빠르지만, 그만큼 쉽게 역산됩니다.

예시

f(x₁, x₂, x₃) = x₁ ⊕ x₃는 선형입니다. f = x₁ ⊕ x₃ ⊕ 1은 아핀이고, f = x₁x₂ ⊕ x₃은 AND 항이 있어 비선형입니다.