# 비선형성 (Nonlinearity)

비선형성(nonlinearity)은 함수나 관계가 선형적이지 않은 정도, 즉 출력이 입력에 정비례하거나 입력들의 단순한 합으로 표현되지 않는 성질입니다. 통계에서는 두 변수 관계가 직선으로 설명되지 않는 상황을 말하고, 암호학에서는 불 함수나 S-box가 모든 선형(아핀) 함수로부터 얼마나 떨어져 있는지를 비선형도라는 숫자로 측정합니다.

## 자세히 알아보기

함수 f가 선형이라는 것은 f(x + y) = f(x) + f(y), f(ax) = af(x)를 만족한다는 뜻입니다. 선형 시스템은 입력을 쪼개 따로 계산한 뒤 합치면 되므로 분석이 쉽고, 미지수가 있으면 연립 일차방정식으로 풀립니다.

암호에서 이것은 치명적입니다. 암호가 전부 선형이라면 평문·암호문 쌍 몇 개로 키에 대한 일차방정식을 세워 가우스 소거법으로 즉시 풀 수 있습니다. 그래서 모든 현대 대칭 암호는 반드시 비선형 부품을 갖고, 선형 부품(확산 층)과 번갈아 배치합니다. 불 함수의 비선형도는 진리표에서 가장 가까운 아핀 함수까지의 해밍 거리로 정의하며, 월시 변환으로 계산합니다. 비선형도가 높을수록 선형 암호 분석에 강합니다. 비선형도 외에도 대수적 차수, 차분 균일도 같은 보완 지표를 함께 봅니다.

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

- AES: 지갑 파일과 거래소 통신을 보호하는 AES에서 비선형 요소는 S-box 하나뿐이며, 그 비선형도는 112로 8비트 순열에서 알려진 최고 수준입니다.
- 해시 함수: SHA-256의 Ch·Maj 함수와 정수 덧셈, 이더리움 Keccak-256의 χ 단계가 비선형성을 공급합니다. 이것이 없으면 채굴용 해시나 주소 해시의 충돌을 방정식으로 풀 수 있게 됩니다.
- 영지식 증명 비용: zk-SNARK 회로에서 덧셈(선형)은 거의 공짜지만 곱셈(비선형)마다 제약이 하나씩 생깁니다. Poseidon 같은 해시가 비선형 연산 수를 최소화하도록 설계되는 이유입니다.
- 참고로 RSA·타원곡선 같은 공개 키 암호의 안전성은 '비선형성'보다는 인수분해·이산 로그 같은 수론적 문제의 어려움에서 나옵니다.

## 쉽게 말하면

선형은 '두 배 넣으면 두 배 나오는' 정직한 관계, 비선형은 그렇지 않은 관계입니다. 암호는 일부러 정직하지 않은 부품을 넣어 역산을 막습니다.

## 예시

f(x) = 3x는 선형이고 f(x) = x²은 비선형입니다(f(1 + 1) = 4 ≠ f(1) + f(1) = 2). 불 함수 x₁ ⊕ x₂는 선형, x₁x₂는 비선형입니다.

---
출처: https://achivx.kr/glossary/nonlinearity-%EB%B9%84%EC%84%A0%ED%98%95%EC%84%B1/ · ACHIVX 용어 사전 · 수정일 2026-10-20