Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

본 논문은 대칭 암호의 선형 계층이 갖는 순환 구조를 활용하여 변환 시퀀스를 구성하는 새로운 접근법을 제안하며, 이를 통해 Whirlwind 및 AES 와 같은 블록 암호에 대해 이전 최첨단 결과에 비해 XOR 연산 횟수와 회로 깊이를 현저히 개선한 휴리스틱 알고리즘을 가능하게 한다.

핵심

당신이 특정 레고 블록 세트를 사용하여 복잡한 기계를 만드는 마스터 건축가라고 상상해 보세요. 암호학(비밀 코드의 과학) 의 세계에서는 이러한 "기계"를 선형 계층이라고 부르며, 데이터를 안전하게 보호하기 위해 데이터를 뒤섞는 일꾼 역할을 합니다.

수년 동안 건축가들은 공간을 절약하기 위해 가능한 한 적은 수의 블록을, 속도를 절약하기 위해 가능한 한 짧은 시간을 사용하여 이러한 기계를 구축하려고 노력해 왔습니다. 귀하가 제공한 논문은 설계도에서 숨겨진 패턴을 발견함으로써 이러한 기계를 설계하는 새로운 방법을 제시합니다.

다음은 그들의 발견을 간단히 설명한 내용입니다:

1. 문제: 복잡성의 "벽돌 벽"

암호학적 선형 계층을 거대한 스위치 벽으로 생각해보세요. 메시지를 뒤섞기 위해서는 이 스위치들을 매우 특정된 순서로 전환해야 합니다.

• 목표: 에너지/공간을 절약하기 위해 가장 적은 횟수의 이동으로, 그리고 속도를 높이기 위해 가장 적은 단계로 스위치를 전환하고 싶습니다.
• 과거의 방법: 이전 방법들은 이 벽을 거대하고 혼란스러운 스위치 덩어리로 취급했습니다. 그들은 최적의 순서를 찾기 위해 시행착오 알고리즘을 사용했지만, 벽이 너무 크고 지저분했기 때문에 종종 가장 효율적인 경로를 놓쳤습니다. 이는 벽에 무작위로 부딪히며 미로를 해결하려는 것과 같습니다.

2. 발견: "회전하는 바퀴" 패턴

저자들은 이러한 암호학적 벽들 중 많은 부분이 실제로 무작위가 아니라는 것을 발견했습니다. 이들은 순환 구조를 가지고 있습니다.

• 비유: 회전목마를 상상해보세요. 말들의 사진을 찍은 후 사진을 회전시키면, 말들의 패턴은 거의 동일하게 보이지만 약간 이동된 것처럼 보입니다.
• 수학적으로 말하면, 행렬 (스위치의 설계도) 은 단일 행을 반복적으로 이동시켜 구성됩니다. 이는 반복되고 회전하는 패턴입니다.
• 통찰력: 이전의 건축가들은 이러한 "회전목마" 패턴을 무시하고 벽을 혼란스러운 덩어리로 취급했습니다. 저자들은 이 패턴을 인정한다면 벽을 훨씬 더 효율적으로 해체할 수 있음을 깨달았습니다.

3. 해결책: "접기" 트릭

거대한 벽 전체를 한 번에 해결하려는 대신, 저자들은 문제를 접어 내리는 방법을 개발했습니다.

• 은유: 반복되는 패턴이 있는 거대하고 무거운 이불이 있다고 상상해보세요. 전체를 한 번에 접으려 하기보다는, 패턴이 반복된다는 사실을 깨닫고 왼쪽 절반을 오른쪽 절반 위에, 그 다음 윗부분을 아랫부분 위에 접을 수 있음을 알게 됩니다.
• 이 "접기" 기법 (수학적으로 행렬을 변환) 을 사용하면 거대하고 복잡한 벽을 훨씬 더 간단한 삼각형 모양으로 바꿀 수 있습니다.
• 벽이 이 삼각형 모양으로 단순화되면, 표준 도구들이 작업을 쉽게 마무리할 수 있습니다. 이는 매듭을 묶기 전에 엉킨 털실 뭉치를 깔끔하고 곧은 실로 만드는 것과 같습니다.

4. 결과: 더 빠르고 작은 기계

저자들은 이 새로운 "접기" 방법을 인기 있는 보안 시스템에서 사용되는 실제 암호학적 기계에 테스트했습니다. 결과는 인상적이었습니다:

• "소용돌이" 기계:

  • 속도: 기계를 실행하는 데 걸리는 시간을 39% 줄였습니다. 예전에 1 마일을 주행하는 데 28 초가 걸리던 자동차가 이제 17 초 만에 주행한다고 상상해보세요.
  • 크기: 필요한 "블록" (논리 게이트) 의 수를 약 30% 줄였습니다. 이는 기계가 더 작아지고 전력을 덜 사용한다는 것을 의미합니다.

