Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

본 논문은 경량 하이브리드 ARX-SPN 암호 GFSPX 의 큐비트 최적화 양자 회로 구현을 제시하고, 병렬화된 그로버 공격을 통해 사후 양자 보안을 평가하여, NIST Level 1 임계값 미만이지만 다른 경량 설계에 비해 우수한 저항성을 보여주는 총 $1.12 \times 2^{159}$ 게이트의 양자 비용을 규명하였다.

핵심

상상해 보세요. 스마트 센서나 RFID 태그 같은 소형 장치를 보호하기 위해 설계된 매우 특수하고 가벼운 디지털 자물쇠 (GFSPX) 가 있다고 가정해 봅시다. 이 자물쇠는 빠르고 매우 적은 에너지를 사용하도록 만들어져 '사물인터넷 (IoT)'에 완벽합니다.

하지만 양자 컴퓨터라는 새로운 종류의 '슈퍼 도구'가 등장하고 있습니다. 일반 컴퓨터가 키를 하나씩 확인하는 것과 달리, 양자 컴퓨터는 여러 키를 한 번에 확인할 수 있어 이러한 자물쇠를 훨씬 빠르게 뚫을 수 있습니다. 이 논문은 단순한 질문을 던집니다: 만약 양자 컴퓨터가 이 특정 자물쇠를 뚫으려 한다면, 실제로 얼마나 어려울까요?

일상적인 비유를 사용하여 그들의 발견 사항을 다음과 같이 정리해 보겠습니다:

1. 자물쇠의 설계: 하이브리드 엔진

GFSPX 자물쇠는 한 가지 유형의 메커니즘만으로 만들어지지 않았습니다. 가솔린 엔진과 전기 모터를 모두 사용하는 자동차처럼 하이브리드입니다.

• "가솔린" 부분 (ARX): 이는 매우 효율적이지만 데이터를 통해 변화를 확산시키는 데는 다소 느릴 수 있는 간단한 수학 연산 (덧셈, 회전, XOR) 을 사용합니다.
• "전기" 부분 (SPN): 이는 카드 덱을 섞는 것과 같은 복잡한 치환 네트워크를 사용하여 변화를 매우 빠르게 확산시킵니다.
• 결과: 이 둘을 결합함으로써 자물쇠는 빠르고 효율적입니다. 저자들은 양자 컴퓨터가 내부 작동 방식을 정확히 파악할 수 있도록 이 자물쇠에 대한 디지털 청사진을 구체적으로 구축했습니다.

2. 양자 청사진: 회로 구축

자물쇠를 테스트하기 위해 연구자들은 '양자 회로'를 구축해야 했습니다. 이는 모든 단계가 완벽하게 되돌릴 수 있어 (정보 손실 없이) 미니멀한 가역 공장을 건설하는 것과 같습니다.

• 도전 과제: 양자 컴퓨터는 매우 취약합니다. 데이터를 임의로 복사할 수 없으며, '큐비트'(작은 회전하는 팽이와 같은 양자 비트) 를 매우 신중하게 다뤄야 합니다.
• 해결책: 연구자들은 가능한 한 적은 수의 큐비트 (209 개) 를 사용하도록 설계를 최적화했습니다. 수학 부분에는 '리플 캐리 어더 (ripple-carry adder)'라는 교묘한 트릭을 사용했는데, 이는 공간을 낭비하지 않는 매우 효율적인 조립 라인과 같습니다.
• 발자국: 최종 청사진은 컴팩트하여 한 번의 전체 암호화를 실행하는 데 209 개의 큐비트와 특정 수의 단계 (게이트) 가 필요한 '공장 바닥'을 요구합니다.

3. 공격: "그로버" 검색

