선형 복잡도 (Linear Complexity)

선형 복잡도(linear complexity)는 주어진 수열을 정확히 만들어 낼 수 있는 가장 짧은 선형 귀환 시프트 레지스터(LFSR)의 길이 L입니다. 수열을 '선형 규칙으로 얼마나 짧게 설명할 수 있는가'를 재는 복잡도 척도이며, 이 길이를 찾는 알고리즘을 베를레캄프-매시(Berlekamp–Massey) 알고리즘이라고 합니다.

자세히 알아보기

베를레캄프-매시 알고리즘은 수열의 연속된 2L개 비트만 있으면 길이 L인 LFSR의 귀환 다항식과 초기 상태를 O(N²) 시간에 찾아냅니다. 즉 선형 복잡도가 L인 수열은 2L비트를 관찰한 순간 이후 전체가 예측 가능해집니다. 길이 n인 LFSR로 만든 최대 주기 수열(m-수열)은 주기가 2ⁿ − 1로 매우 길지만 선형 복잡도는 n에 불과합니다.

진짜 무작위 수열은 길이 N에 대해 선형 복잡도가 약 N/2 근처에 있고, 수열이 길어짐에 따라 계단처럼 꾸준히 증가합니다(선형 복잡도 프로파일). 따라서 높은 선형 복잡도는 키스트림이 안전하기 위한 필요조건이지만 충분조건은 아닙니다. 선형 복잡도가 높아도 다른 통계적·대수적 약점으로 예측될 수 있습니다. 선형 복잡도는 엔트로피, 콜모고로프 복잡도와 함께 여러 복잡도 척도 중 하나입니다.

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

• 난수 검정: NIST SP 800-22 무작위성 검정 모음에는 '선형 복잡도 검정'이 포함되어 있어, 블록별 선형 복잡도가 무작위 수열의 분포와 맞는지 확인합니다. 지갑·HSM의 난수 생성기 검증에 쓰입니다.
• 스트림 암호 설계의 교훈: LFSR만으로 만든 키스트림은 선형 복잡도가 낮아 쉽게 깨집니다. 그래서 고전적 스트림 암호는 여러 LFSR을 비선형 함수로 결합해 선형 복잡도를 높였고, 현대의 ChaCha20 같은 스트림 암호는 아예 비선형 ARX 연산(덧셈·회전·XOR)으로 키스트림을 만듭니다.
• 비암호 난수의 위험: 선형 구조를 가진 일반 의사난수 생성기를 키 생성에 쓰면 출력 일부만으로 나머지가 복원될 수 있습니다.

쉽게 말하면

선형 복잡도는 '이 수열을 만드는 가장 작은 선형 기계의 크기'입니다. 기계가 작으면 몇 개만 보고도 다음을 맞힐 수 있습니다.

예시

수열 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, …(주기 7)은 s_t = s_{t−2} ⊕ s_{t−3}으로 만들 수 있어 선형 복잡도가 3입니다. 6비트만 관찰하면 규칙 전체를 찾을 수 있습니다.