• "AES" 기계 (금표준):

  • AES 는 세계에서 가장 유명한 암호화 표준입니다. 그 "MixColumn" 부분은 효율적으로 해결하기 위해 notoriously 어려운 퍼즐로 알려져 있습니다.
  • 성과: 저자들은 인간 전문가가 수주 동안 수동으로 설계를 조정하며 거의 완벽하게 해결한 퍼즐을 거의 동등하게 해결하는 자동화 시스템을 구축했습니다.
  • 단점: 인간 전문가의 설계는 105 개의 "블록"을 사용했습니다. 저자들의 자동화 설계는 107 개를 사용했습니다. 이는 수동으로가 아닌 자동으로 달성된 결과에 불과 2 개의 추가 블록입니다. 또한 그들은 가장 빠른 속도 (깊이) 기록에도 부합했습니다.

5. 이것이 중요한 이유

• 미래를 위해: 컴퓨터 (양자 컴퓨터 포함) 가 더 강력해질수록, 이러한 "기계"들은 보안을 유지하기 위해 더 빠르고 작아야 합니다.
• 교훈: 단순히 설계도가 회전목마와 같은 반복적이고 회전하는 패턴을 가지고 있음을 인식함으로써, 저자들은 이전 방법들이 놓쳤던 단축경을 발견했습니다. 그들은 새로운 종류의 블록을 발명하지 않았습니다. 단지 더 똑똑하게 쌓는 방법을 찾았을 뿐입니다.

요약하자면: 이 논문은 "우리는 많은 보안 코드가 반복되는 패턴 위에 구축되어 있음을 발견했습니다. 이 패턴을 사용하여 설계를 먼저 단순화함으로써, 우리는 이전보다 더 빠르고 작은 보안 시스템을 구축할 수 있으며, 심지어 최고의 인간 전문가들 중 일부까지도 능가할 수 있습니다"라고 말합니다.

기술 요약

기술적 요약: 순환 구조를 활용한 선형 계층 구현 최적화

문제 제기
대칭 암호학에서 선형 계층의 최적화는 게이트 수와 면적에 제약받는 경량 구현과 회로 깊이 및 DW 비용에 제약받는 양자 보안 평가 모두에 중요합니다. 일반적인 가역 행렬에 대한 CNOT 회로 (양자) 와 XOR 회로 (고전) 합성을 위한 휴리스틱 알고리즘이 존재하지만, 암호학적 설계에 내재된 특정 대수적 구조를 완전히 활용하지 못하는 경우가 많습니다. AES MixColumn 및 Whirlwind 와 같이 널리 사용되는 많은 행렬들은 **순환 구조 (circulant structure)**를 갖습니다. Shi 와 Feng [SF24] 의 것과 같은 기존 최첨단 방법들은 이러한 행렬들을 일반적인 $n \times n$ 이진 행렬로 취급하여, 근본적인 순환 특성을 활용함으로써 회로 깊이와 게이트 수를 줄일 수 있는 기회를 놓칠 수 있습니다.

방법론
저자들은 행렬의 순환 구조를 명시적으로 활용하여 효율적인 회로 합성을 안내하는 새로운 프레임워크를 제안합니다. 핵심 방법론은 $F_{2^k}$ 또는 $GL(F_2, m)$ 과 같은 체 확장 (field extension) 위의 순환 행렬을 상삼각 행렬과 같은 더 간단한 형태로 변환한 후 표준 휴리스틱 최적화를 적용하는 재귀적 분해 전략을 포함합니다.

주요 기술 구성 요소는 다음과 같습니다:

1. 재귀적 블록 변환: 정리 3 은 $F_2[x]$ 위의 $2^k \times 2^k$ 순환 행렬이 기본 행 및 열 연산을 사용하여 블록 상삼각 행렬로 변환될 수 있음을 보여줍니다. 이 알고리즘은 행렬을 블록 $A$ 와 $B$(여기서 $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$) 로 재귀적으로 분할하고, 특정 블록을 0 으로 만드는 연산을 적용합니다 (예: $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$ 로 변환).
2. 변환 경로 탐색: 저자들은 재귀 단계 중 행 및 열 연산의 서로 다른 선택이 서로 다른 중간 행렬로 이어진다고 관찰합니다. 알고리즘 (알고리즘 1) 은 후속 회로를 가장 효율적으로 만드는 경로를 찾기 위해 여러 변환 경로를 탐색합니다 (작은 $k$ 의 경우 최대 $4^{2^k-1}$ 개의 가능성).
3. 조기 종료 및 폴백: 깊이가 깊어질수록 재귀의 이점이 감소한다는 점을 인식하여, 저자들은 재귀를 조기에 중단하는 전략 (알고리즘 2) 을 도입합니다. 이 알고리즘은 서로 다른 "블록 크기"를 반복하여 재귀 깊이를 효과적으로 변화시킵니다. 재귀가 조기에 중단되면, 결과 행렬은 일반적인 CNOT/XOR 합성을 위한 표준 휴리스틱 최적화기 (Heu) 로 전달됩니다. 여기에는 재귀 깊이가 0 인 경우 행렬을 일반 사례로 취급하는 "폴백" 전략이 포함됩니다.
4. 자동화된 최적화: Zhang 등 [ZSWS24] 의 AES 를 위한 이전의 수동 접근법과 달리, 이 방법은 "더 간단한" 행렬 형태와 해당 게이트 시퀀스를 찾는 과정을 자동화하여 인간의 개입을 불필요하게 합니다.