자물쇠를 뚫기 위해 양자 컴퓨터는 **그로버 알고리즘 (Grover's Algorithm)**을 사용합니다.

• 비유: $2^{128}$ (이해하기 어려울 정도로 거대한 숫자) 권의 책이 있는 거대한 도서관이 있고, 그중 오직 한 권에만 올바른 키가 있다고 상상해 보세요.
  • 일반 컴퓨터는 한 권씩 확인하는 사서와 같습니다. 영원히 걸릴 것입니다.
  • 양자 컴퓨터는 여러 권을 동시에 확인할 수 있는 마법 같은 사서와 같습니다. 올바른 책을 찾는 데 걸리는 시간은 대략 제곱근 수준으로 줄어듭니다.
• 함정: 양자 컴퓨터가 잘못된 책을 선택하지 않도록 (거짓 양성) 하기 위해, 연구자들은 컴퓨터가 동시에 세 가지 다른 자물쇠 (세 가지 다른 잠금/해제 메시지 쌍 사용) 를 확인하도록 만들었습니다. 만약 한 키가 세 가지 모두를 열면, 그것은 확실히 올바른 키입니다.

4. 결론: 강력하지만 '포스트 양자' 증명에는 미치지 못함

연구자들은 이 양자 공격의 총 '비용'을 계산했습니다.

• 비용: 그들은 자물쇠를 뚫는 데 $1.12 \times 2^{159}$ 연산에 해당하는 막대한 컴퓨팅 파워가 필요하다는 것을 발견했습니다.
• 기준: 미국 국립표준기술연구소 (NIST) 는 미래를 위한 '안전 기준'을 설정했습니다. 양자 컴퓨터에 대해 진정으로 안전하다고 간주되려면 (레벨 1 보안), 자물쇠의 비용이 최소 $2^{170}$이어야 합니다.
• 결과: GFSPX 자물쇠는 안전 기준 아래에 있습니다. 가장 엄격한 포스트 양자 표준에 대해서는 안전하지 않습니다.
  • 그러나 논문은 다른 경량 자물쇠들과 비교할 때 GFSPX 는 실제로 뚫기 가장 어려운 자물쇠 중 하나라고 지적합니다. 이는 소형 장치에 매우 효율적이면서도 최고 수준의 보안 테스트를 통과하지는 못하더라도 양자 공격에 대한 상당한 저항력을 제공하는 '황금 지대'에 위치해 있습니다.

5. 핵심 교훈

이 논문은 현재 자원이 제한된 장치에는 이 하이브리드 자물쇠가 훌륭하지만, 128 비트 키 크기는 미래의 의도적인 양자 공격을 견디기에는 단순히 너무 작다고 결론 내립니다.

• 트레이드오프: 작고 빠른 자물쇠 (오늘날의 센서에 적합) 를 가질 수 있거나, 거대하고 느린 자물쇠 (미래의 양자 안전에 적합) 를 가질 수 있지만, 이 특정 설계는 둘 다 시도하다 보니 '미래 안전' 측면에서 약간 부족합니다.
• 미래 조언: 이 설계를 진정으로 양자 방어적으로 만들기 위해 저자들은 키 길이를 늘리거나 (192 비트 또는 256 비트와 같이) 양자 컴퓨터가 처리하기 더 어렵게 만들기 위해 수학 부분을 조정할 것을 제안합니다.

간단히 말해: GFSPX 는 대부분의 동종 제품보다 뚫기 더 어려운 매우 영리하고 효율적인 자물쇠이지만, 약간의 업그레이드 없이는 미래의 초강력 양자 컴퓨터를 견딜 만큼 충분히 강력하지는 않습니다.

기술 요약

기술 요약: 하이브리드 ARX-SPN 암호 GFSPX 의 양자 회로 구현 및 그로버 암호분석

문제 제기
양자 컴퓨팅의 부상은 고전적인 대칭키 원시적 암호의 보안을 근본적으로 위협합니다. 쇼어 알고리즘이 공개키 암호를 위협하는 반면, 그로버 알고리즘은 비구조화된 검색에 대해 이차적 속도 향상을 제공하여 대칭키 구조의 보안 마진을 효과적으로 절반으로 줄입니다. 따라서 사물인터넷 (IoT) 및 RFID 와 같은 자원이 제한된 환경을 위해 설계된 경량 블록 암호 (BC) 들은 사후 양자 시대의 복원력에 대한 엄격한 재평가가 필요합니다. 구체적으로, 덧셈 - 회전 - XOR(ARX) 와 치환 - 치환 네트워크 (SPN) 패러다임을 결합한 하이브리드 설계에 대한 키 복구 공격을 수행하는 데 필요한 양자 자원을 정량화할 필요가 있습니다.

방법론
저자들은 64 비트 데이터 블록과 128 비트 비밀 키를 특징으로 하는 경량 블록 암호 GFSPX 에 대한 포괄적인 양자 회로 구현과 그로버 암호분석을 제시합니다. GFSPX 는 비선형성을 위한 ARX 기반 함수 ($F_1$) 와 빠른 확산을 위한 32 비트 SPN 구조 ($F_2$) 두 가지 기능 블록을 통합한 4-분기 일반화 피스텔 구조 (GFS) 를 활용합니다.

방법론은 세 단계로 진행됩니다:

1. 양자 회로 구현: GFSPX 의 고전적 구조는 가역 양자 회로로 매핑됩니다. 저자들은 피스텔 네트워크의 고유한 가역성을 활용하여 보조 큐비트 (ancilla qubit) 사용을 최소화합니다.
   • $F_1$(ARX): 쿠카로 (Cuccaro) 등의 아키텍처에 기반한 컴팩트 리플 캐리 어더 (RCA) 를 사용하여 구현됩니다. 이 접근법은 모듈러 덧셈을 위해 최종 캐리 비트를 생략하고 인-플레이스 매저리티 (MAJ) 및 언매저리티 - 앤드 - 애드 (UMA) 게이트를 활용함으로써 큐비트 오버헤드를 최소화합니다.
   • $F_2$(SPN): S-박스 레이어 (PRESENT 기반) 는 추가 보조 큐비트 없이 최소한의 CNOT 및 토폴리 게이트 집합으로 합성됩니다. 치환 레이어 (P-레이어) 는 낮은 회로 깊이를 유지하기 위해 병렬화 가능한 SWAP 게이트를 통해 구현됩니다.
   • 키 스케줄: 128 비트 마스터 키 스케줄은 113 비트 왼쪽 순환 회전, S-박스 치환, 라운드 카운터 XOR 을 포함하는 유니터리 진동으로 실현되며, 인-플레이스 실행을 위해 최적화됩니다.
2. 자원 추정: 양자 비용은 표준 분해 지표 (NOT 및 CNOT 비용 = 1, 토폴리 비용 = 6) 를 사용하여 계산됩니다. 분석은 기준 비용 (SWAP 라우팅 오버헤드 제외) 과 상한선 (SWAP 을 세 개의 CNOT 으로 분해) 을 모두 평가합니다.
3. 그로버 암호분석: 키 복구 공격에 대한 암호 평가를 위해 병렬화된 그로버 오라클 ($U_f$) 이 구축됩니다. 128 비트 키 공간에서의 허위 매칭을 제거하기 위해 오라클은 세 개의 평문 - 암호문 쌍 ($r=3$) 을 활용합니다. 공격 복잡성은 오라클의 자원 지표를 최적의 그로버 반복 횟수 ($\approx \frac{\pi}{4}2^{64}$) 로 스케일링하여 추정됩니다.

주요 기여

• 최적화된 양자 구현: 이 논문은 GFSPX 를 위한 큐비트 최적화 양자 회로를 제공하여 209 개 큐비트의 발자국을 달성합니다. 이 설계는 7,617의 회로 깊이와 함께 32,498개의 게이트 기준 양자 비용을 달성합니다.
• 하이브리드 아키텍처 분석: 이 연구는 하이브리드 ARX-SPN 설계의 자원 분포를 상세히 설명하며, 모듈러 덧셈 원시적 연산이 총 게이트 수를 지배하지만 SPN 구성 요소의 병렬화 된 치환 레이어가 경쟁력 있는 게이트 - 대 - 깊이 비율을 유지하는 데 도움이 된다는 것을 보여줍니다.
• 정량적 보안 평가: 저자들은 세 개의 평문 - 암호문 쌍을 사용하여 그로버 오라클을 구축하고 NIST 의 MAXDEPTH 프레임워크 하에서 총 공격 비용을 계산합니다. 분석 결과, $r=3$인 경우 총 양자 공격 비용은 약 $1.12 \times 2^{159}$개의 게이트로 나타났습니다.
• 비교 벤치마킹: 구현은 다른 경량 암호 (예: PRESENT, GIFT, SIMON, SPECK) 와 비교하여 벤치마킹되었습니다. GFSPX 는 비교된 설계 중 가장 낮은 비용 - 대 - 깊이 비율 (4.27) 을 달성하여 높은 병렬 실행 효율성을 나타냅니다.

결과

• 자원 지표: 전체 20 라운드 GFSPX 회로는 209 개의 큐비트가 필요합니다. 기준 비용은 32,498 이며, SWAP 라우팅 오버헤드가 포함되면 47,789 로 증가합니다. 회로 깊이는 7,617 입니다.
• 공격 복잡성: 키 복구 공격에 대한 총 양자 비용은 ($r=3$인 경우) $1.12 \times 2^{159}$로 추정됩니다.
• 보안 분류: NIST 사후 양자 암호 프레임워크 하에서 레벨 1 보안 임계값 (AES-128 에 해당) 은 최소 $2^{170}$의 총 공격 비용을 요구합니다. GFSPX 의 추정 비용 ($2^{159}$) 은 이 임계값보다 낮습니다.
• 설계 트레이드오프: GFSPX 는 많은 순수 SPN 설계 (약 $2^{152}$ 주변에 군집) 보다 높은 양자 공격 저항력을 보이지만, 128 비트 키 길이에 대해서는 NIST 레벨 1 보안 기준을 충족하지 못합니다. 하이브리드 설계의 비용은 ARX 구성 요소 (모듈러 덧셈) 에 크게 영향을 받아, 보안 프로파일이 SIMON 및 SPECK 와 같은 ARX 기반 암호에 더 가깝습니다.

의의
이 논문은 차세대 암호 설계에서 고전적 하드웨어 효율성과 양자 복원력 사이의 균형에 대한 중요한 통찰력을 제공한다고 주장합니다. 이 연구는 근본적인 트레이드오프를 강조합니다: 하이브리드 ARX-SPN 구성은 순수 SPN 설계보다 강력한 고전적 성능과 더 나은 양자 저항력을 제공하지만, 128 비트 키 길이는 고급 양자 적대자에 대해 NIST 레벨 1 보안을 달성하기에 구조적으로 불충분합니다. 저자들은 향후 연구가 보안 마진을 개선하기 위해 키 길이를 확장 (예: 192 또는 256 비트) 하거나 가역 모듈러 덧셈 원시적 연산을 최적화하는 데 초점을 맞춰야 한다고 제안합니다. 이 작업에서 확립된 방법론은 자원이 제한된 환경에서 다른 하이브리드 설계를 평가하기 위한 엄격한 프레임워크 역할을 합니다.