데시메이션 (Decimation)

데시메이션은 원래 시퀀스에서 일정한 간격 d마다 한 원소씩만 골라 새로운 시퀀스를 만드는 연산입니다. 원래 시퀀스가 x₀, x₁, x₂, …이고 시작 위치가 k일 때, d배 데시메이션의 결과는 y_i = x_d·i+k, 곧 x_k, x_k+d, x_k+2d, …입니다.

예시

비트열 1 0 1 1 0 0 1 0 1 1 0 1을 d = 3, k = 0으로 데시메이션하면 0, 3, 6, 9번째 비트를 골라 1 1 1 1이 됩니다. 시작 위치를 k = 1로 바꾸면 1, 4, 7, 10번째 비트인 0 0 0 0이 나옵니다. 같은 d라도 시작 위치에 따라 결과가 달라집니다.

암호학에서의 데시메이션

스트림 암호에서는 선형 귀환 시프트 레지스터(LFSR)가 만드는 시퀀스의 성질을 분석하거나, 그 선형성을 깨는 데 데시메이션이 쓰입니다.

• m-시퀀스의 데시메이션: n단 LFSR의 최대 주기 시퀀스(m-시퀀스)는 주기가 2ⁿ−1입니다. d와 2ⁿ−1이 서로소이면 d배 데시메이션 결과도 같은 주기의 m-시퀀스가 되며, 일반적으로 다른 귀환 다항식에 대응합니다. 서로소가 아니면 주기가 (2ⁿ−1)/gcd(d, 2ⁿ−1)로 줄어듭니다. 이 성질은 m-시퀀스 사이의 관계를 분석하고 상관 성질이 좋은 시퀀스 쌍을 고르는 데 쓰입니다.
• 규칙적 데시메이션의 한계: 간격이 고정된 데시메이션은 선형 연산이어서, LFSR 출력을 규칙적으로 솎아 내도 결과는 여전히 LFSR로 만들 수 있는 선형 시퀀스입니다. 따라서 보안을 높이지 못합니다.
• 불규칙 데시메이션: 솎아 낼 위치를 다른 시퀀스가 정하면 선형성이 깨집니다. 축소 생성기(shrinking generator, 1993)는 두 번째 LFSR의 출력이 1일 때만 첫 번째 LFSR의 비트를 출력하고, 자기 축소 생성기(self-shrinking generator, 1994)는 한 LFSR의 비트 쌍으로 같은 일을 합니다. 이런 생성기는 선형 복잡도를 크게 높이지만, 출력 속도가 일정하지 않아 타이밍 정보가 새지 않게 구현해야 합니다.

신호 처리에서의 데시메이션

디지털 신호 처리에서 데시메이션은 표본화율을 1/d로 낮추는 것을 말하며, 보통 저역 통과 필터로 고주파 성분을 먼저 걸러 낸 뒤 표본을 솎아 냅니다. 필터 없이 표본만 솎아 내면 잡음이 줄어드는 것이 아니라 높은 주파수 성분이 낮은 주파수로 겹쳐 보이는 에일리어싱이 생깁니다. 데시메이션의 효과는 데이터 양과 처리 비용을 줄이는 것이며, 그 대가로 솎아 낸 원소의 정보는 사라집니다.

왜 중요한가

데시메이션은 스트림 암호를 분석할 때 양쪽으로 쓰입니다. 설계자는 불규칙 데시메이션으로 선형성을 깨려 하고, 분석자는 출력 시퀀스를 여러 간격으로 데시메이션해 숨어 있는 선형 구조나 상관관계를 찾으려 합니다. 데시메이션된 시퀀스가 원래보다 짧은 LFSR로 설명된다면, 그만큼 생성기가 약하다는 신호가 됩니다.