불 함수 (Boolean Function)

불 함수(Boolean function, 부울 함수·불린 함수라고도 함)는 n개의 이진 입력을 받아 0 또는 1을 출력하는 함수 f: {0,1}ⁿ → {0,1}입니다. 조지 불의 논리 대수에서 이름을 땄습니다. 암호학에서는 S-box나 해시 함수의 각 출력 비트를 입력 비트들의 불 함수로 보고, 그 성질을 분석해 안전성을 평가합니다.

자세히 알아보기

n변수 불 함수는 길이 2ⁿ의 진리표로 완전히 표현되므로 가능한 함수는 2²ⁿ가지입니다. 같은 함수를 XOR와 AND만으로 쓴 대수적 정규형(ANF)으로도 나타낼 수 있으며, ANF에서 가장 긴 곱 항의 변수 수가 대수적 차수입니다. 여러 출력 비트를 갖는 함수 {0,1}ⁿ → {0,1}^m은 벡터 불 함수라 하고, S-box가 그 예입니다.

암호에서 중요한 불 함수의 성질은 다음과 같습니다.

• 균형성: 출력 0과 1이 같은 수만큼 나와야 편향이 없습니다.
• 비선형도: 모든 아핀 함수로부터 해밍 거리가 멀수록 선형 암호 분석에 강합니다.
• 대수적 차수: 높을수록 대수적 공격·고차 차분 공격에 강합니다.
• 상관 면역성: 일부 입력 변수와 통계적으로 무관해야 스트림 암호의 상관 공격을 막습니다.

이 성질들은 서로 상충하는 경우가 많아, 설계는 균형점을 찾는 문제입니다. 월시-하다마드 변환이 이 분석의 표준 도구입니다.

'논리 함수'는 같은 대상을 회로·게이트 관점에서 부르는 말로, 실질적으로 같은 의미로 쓰입니다.

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

• SHA-256: 비트코인 채굴과 주소 해시에 쓰이는 SHA-256의 Ch(x, y, z) = (x ∧ y) ⊕ (¬x ∧ z)와 Maj(x, y, z)는 비트마다 적용되는 3변수 불 함수입니다. 둘 다 균형 함수입니다.
• Keccak: 이더리움의 Keccak-256에서 유일한 비선형 단계 χ는 b_i = a_i ⊕ (¬a_{i+1} ∧ a_{i+2})라는 차수 2 불 함수를 행마다 적용합니다.
• AES S-box: 지갑·거래소 암호화의 AES S-box는 8개의 8변수 불 함수이며, 각 함수와 그 선형 결합의 비선형도는 112입니다.

쉽게 말하면

불 함수는 0과 1로 된 스위치 n개의 상태를 보고 전구 하나를 켤지 끌지 결정하는 규칙입니다.

예시

다수결 함수 Maj(x, y, z)는 입력 중 1이 두 개 이상이면 1을 냅니다. 진리표(000~111 순)는 0, 0, 0, 1, 0, 1, 1, 1이고, 1이 4개로 균형 함수입니다.