주요 기여

• 새로운 프레임워크: 이는 선형 계층의 순환 구조를 체계적으로 활용하여 회로 구현을 최적화하는 첫 번째 작업으로, 대수적 행렬 속성과 회로 합성 휴리스틱 간의 간극을 메웁니다.
• 자동화된 합성: 저자들은 수동적이고 사례별 최적화를 대체하는 자동화된 알고리즘을 제공합니다. 이는 하류 휴리스틱이 더 효율적인 구현을 찾을 수 있도록 변환 행렬 시퀀스를 생성합니다.
• 이중 최적화: 이 프레임워크는 양자 회로(CNOT 수 및 깊이 최소화) 와 고전 회로(XOR 수, 특히 g-XOR 및 s-XOR 최소화) 모두에 적용 가능합니다.

결과
저자들은 블록 암호 (AES, Whirlwind, Clefia, PRIDE 등) 의 선형 계층 데이터셋과 구성된 MDS 행렬에 대해 이 방법을 평가했습니다.

• 양자 회로 깊이:

  • Whirlwind M0: 제안된 방법은 [SF24] 의 이전 최첨단 결과인 28 에서 17로 회로 깊이를 줄여 39% 개선을 이루었습니다. 게이트 수도 286 에서 200 으로 감소했습니다.
  • AES MixColumn: 자동화된 방법은 10의 깊이를 달성하여 Zhang 등 [ZSWS24] 의 수동 최적화 최첨단 결과와 일치했습니다. 게이트 수는 107 이었으며, 이는 수동 결과 (105) 보다 CNOT 2 개만 많고 [SF24] 가 달성한 131 CNOT 보다 훨씬 우수합니다.
  • 기타 행렬: 밀도가 높은 행렬 (예: Whirlwind, SKOP15 8x8) 에서는 상당한 깊이 감소가 관찰된 반면, 휴리스틱이 이미 잘 수행되는 희소 행렬의 경우 개선은 미미하거나 존재하지 않았습니다.

• 고전 회로 (XOR 수):

  • Whirlwind M0: 이 방법은 s-XOR 수 159를 달성하여 Yuan 등 [YWS+24] 의 이전 최상위 결과인 173 보다 약 8% 우수한 성능을 보였습니다.
  • 일반적 성능: 이 방법은 많은 행렬에 대해 크기 오버헤드를 수반하지만, Whirlwind M0 및 M1 과 같은 특정 고밀도 행렬에 대해서는 최첨단 결과를 성공적으로 능가했습니다.

의의 및 주장
이 논문은 순환 구조를 활용하는 것이 선형 계층을 최적화하기 위한 강력하지만 이전에 충분히 활용되지 않았던 방안이라고 주장합니다. 저자들은 그들의 접근 방식이 다음과 같다고 주장합니다:

1. 표준 탐욕 전략이 어려움을 겪는 특정 고밀도 행렬에 대해 기존 휴리스틱보다 우수한 성능을 발휘합니다.
2. 수동 개입 없이 AES MixColumn 에서 볼 수 있듯이 인간 전문가가 튜닝한 회로와 비교 가능한 결과를 달성함으로써 수동 최적화를 자동화합니다.
3. 양자 보안 평가에서 선형 계층에 대한 더 정확한 깊이 추정을 제공하여 포스트 양자 보안 평가에서 DW(깊이 $\times$ 너비) 비용 계산에 필수적인 새로운 기준을 제시합니다.

저자들은 이 방법이 모든 행렬 유형 (특히 희소 행렬) 에 대해 보편적으로 우월하지는 않지만, 순환 구조와 고밀도를 가진 행렬에 대해서는 상당한 이점을 제공하며 대수적 속성을 회로 합성에 통합하는 잠재력을 입증한다고 결론지었습니다.